TopCoderの問題
タイトルの通り、今日は最初にTopCoderについて・・・
(本当は一緒にJava入門も掲載しようと思ったのですが、紙面上のつごうでJava入門は分けて別の記事にかこうと思います。)
・・・で、TopCoderを未だに始められていない僕ですが、英語訳すぐらいなら・・・と、ある問題を日本語訳したので、一応掲載しとこうと思います。。。
わ~。。。書くのつかれました(汗
でもJava入門も頑張ろうと思うので、少し待っててくんさいm(_ _)m
(本当は一緒にJava入門も掲載しようと思ったのですが、紙面上のつごうでJava入門は分けて別の記事にかこうと思います。)
・・・で、TopCoderを未だに始められていない僕ですが、英語訳すぐらいなら・・・と、ある問題を日本語訳したので、一応掲載しとこうと思います。。。
コンテスト:マラソンマッチ66
問題:数字模様
問題文
四角形のグリッドに数字で満たされたセルで作られた模様があります。新しく満たされた
セルは1の値を得て、そのセルに(垂直および平行方向に)隣接したセルたちは元々その
セルに満たされていた値に1を足した値を得ます。この様に、一見見た目は同じセルはそ
れぞれ違う順序で満たされることにより違った値の模様を作ります。
あなたはString[]にあなたが作りたいtargetPatternを与えられます。targetPattern
[i][j]は満たすことのできなかったセルを'.'とし、それらの中に値を持っているセルを
数字の'1'~'5'とするでしょう。
あなたの仕事はセルを満たした数の順序を戻すことです。よってその結果の模様はできる
限りtargetPatternに近づきます。それらの模様の間で行われた“行程”は同じセル同士
の値がまったく違うので明確です。i番目に満たされなければいけないセルのあなたが返し
た結果の行と列の要素は2*iと2*i+1です。あなたが返した全てのセルはまったく違うもの
でなくてはなりません。あなたは'1'~'5'でマークされた模様のセルだけ満たすことがで
きます。また、それと同時にそのようなセルを全て満たさなくてはなりません。この様に
あなたの返した数字要素は2*(targetPatternのセルの'1'~'5'の数字)と等しくなくては
なりません。
(中略)
テストケースは次に述べる生成されます。targetPatternの行Wと列Hの数字は10から100
の間で選ばれ、それらを全て含むでしょう。その時、10から30の間の'?'記号によるでたら
めな菱形はグリッドの中に表されます。半径がw0で中心が(i0 , j0)であるような菱形はabs
(i)0、abs(j) 0およびabs(i+j) 0であるセル(i0+i , j0+j)のグループです。菱形はグリ
ッドの外側に不完全な状態でいることができます。最後に、全ての'?'記号は次に述べるう
ちの一つの方法で'1'~'5'の記号に置き換えられます(ほぼでたらめと同じような確率で
選ばれる。)全てのセルがでたらめに値を与えられるか、あなたが結果を返すのに使った
プロセスと同じ方法でそれらが満たされるかのどちらか一方の命令でセルは満たされます。
(以下略)
定義
クラス: DigitsPattern
メソッド: recreate
パラメータ: String[]
返り値: int[]
メソッドのサイン:int[] recreate(String[] targetPattern)
(あなたのメソッドがpublicであることは確信している。)
はしがき
*メモリー制限は1024MBとしタイム制限はテストケース(あなたのコードに使われた時間
のみを含む)につき10秒とする。ここには明確なコードのサイズ制限はない。
*ここには10このテストケース例と、100の完全な提出されたテストケースがある。
※テストケース例や得点の詳細などはTopCoderよりご参照ください。
わ~。。。書くのつかれました(汗
でもJava入門も頑張ろうと思うので、少し待っててくんさいm(_ _)m