今回から8問ABC。FH以外の6完。ABが若干PASTみを感じる重さで、少しでも時間が欲しい中では嫌な感じ。Fが位置のわりに難しかったね。Hを読む時間がなかったのは残念。
A - Alloy
生成された金属がちゃんとある(0グラムではない)という設定。それなら、銀がなければ純金。金がなければ純銀。そうでなければ合金。サンプルは自動でチェックするからスペルミスの心配はないが、たくさんの単語を手で打ち込んだりコピペしたりする必要があってイヤ。
B - Weak Password
andのorなのがやや複雑。まあそこは力でねじ伏せることができる。問題は実装で、1234みたくなってるかの判定で、文字から'0'を引いておかないとmodで判定できないことにその部分を書くまで気づかなかった。
(解説を見て)あー両方modとれば文字のままでもいいのね。でもかなり難しいので避けたい。
C - Min Difference
解けるけど難しくて焦る。まず、ソートしてしまっていいのでソートする。すると、しゃくとりが見える。しかし前後を見る必要があるのでかなり面倒。少し考えて二分探索を選択。返ってくる位置は0からMまであるので、端っこのときは1か所しか見ないようにする。
D - Querying Multiset
よくあるやつ。とりあえず操作2のXの和を持つ(Sとする)。priority_queueを使い輪郭を描いていく。すると、priority_queueから取り出してSを足して出力するという方針で行けそうなことがわかる。自分が加入したときから出力クエリまでに足されたぶんがわかればいいので、ボールを袋に入れるときにそのときのSを引いておけばよい。結果的には早く解けたが、簡単だとわかっている問題の解法がなかなか見えず不安だった。
E - Safety Journey
5000^2っぽいグラフなので、定数倍が大丈夫なのかヒヤヒヤしながら読み進める。わからないので、まずM=0のケースを考える。まず手で実験。各頂点に通り数を持ち、その総和を求めてから、移動しないことはできないというぶんを引けばいい。ということは、ここから更にM本の使えない辺のぶんを引けばよさそう。なるほど、グラフは普通定数倍が重いけど、今回は長さM*2の配列をだーっと見ていけばいいので辺へのアクセスは高速なんだ(引き算はランダムアクセスっぽくなってしまう(今考えると頂点数が5000で少なく持ってるデータも通り数だけで小さいからキャッシュに乗って高速だ))。
ここまで30分で解けているのはだいぶ良い。結果的にはこの時点でパフォーマンス1900以上が確保されていた。
F - Greedy Takahashi
ダブリングっぽいので嫌だなあと思いGを先にやることを考える。少しだけ実装してみたが、そもそもスタート地点が都市番号*時刻でめちゃくちゃいっぱいあり、素直なダブリングでは無理そうだと気づく。ここで順位表を見て、後半3問がヤバそうなのを知る。一番解かれていたのがG。得意そうな見た目でもあったので、以降ずっとGをやっていた。
(追記)ダブリングを使いクエリはオンラインで処理する。M個のバスは、普通に配列へ保存するのと、都市毎に出発時刻でソートして持っておく。都市と時刻が与えられたら次のバスの番号を返す関数を書く(二分探索)。それを使い各バスについて次のバスを求め、それを元にダブリングの前計算をする。クエリの処理は、まず時刻Zまでにバスが来るかを判定する。来ないならYが答え。来るなら、ダブリングで大きいほうから出発時刻がZより前なら進むようにすれば最後に乗るバスがわかり、バスから降りたかで場合分けして出力。―この流れを実装前にイメージすることは不可能。確かに考察難度は500点でしかないが、自分はバスだけに注目してダブリングという見方に自力では気づかなかったし、この実装をあの短いコンテスト時間内にやり切ったやつは化け物。
G - Power Pair
x=0の場合は常にy=0の1通り。そうでないとき、xが原始根ならP-1通り。P=7として手で色々考える。x=3だと周期6で、x=2だと周期3。その2は、x=3のシーケンスだと2番目に出てくる。周期6のところを歩幅2で歩くから周期3になるのだ。つまり、Pに対する原始根の一つをr、P-1の約数をdとすると、r^dに対するyの個数は(P-1)/d個だ。0からP-2までのうちdの倍数は(P-1)/d個あり、それらに対しても(P-1)/d個以下だとは言える。とりあえず約数列挙はしてみるが、約数同士が複雑に絡み合ってどうしたらいいかわからない。最初は簡単そうに思えたが、何も進まなくなった。色々考えるが、Pがでかいのでつらい。それどころか愚直っぽいものも混乱して書けない(とりあえず足しといて約数の約数のぶんを引くという方針だが、なんか合わなかった)。それとは別に、Pが偶数のときがコーナーケースになるといけないので、まだそれが必要かはわからないが、Pが小さいとき用の愚直を書いておいた。
残り15分くらいになって、約数の包除原理に関連して高速ゼータ変換が浮かぶ。約数に対してだけなら間に合う。手で単純なケースをいじり、累積和をとるのの逆の操作は、小さいほうから引き算していけばいいんだなと。時間がないけど短時間で書ける方針が見つかると願いながらやる。まず、P-1を素因数分解(unordered_mapで何が何個というのを持ったが、何個という情報は要らなかった)。mapで各約数についてその倍数が(P-1個中)何個あるかを入れる。これが、累積和をとったらこうなったという結果なので、各素因数について累積和の逆の操作をする(大きいほうへ向かって操作していくのでmap)(mapに含まれている範囲だけ操作する)と、それがもう答え。掛け算して足していくだけ(ここは最初に書いておいた)。100分8問のABCで、Gに1時間くらいかけてしまったけど、最後10分程度で難しそうな実装ができたのはよかった。
H - Nim Counting
(追記)アダマール変換、難しそうで触れてなかったけど、多次元のDFTと見ることができるんだね。Wikipediaにも書いてあったけど以前見たときは目に入らなかった。ABCでこういう典型が出ると、Twitterで話題になってそれを見て理解のきっかけになるというメリットがある。多次元の畳み込みについてもそういえば考えたことがなかった(そもそもFFTについて多倍長整数の乗算と画像処理しか用途を知らない)。xorは言われてみれば長さ2の巡回畳み込みになっている(ビット数が次元数)。正直あまりわかってないけど、まずてきとうにACをとってそれから布団の中で考えるというのを昨夜やって少し理解が進んだ(理解が不可能なときにどんな手段でもいいからACしてそれから考えるというのはたまにやってわりと効果的)。肝心の、なぜアダマール変換でこの問題が解けるのかという部分だが、最初に解法を見てしまった(というか解説を見るまで(DPは見えていたものの)高速に解けるとは思えなかった)ため、「言われてみれば正しそう?」くらいにしかならない。線型性はまあいいとして、DPを2回進めるのに3乗すればいいというのが感覚にない(これも1回進めて逆変換して変換して1回進めてとすれば確かにそうなってはいるんだけど)。DPを1回進めるのがxor畳み込みになってるというのも「それっぽいなあ」程度。