2完。先週はコンテストがなかったため、昨日は準備運動として久しぶりにyukicoderに出た。今日は夕食をたくさん食べて少しだけ横になった。
結果はよかったけど、内容は完全に運ゲー。最後のほうで順位表を見てたけど、AGCは本当に頂上決戦という感じ。問題文も一応全部目を通したけど、シンプルな設定で難しいけど解ける（出題されているからには解けるのだろう）という。自分はそのほんの表層で結果が良かったり悪かったりするだけなんだなあと思った。
2問しか通してないとはいえ時間が長いコンテストなので書くことたくさんあってしんどいな。
A - Antichain of Integer Strings
最初、全く頭が働かなかった。AGCは「つまらない」状態になりやすい。コンテスト中の時間がもったいないという意味もあるので、できるだけ早くこの状態を脱したいが、他の問題を考えるくらいしかないかなあ。
考え続けていると、だんだん景色が整理されてくる。まず、桁数が同じであれば集合に全部入れることができる。そして、例えば3桁の数を全部（900個）入れたらそれより少ない桁の数は全て部分文字列に現れているので一つも入らない。おそらく、Rが4桁なら3桁以上だけ考えればいい（小さい数は少ないし部分文字列に現れやすいし）。4桁だけ入れるのと3桁だけ入れるのは簡単。問題は両方を選ぶケース。900個を上限に連続する数を選ぶことはできそうだ。そのように実装する。Rと桁数が同じ10冪を求める（R以下の最大なのかR未満の最大なのか、色々あって難しかった）。そこを境界にして頑張って書く。サンプルが合わない。
弱いと思っていたサンプルに助けられたよ。1000と100は同居できないので、[100, 1000]だと（901個ではなく）900個が答えになるのだが、例えば[200, 1199]なら下3桁1000通り全部選べるし4桁の数の上3桁も100から119までしか現れないから答えは1000個。上3桁の増加は緩やかだ。上から1000個まで選べそう。というわけで提出してAC。きっちり証明したわけではないが、これだけ時間をかけると最初は想像もできなかったくらいの感触が得られているし、コンテスト中にこれ以上考えても仕方ないという割り切りもできる（そのくらいやばい問題）。
B - 2A + x
あるA_iにK回操作したときの最小値と最大値を考える。その最小値と最大値の間の数を、Xが1でさえ全部選べるんで、1以上なのだから全部選べる。例えば全体の最小値を固定したら、各A_iについてO(log(その最小値))で最適な操作がわかるよなとか考えたけど、それだけ。問題は面白そうだけど具体的にどこから攻めるかが見えなかった。
操作するかしないかで分けて、しないなら簡単。するなら、最小のA_iは操作する（他のやつだけ操作しても悪化するだけ）。あとは最大値と最小値の差を逐次高速に求めることができれば希望が出てくる。操作後の状態を（閉）区間で考える（区間内の数（整数）はどれでも選べる）（区間の最大値が最小のものを操作するとしてよい）。区間の最小値でソートすると、最小値が最大の区間からは最小値を選ぶとしていい。他の区間はどれもそれ以下の数を選ぶことができるので、区間の最大値の最小がわかれば最小化したい「差」もわかる（その最小を同じやつがとってても大丈夫（そのときの差は0））。たぶん2^60を超える演算は要求されないというメタ読みで決め打つと、操作回数はlogが付く程度で押さえられ、操作もlogくらいでできるので、TL4秒ならなんとか通りそう。2つの整数のペアを持ち、要素の削除と追加ができて、ペアの1個目の最小と2個目の最大がわかるデータ構造が欲しい。こういうの、「AGCで枝葉末節でつまづかないように8問ABCで備えていた」という感じがして、いいね。priority_queueとか考えたけど結局multisetに。区間なので整数が2つあり、multisetも2つ使う。バラバラに入れて、ペアの削除挿入はまた別のsetみたいのに入れて管理するイメージだったが、色々考えて、multisetにペアを入れてもう一つのmultisetで違う側だけ入れて「区間の最小値の最大」を管理するようにした。最大値が最小な区間を一つとり、削除して、操作したものを挿入する。急に実装が終わって提出。TLEにビクビクしていたが、ジャッジに2分かかってAC。C++で2秒以上かかってしまった。2^60以上になる操作はしなくていいというのも証明してないし、表面をなでて結果だけ持っていったゴミ。問題は面白かった。
C - Increment or Xor
隣とのxorをあの形に持っていく。最下位ビットはどちらの操作でも反転するだけなのでそこは交互になっている必要がある。2段目からが難しい。そこもxorでは個別に操作できないので、1を足して最下位が1のところだけ繰り上がって更に最下位に1をxorすれば2段目だけ足し算した格好に。3段目からがマジで霧がかかっていて視界が届かない。ちまちま足し算で操作するのもしんどいし、途中でxor挟まれることもあるので難しくなる。
