4完。すべてがだめだった。食べ過ぎて開始前に2回トイレに行ったが、Dを実装している途中にも行きたくなり、Eをスマホで撮って読みながらのトイレだったのでタイムロスは少ないと思いきやEもFも解けず。Dのタイムが悪くなったうえ、EもFも中途半端でどちらかに集中していればあるいはという感じだった。内容的には楽しめたんじゃないかと思う（その意味ではタイムロスほとんどないし）。しかし、問題を通すところまで行けないのはもどかしい。
EFをじっくり考えた。あるいはじゃないんだよな。あと1時間あったとしてもどちらも解けなかった。結果は酷かったけど問題は面白かった。でも実装は嫌です。
A - Who Ate the Cake?
AとBが同じなら特定できない。そうでないなら、3人のうち2人が候補から外れるので特定できる。特定できる場合、A xor B xor 1 xor 2 xor 3 が答えになる。
B - Piano 2
値とABどっち由来かのペアを値でソートして、「相異なる」という制約から隣同士を全部見てA由来が連続しているところがあるかを調べる。
C - Bingo 2
斜めやりたくねーって言いながら書いてた。しかし斜めが思ったより難しかったので、斜めを外した問題にするわけにもいかなかっただろうなと。N*2+2個の列について何個埋まっているかを持つ。対角線の片方は、A_i（を0-indexedに直したもの）がN+1の倍数かで判定できるが、もう片方はN-1の倍数というだけでは0やN*N-1まで含まれてしまう。
斜めも、A_iから直接ではなく、マスの座標で判定すればいいらしいです。いやN+1の倍数が見えてしまったら戻れないね。座標は縦横のために求めてあるのに。
（追記）Nが小さいの忘れてたなあ。忘れてなかったとして、特に解き方は変わらなかったと思うが。
D - Intersecting Intervals
ソートしてBITというのをやりたいので、まず座標圧縮する。順序を考慮しないすべてのペアについて数えるので、ソートしてもいい。rでソートして、自分より前のものとの条件を満たす個数を数える。共通部分があるかどうかは、相手のlに依存しない。相手のrが含まれていればそこが共通部分だし、含まれていなければそこより左に含まれるものはない。自分のrで終わる世界で考えることができる。つまり、rの位置に1を足しておいて、自分のlから右の個数を数えればいい。今回は自分自身もカウントしてしまうので、和を求めたあとで1を足す必要がある。
しゃくとりでできるマジ！？ちょっと考えたけどわからなかった。
（追記）lでソートして自分より前で自分と共通部分を持たない区間の個数がわかればいい。これは、rをソートして自分のlより小さいものの個数がわかればいい。確かにしゃくとりでできそうだ。lとrを別々にソートしていいというのがやばすぎる。実装しようと思ったが、えびま解説を見たらまとめてソートしていけそうでこっちのが実装楽そうだったのでこっちにした。
E - Guess the Sum
またセグ木みたいにやって、簡単すぎないか？と思っていたら、[0, 7)は3回ではなく引き算すれば2回でできる。最小回数をDPで求めて復元かなあとトイレでは考えていたが、改めて考えると全部の区間を考えると（2^18の）2乗になってしまい無理。じゃあ再帰型のセグ木みたいにやるか。これも、ノード数はセグ木と同じで大丈夫だが、引き算するかどうかで2通りに分かれるので計算量がわからない。
結果的に、EFを交互に考えた。毎回、反対側には戻らずこれを解くというつもりでやっていたのに。
再帰で2つに分かれたとき、区間の片側は2冪に揃う。つまり、[0, r)という形の区間だけ最小回数がわかればいい。これをDPしようとするが、引き算が1回とは限らない可能性に気づいた。2冪まで15足りないとかの場合がよくわからなかった（今考えると15を2回で作っても、1回かけて16にしてから16を1回で引いても同じかなあ（引き算するときは全体をやるぶんの1回がかかるので見通しが立たなかった））。2冪を足し引きして0にすると思っていいのかどうかも自信が持てない（端ではなく半端な境界線でやってるからなあ）。じゃあもう計算量には目を瞑って再帰かと思って書き始めるが、復元も必要なのでかなり大変で、残り10分になってあきらめた。
[0, r)の区間で、rが奇数だったら幅1の区間は必ず使う。使う場所はrの前後としていいだろう。前後2通りの遷移でDPできそう。あとは、2冪に区切らない[1,15)みたいなパターンがあって、区切ったとしても(1,8]みたいな逆向きもやらなきゃいけないの嫌すぎる。実装のビジョンが見えない。
（追記）類題とされるものを見て、いや関係ないだろと思い、しばらくしてグラフで解けそうだと気づいた。おもっくそ関係あった。いやこれは見えない。あまりにも見えない。使える規則性がありそうなところで牛刀を持ちだす勇気。これは無理だ。力不足だ。正当性は、Lが含まれてL-1が含まれない質問が必要なので最適解があったらそういう質問をとることができて、繰り返すと全質問は区間の左端の移動だけになり、逆にグラフの経路があれば向きで符号を付けて経路の長さの質問回数で答えがわかる（けっこう難しい）。実装は、BFSして復元。無向グラフなのでやりやすい。質問の形式がこれなので、面倒だしデバッグがしづらい。実装を本当にやりたくない。どうにか書き上げた。
F - MST Query
木に1本加えて最小全域木。LCAを求めてそこまでの最大値がわかればいい。と思ったら辺は追加されっぱなしになるらしい。不可能なのでEへ。
けっこう解かれている。これ、追加した辺が使われたら、使われなかった辺の重みを追加した辺に変更してもいいか？実装は簡単だが大変（？）、正当性あるいは反例が全然わからない。追加した辺のみで閉路ができたときに何か起こりそうな気もするが。今考えたら反例が見つかった。
逆から考えるというのをやってみたら、急に行けそうになり、でもやっぱりだめだった。感覚がぶれすぎる。将棋で言うと一手深く読むたびに評価値が大きく変わる感じの。これでは、どの手を読むのがいいかなども判断できない。
（追記）重みが10以下なの今まですっかり忘れていた。しかしそれでも解けず。辺の重み0か1の場合で考えてもわからない。えびま解説を見るが、わからない。実際にどんな処理をしているかを見て、それも解法というものには見えなかったが、しばらくすると確かにそれで解けていそうだ。解法でないもので解けているように見えて変な感じ。そっち方向から見る発想がなかった。確かに、クラスカル法の途中経過はそうなるし、その情報で解けている。
