ちゃんと3つとも解いた！
これで予選の準備は万端… だといいな。
書いたコードはこっち(GitHub)です。以下は簡単な解説。
A: 数珠つなぎ
スナッパーのOFF/ON状態を0/1で表すと、 0000 -> 0001 -> 0010 -> 0011 -> 0100 みたいになってて、増えていく2進数と同じ形になるので、Kの数を2進数表現したときに下位Nビットが立っているかを調べればOK.
B: 数の集合
多分2つ知ってないといけないことがあると思う。1つは素数のリストの作り方で、これはエラトステネスのふるいっていうのを使った。もう一つは集合を効率よく結合していく方法で、Union-Findっていうアルゴリズムが有名らしい。チャレンジブックで習った。その２つが使えれば、あとはP以上の素数ごとに区間内からその素数の倍数を探して、属してる集合を結合していくだけ。区間の長さを超える素数は2つ以上倍数が見つかる可能性が無いので用は無いです。
C: 遊園地
計算結果をメモしておく工夫と周期的な動きを利用する工夫で計算量を減らせる問題。「iグループ目が先頭の状態でコースターが来たら、何人乗れて、次はどのグループが先頭になるのか」を先に計算しておいて再利用する方法でlargeが10秒くらい。「iグループ目が先頭の状態からいくつかコースターが来たらまたiグループ目が先頭になった」というループ状態を見つけて、その部分の計算をはしょると、largeが0.05秒くらいでした。
解くの時間かかったけど、勉強になるなぁ
