A: Snapper Chain
Snapper という謎の装置があって、以下の機能を備えている。
- 電力の入力プラグと、出力プラグがある。さらに、ON/OFFスイッチがある。
- 電力が供給されているときに指をパチンと鳴らすと、スイッチが切り替わる。
- 電力が供給されていて、かつスイッチがONだと、出力から電力を供給し始める。
で、この Snapper を数珠つなぎにして指をパチンパチン鳴らしまくったときに、その末端の電力の供給状況がどうなるかをチェックする、という問題。
ややこしかったのでいくつか図を書いたら結構簡単に解けた。
……と思ったら、その肝心の図を描いたときに「一度供給された電力はOFFになっても供給され続ける」ような間違いをしてしまったためにえらい手こずった。
どうしても分からないときは問題文を再度見直す、というのは2009年のときの教訓の一つ。
読み直して、ちゃんと図を描き直したらようやく間違いに気づいた。
N個目がオンになるときは指パッチンの回数Kが2**N-1以上でかつKが奇数のときということに気づけば後は簡単。
最初の提出は17分だったが、結局57分もかかった。
……で、解説を見ると、
「ON/OFFの部分がちょうど2進数表記での1/0に対応しているから指パッチンの回数を01に変換してから 目的のプラグの位置のビットを確認すれば余裕」
そこまで気づかなかった……。
B: Fair Warning
Large のデータ範囲が 〜10**50 とかひどいことになってたが、Python を使ってたので何も問題なかった。
これ C/C++ とか使ってる人どうすんだろ、とか思ってたら解説で
「24時間ありゃ Big Int 対応ライブラリぐらい実装できるっしょ。これで次のラウンドからみんな公平だね！ やったね！」
とか書いてあってマジ鬼畜。
この問題のタイトルはそういう意味らしい。「おめーらこれで次から big int でてきても文句言うんじゃねえぞ」だって。
問題を説明するのがちょっと面倒だが、ようするに数字セットが与えられた時、それぞれの数字に別の数字を足すとする。全体の最大公約数を最大にするにはいくつ足せばいいか、ということ。
まず最大公約数を求める関数が必要。ユークリッドの互除法を実装すればいいのだが、これくらいの関数は言語標準で実装されてるだろ、と思い探してみることにしたら本当にあった。
python2.6 からは fractions モジュールというのがあり、その中に gcd() 関数がある。
http://pythonjp.sourceforge.jp/dev/library/fractions.html
車輪の再発明をせず、言語のマニュアルにあたるべしというのも去年の教訓の一つ。
去年は ruby1.9 に permutation メソッドがあることを知らず、痛い目を見た。
で、解き方だが、自分はまず「各数字間で最も小さい差分が、GCDの上限」ということに気づき、それを求めた。
次に、その差分を求めるのに使った数字のいずれかを用い、他の数字との差分を求めた。
最後に、その差分同士のGCDを求めたときに一番小さいものが、最大のGCDとなる。
答え見たらもっと単純に考えてた。
最初の数字から、他の全ての数字に対し差分をとってGCD計算すりゃいいじゃんて書いてあった。
考えてみりゃそりゃそうだ。
結局1時間ほどかかった。
C: Theme Park
1日にR回運行するk人乗りのジェットコースターの1日の売上を求めよ、という問題。
乗客はグループ単位できて、空き席があってもグループ人数分足りなければ、その回はスルーする。
データセットが小さければ特に難しいところはない。丁寧に実装すればおしまい。
問題はやはり Large セットで、R<10**8, k<10**9 なんていう素敵なサイズを見せてくれる。
「あるグループから乗りはじめた時、どのグループまでで終わるかは常に同じである」
ことに気づいたので、とりあえずキャッシュをしておくことに。
「乗車パターンはループする」
ことにも気づいたので、この1ループごとまとめて計算するようにした。
……と、ここまではよかったのだが、結局 Large は時間切れになった。
原因の一つは、ループしたときに残りの運行回数を引き算していたことだ。
1ループでの運行回数で除算すれば一瞬なのに、このせいで全く性能が出ない。
もう一つの理由は、ループが運行1回目から始まるときにしか対応していなかったことだ。
頭では気づいていたのに、いつの間にかそういう実装になっていた。
だからループを検知できてなかった。
答えをみても大体そんな感じ。
バイナリサーチ使えばもっと速くなるけど、この問題ではそこまで必要ない、とも書いてあった。
まとめ
去年は5時間かかって76点、今年は2時間40分かかって76点。
少しは成長したが、トップの人たちは30〜60分ぐらいで満点をとってるのでそれに比べればまだまだレベルが低い。
読み間違いを含む細かいミスも多いし、頭の柔軟性も足りない。
もっと精進しなきゃね。
