KEIS BLOGは株式会社ケイズ・ソフトウェアが運営しています。

KEIS BLOG

TopCoderをやろう!

LINEで送る
Pocket

TOPCORDER

こんにちは、ここ3年ほどTopCoderをやってる松野です。
今日はTopCoderについて少し書きたいと思います。

TopCoderというのは、簡単に言うと1週間に3, 4回開催されている
プログラミングコンテストのサイトです。
TopCoder

日本だと、CodeIQみたいな感じですかね。
CodeIQ

個人的にはあまり英語は得意ではないので、CodeIQのほうが読みやすいのですが
TopCoderのほうが、問題数(過去問含め)がかなり多いので、
勉強したい人にはオススメです。

さて、そんなTopCoderですが、
とりあえずは過去問をとくことから始めてみましょう。
過去問を解いてみる

上記から過去問のアーカイブを見ることができます。
Problem Nameが問題の名前で、Divというのは、難しさのレートです。

Div1のほうが簡単で、Div2のほうが難しいです。
Div1 100% だと すごく簡単
Div2 5% だと すごく難しい

今日は一番最初なので、Div1が低い(簡単)なものを見てみましょう。
http://community.topcoder.com/stat?c=problem_statement&pm=7558

上記を日本語に訳すと(あまり英語が得意ではないので
間違っているところがあるかもですが)

——————————————————-
あなたは広告代理店で働いている。
そこには広告代理店が所有している1-100までの番号が付いた看板が100個ある。
お客はリクエストを次々に送信する。
それぞれのリクエストには看板の番号が付いている
リクエストに対応する看板がまだ1回もリクエストされていなければ、そのリクエストを許容する
1回以上リクエストされている場合は、そのリクエストを拒否する。

引数にintの配列を与えて、何回リクエストを拒否したかを戻すプログラムを作成せよ。
——————————————————-

問題としては、入門といったところでしょうか。
Definitionにクラス名やメソッド名、引数が書いてあるので、
下記Exampleの動きをするようなプログラムを作ってみましょう。

Examples
0)
{1,2,3}
Returns: 0
すべてのリクエストを許容

1)
{1,1,1}
Returns: 2
1つだけリクエストを許容し、他のリクエストは拒否
拒否したリクエストの数を返す

2)
{1,2,1,2}

3)
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100, 100, 100, 100, 100, 100, 100
}
Returns: 49

以下解答

答えは1つではないので、正しい動きをすれば正解です。
このプロブレムで優勝したコードを見てみましょう。
※ちなみに1分39秒で書いてsubmitしてます。


import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class AdvertisingAgency
{
  public void sop(String s){System.out.print(s);}
  public void sopl(String s){System.out.println(s);}
  public int ipi(String s){return Integer.parseInt(s);}
  public int gcd(int x, int y){if (y==0) return x; return gcd(y,x%y);}
  int INF=2147483647;
 
  public int numberOfRejections(int[] r)
  {
    boolean[] v=new boolean[110];
    int ret=0;
    for (int i=0;i<r.length;i++)
      if (!v[r[i]])
      {
        v[r[i]]=true;
        ret++;
      }
    return r.length-ret;
  }
 
 
}
//Powered by [KawigiEdit] 2.0!

もし時間があれば、いろんなコード書いてみてくださいネ(・3・)

以上、今日のTopCoderでした。

 

【関連記事】
ハニーポットについて (1)サーバーを立てる
ハニーポットについて (2)アクセスログ有効活用方法

 

LINEで送る
Pocket