TopCoder Member SRM489 Div1

うさぎさんがでてきた回。

300

N種類の球があって、そのうち2つを同時に入れると2つの球によってある決まった球を返してくる装置がある。与えられた装置が、「どんな球の集まりに対しても、どうやって装置に球を入れて１個になるまで繰り返したって結果同じ球になる」ようなものか判定せよ。

装置による変換を「A $ B」とでも表すと、交換法則「A $ B = B $ A」が成り立つことは問題文中に書いてある。結合法則「(A $ B) $ C = A $ (B $ C)」が成り立つか調べればよい。
（といっても、3つの場合の結合法則が成り立つからといって任意の場合成り立つことは自明ではない。でもWikipedia「結合法則」を見ると3つの場合が成り立てば何個でも成り立つって書いてある）

500

サイコロが置いてある。最初、１の目が一番上になっている。右か上にだけ転がして良い。ある座標に着いた時、一番上の目は１じゃなきゃいけない。また、そこに着くまでに一番上の目が１であるようなことがあってはならない。何通りの動かし方がある？答えは32ビット整数に収まるよ。

状態遷移図を書くと、「右いって、上にくるくるして、右いく」か「上いって、右にくるくるして、上いく」で裏返した状態になり、そこから同様にして１が一番上の状態になっていくことがわかる。
あとは、その「くるくる」の回数を適当に変数で置いて、移動後の座標をその変数たちで表して、与えられた座標と同じになるような場合の数を求めるだけ。

1000

木が何本かあって、長い道に植えたい。木はそれぞれ、隣の木との長さの最小値が決まっていて、すべての木に対してその最小値を満たさなければならない。木の植え方は何通りある（かを1,000,000,007で割った余りは）？

なんとなくわかったけど、時間が足りなくて組めなかった

結果

500で(x==1&&y==1)?0:2という意味不明なコードがあったので落とそうとしたらボタンを押したのに僅差で落とせなかった

oox +0.0 683.42 18位

Rating: 1989 -> 2167