08/08(月)

正午起床。起き抜け、喉に違和感があり、「やったか」と思った。コロナウイルスの今流行っている変異株では喉の痛みが初期症状らしい。しかし一方で、エアコンを除湿モードにしたまま口を開けて寝ていたようだったので、ただ乾燥しているだけという可能性もある。

とりあえず今日は家から出る用事もない。食事して午後1時からMulti-Universities Camp 7回目。

"蔚来杯"2022牛客暑期多校训练营7_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

チームでGKCFJA、自分はGとFを解いた。序盤の速度は非常に良く、確か30分ちょっとで5完してその時点では1位だったはず。しかし6問目が通ったのがコンテスト開始2時間後ですでに順位は下がり気味、その上それ以降1問も解けず、最終順位はこれまでのCampでも格段に低かった。

Gは文字列に対してその全体にマッチする最短の正規表現の長さと種類数を求めよというもの。基本.*で良いためギャグ。Fは、円状に並んだ数列から隣り合う要素であって「等しい」「足して $x$ になる」のどちらかを満たすペアを削除する操作が、最大で何回行えるかという問題。 $a$ とペアにして削除できる数は $x-a$ とペアにしても削除できるため、どちらを残すかなど考えず貪欲に操作してよい。

Eをサンプルからエスパーして書いてみたものの、出すと落ち、さらに手元で愚直を書いただけでも全然答えが違うことが判明して絶望。じっと考え込んでいるうちに眠気がひどくなり、30分ほど仮眠を取ったが改善せず、インターン先定例会で離脱するまで自分は使い物にならなかった。

午後4時半からインターン先定例会。特に何もなし。進捗もあまりない。勉強会は「イノベーションのジレンマ」という本に関してで、論理は理解できるもののあまり興味が持てなかった。企業経営の視点だけでなくエンジニア目線での話もされていたが、会社で働く人間としての自覚が薄いためどうにもふわふわした手触り。自分で何かを判断するようなことがないのが大きそう、と考えた。

母親から電話がかかってきて、これ幸いと帰省について少し相談した。元々明日からの予定だったが、起きた時の喉の痛みもあるし、コンテスト中の異常な眠気も怪しい。つい昨日、東京に行って数人とテーブルを囲み食事したという事実すらある今、帰省を取りやめにするべきなのではないか。結局その場で結論は出ず、明日起きた時判断する、ということになった。

日記を書いていたらへのkからDMが来た。日本最強プログラマー学生選手権の宿泊について。お互い前泊するつもりらしく、まだ宿を決めていない。このとき、二人分の宿泊費を合わせればパークハイアット東京という高級ホテルに泊まれるのではないかとのこと。実際は土曜日夜は値段が跳ね上がるため不可能なのだが、ともかく二人で泊まるというのはなかなか面白い行動に思えた。

しかしAtCoderのほうに問い合わせると感染症対策のためやめてほしいと返答が来た。当たり前すぎる……。

@chokudai
日本最強プログラマー学生選手権の宿泊についてですが、出場者複数人で同じ部屋に泊まる場合も「一人当たり」に負担していただける予算は変わらないと想定してよいでしょうか？
— こたつがめ (@kotatsugame_t) 2022年8月8日

感染症対策としてそういうのは基本ダメらしいです
— こたつがめ (@kotatsugame_t) 2022年8月8日

それでも泊まる宿は合わせることにして、しばらく相談を続けていた。いろいろ探すうち、なぜか予約サイトのポイントが大量付与されて2割引きで泊まれるものを見つけた。割引なしではまったく手が届かない値段だからかなり良いホテルのはず。そこに決め、予約した。

午後11時半、ひとまず週記を書き上げて投稿。先週分は校閲がされていないどころか日曜日の部分をこれから書く予定の参加記に丸投げしているので、内容が非常に薄い。とは言え間に合ったので、その解放感からしばらくYouTubeに意識を持っていかれていた。

校閲まで終わったのが午前2時半。上で予約したホテル代と調べた交通費をもとに日本最強プログラマー学生選手権の参加登録のフォームを埋めて送信した。その後はしばらくYouTubeを眺め続け、午前5時就寝。

08/09(火)

午後1時起床。喉の痛みはない。頭が多少ぼんやりしている気がする。

さて。喉の痛みは、昨日書いたようにただの乾燥である可能性が高い。また眠気がひどかったり頭がぼんやりするのも、最近睡眠不足だからという理由が考えられる。そもそも、日曜日に東京でウイルスをもらってきたとして、次の日いきなり発症ということはまずないはずだ。だから昨日今日の体調不良は別の原因であると言い切ってよいだろう。

しかし東京に行った数日後に帰省を強行するというのもまた躊躇われることであるのは間違いない。なのでやはり帰省は取りやめにしようという決断をし、両親に電話して伝えた。PCR検査で判断したいところだったが、軽く調べた感じお盆前で予約が完全に埋まっているらしい。

先週金曜日に参加したDMOJのYet Another Contest 4が終了していた。ここに感想を書いておく。

Yet Another Contest 4 - DMOJ: Modern Online Judge

P1は操作しても何も変わらない。P2は $b_i$ について $b_j=b_i-1$ なる $j$ があるなら $i\rightarrow j$ とすればよく、なければ $b=b_i$ なるインデックスを集めて長さ $b_i$ のループをいくつか作るしかない。ここまでは簡単枠で、さあこれからだと思っていたら、なんと3問目以降1問も完答できなかった。

P3は2部グラフなら自明、そうでなくても3彩色可能だと考えた。実際、2部グラフだと思ってdfsで白黒に塗りつつ、もしどの色で塗っても同じ色に隣り合ってしまう場合は必ず白を使うと固定したところ、ちゃんと黒が隣り合うことはなく、また白で塗られた頂点だけ見たとき2部グラフになっていた。assertで確認した。ここを改めて塗りなおすことで3彩色が完成するため解けた、と思ったのだが最後の部分点でWAが出る。理由がわからないので、60点のまま飛ばしてP4に移った。

P4は苦行。縦横入れ替えることを考えると、横に切ると固定してよい。この時条件は、「行・列ごとの和がすべて偶数であること」「切った上半分だけ見たとき、列ごとの和がすべて偶数であること」と書き直せる。前者を見ることで操作の対象にするべき長方形の縦横が決まることもあるので、縦と横が決まるか決まらないか、都合4通りの場合分けをして、気合いでチェックする。チェックの方法を事細かに書く気はない。基本的に、どの場合でもまず切る行を固定して、それから条件を満たす長方形とその内部の奇数が存在するかを、適切に前計算することで見た。

とりあえず最初の部分点は通ったものの、その後全く先に進まない。コンテスト終了間際に勘違いに気づいたものの修正できるわけもなく、合計265点に終わった。直後からしばらくかけてP3、P4、P5のupsolveをした。

まずP3だが、なんと「2部グラフなら自明」と書いたところが間違っていたことが判明した。 $B$ 以下で最大の2べきを $2^t$ とすると、 $2^t$ と $2^t-1$ を交互に置くことで最大 $2^{t+1}-1$ が達成できる。自分は $B$ と $0$ を置いており、しかもそこに何ら違和感を覚えなかった。3彩色の部分ではちゃんと2べきのことを考えていたのに、いったい何をしていたのだろうか。

ちなみにカクタスグラフは3彩色可能。より一般に外平面的グラフは3彩色可能であり、これは5月に受講した集中講義の課題にもなっていたが、四色定理でぶん殴る証明がある。外平面的グラフとは、1頂点追加してそこからすべての頂点に辺を伸ばしても平面的なグラフだと言えて、これを4彩色すると追加した1頂点の色は残りの頂点に塗れないため、その頂点を削除すると3彩色になっている。まあそもそも平面グラフの4彩色を得るのが難しいため今回の問題には関係ない。

P4。コンテスト中の勘違いとは、長方形の縦が決まっていないとき、わざと広く取ることで遠くの奇数マスを巻き込めることを完全に見落としており、近くで解決できないならダメだと諦めていたこと。しかしこれを修正しても全然通らなかったため、ひとまず愚直を書き、4通りの場合分けそれぞれを置き換えてどこが間違っているのか試してみた。これを書いてさえいればあと15点くらい入ったはず、と思いながら実装していた。

しかし相変わらずWAが出てよくわからない。しばらく苦しんでついにバグを発見した。なんと、行列の縦横を入れ替える部分のコードが間違っていたのだ。添え字ミスで $N\times M$ を $M\times N$ にするはずが逆になっていた。これを修正し、満点。基本のアルゴリズムは勘違いを修正して以降特に弄っていないものの、そもそもその勘違いの修正すらコンテスト時間内に修正できなかったのだから、満点は絶望的だったか。

P5はコンテスト中に見ることができなかったが、非常に簡単だった。 $K$ を左から右に動かしていくことを考えると、 $K=(p_i+p_j)/2$ を境に $i$ と $j$ の順番が入れ替わる。またその位置を通る瞬間、標識は2通りになって、そのうち1通りは直前までのものだから、答えに $+2-1$ すると考えられる。より一般に、 $(p_i+p_j)/2$ が複数のペア $(i,j)$ によって一致する場合、各ペアの順序は全く独立だから、重複度を $k$ として答えに $+2^k-1$ することになる。畳み込みで重複度を計算できる。

順位は33位、レートは2625→2475(-150)。最悪。なんだかDMOJが苦手らしい。問題が苦手だし、順位表が見えないというコンテスト形式も苦手。

午後2時に二度寝。寝ている間にGCJ Tシャツが配達されて、何とか意識を取り戻して受け取れた。開封とツイートは深夜に行った。

2022 pic.twitter.com/SQvOFeODWQ
— こたつがめ (@kotatsugame_t) 2022年8月9日

午後6時に目覚ましで起床。家を出て、相も変わらず込み合っているみどりの窓口に並び、帰省用に購入した新幹線の切符を払い戻した。日付変更もできるようだったが、まだ代わりの帰省の予定は決まっていない。

立ち食い蕎麦を食べてゲーセンへ。今のところ体調不良もないし、東京での行動は帰省を自粛するレベルではあったものの、ゲーセンすら行かず引きこもるほどではないという考えである。今日は14を頑張っていた。成果はまとめてツイートしたが、AJが三つ、SSS+が一つ。

J219 AJ
AVALON AJ
Elemental Creation AJ pic.twitter.com/0qeRYcggyN
— こたつがめ (@kotatsugame_t) 2022年8月9日

J219は中盤の鍵盤がやたら上手かったため、ラストをどついてAJ通過することを祈るゲームになった。何回かやったら成功した。

AVALONはまっとうに頑張った。105、106小節は全部擦り。プレイを重ねるうちいたるところに癖がついて大変だった。

Elemental Creationはありえないくらいうまかった。今日2プレイ。105小節と107小節は擦って、それ以外は全部押した。ひたすら忙しくてあまり粘着したくない部類の譜面なので、しっかり決め切れてよかった。

Tango Rouge 1-0
14全SSS+ pic.twitter.com/UCHBfsRs4Y
— こたつがめ (@kotatsugame_t) 2022年8月9日

今日1プレイ。ホールドの上に重なったタップで出した。次のプレイは序盤のタップスライドで出してしまい、やる気が一気に消え失せた。これも粘着したくない譜面。とりあえずSSS+に乗ったことは嬉しい。これで14全SSS+達成である。

ゲーセンにいる間に午後9時を迎え、AHC013が始まった。プレイの合間を縫って問題を読み、スマホから提出していた。

RECRUIT Nihonbashi Half Marathon 2022 Summer（AHC013） - AtCoder

ゲーセンが閉店した後、どこかで食事することもなくすぐ帰宅。それから次の日の昼までずっとネット小説を読んでいた。

まずなろう。午前7時に「限界超えの天賦《スキル》は、転生者にしか扱えない　ー　オーバーリミット・スキルホルダー」を読了。

https://ncode.syosetu.com/n5378gc/

非常に面白かった。以下の引用部分で言及していたものがこの作品である。

数日ほど睡眠時間を削って読みふけっていた日があったが、途中でそんなことをやっている暇はないということに気づいて、300話ほど読んだところで止まっている。
週記（2022/08/01-2022/08/07） - kotatsugameの日記

睡眠時間を削ってまで読みふけってしまったのは、途中で読むのをやめられなかったから。設定上の面白さとストーリー展開の面白さがどちらも好みだった。前者はつまり主人公のチート能力やその強さについてである。後者については、どことなく漂う不穏さが状況を否応なく先に進めていくのでグイグイ引き込まれた。

主人公の思い通りにいかない展開は主人公最強モノとはあまり両立しないように見えるし、自分でもストレス要因となってあまり好まないように思っていたが、しかしそういう展開が少し含まれていると面白さが増したと受け取るらしい。このことは「無職転生」や「ここではありふれた物語」など、自分に強い印象を残した作品に共通しているように感じられる。

今も書いたが、主人公最強モノ。個人的には2章が一番好きだった。まだあまり有名でない状態から強さを一気に見せつけるのは好みのシーンである。それが、見せつける対象を変えつつ何段階かで行われていた。

その後ハーメルンを読み、午後1時就寝。

08/10(水)

午後6時半起床、午後11時頃寝落ち、午前3時半起床、午前10時半頃寝落ち。その間はずっとハーメルンを読んでいた。

08/11(木)

午後7時起床。午後9時半にハーメルンを一つ読了。「非科学的な犯罪事件を解決するために必要なものはなんですか？」。

syosetu.org

これも非常に面白かった。普段はポンコツなのに決めるべきシーンではばっちり決める主人公が非常に格好いい。話が進むに従って主人公の能力や過去が徐々に明らかになっていき、それにつれて主人公が思ったより強いことが分かってくる。その分、最初数話は主人公が何者なのかわからず戸惑ったが、少し読み進めるとすぐ話に引き込まれた。まだ自分の想像を超えた設定があるようで、これからの展開が非常に楽しみ。

ちなみになろうのほうでも連載されている。そちらで一区切りついてから一気にハーメルンに投稿しているようなので、なろうのほうが新しい話を先に読める。

その後また別作品を読み始めたが、さすがに数日何もしていないのはまずいと思って布団から脱出し、午前3時頃から日記を書き始めた。午前9時半ごろ切り上げてまたハーメルンを読み始め、正午就寝。

08/12(金)

午後6時起床。布団でずっとラノベを読んでいた。

このままだと今日何もできずに終わってしまうなと危機感を覚え、午後9時20分から久しぶりにyukicoderのコンテストに出た。昨年の11月末以来だから、8か月ほど間が空いたらしい。

yukicoder contest 356 - yukicoder

Aはよい。Bは難しかった。最初に適当に待つことで、動き出したら取り除かれるまで止まらないと思ってよい。取り除かれるタイミングを1回目、3回目、5回目、……と固定して、後ろの駒から割り振っておく。そのタイミングで取り除かれるには何回目のタイミングから移動しなければならないか求め、もしこれが負だったら全体をその分ずらす。こうして求めた、先頭の駒が取り除かれるタイミングが答えになる。

Cは $A$ の具体的な値には興味がない。 $A_i\lt A_{i+1}$ なら $+1$ 、そうでなければ $-1$ として累積和を取り、これを折れ線だと思うと、操作は山になっている部分を谷に折り返すことに相当し、操作をし切った状態が累積和の先頭（ $0$ ）と末尾をつなぐ大きな谷として求まる。1回の操作である項だけが $-2$ されるということから、和を比較することで操作回数が求まる。

Dは、ランレングス圧縮して実験すると、2段進んだとき両端から一つずつ要素を落とした形になることが見えた。より精密に確かめるため、並んだ3個のブロック2³通りで2段進んだときを計算すると、ほとんどの場合は真ん中の要素が保存されることが分かった。しかし010の場合だけ0になってしまうらしい。よって最初の2段と、必要なら最後の1段だけを愚直に計算すればよい。

Eは手で試していると奇数桁目を全部 $1$ にしてよいことに気づいた。しかもそれを取り除いて偶数桁目だけ見ると、使える数字が $2$ 以上になった以外はほとんど同じ形の問題になっている。正確には隣り合う要素が異なる必要がないのだが、今 $N\le 500\lt 2^9$ なので気にしなくてよい。結論として、 $X_i$ は $i$ の2進数におけるtrailing zerosに $1$ 足した値となる。

Fは簡単。操作を逆順に考えることで、 $y$ が必ず $N$ の約数となるとわかる。なので約数だけ取り出すことで $y$ の値を持つdpができる。この制約なら最大で $1344$ 個なので、遷移は全部試してよい。 $a$ から $b$ に遷移する際は、 $a\mid b$ かつ $a,2a,\dots,b$ に $C$ の要素が含まれないのが条件。 $a$ を決めるループの際に $C$ から $a$ の倍数であるようなものを抜き出しておくと、後者の判定が二分探索2回で行える。 $N$ の約数のペア $(a,b)$ であって $a\mid b$ を満たすものは少なそうなので、十分高速。

Gは解けなかった。区間dpの方針で考えると、重複を省くのが難しくなる。かといって先頭から見ると、良い文字列であることがうまく判定できない。6完。

Cは $\pm 1$ にした後転倒数になっていたらしい。面白い。Fで二分探索をしていた部分は、 $C$ のうち $a$ の倍数であって最小のものを見つけるだけでよかったようだ。正直何を書いても間に合うと思っていたので、判定の高速化は全く考えなかった。

またラノベ。午前0時に1冊読了。「クラスで2番目に可愛い女の子と友だちになった」2巻。1巻がかなり好みだった記憶があるが、2巻はそれほどでもなかったと思う。1巻の内容をあらかた忘れてしまっていたのも良くない。この巻はひたすら主人公とヒロインがいちゃつく巻で、加えて主人公の家庭の問題も表出する。甘ったるいシーンは強く印象に残らないし、家庭の問題の結末も正直納得できなかった。ただ決して悪くはない。悪くはないが、1巻が好みだった分の落差があったのも確か。

別のラノベを開いてまた読みふけっていたが、午前4時半からは日記を書き始めた。

書いているうちに、先週土曜日のTCO22 Wildcardの結果が公開されていたことに気づいた。ちゃんとシステスに通って3完のまま、19位に上がってレートは2969→2934(-35)。思ったより優しい。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19337

1000点問題をupsolveした。まず先週の解法から説明しよう。memberに含まれる人のみをbitDPして残りを単に人数で管理すると書いた。memberに含まれない人数を $R$ とおく。bitDP部分が $i$ から $j$ に遷移する場合を考えてみる。ここでdp配列を $dp_{i,\ast}$ 、 $dp'_{j,\ast}$ と書く。 $dp'$ は次のdp配列になる。

まず、 $i$ と $j$ のbitwise ANDが非ゼロの場合。このとき残りの人をどのように決めても必ず条件を満たすから、 $dp'_{j,l}$ には $\binom{R}{l}\sum_k dp_{i,k}$ だけ足されることになる。 $(i,j)$ が $4^{M-R}-3^{M-R}$ 通りあるので、愚直に書くと $O((4^{M-R}-3^{M-R})\times R)$ となる。

次にそうでない場合。この場合残りの人が被るように遷移しないとならないため、 $k$ 人から $l$ 人に遷移するとき $dp'_{j,l}$ には $dp_{i,k}\times\left(\binom{R}{l}-\binom{R-k}{l}\right)$ だけ足される。 $O(3^{M-R}R^2)$ となる。

これを高速化する。まず後者について、もはや $i$ の情報は必要ないため、 $k$ 人という情報ごとに和をとって最後にまとめて遷移してもよい。これで $O(3^{M-R}R+2^{M-R}R^2)$ になる。次に前者だが、こちらは $i$ どころか $k$ の情報も必要ない。よってあらかじめ $dp_{\ast,\ast}$ の和をとっておき、そこから $i$ と $j$ のbitwise ANDがゼロの場合を取り除いたものを使えば十分である。 $O(3^{M-R}R+2^{M-R}R)$ となる。

以上で1年分の遷移が $O(3^{M-R}R+2^{M-R}R^2)$ となり、これを $Y$ 回繰り返しても余裕で通る。整理するとかなり簡単な高速化だった。コンテスト中は確か $\sum_k dp_{i,k}$ をあらかじめ持ってどうにかしようとしていたはず。後者で $i$ の情報が必要ないことに気づけなかったのだが、式を見れば明らかなので当時はかなり焦っていたのだろう。

午前8時前に布団に入った。すでに睡眠時間が6時間を切っているが、うっかりハーメルンを1作開き、話数が少なかったためそのまま最新話まで読んでしまった。「言語系チート授かったのでvtuber始めました」。

syosetu.org

特に好みではない。人に英語を教える描写など、喋れるのと教えられるのは全く違うはずとか余計なことばかり考えてしまった。異種族の言語も扱えるというのは設定として面白そうだったが、今のところこれはと思った展開はない。

午前9時半就寝。

08/13(土)

午後0時半の目覚ましで一瞬意識を取り戻したはず。その時に45分に目覚ましをかけなおしたが、そちらでは起きられなかったようだ。ふと気づくと55分だった。慌てて布団から跳ね起き、PCの前に座った。午後1時からMulti-Universities Camp 8回目。

"蔚来杯"2022牛客暑期多校训练营8_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ

12問のうち半分がsolved数2以下というかなり難しいセットだった。そんな中チームでFDHIAJの6完、2位。かなりうまくいったらしい。自分はFHAを解いた。Fは唯一の簡単枠。Aはサンプルからエスパーすると再帰的な構造が見えるので丁寧に実装。

Hは自分の好きなタイプの問題だった。32bit符号なし整数を保持できるメモリが $r[0]$ から $r[2^{10}-1]$ まで $2^{10}$ 個あるマシンを使い、制限された操作だけで加・減・乗が入り混じった数式を評価せよというもの。ただし値は32bit符号なし整数で求める。プログラム領域とデータ領域が分かれておらず、 $r[0]$ をプログラムカウンタとして $r[r[0]\bmod 2^{10}]$ を実行しながら進んでいく。

実行する値を $2^{10}$ 進数で4桁の数だと思い $abcd$ と表したとき、 $a=0,1,2,3$ に対応して4種類の操作が行える。 $a=0$ は $r[b]$ を出力して停止、 $a=1$ は $r[b]$ に入力を1文字読み込んで、読み込みに成功したら $r[0]\leftarrow r[c]$ 、失敗したら $r[0]\leftarrow r[d]$ とする。この二つは入出力なので、計算として行える操作は実質残りの二つだけになる。 $a=2$ は $r[b]\leftarrow r[b]+r[c]$ と $r[0]\leftarrow r[d]$ 。 $a=3$ は条件分岐で、 $r[b]=0$ の場合 $r[0]\leftarrow r[c]$ 、そうでない場合 $r[0]\leftarrow r[d]$ 。

数式の評価方法を丁寧に考えればすぐ解けた。実は変数を五つしか使わなくてよいため、実行する値をコード中で生成するとかアクロバットな手法は必要ない。

使う変数のうち二つは入力文字と一時変数。残りの三つを $x,y,z$ とおく。加減算で分割した項のうち現在見ているもの以外を $x$ にもち、見ている項の値を $y$ と $z$ を使って計算する。数の掛け算はできないが、1文字読んで $w$ とし、 $y\leftarrow 10y+wz$ と更新するのを繰り返すことで、 $y$ に $z$ と読んだ数を掛けた値を計算できる。+や-が来た時点で $x\leftarrow x+y,y\leftarrow 0,z\leftarrow\pm 1$ とし、*が来た場合は $z\leftarrow y,y\leftarrow 0$ とする。初期状態は $x=0,y=0,z=1$ である。

代入操作など存在しないので、いったんゼロクリアしてから足し算することになる。ゼロクリアは自分に自分を32回足すことで行えるが、わざわざ32回操作を書き並べなくとも $a=3$ の条件分岐を使ってwhileループを作れば問題ない。 $10y$ は $2\times y+2^3\times y$ として計算する。そこに $w$ 回 $z$ を足すのは愚直にループして行った。以上のアルゴリズムを丁寧に実装すればよい。操作が $r[0]\leftarrow d$ ではなく $r[0]\leftarrow r[d]$ であることに注意。

今回はコードの最後のほうにチェッカーを書いた。普段はジャッジプログラムを別に作りがちなのだが、それは面倒なだけで利点は少ない。

しばらくTLでコンテストの感想を眺めたあと、食事し、午後7時から1時間半ほど仮眠を取った。起き抜けは明らかに頭が回っておらず大変だった。何とか眠気を振り払い、午後9時からABC264。

freee Programming Contest 2022（AtCoder Beginner Contest 264） - AtCoder

今日も全部C++。Aはよい。Bは読んですぐ書き始めたものの思ったより大変だった。まず $R\ge C$ となるようにswapして下三角領域のみを考える。それをさらに二分割する必要があったため $R+C\le 16$ をチェック。真ならば $C\bmod 2$ 、偽ならば $R\bmod 2$ を見て、 $1$ の場合がblackに対応する。Cはbit全探索。Dは何も考えずにBFSした。

Eは逆から見る典型。UFで管理する集合に発電所が含まれるかのフラグを持たせたかったため、その場でUFをフルスクラッチしたら、なんとfind関数をかませ忘れるというミスを犯して1WA。どうやらまだ頭が寝ていたらしい。

Fはdpで、マス $(i,j)$ にいるとき行 $i$ をflipしたか・列 $j$ をflipしたかのフラグを持ち、 $H\times W\times 4$ 状態で計算する。例えば $(i+1,j)$ に進むとき、 $A_{i,j}$ と $A_{i+1,j}$ の値が等しいかどうかで行 $i+1$ のflip状態を行 $i$ に合わせるかどうかが決まる。それ以外の行・列は関係しない。

Gは、文字列の末尾を状態、1文字追加するのを遷移だと思うと、最長経路問題になる。符号を反転して考え、ベルマンフォード法で負閉路の存在を判定。よく考えると状態としては末尾3文字ではなく2文字しか持たなくてよいため、先頭に埋めるためのダミー文字を含めても状態数 $27^2$ 、遷移が状態ごとに $26$ 種類で十分高速。

Exは、頂点を追加するたびにその頂点を含むような完全二分木を数えることにする。まず深さ $d$ が $18$ 以上の頂点は無視してよい。なぜなら、その頂点を含むような完全二分木は頂点数が $2^{d+1}-1\ge 2^{19}-1\gt 3\times 10^5$ となるから。逆に、無視しなかった頂点の親は $d$ 個しかないため、それぞれ見て計算することが可能になる。具体的には、深さ $d'\lt d$ の親について「その頂点を根とし、深さが $d-d'$ であるような完全二分木の個数」を考える。子について同様の値の和を管理しておけば、今追加した頂点による増分を持って遡っていくことで順次求まる。

Exが12分で解けたのは我ながらかなり速かった。50分足らずで全完。しかしEの1WAが響いて2位から3位に転落し、賞金額も25000円くらい減ったように見える。残念。

Bは $\min(R,C,16-R,16-C)\bmod 2$ で判定できるが、コンテスト中の場合分けも丁寧に考えるとこの式と一致するようだ。Dは転倒数と聞いてびっくり。Eは発電所をひとまとめにするのがかなりうまいやり方に見える。ちゃんと思いついていればUFを空で書いてバグらせることもなかったかと思うと余計残念になってきた。

コードゴルフ。これはCF後に少し縮めたものも含む。A問題はVimで、全完後に22Bを書いたのだがコンテスト開始すぐにほぼ同じコードが提出されており負け。Bはdcで $\max((R-8)^2,(C-8)^2)\bmod 2$ を判定。CはRuby。 $A$ にtransposeとcombinationを2回使うことで、インデックスを使わず直接行・列を抜き出している。

Dはatcoderの文字を順に消していくと、消すときのインデックスの総和が答えになる。転倒数を求めているのと同じ。これをPerlで書いた。実際にはatcodeの6文字だけでよいこと、またatcode=~/./gとするよりa,t,c,o,d,eと直接リストを書いたほうが短くなることが短縮ポイント。EFGは手つかず。Exはコンテスト中に書いたコードがそれなりにシンプルだったので縮めてみた。RubyだとTL 3secでかなりギリギリだったのに、Perlで書くと縮んだうえ速くなった。

午後11時半からCF #813 div.2。

Dashboard - Codeforces Round #813 (Div. 2) - Codeforces

Aは先頭 $k$ 項のうち $k$ より大であるものの数が答え。Bは未証明だが $(n,n-1),(n-1,n),(n-2,n-3),(n-3,n-2),\dots$ とペアにしていくのがよさそう。出したら通った。

Cはある地点を境に左は全部 $0$ 、右は全部そのままとなる必要がある。そのような状態が可能な地点のうち最も左のものを探す。つまり、左右両方に出現する値が存在せず、また右側が単調増加になっているような地点。各数に対しそれが出現する最も左のインデックスを求めておいて、数列を右から順に見ていくことで、すべての地点に対してチェックできる。

Dは面倒だった。まず $d(u,v)=\min(\min(a_u,a_{u+1},\dots,a_v),2\times\min a)$ である。よって最小値を大きくするように変更するのがよくて、そのもとで $\max d(u,u+1)$ を計算すればよい。とりあえず小さいほうから $10^9$ に変更して、選ぶ箇所に自由度がある値は特別扱いした後、 $\max\min(a_u,a_{u+1})$ を求めた。しかしWA。

最小値を少し小さくしてでも $\min(a_u,a_{u+1})$ が大きいところを作ったほうが良いことがあると気づいて、各 $u$ についてまず $a_u,a_{u+1}\leftarrow 10^9$ とした後最小値を押し上げるケースに対応した。しかしこれもWA。 $a_u$ と $a_{u+1}$ の両方ではなく片方だけ変更するようなコードも追加したら通った。疲労困憊。

Eは難しい。 ${\rm lcm}(i,j,k)\lt i+j+k\lt 3k$ なる $(i,j,k)$ を数える。ここから ${\rm lcm}(i,j,k)=k,2k$ が得られ、 $i,j\mid 2k$ が必要。さらに ${\rm lcm}(i,j,k)=2k$ なら、つまり $i\nmid k$ または $j\nmid k$ ならば $i+j\gt k$ も必要。

E1は $j=L\dots R$ を固定した後 $j\mid 2k$ なる $k$ を列挙して解いた。 $j$ をインクリメントする前に $i=j$ とした場合の前計算をすることができる。まず $i\mid k$ かどうかで分かれ、さらに $i+j\gt k\Leftrightarrow k-i\lt j$ が必要かでも分かれるため、3種類の値を管理した。 $k-i\lt j$ という条件を扱うため、 $j$ を昇順に探索している。

E2はこれを $L=1,R=2\times 10^5$ で解きつつクエリにオフラインで答える問題。 $i=R\dots L$ と降順に見ることができれば、BITの $k$ 番目に答えを足しておいて $i=L$ となった瞬間 $[L,R]$ の区間和を取得することで解けるため、その降順に見る方法を考えなければならない。先ほどは $k-i\lt j$ を満たした瞬間に前計算の配列をインクリメントしたが、逆に $k-i\lt j$ を満たさなくなった瞬間デクリメントする手もあって、こちらだと $i$ を降順に探索できる。

Fは解けず。システスは全部通ったがDでWAを出すし遅いしで順位は散々だった。その大変だったDは二分探索できるらしい。これだと細かいことを考えなくて済むのでかなり簡単。

しばらくYouTubeを見た後午前4時から日記を書き始めた。朝方切り上げて布団に入り、2時間ほどハーメルンを読んで、午前8時半就寝。

08/14(日)

午後7時起床。今日はAGC以外のコンテストがないが、かといって直前まで寝ているのはまずいため、眠気を振り払って身を起こした。10時間以上寝たのになぜまだ眠いのか。

食事したりシャワーを浴びたりとかなりゆっくり準備を整え、午後9時を待った。

・落ち着くこと
・400点だからと適当に提出しないこと
・行き詰っていると感じたら席を立って気分を変えること
・コードをガチャガチャしないこと
・ちゃんと詰めてから書き始めること
・自分が天才であると信じること
— こたつがめ (@kotatsugame_t) 2022年8月14日

コンテスト開始は10分延期された。午後9時10分からAGC058。

AtCoder Grand Contest 058 - AtCoder

Aから躓きそうになったが、天才的な閃きが降りてきて助かった。長さ4の順列 $(P_1,P_2,P_3,P_4)$ であってすでに $P_1\lt P_2$ が満たされたものを考えると、高々1回のswapで $P_1\lt P_2\gt P_3\lt P_4$ を満たせる。順列を全部試して確かめた。この事実を用いると、最初に $P_1\lt P_2$ とした後、長さ4の連続部分列を2個ずつずらしながら揃えていくことで高々 $1+(N-1)$ 回で条件を満たせる。これをどうやって思いつくかというのは難しい話で、やはり閃いたとしか言いようがない。一応、サンプル1を見て長さ4の順列を考えたのが初手だった。ともかく解けてよかった。

Bはほぼ既出。自分が見たのはyukicoderで、特に解説がかなり綺麗だったので丸ごと記憶に残っていた。念のため正当性を確かめた後、実装。すぐ通った。コンテスト後のTLで以下の問題だったことを知った。

No.1378 Flattening - yukicoder

Cは難しかったものの考察が順調に進み、かなり気持ちよく解けた問題。ただし考察の初手には飛躍がある。というのも、なんと $1,4$ の頂点は全部葉であるとしてよいのだ。次数が2だとして、適当に繋ぎ変えることで1にできることを確かめた。例えば1頂点だけ $1$ で他全部 $2$ の場合などはこの限りではないのだが、今4種類の頂点それぞれが必ず一つ以上存在するので、そのようなコーナーケースは考えなくてよい。よくわからない制約もちゃんと使えていて、答えに近づいていることを強く実感した。

$1,4$ の頂点を全部無視したときに隣り合う $2,3$ の頂点の各ペアについて、そこを結ぶパスの長さを考える。ペアの間にある $1,4$ の頂点は、パスのどこかに接続するしかない。しかも交差してはならないため、十分な量の $2,3$ の頂点を含む必要があって、パスの長さはある数以上とわかる。この値を、ちゃんと偶奇も確かめつつ求めておいて、ぴったりその長さのパスを作るように隣り合う二つの頂点集合をマージすることを繰り返した。

最初は長さ1のパスで結べるペアを結ぶ。するとその頂点集合は長さ $1$ のパスを持つことになる。隣り合う二つの頂点集合が長さ $l$ と $r$ のパスを持ち、その間を結ぶためのパスの長さが $m$ だとすると、新しく張る辺1本を含めて $l+r+1\ge m$ の場合に結ぶことができて、マージした頂点集合には長さ $l+r-m+2$ のパスが残る。先ほど丁寧に偶奇を処理したのでここでは気にしなくてよい。すべての頂点集合をマージできるか、できたら最後に残ったパスがまだ結んでいないペアの要求を満たすかをチェック。

サンプルを合わせて出したら通った。CのACは4番目で、全体5位。Dに2時間残したことだしこれはレート爆上げか！？と思ったものの、以降はずっと椅子を温めることになった。

Dは、とりあえず文字を012に直した後インデックス $\bmod 3$ でずらしてから考察を開始した。包除原理を疑いつついろいろ見るうちに、直接求められる気になって、そこから戻ってこられなかった。A、B、C、AB、BC、CAの6種類に分けると、どれの後にどれが来てよいかというグラフが書け、それだけで可能な文字列を表せる。なのでそのグラフとずっとにらめっこしていた。個数の条件を扱えなかったので、ここで包除原理を使いどうにか制約を緩めた問題に帰着させようとしたものの、どうにもならなかった。

3完最速で42位、パフォーマンス3098、レートは2835→2864(+29)。highestを更新し、銅冠を戴いた。Dに苦しみすぎており実感は薄い。

AGC058 ooo--- 42nd
Perf : 3098
2835 -> 2864 (+29) highest

銅冠になりました pic.twitter.com/9Q4ZNPTd9c
— こたつがめ (@kotatsugame_t) 2022年8月14日

Cは、わざわざマージ条件をチェックしなくともとにかく結びまくって、最後に残ったパスの長さが正か見ればよかったらしい。これならもうちょっと速くACできただろうが、3完最速である以上速度面の改善は全く関係ない。D問題はコンテスト中の考察だとあと何時間あっても答えにはたどり着けない。

TLで感想戦を眺めたり、Dの解説を読んだりしていたら、コンテスト終了からかなり時間が経っていた。眠気が強いので日記も書かず午前4時に布団に入った。

昨晩の続きのハーメルンをしばらく読んでいたが、どうにも読みづらかったので放棄した。誰がどういう立場のキャラなのか、味方か敵なのかがわからない。原作を知らないし、本文にも特に描写されないのだ。ぬらりひょんの孫はアニメをたまに見たという記憶があるだけ。呪術廻戦に至ってはTLに流れてくるコラ画像が精一杯。

syosetu.org

別のハーメルンを開いて、こちらは非常に面白かったので一気に読み終えた。「ローカル役でしかあがれない」。主人公の能力が非常に豪快でよい。配牌が純正九蓮宝燈の人と、それと同じ種類の牌しか持たない人がいた場合、後者は何を切っても前者の役満に放銃することになる。当たり前だが実際に描かれると感動。

syosetu.org

午前8時就寝。

日記を書いていないのに4時間もハーメルンを読んでいたらしい。結局先週末のDDCC参加記もまだ書けていないし、大変。書く気はあると明言しておきたい。