CodeChef August 2010 Cook-Off - simezi

CodeChefは、インドの企業が主催しているオンラインプログラミングコンテストのwebサイト。
昨日たまたま、今から月１のコンテストが開催されるらしいというつぶやきをtwitterで見たので、自分も参加してみた。

Result

35位
00:36:56(0) / 00:25:41(0) / 02:08:47(4) / - / -
合計時間04:31:24 penalty 4 score 3.00000

3問早解きでシャツ貰えるラインだったらしいけど……
DPで1時間半ハマるとかさすが自分。理解が完璧じゃないからハマるんだよ全く。ざこいざこい。

Registration

コンテスト開始30分前、アカウントがないのでまずは登録。
結構入力事項が多いのね……コンテストの入賞者には商品が贈られるらしいのでしょうがない。
というか月１で世界中の20人に商品送ってるのかこの企業ｗ年間100万は軽くかかるんじゃｗ
サイトもデザイナーとか居る感じで太っ腹だなあ。日本の企業もこういうのやってほしいなあ。

次にコンテストの参加方法・ルールを読む。参加方法は特に記述がない。アカウント持ってるだけで自動的に参加できるようだ。
コンテストのルールは、ICPCというか、CodeForecsの形式にほぼ同じ。
問題数が多い人が勝ちで、同じ題数の場合は時間で優劣をつける。

……うん？Ruby,PHP,Lispは制限時間3倍？Lisp？？PHPとかLispとか使えるICPC形式のコンテストなんて初めて見たぞｗｗｗ
Javaは２倍。Javaってそんな遅くないだろ別に……
アセンブラとかまで使用可能言語に入ってる。ていうかこれだけ言語使えるならBoostとか使用可能にしたらいいんじゃｗ

次にSubmitの方法を確認。
Practiceがある。ふつうのオンラインジャッジっぽい。ファイルのからの提出も出来るみたいだ。
Easyの一番上にあった奴を解いてみる。

素でWA...orz問題文読み間違ったお。入力をそのまま出力するだけなのにソートとかしてたｗ
直してAC.
これ実行時間0msとかでも、判定出るまでずいぶん時間かかるんだなー。

まあ提出の方法はわかった。
そんなことをしているうちに開始時間になったので参加。

Baking Cupcakes

事前に問題は難易度順に並んでないよ！という情報を得たので真ん中にあった問題から読んでみる。

ノード数nの一般グラフの独立頂点集合で、大きさがgのものが存在するかを判定せよ、という問題。
なんだろうこれNP完全じゃねーのｗ
n-g≦15という制限があるらしい。これだと多項式時間で解けたりするのかな？
ぐぐってみる。あんまり情報でない。まあよく解らないし、明らかに他に簡単な問題があるはずなので飛ばす。

Arranging the Appetizers

どうもCodeChefは問題文が読みにくいような気がする。
PKUのUSACOとかの問題文でも思うけど、英語ネイティブ向け（でもないけど）のコンテストって語彙だとか表現だとかが難しいこと多いんだよね。

appetizerは食前酒か何からしい。単語調べたけど結局題意はよくわからないぞ……
二進数をひっくり返した位置に字を入れ替えろ、みたいなことを言っているみたいだ。
サンプルをみる。
ans[i]=str[inv(i)]みたいな感じ？
書いた。合わない。修正。合わない。修正。サンプル合った。

送信ー。AC.

Cleaning Up

一問ゆっくり解いたところで各問題の正解者数を見てみると、これが一番簡単な問題みたいだ。
てかシステムがまんまCodeforcesだなあ。

n個の仕事のうち、既に終わった仕事の番号が与えられて、まだ終わってない仕事を部下と二人で分担する。
番号の若い順に自分・部下・自分・……と仕事を割り当てるときに、自分の仕事と部下の仕事を出力せよ、という問題。

書いた。
うん？なんか出力合わない。
シェフの仕事出力するんじゃないのか？そもそもあからさまに行数が多いし。
ああシェフと部下の仕事両方出すのか。

訂正。送信。AC.

Fetching Cooking Tools

で、次に解いてる人多いのがこれ。

n人のコックが座標平面上の(xi,yi)いて、それぞれが必要な道具が(x'i,y'i)にある。
道具は同時に2個しかもてないとき、道具を取ってきて対応するコックに配って歩くのに必要な最短距離を求める問題。

n≦8らしい。すくなっ
なんかまんまこんな感じの問題がCodeforcesで出たような気がするなあ。
どうやったっけ……確かその時は解けなかったような気が。

dp[i][j][k][l]にコックが道具を貰ったかビット、左手の道具の番号、右手の道具の番号、位置のときの最短距離みたいな感じにしてDPすればいいのかなと思ったんだけど、なんか処理がごちゃごちゃして物凄くはまる。
dpにがてー；添え字4つとか頭混乱してやってらんないよ！

40分くらいもやもやして結局書けなかったところで方針転換。
dp[i][j]にビットiで位置jにいるときの最適解を持つ、んで、道具は取ったらすぐ渡すようにすれば添え字減るんじゃないのか！
んで書いてみる。苦心してサンプル通った。
送ってみる。

WA.
あ、うんなんかそんな感じしたんだ……
えーとそもそもビットが単調増加にならないとDPはできなくてー、
なんか添え字色々と間違ってる。修正した。

あれ？サンプル通らなくなってしまった。
サンプルを紙に書いて考えてみると、道具はすぐに渡さない場合があるらしい！
うーん、方針が間違ってるぽい。添え字1個増やして、片手だけ持ってる道具を記憶するようにしたらどうだろう。

書いて、送信。
WA.
見直す。添え字だの間違ってる。直す。

WA.
うーんごちゃごちゃする。もう一度見直す。距離の関数の引数間違ってるかなあ。
間違ってた。訂正。更によーく見直して、コードもアルゴリズムも大丈夫だろうと思い送信。

WA.
あれーorz
もう一度見直す……あ、配列の初期化がおかしい！orz

送信。AC.
むー。

Backup Functions

問題文がグロそうだったので見てない。