TopCoder SRM 489 (Div 1) - simezi

久々のSRM.
りんごさんがregisterしてなかったりで多分りんご回だと思ったらやはり……

203.38 / 241.50 / Unopened -25
170位
1818->1850

解くの遅い。

Laycurseさん、iakasTさんなど日本人が他に4人いる部屋。

ボールi,jを入れるとconvert[i][j]のボールがでてくる機械がある。
最初のボールを決め、ボールが一つになるまでconvertを繰り返すとき、
機械がどんな初期状態に対しても最後の一つのボールが一意に決まるものであるかどうかを判定せよ。

300やめて！
サンプルはかなり親切っぽいのでサンプル合えば送ってよさそう。

問題を読んで理解するまでにかなり時間がかかる。
読み終えても方針が立たない。
グラフか何かに落とし込めるのか？落とし込めなさそう。
これもしかして3つだけ順番見れば必要十分とか？

((a,b),c)と((b,a),c)とかの場合があるから6通り見ないとダメでー……
ん、交換法則が成り立たない場合その二個だけで結果が一意に決まらなくなってしまうので、
まずはconvertが対称か判定する。

その後3通りが一致するか見る。……これでいいんかなあ。
書いた。
実行中に落ちる。あー'Z'の次の文字って'a'じゃないのか。訂正してまたテスト。
サンプル通った。慎重に見直して送信。。。ってみんなはえええ。

座標平面(0,0)にサイコロが1の面を上にして置いてある。
これを(goalx,goaly)まで、右または上方向に1ずつ、以下の条件を満たしたまま転がして移動させる場合の数を求めよ。

1≤goalx,goaly≤10億を満たす。

サンプルが全部2だ……
これちょっと大きくなるとどうやっても2とか？
小さい場合色々考えてみるけどよくわからない。DP書こう。

DP書いて20x20くらいの表を出力してみる。
なるほど、すごいわかりやすい規則が……

ハードコーディングして、時間ギリギリまで見直しして送信。

開いてない。

yak_exさんのコードが怪しそうに見えたのでよく考えないで1,4を突っ込んだらFailed……ばかすorz
そんなことをしている間に速攻で5人落とされててチャレンジできるものがなくなった。

部屋は全員通ってる。
全体でもほとんど誰も落ちてないw