全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する」という制約から推移律を破るような循環する入力は与えられないと思ったけど勘違いだろうか。あるいは単純に計算量が見積もれていないだけだろうか。N≦50 だから４乗でも通るはずだけど。TLE の原因がわからない。Ruby で最初に提出された #44259309 (kuma_rb さん) の着眼点がすごい。負けなかった人が一人だけいたならその人が最強だと。トーナメントではそういう話を聞いたことがあるけどね(「優勝者とは唯一負けなかった者のことである」)。■C 問題「Approximate Equalization 2」。これは B 問題より簡単だった。平均として考えられる２つの整数(切り捨てと切り上げ)を考えて、A 数列のすべての要素について下げるなら下げる量、上げるなら上げる量を数える。下げる量と上げる量の大きい方が答え。上げるのと下げるののうち操作回数が余った方は２つの平均値のあいだを移動するのに使われている。■D 問題は答えを求める手順がわからなくて飛ばした。もし答えが絶対にわからないときの答え方が用意されていたら、まんまと「わかりません」と答えて WA をもらっていたところだった。■E 問題「Duplicate」。そもそも長さ１に収束するというのがけっこうなレアケース。S="22" でも永遠に短くならない。先頭の文字はどうでもいい。２番目以降の文字が操作後の長さを決める。１なら現状維持(ということは操作により末尾の１文字分減る)。２以上なら伸びる。しかし２から９までの数が２から９までの数を増やして伸びることはない(そうしたら収束しない)。２から９までの数が末尾に至って消滅するまでに何個の１を生成するかを数える問題。右側にある文字数と同じ回数だけ、決まった長さ(１から８)だけ伸びる。右側にある文字数が知りたいので末尾から(ほとんど１の)長さであり操作回数を数える。■D 問題「Odd or Even」。コンテスト終了まで考えていた F 問題 Flip Machines が解けなかったので終了後に D 問題に戻ってきた。N 回のクエリで数列全体の偶奇(の連鎖)が決まるのはわかる。たとえば A[1..K] の偶奇がわかって A[1..K-1,K+1] の偶奇がわかると A[K] を基準にして A[K+1] の偶奇が同じか異なっているか決めることができる。同様にして A[K+2] 以降も決める。A[1] から A[K-1] の偶奇についてもうまいことやって決める。ここからが問題だった。クエリ回数は上限の N 回まで使い切っている。A[K] の偶奇を基準にして同じか異なっているかはすべて判明しているが、A[K] の偶奇を決めることができるのかどうか。たぶんここで K が奇数だということが効いてくるのかな。最初のクエリを思い出そう。A[1..K] の偶奇がわかっている。そして A[K] を基準にした仮の偶奇について、１から K までの範囲の偶奇はどうなっているだろうか。一致しているだろうか異なっているだろうか。もう解けた。■コンテスト成績証。自分のすべての提出。D 問題も時間内に解きたかったけど、終了後に１時間かけているので惜しいところはなかった。それというのも人間ジャッジがときどきレスポンスの偶奇を間違えるからなのですね。解答のデバッグと並行していつの間にかジャッジのデバッグをさせられていたのでは時間もかかる。D 抜きでも青パフォが出たのは E 問題様様です。■F 問題について。N≦40 と制約はかなり控えめ。各マシンについてありうる未来はかなり限定されていると思った。操作しなければ２枚のカードについて {表表}。１回の操作で {表裏,裏表}、２回の操作で {表表,裏裏}、３回の操作で {表裏,裏表} これは１回の操作と同じ未来。それでどうする？