週記（2021/03/15-2021/03/21）

03/15(月)

週記を投稿してから少しハーメルンを読み、午前9時半に就寝。

午前11時、前日シャワーを浴びなかったことによる頭皮の異常なかゆみに耐え切れず、いったん起床してシャワーを浴びた。そうすると目が覚めたので、生活リズムを無理やり整えるためにも起き続けておくことにした。しかし今度は微妙な眠気でなんのやる気も起きない。

昨日のARC114Eを解いた。「各直線が使われる確率の和（+1）が全体の期待値」という考察、この一言に700点がついているという感じで、本当にすごい問題。一言聞くだけでたちどころに了解できてしまう考察なのだが、コンテスト中は解けなかった。

適当に縮めたあと、この問題では最速コードも狙ってみることにした。1からNまでの逆元を求めるのには、有名なO(N)の実装があるが、変数による剰余算や配列のシーケンシャルでないアクセスが入って遅そうに感じる。ここで\frac{1}{i}=\frac{(i-1)!}{i!}を利用してみることにした。これはO(N+log mod)だが、適当に埋め込めばlog modは消せる。しかし配列を2本使うのはやはりまずかったのか、遅くなってしまった。例えば、普通のO(N)の実装ではmod/iとmod%iが両方出てきているが、適切に最適化がかかっていれば、これはdivmod相当のことができて1回の演算でどちらも取得できる。やはり見た目よりは高速に動作するのだろう。

逆元の和を取る部分は、事前に累積和を計算しておくことで対応できる。ほかにも剰余を取る演算を引き算に直したり、入出力を自前で書いたものにして、そこそこ速そうなコードが完成した。少し提出して様子を見ると、Clangを使ったほうが速いようなので、それで提出を繰り返す。現在の最速は8msだったわけだが、数回の提出で無事7msを引き当てることに成功した。しかし別の提出について実行時間の内容を見てみたところ、7ms以上を記録したケースが1つしか存在しないものを発見した。これは6msも狙えるのでは！？となって、そこから20回弱の提出を繰り返し、なんとか6msを引き当てた。本当に運が良ければ5msも出ないことはなさそうだが、ジャッジアップデート後のAtCoderの実行時間はブレブレなので、これくらいで止めにしておこう。

atcoder.jp

C問題のコードゴルフをする。解説の式は、k=i-jと置くとこうなる。

\displaystyle N M^N-\sum_{x=1}^M\sum_{k=1}^{N-1}(N-k)(M-x)^{k-1}M^{N-k-1}

2つ目の\sumから先をWolframAlphaに投げると、うまいこと閉じた式が帰ってくる。

\displaystyle N M^N-\sum_{x=1}^M\frac{(M-x)^N-N(M-x)M^{N-1}+(N-1)M^N}{x^2}

M-xでループしたりしてみたが、結局このままのほうが短くなるようだ。N M^Nを\sumの中に入れて、

\displaystyle \sum_{x=1}^M\frac{M^{N-1}(M+Nx(x-1))-(M-x)^N}{x^2}

atcoder.jp

昨日のTROC20のC問題の解法が間違っていた。全部1のときは常にYESらしい。僕の解法（実際に試してみる）だと、少なくとも2x4の盤面でNOを出力してしまう。

そのあと、ARC114Aのコードゴルフをしたあたりで本格的に眠気が耐えられなくなり、午後6時くらいに1時間の目覚ましをかけて昼寝することにした。この目覚ましで意識を取り戻すまではよかったのだが、さらに1時間伸ばして二度寝した結果、今度の目覚ましには気づけず、日付が変わるまでぐっすり寝てしまった。

03/16(火)

午前2時半起床。あまりよろしくない生活リズム。うっかりハーメルンを読み始めてしまい、そのくせ午前7時半くらいに再度寝落ちした。次に起きたのは正午で、これはICPC 1日目の予定が始まる直前だった。ここからのことは参加記の1日目の部分に書いてある。

kotatsugame.hatenablog.com

夜作っていた2Dセグ木ライブラリについて、もう少し詳しく書いておく。これは、先週のICPCチーム練で出会った問題を解こうとしていた。

残り時間はIと格闘していた。明らかに計算量がヤバそうな解を書いてTLEを出しまくるも通らず、このタイミングで参加してきたゆきのんさんに2Dセグ木では？と言われてうしさんのライブラリをコピペしてきたが使い方がよくわからず、提出が数秒間に合わなかった。ちなみにTLEした。コンテスト後もしばらく格闘していたが、ずっとtest 5でTLEしていてつらくなったので通らないまま諦めた。

週記（2021/03/08-2021/03/14） - kotatsugameの日記

この日使っていたうしさんの2Dセグ木は、HとWが105オーダーの時に必要な箇所だけ作るタイプのセグメント木だったようだ。そうではなく、HW個ちゃんと作るタイプの2Dセグ木もあるようで、今日はこちらを実装した。dat[i][j]が、iが対応する区間の行掛けるjが対応する区間の列の値となる。演算の順番は保存できないため、可換性が要求される。1点更新と2次元区間取得はどちらもO(\log H\log W)となる。

algoogle.hadrori.jp

ここにある実装を参考にした。「単純にセグメント木を拡張したもの」とだけ書いてあったので、具体的なアルゴリズムは実装から読み解くことになったのだが、わかってしまえば確かに「単純に拡張したもの」にしか見えない。上の実装は再帰関数によるものだが、通常のセグメント木とほとんど同じロジックで非再帰にできる。結局、僕の実装では以下のようになった。ACL準拠のつもりで関数opはテンプレート引数になっている。

library/segtree_2D.cpp at master · kotatsugame/library · GitHub

これを使って、先週のICPCチーム練のIに再挑戦した。数回の挑戦の後、入力部を少し変えたら1996msで通った。

ヤバすぎ。

FastIOもライブラリ化しておこうと思ったが、設計を考えながら布団に入ったら（？）寝落ちしてしまった。午後10時だった。

03/17(水)

午前3時半起床。昨日と同じくベッドでハーメルンを読んでいたが、今日の予定は昨日よりさらに早いため、万が一にも寝落ちするとまずい。布団を出てTechFULのイベントを進めることにした。TCB34は今日から開催されている。

なんとか全完した。現時点では1位だが……。このセットだと結構ペナが出ると思うのだが、これからイベント終了までどこまで下がるのだろうか。この週記が公開される頃にはイベントが終了しているので、今回もここに解法を書いておこう。

1から5問目はよい。6問目はいくらか迷走したが、小さいほうから(K+1)/2個に1個ずつ取っていくことになる。7問目は後ろから見た。ひたすら面倒。8問目はすべての問題の中で最も簡単だが、セグメント木を使うという1点からここに配置するしかなかったのだろう。9問目は、絶対値をmaxに言い換えて左から見たセグ木と右から見たセグ木で別々に持つ。頭がなかったので1WA。

10問目は問題名を見た瞬間からbinary trieを使うのだろうとは思っていて、事前に準備しておくつもりだったが、9問目でWAを出したのでヤケクソになって突撃。見た瞬間binary trie+Mo's algorithmのO(\sqrt{N}(N+Q)\log \max X)が思い浮かんで、それ以外の方法が全然わからなかったので、書いた。最初に提出したものは初期化ミスで全ケースWAだった。2回目に提出したものはTLE。ここで、Mo's algorithmの影響で同じ値を何度もbinary trieに出し入れしているため、アクセスするノードを前計算しておくことにすると、最遅ケースで3.5secになり、通った。

かなりつらい。TechFULのジャッジは弱い、というのはわかっていたので、最初からできるだけの高速化をしておけと言われればその通りなのだが……。もうちょっとオーダーの良い解法があるのだろうか。ほかの人がどうやって解いたのか知りたい。

これをきっかけとしてbinary trieのライブラリを作ることにした。bit幅をテンプレート引数で受け取るようにする。keyを表す型は、unsigned long long固定ではなく、bit幅に応じてunsigned intと切り替えて使い分けるようにしたいが、このようなことは可能だろうか？TLに質問を投げたところ、えびちゃんさんからconditionalというものを教えてもらった。C++11かららしい。

std::conditional - cppreference.com

これを使って少し書いていたら、ICPCの2日目が始まった。コンテストとそのあとの懇親会については参加記の2日目の部分に書いておいた。昨日の日記にもリンクを貼ったが、ここにも貼っておこう。

kotatsugame.hatenablog.com

そういえば、昨日の夜格闘していたICPC練のI問題についてだが、こるとんさんのチームも最近同じセットを走ったようなので、懇親会で聞いてみたのだった。どうやらlog 1つの解法があって、ただ2Dセグ木によるlog 2つでも通らないことはないだろう、というコメントがkoosagaから出ていたらしい。

夜、参加記を書いていたが、こどふぉが始まっていたことに気づいたのでなんとなく参加した。CF #708 Div.2である。途中から眠気がすごくて大変なことになったが、何とか全完した。

Aから面倒だが、適当にやってよさそう。Bは2WAしてキレそうになったが、よく見ると(M+1)/2であるべきところがM/2になっていた。最初のWAのあと、この部分も確認したはずなのだが……。このあたりで自分が思ったより疲れていることを自覚した。C1は気合いで場合分けしたらできた。C2も気合いで場合分けしそうになったが、ふと、3個残して他を全部1にするとC1に帰着できることに気づいた。TLでは面白い問題であると評価されていたが、確かに、誘導としてのC1がないとハマってしまったかもしれない。

この時点でDはsolvedが2人とかだったので飛ばし、E1に行った。E1は自明。その後Dに戻った。メモリ制限が厳しいタイプの問題のようだ。dpをするとき、配列を使いまわすことで次元を1つ減らすテクを使えば、この制限自体は簡単にクリアできそうな気がする。適当に書いたらサンプルが合わなかったが、よく見るとサンプルの出力と説明に書いてある値が異なっている。説明を信じることにすれば、僕の出力は正しいようだったので、提出してみたところ、1ケース目のサンプルで落ちてしまった。これはペナルティに含まれないはずなので、まあよい。サンプルを合わせて再度提出すると、今度は4ケース目でWAが出た。これの解消には非常に苦しんだが、試行錯誤の過程でセグメント木を使用する必要がないことに気付いたため、実行時間が大幅に短くなったのはよかった。眠気に抗いながら考えて、何とかHackケースを見つけることができてAC。メモリも実行時間も申し分ない。

E2はかなり速く解法にたどり着くことができたが、コーディングも終盤に差し掛かったあたりでふと残り時間を見ると、コンテストがあと2分くらいになっていて非常に焦った。急いで書き上げてサンプルを確認し提出したところ、残り時間が増えてびっくり。これは、途中でコンテストが15分伸びたのに、ページをリロードしなかったせいで起こった勘違いだったようだ。

コンテストが終わってから再度参加記を書く作業に戻り、午前2時半に投稿。午前3時就寝。

03/18(木)

午後2時起床。

懇親会でkotamanegi氏に聞いてみたところ、似たような問題設定を考えていたこと、またこのような問題設定が好きであるからC問題に手を付けたと言っていた。僕も同様に、このような問題設定（または問題名「Short Coding」）に好奇心を刺激されたので手を付けた。確かに問題の見た目的に重そうではあるものの、この問題に興味を持つようなチームが2つも存在してしまった、というのがbeet_aizu氏の戦略がうまくいかなかった原因だったのだろう。そうでなければ後回しにすべき問題に見える、というのには頷ける。

ベッドの上から動かないまま寝たりなろうを読んだりしていたら、午後9時半になってしまった。起きて食事。今日は板チョコレート。そのあと、しばらく自分の本名で検索して遊んでいた。自分の本名というのは検索してはいけないワードとしてよく挙げられるものであるが、僕の場合はマイナスイメージのあるような検索結果が出ないため、かなり気軽に検索できる。

Twitter Web Appのフォローボタンが、これまでは未フォロー⇔白だったのに、既フォロー⇔白になっていた。なんで色を、よりにもよって真逆にしてしまったのか。全然慣れない。

ECR106があったので出た。4完、5完時点では1位だったが、Fに手間取って4位。Gは手も足も出なかったのでなろうを読んでいた。

Aはよい。Bは、最も右にある00と最も左にある11のインデックスを比較した。Cは何回曲がるかを全探索すればよい。

Dはちょっと難しい。数aとbに対し、g=\gcd(a,b)、a'=\frac{a}{g}、b'=\frac{b}{g}とおくと、ca'b'g-dg=xが得られる。よってa'b'=\frac{x/g+d}{c}。gを決め打ったとき、左辺の2数は互いに素であればよいため、右辺の素因数を（指数ごと）a'とb'のどちらに振り分けるか？という問題になる。さすがに毎回素因数分解していては間に合わないだろうから、素因数の種類数を2\times 10^7まで求めておくことにした。gはxの約数を全探索するが、まあこれくらいなら制限時間に収まるだろう。実際収まったが、前計算に800ms使っているのでちょっとひやひやしていた。

Eはパッと見難しいが、初期値としていろんなところに1を入れたdp配列でdpすると求まる。片方の文字列の長さが0になってしまうケースは、dp遷移で排除できなさそうなので、別個に計算して引いておいた。Fは木DP。部分木に対して、その根からたどれる一番深い頂点の深さをkeyにして場合の数を数え、直径がkを超えないようにマージしていく。深さk/2以下はいくつでもマージしていいので一気に計算して、k/2より深い場合は、その深さを達成する子（これは全部試す）とそれ以外の子に分けて計算する。mod上の除算が必要になって、間に合うだろうと適当に出したらTLEしてしまった。ちゃんと左と右から累積積を持つことでAC。

Gは、そもそもクエリ形式になる前の最初の問題すら解けなかったが、本当に有名問題だったらしい。

noimi.hatenablog.com

結局、パスの端点がユニークで、パスに含まれる辺が交互に塗られていればよいはずだ。パスの端点のユニーク性については被ったら適当に繋げればよくて、hash全部の和と現在答えに足されているhashだけの和を持てば色のflipができる。パスを閉じてループにするような辺を追加するときだけ、パス全体を取り除いてしまうことにする。復元も難しいが、頂点ではなく辺に対してそれに繋がる辺番号を持たせておけばよい。微妙なミスでWAを出して原因の原因の原因を特定するのに非常に苦労したが、なんとか通った。重いのは出力を毎回flushしているから。

https://codeforces.com/contest/1499/submission/110399277

ゴミ出しをし、布団に入ってなろうを読んでいた。午前9時半就寝。

03/19(金)

午後3時、学生支援課活動支援係からの電話に気づいて起床。どうやら部員名簿にある人数と別の書類に書かれた人数に大きな隔たりがあるらしい。今現在の部員名簿を再度提出することになった。

昨日から読んでいた「奇運のファンタジア」の最新話に追いついた。

https://ncode.syosetu.com/n8357fd/

天才経営者、とか大企業に成長、とか書いてあったので、法人としてのチートみたいなことを期待して読んだのだが、個人のチートに重きを置かれていてちょっと見込み違い。ただ、丁寧なテンプレ展開で非常に心地よく読める作品だった。

そのまま午後5時半に寝落ちして、次に起きたのが午前2時だった。昼間受けた電話で、活動支援係の方に、夜のうちに書類を出しますと言っていたのだが、すでに夜中になってしまっている。慌てて作成を始める。

部員名簿は新歓期間の終了時に更新したものを作ったはずだが……とサークルのGoogle Driveを探して、12/26に作成した書類を発見した。これにはちゃんと正しい人数が記載されているように見える。この日の日記にも次のように書かれている。

今年度の新歓期間は12月の半ばまであったが、それが終了したので、サークルの名簿などに更新がある場合報告せよとのメールが来ていた。名簿を更新して提出した。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

しかし、いざ送信済みメールを探してみると、提出のメールがない。どうやら作成だけして提出をすっかり忘れていたらしいことが分かった。これはひどい失敗だ。なぜこのようなことが起こったのかさっぱりわからないので、再発防止策も取れない。とりあえず、今年に入ってから入部してくださった2名の新入部員をさらに付け足して提出しておいた。

寝ている間に行われたyukicoderの問題を解く。A、Bはよい。Cは面倒だが、まあやればできる。Dはタグに尺取り法と見えてしまったが、これは設定でゆるふわモードにしているからで、変える気はない。E以降はsolved数が少ないので止めておくことにした。

水曜日にちょっと書いてから放置されていたbinary trieを完成させた。ほかの人のライブラリを参考に、適当に必要そうな機能を盛り込んでおいた。binary trieに限らずtrie木一般に、子のノードをポインタで持つ実装をよく見るが、Library-CheckerのSet Xor-Minではvectorとそのインデックスで持つ実装のほうが速かったので、そちらを採用した。trie木だけのシンプルなコードのためvectorのメモリ空間の再確保が行われないから速い、というだけかもしれない。

library/binarytrie.cpp at master · kotatsugame/library · GitHub

さらにFastIOを作った。

library/FastIO.cpp at master · kotatsugame/library · GitHub

いろいろ仮定してできるだけ速くなりそうな書き方をしている。例えば、空白や改行が2つ以上連続したりすればそれだけで壊れてしまうし、数値の途中に変な文字が紛れ込んでいても気づけないかもしれない。わざわざFastIOを使うのだから、どうせオンラインジャッジ上で正しい入力のときだけ動けばよくて、それより余計な比較などをできるだけ省こうという算段だ。設計はclayのものを大いに参考にした。

布団でなろうを読む。いろいろな作品の冒頭だけ読んで投げ出すということを繰り返していた。1作、面白いと感じるものを見つけて読了した。「異世界で美少女になった俺、地球に戻れたので裏垢やってみる。」。

https://ncode.syosetu.com/n6063gu/

ABCに向けて、さすがに寝ないとまずい。午後3時半就寝。

03/20(土)

午後6時、地震で起床。頭の真上にあるエアコンを見て、これが落ちてきたらまずいな、と思ってベッドの足元のほうに避難し、布団を引っ被って揺れが収まるのを待っていた。前回の地震の際、本棚に取り付けてある突っ張り棒のゆるみに気づいて直していたおかげか、今回は特に本が落ちてきそうになることはなかった。

机の下にもぐっていると、本棚がグラグラ揺れているのに気づき、思わず押さえに行ってしまった。

週記（2021/02/08-2020/02/14） - kotatsugameの日記

宮城県の沿岸部に津波注意報が出たらしいが、おそらく自分が今住んでいる場所は沿岸部ではないだろうと考えて、そのまま二度寝した。さすがに眠すぎた。

午後7時から30分おきの目覚ましを聞きつつ、午後8時半起床。ギリギリまで寝られたので良かった。部屋の中を確認したが、モニターがずれているくらいで特に地震の影響はないようだった。

食事してABC196に参加した。全完18位だった。A、Bはよい。Cも全探索してよい。Dは、一行持つbitDPを書いたのだが、うっかり4Wくらいの計算回数になってしまってTLEした。1行の場合がまずいので、1行目だけ見なくてもよいとわかる部分を見ない3WにしてAC。Eは適当に関数合成。Fはこれ↓で、(a-b)^2を展開した。解説によれば、a xor bをa(1-b)+(1-a)bと式変形できるらしい。僕の解法は2乗の項の処理がちょっと面倒。

?（任意の1文字）を含む文字列のマッチングがFFTでできるという話を覚えていたので、試した。?を0に、その他の文字をユニークな正整数に対応させて、Σ_{i-j=k}a_ib_j(a_i-b_j)^2を計算する。

週記（2020/11/30-2020/12/06） - kotatsugameの日記

コードゴルフをする。A問題は、まずbashで解いて、全完後にAWKで書くと縮むことに気づいた。そのあと、この日記を書いている間にさらにAWKで縮められていた。getlineを使う発想が出てきた試しがない。実際に書いたことがないため、どのようなときに縮むのか？という嗅覚が育っていないのだろう。B問題はsedだと思っていたがVimに負けた。7Bの解は、削除しようとしたときに何も削除しなかったらレジスタの状態が変わらないのを利用していて面白いと感じられたが、普通にdwで取れたようだ。6B。7Bの面白さに夢中になっていて気づけなかった。C問題はAWKが短いと思ったらdcに負けた。同じくdcで取り返したところ、等号付き不等号の等号が外せたらしく、再度取られた。26B。これも単純なミスで非常に悔しい。

DEFはRuby。Dは判定方法が面白い。畳が覆う2マスの番号をペアにしてリストアップしておき、そこからA個取り出し、覆うマスに重複がないか見る。これはCythonの判定方法を移植しただけ。なぜコードゴルフにおいて頑なにPython系の言語を使おうとするのか……。Eは、clampのLとRをリストで持つと覿面に短くなった。clampに渡すときはsplat演算子で一発だし、更新のときもLとRは同じ処理なのでmap!でできる。Fは嘘bitset解法が通る間に縮めておいた。

今回は僕がやってることで、僕からすればデメリットが一切なくてただ嬉しいだけだったが、ほかの人がこれをやってるのを僕が見ると、ちょっとどころではなくモヤモヤしてしまうだろう。より一般に、八百長コードゴルフみたいなことをしたくないという僕のささやかなプライドが理由となり、今後も僕がAtCoderで作問作業に関わることはない。

布団でハーメルンを読もうとしたら素早く寝落ちした。午前8時半。

03/21(日)

午後2時、目を覚ます。寝落ちする前に読んでいたハーメルンを開いてしまい、そのままずっと読み続けていた。全体の話数の半分くらいで本編が終了し、残りは番外編という位置づけであることがタイトルからわかる。とりあえず本編終了まで流し読みしたが、求めていたものとは違った。

syosetu.org

「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」というなろうに似た作品を読みたいと思い、「財閥」というキーワードで検索して出てきた作品。実際にある架空の財閥の栄枯盛衰を描く話なのだが、物語というよりかは資料という側面が強いように感じられた。さすがにそういう設定だけ食べて生きていけるほど鍛えられてはいない……。

午後4時、さすがにもう少し寝ておかないとまずいという気持ちになったので、寝た。午後5時半から30分おきの目覚ましがかかっていて、午後7時のもので何とか起床に成功。コンビニに出かけて食事を買おうとしたが、時間帯の問題かかなり売り切れていてびっくりした。食べてしばらくするとARC115。

ARC115はギリギリ5完でパフォーマンス2628、レートは2665→2662(-3)。世知辛い。

Aから難しいが、しばらく考えていると、なんとなく__builtin_parityが異なるペアを数えればよさそうというのがわかってくる。これは頑張れば証明できそうだが、どうにも焦って頭が回らないので、提出することにした。AC。BはTakahashi's Information。Cはよくわからないが、ある数がxと決定した時にそれの倍数すべてにmax(*,x+1)を作用させたら通った。この時点で15分。

atcoder.jp

Dは難しい。45分考えてちっとも進まなかったので、Eに飛んだ。Eは、まず109要素のdp配列を考えてみると、おおよそdp<-sum(dp)-dpのような遷移をすることがわかる。Aの値によってdp配列の後ろの要素が増えたり減ったりするが、ある程度の区間は常に同じ値になる。これを区間ごとにシミュレートすればよい、ということまではすぐわかった。実はこれは一次関数が作用素の遅延セグメント木に言い換えられるようだが、コンテスト中は思いつかず、必死にstackをいじって値を合わせようと格闘していた。改めて思い返してみれば、一番最初だけsum(dp)の代わりに1を使わなければいけないことにハマっていたのだろうと思える。符号を交互に切り替えて足す操作を累積和で再現するのは最初から上手くいっていたが、左端のoff-by-oneエラーに苦しめられた。40分くらいかけて何とか合わせたら通った。残り20分。Dに戻る。

閉路の個数に着目すべきだと考えた。極小な閉路（これにはサイクル基底という用語があるようだ）の個数を使って云々、を考えていたが、全探索するコードの出力と考えている結果がどうにも合わない。もう少し単純なグラフの出力を観察してみようとしていくらか試していると、どうやら、すでに連結な頂点同士を結ぶ辺を追加すると値が2倍されるらしいということが分かってきた。いったんこれを認めることにすると、あとは森に対する答えがわかればよい。パスの長さを変えて観察していたが、ここで閃く。6頂点のパスと6頂点の木を与えてみると、どちらも出力が同じであることが分かった。木なら頂点数だけから答えがわかるようだ。どうやって答えを計算するのかも少し悩んだが、少し考えると頂点のうちいくつか選ぶ組み合わせの個数であることに気づく。ここまでわかった段階で、さかのぼって実験で確かめたいくつかの事実の確からしさというものが上昇したのを感じられた。もう時間もないので証明は一切考えずそのまま書くことにする。

UFで連結成分のサイズと全域森に含まれない辺の本数を数える。連結成分ごとに組み合わせの値を記録した数列を作って、全部を畳み込みで掛け合わせ、さらに要素を2の何乗倍かする。サンプル2が合わなくて焦ったが、偶数インデックスだけ抜き出した列を計算していたせいで出力するときのアクセス箇所がずれていたようだ。何とか修正して投げるとACした。残り1分もなかった。

残り20分で3完から5完まで駆け上ったはいいものの、レートを上げるには遅すぎたらしい。自分はDで45分間何をしていたのだろうか。こういうところで詰まるとダメなんだなあ。また、D問題は自前のUFとACLのmodint/convolutionを併用したので、oj-bundleで展開した後さらにACLをincludeパスに含めるという手間がかかってかなり焦ってしまった。こういうのも一発でできるようにしておきたいが、さておき常にACLをincludeパスに含めるとCFなどでもそのまま提出してしまいそうで怖い。oj-bundleでACLも展開しようとすると、include"atcoder/*.hpp"などとhppを付けたりダブルクォーテーションで書かなければならないようで、ちょっと面倒。

ARCの直後にCF 709 div.1があったので出た。3完270位で2744→2649(-95)。これはひどい。

Aは可能な日が少ない友人から一気に割り当てていったらWA。可能な日が最も多い友人について、ほかの友人が可能でない日から先に(m+1)/2日割り当てると通った。可能な友人が最も少ない日から貪欲に割り当ててもよかったようだ。Bはqueueと双方向リストでシミュレート。これも最後のほうの処理でミスして1WA。Cはセグメント木を書きそうになったが、区間クエリの右端が必ず全体の右端なので、priority_queueで書ける。値のほうを優先度にして持つpriority_queueも作っておいて、消えた要素は適宜インデックスに対するフラグを立てて読み飛ばせばよい。

Dは、3つ組(u,v,l)について、コストcの辺u->wを使って(w,v,l-c)に書き換えるという操作を何度も繰り返せばよいと考えた。当然vのほうからも縮めていく。lの大きいものから順に更新していきたいのでpriority_queueで見ていく。……ところがMLEしてしまった。priority_queueに入る要素数が多すぎるのだろうか。しばらく試しても通らなかったので、優先度書き換えできるとよいと考え、えびちゃんさんの記事からFibonacciヒープを盗んできて貼り付けてみた。今度はTLEした。本当に絶望。そのまま通らずにコンテスト終了。

rsk0315.hatenablog.com

TCB34が終了した。6位だった。1位は理論値らしい。このセットで理論値出すのはさすがにヤバい。埋められない差を感じてしまう。10問目のbinary trie+Mo's algorithmは、考えたもののTLEしたので諦めたという人がいくらか見られた。もっとちゃんとした解法があるらしい。1つだけTLで見たのは、使える魔法の区間の右端でソートして、左端についてはbinary trieで条件を満たすような魔法のインデックスの最小値を求めて比較することで判定する、というもの。これは非常に面白く感じられる。binary trieというのはつまるところ必要な箇所しか作らないセグメント木であると見れて、そのとき当然区間minクエリに答えられるし、さらに全体にxorできる性質も変わらない。

ARCのコードゴルフをした。AはPerlでy/1//&1がいい感じ。Bはよくわからないが、とりあえずOctaveで解いておいた。Cは1 2 2 3 3 3 3 4...という出力をする解法が天才的。Rakuでmsbを使う。Eはぽかーん懐古DPさんの解が強い。僕のコンテスト中のACコードから頑張って変形してみたが、今何イテレーション目かによって答えの符号を変えることで累積和を単純なものに落とし込めるようで、そこからさらに和の取り方を変えると、区間の両端を持たなくてよくなったり累積和がいらなくなってpopしたstackの要素を足し合わせればよくなったりする。