SRM489 Div1

ここには書いていなかったのだけれど、前回のSRM488でDiv1に上がっていたので、今回からDiv1です。
とりあえず、Div2に戻らないように頑張りたい。

結果

○×× 176.84 pt
1230 -> 1300
でした。

以下、断片的なメモ

250

なにやら、二つのボールから一つのボールにする変換を繰り返して、ボールを一つにするのだけれど、その結果が変換の順序によらず一意に定まるか求めるらしい。
ということは、この演算が可換ならばいいはず。
xy = yx になることは、問題で保証されているから、結合則が成り立てば良い。
結合則は、3つの組み合わせの場合に成り立てば、帰納法で全部の個数の組み合わせについて成り立つことが示せるから、結局3つのボールの組み合わせについて結合則が成り立つか確認してやれば良いのか。
書いて、サンプルもあって submit
System testも通った。

500

たぶん、x,yがある程度大きければ移動の方法は存在するはず。
ほとんどの場合は、2なんだろうけどさすがに例外があるはず。
その例外を見つけられなかったので、結局かけなかった。