05/17 (MON)
睡眠時間が短すぎて、9:00 には起きていたが半寝状態で 10:00 ぐらいまで何もしなかった。起き上がれたため、大学に向かう。 そんなんで眠すぎる故、行きの電車は何かをチェックしたり考えたりすることなくひたすら寝ていた。
大学に着くと、昨日の分の週記を書き上げて初めての週記を投稿する。妙な達成感がある。 それはそうと昼飯は月曜日のキッチンカーであるところのケイジャンビーフステーキチーズ＆ライスを食べた。寝不足には重かったが美味しかった。来週こそは写真を撮ってここに貼ろうと思う。
ゼミが始まる。この時期の月曜は B4 の輪講（例年同じやつ）なので聴きながら裏で作業したりすることが多い。 作業をしようと思ったが、今日の典型を確認していないことに気づいたので先にそちらをチェックする。
https://atcoder.jp/contests/typical90/tasks/typical90_ap
正整数 $ K $ が与えられて、10 進数での桁和が $ K $ かつ、その数そのものが $ 9 $ の倍数であり、さらに $ 0 $ を桁に含まないような整数を数え上げろ、という問題。
$ 9 $ の倍数である事と桁和が $ 9 $ の倍数である事は同値である事はあまりにも有名。というかまあ式を書けば一瞬で確認できる。 $ N $ 進数における $ N-1 $ の性質だと思う。 つまり、$ K $ が $ 9 $ の倍数でないなら答えは $ 0 $ であり、$ 9 $ の倍数ならば二つの条件は自然に満たされる。あとは $ 0 $ を含まないように整数を構成するだけだ。 これは $ 1 $ 回で $ [1,9] $ マス先に進める時の $ 0 $ マス目から $ K $ マス目までの経路数に等しい。普通に DP をするといい。更新の時に区間加算をするので高速になるが今回は遷移が多くないので愚直でも問題ない（というか $ 9 $ ならキャッシュとか考えて絶対に愚直の方が速いだろう）。理論上は線形探索は悪だが、実際はシーケンシャルな処理なので相当キャッシュとかが効いてある程度まではむしろ高速だよねという話題、あまり競技プログラミング界隈では聞かないな。
ゼミも終わり、一頻り喋ったりしたあと作業に戻る。作業の途中で典型のジャッジが来ていそうなので提出する。$ K \bmod 9 \neq 0 $ の場合に $ 0 $ を出力するのを忘れていて WA をもらう。書き直す。AC。 先週の金曜と土曜の典型をまだ書いていない。なぜなら最大流ライブラリをまだ書いていないためである。いやその理論だと土曜のは書けるな。 アルゴリズムもわかっているしなんなら空で書くことができると思うんだけど、どうせ書くなら綺麗にしたいため中々面倒くさい。
そういえば今日も途中で大学に入っているセブンへプリンを買いに行った。なんか毎週同じことをしている気がする。 大学に入ってからというもの一週間スパンでループをしているような気がする。社会にでたらもっとこれになるのかと考えたら尚更社会に出たくなくなってきた。日常に刺激がないと死んでしまうため。
ところで今作業がほぼほぼ調べ物フェーズなんだけど、全然出てこない。競プロの知見とかって死ぬほどよくヒットするけど、研究に必要な知見はゲボほど出てこなくて発狂しそうになる。 調べ物といえば先週ローカルに落とすかと言っていたチートシートはまだ落としてなくて $ \bmod $ を出すためにまたググってしまった。
なんか取れたデータが壊れていそうな気がしたが、もう燃料切れなので帰宅する。 帰宅して晩飯を食べて、もこうの最新動画を見て、ジャンプを読んだら日付変更まで 30 分を切っていた。 もこうが全然使われないポケモンを使って興奮している動画を見るのが好きなんだよな。 ジャンプは Dr. STONE でようやく千空が復活した。一言でコメントできるのが Dr. STONE ぐらいしかない。
伝説の害悪戦法「レベル1ココドラ」を完全再現してみたｗｗｗｗ【ポケモン剣盾】 - YouTube
例によって例のごとくこの時間に競プロをやろうとする。いい加減もう少しマシな時間にやる人間になりたい。 とりあえず最大流ライブラリが必要ない典型 41 の実装をすることにした。
凸包を求めるアルゴリズムを完全に忘れている。まあライブラリがあるからいいと言えばいいが、ソートして凸になるように上半分と下半分に分けて構築するだった気がする。多角形は反時計回りの順序の点の列にするため、最後の $ 2 $ 点と次に追加する点の関係がちゃんと反時計回りになっているかチェックして、なっていなかったら最後の点を削除、という操作を繰り返すと下半分が構築できる。上半分はソート逆順にやることで構築できる。最も左下と最も右上の点は絶対に凸包に入るので簡単に証明はできたはず(はず)。久々に書くと意外と面倒。自分の幾何ライブラリを見ると汚くてびっくりする。
典型 41 の解法自体は先週の週記に書いたので割愛する。今日は完全に寝不足なのでここで活動終了。
05/18 (TUE)
12:00 起床。かなり身体のダルさが取れた。今日は普通に活動ができそうだ。 正午まで寝ていたことがバレて親父がヒリついていたことを除けばかなり良い滑り出し（10 : 0 で僕が悪いのでかなりつらい）。 今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_aq
二次元グリッドが与えられる。マスの種類は '#' と '.' であり、それぞれが壁と空間。壁を通ることはできない。スタート地点とゴール地点が与えられるので、スタートからゴールまで行くとき方向転換の回数の最小値を求めよ、と言う問題。
この問題は過去に何度か見たことがある気がする。普通のグリッド上の位置の状態をさらに $ 4 $ つの向きによって分割する。これで向きが変わる遷移について $ 1 $ 、そうでない遷移について $ 0 $ に設定した最短経路問題になる。この制約ならグラフを陽に持たなければ dijkstra 法で耐えるかもしれないが、まあ 01BFS をすればいいだろう。解説のキーワードは「追加の情報が必要な場合は頂点を倍加する」みたいなのだろうか。 ケアするポイントとしては最初の移動による方向転換だろうか。自分は始点に上下左右すべてぶち込んでやった。
ここでとんでもないことに気づく。自分の 01BFS が壊れていた。具体的に実装を見ると一回到達した頂点への距離更新が行われない実装になっていた。え、これを使って問題を通したことある気がするんだけど…と思ったけど、$ 0 $ の辺を先に全て隣接リストに入れれば壊れないためだな。かなりタチが悪いバグの残り方だな。直して push や。
時系列が前後するが、実装をする前に昼食をとっていた。昨日の残り物を食した。あと食べかけのコンビーフを処理した。 実装が終わったあとは、ジャッジ来てるかなと思って確認をしたが来ていない。とりあえず週末普通に競プロに力を入れすぎたため少しピアノを弾くことにした。
3~4 時間格闘をしていた気がするが、下手くそすぎてブチ切れそうになった。才能がまるでないように感じられるデーだった。競プロや音ゲーにもたまに訪れる日が今日だったようだ。脳血管が切れそうになったので切り上げて部屋に帰ってクーラーで涼んだ。 弾くときに楽譜が暗くて見づらくならないようになどの理由から白熱灯のライトをつけるのだが、これを弾きながら浴びるとクソ暑い。その部屋のクーラーがまだ使える状態でないためうっかり溶けてバブルスライムになりそうになっていた。
ジャッジが来ているか確認した。流石に来ていた。186ms だった。dijkstra 法でやると落ちる可能性が十分ありそうだ。グラフのサイズは最大で $ 1.6 \times 10^{7} $ ぐらいあるのでまあそれはそうか。
夕食の時間になったので、夕食をとる。チーズ入りチキンカツが美味しかった。というか気づいちゃったんだけどチー牛野郎なのでチーズが好きなんだよね。
夕食の後の一時間ぐらいは Twitter を見たり、ネットサーフィンをしたりしていた。 今日の典型をグラフを陽に持って 01BFS をやるとどのぐらいなんだろうと思って試してみた。1 sec 以上かかっていた。これは dijkstra はかなり厳しいんじゃないか？
明日の 10:45 提出の小レポートがある。今週は週末を自由に過ごしすぎたため、まずはシステムに上がっている講義音声を DL して聞く必要がある。今週はすべての音声ファイルが壊れていなくて安心した。この講義は大学院の講義の癖に全然専門じゃないし、専門的なこともしないため完全に学部生時代の一般教養科目を受けるのと同じテンションで参加している。社会勉強になりますみたいな。 講義音声を聞き終わり、レポートを書いて提出する。週ごとに 400 字前後の目算がうまくなる。
CLIST を確認する。二日後にコドフォの Div.2 があるらしい。いい加減、薄橙にもどらないと恥ずかしいように思ってきた。 そのためにも精進や。とりあえず、最大流のライブラリを作って verify して典型 40 を通すことにした。もういい加減盗人をやめたい。 その理論で行くと beats もそろそろ自分で実装した方が良いかもしれない。まあそれはまた今度…
05/19 (WED)
なんか知らないうちに寝落ちをしていた。11:00 起床。朝飯代わりの何かを口に突っ込む。 少し作業らしき何かをしていたが、間もなく昼食をとることになる。親子丼を食べた。かなりおいしい。
ピアノの日なので、手ならしをするために食後は出かけるまで弾いた。今日も下手くそだ、助けてくれ。 というかそろそろ気づいちゃったけど、これ俺が下手くそなのもあるけど単純にラ・カンパネラが難しい。 完全に暇な週とかがあったらみっちり練習したいが、大学に行く日は練習ができなかったりしてかなり困難だ。
レッスンから帰ってきた。そういえば今日はバタバタしてまだ典型を見ていないことを思い出す。最大流を Ford-Fulkerson と Dinic の両方で書いてリポジトリに push する前に、今日の典型から片づけてしまおう。
https://atcoder.jp/contests/typical90/tasks/typical90_ar
今日の典型は、長さ $ N $ の整数列 $ A $ と以下のようなクエリが $ Q $ 個与えられて、それを処理しろというもの。
- $ x $ と $ y $ が与えられて、配列 $ A $ の $ x $ 番目の数と、$ y $ 番目の数をスワップする。
- 配列全体を一つ右シフトする。一番右の要素は一番左に来る。
- $ x $ が与えられて、配列 $ A $ の $ x $ 番目の数を出力する。
最近の ABC でよく見るやつだ。実際に愚直にシフトすると間に合わない (平衡二分木を貼るのもまた一興だが…)。現在のシフト幅を持ってさえいれば $ x $ 番目の要素を見つけるのは簡単である。これを管理しながらクエリを一個当たり $ O(1) $ で処理できて OK。 雑に実装すると、剰余の演算が多くなる。割り算は（ある意味で当然なのだが）他の四則演算と比べて滅茶苦茶遅い。案の定 400ms とか返ってきてワロタ。掛け算をおこな三項演算子で書きなおす。71ms になる。
このタイミングで兄が部屋に入ってきて星野源と新垣結衣の結婚ニュースを見せてきた。ワロタ。これは絶対に Twitter の人々は大騒ぎだろうと思ってみたら大分楽しい感じになっていた。星野源は前川みくP なんですよね。現場からは以上です。
最大流のライブラリの作成に戻るが、インターフェースをどうしようか迷っている。構築問題で最大流を使うときに流量とかを知らなきゃいけないと思うんだけど、そこら辺のケアが一番面倒くさい。付加的な情報を辺に載せたいことがあるため、struct Edge みたいなものをユーザ定義にする（最もベーシックなやつは用意しておく）みたいなことをするのが良いかもと思ったが、逆辺を張るのをユーザ負担にするのは結構つらそう。インターフェースのことを考えていたら頭痛くなってきた。脳死で常に復元が出来るような辺を持つことにした…。
結果的な実装としては、辺のインデックスを任意に入力することを諦めて張った順番にインデックスを振る。辺インデックスに対応する始点と隣接リスト中の位置を覚えておいた。これをすることで辺インデックスの管理はユーザ負担となるが、代わりに辺の容量と流量を変更したり取得したりするのが簡単に $ O(1) $ で実装できるのでこれを採用。よく考えると ac-library と似たようなインターフェースになっている気がする。
メモリを余計に食うような気も一瞬したが、結局インデックスを辺に載せると辺を張る際に、逆辺と併せて int $ 2 $ 個分のメモリを消費することになるが、視点と隣接リスト中の位置を覚えるのも同じ量のメモリ消費なので変わらない。
復元に使わなそうな辺にインデックスを振らないようにできるように add_edge 関数をしようかとも思ったが、わざわざそんなことを気にする方が大変そうだと思った。
間に夕食を食べたりしながら納得のいく最大流ライブラリが完成した。実は Dinic を書くのが初めてだったのだが、この実装を見て DFS 途中で抜けて途中から再開するみたいな書き方があることを知った。これからの実装方針の糧にしたい。 最小費用流のライブラリも作ろうと思ったがなぜか一般グラフの最大マッチングアルゴリズムに関するスライドを読み始めてしまう。
ふむふむなるほどと言いながら書いていたら夜中になっている。完成はしなかった。あともっと速いやつもあるらしい。いずれにしても一般グラフの最大マッチングについてまた今度にした。
05/20 (THU)
6:30 起床。起床時間の波がえぐすぎる。諸々支度をしてジャムサンドみたいなものを食して大学へ向かう。 家を出た時は全然眠くなかったのに、電車に乗っているうちにクソ眠くなってくる。最終的に典型を確認するのが億劫になるぐらい眠かった。
9:00 からのオンライン講義を受ける。眠いが、そんなに難しい内容ではないため耐えている。というか大学院の講義は意外と適当だ。 多分だけど大学院生の活動のほとんどが研究だからだろう。そんな感じで講義をそつなくこなす。 眠気もマシになってきたので、今日の典型を確認する。
https://atcoder.jp/contests/typical90/tasks/typical90_as
二次元平面上の点が $ N $ 個与えられて、$ K $ 個のグループに分ける。分けた時にグループ内の最大の $ 2 $ 点間距離を最小化せよ。距離は二乗で答えろ、という問題。
うーん、とりあえず $ N \leq 15 $ のため、全ての任意の点集合について最大の $ 2 $ 点間距離を時間内に求めることができる。 そこで bit DP をすれば $ O(K 3^{N}) $ でできそうである。具体的には、点集合ごとに取っていくことを考えて $ K $ グループ以下選んでその最遠距離の最大を求めればよく、被りのない点集合のみを選んで遷移すればこの計算量でいける。これ、間に合うのか？わからない。間に合って欲しいので考えるのをやめた。
競技プログラミングばかりやるわけにはいかないので作業をやる。全然身に入らない、眠すぎる。おかしいぐらい眠い。胃も今年度最悪のコンディションになっている。本日は営業不可能ということらしい。マジでメンタルも終了しそうになるが、人と会話して元気にはなった。ところで今日の昼はタンドリーチキン丼だった。写真を撮ることを毎度忘れる。胃が最悪なこともあって重いがうまい。
そんなこんなで何も捗らないまま家に帰って夕飯を食べる。食後も普通にボケーっとしていた。今日は 2 時間どころが 1 時間すら集中できないことが明らかなので、コドフォ Div. 2 をやらないことにした。「やらない」って宣言してからずっと「やっぱやろうかな・・・」みたいな気持ちになるの本当に勘弁してほしい。
活動が厳しい日で、書くことがあまりないため現在読んでいるマンガの話でも記録しておこうと思う。今「ハリガネサービス」と言うマンガを読んでる。バレーボールの漫画なんだけど、結構好み。作者がキャラクターを大事にする作品に弱い。構成は一般的なスポーツ漫画とそう違わないように思う。もしこの週記をを読んでいる人がいて、興味があったら是非どうぞ。
05/21 (FRI)
12:00 起床。頭はかなりスッキリした。今日は十分に活動ができそうだ。朝食を食う時間がもう残されていないのが残念だが。 昼食をとる。カレーだ。うまい。結局今週も一回も食事の写真を撮らなかった。 古畑任三郎の話などをしていた。田村正和が亡くなったのでまた再放送をやるらしいので見ようかな。
昨日の典型を通さないまま寝たため、昨日の考察の通りに $ O(K 3^{N}) $ の実装をする。怖がりなので生配列を使ったり、in-place にしてメモリ消費もできるだけ少なくしたりした。部分集合を列挙する bit のテク久々に書いた気がする。提出。AC。271ms だった。余裕じゃん。自分は結構厳しめに計算量を常々見積もってしまっている節がある。気を付けていきたい。
きよしくんのツイートを確認したら、彩色数に落ちるらしくてこれによって底が $ 2 $ になるらしいな。まあ（そもそも彩色数自体が）難しいので今はパスや。なぜならこういう問題で底の $ 2 $ と $ 3 $ の区別をつけるのは極めて難しいと思うため。
今日の典型を確認する。☆3 だ。
https://atcoder.jp/contests/typical90/tasks/typical90_at
$ 3 $ つの長さ $ N $ の非負整数列 $ A,B,C $ が与えられて、$ A_i + B_j + C_k $ が $ 46 $ の倍数になる $ (i,j,k) $ の組を数え上げろ、と言う問題。流石に見た瞬間かな。 $ 3 $ つの数列の各要素を $ 46 $ で割った余りを考えてそれぞれ分布を作る。あとはできた三つの分布を畳み込めばいい。普通に三重ループでも間に合うので今回はそれで実装した。普通に FFT を二回とかでもいいはず。早めにジャッジが来ていたので提出。AC。どうせ入力がボトルネックになって高速化を実感できないため速くはしなかった。
そういえば結局典型 40 を通していないことを思い出した。最小カットを意識する辺張りが簡単になるなぁを実感。Dinic と FordFulkerson 両方試す。それぞれ 9ms と 73ms 。Ford Fulkerson はワンチャン間に合わないかなと思ったが杞憂だった。
時計を見てゼミの直前だった。あぶね～と思ったがアウトだった。時々自分の部屋の時計は本当の時刻を示さなくなるのだが、それだった。二個時計があるのに全てが壊れるってなんや。稼働率の期待値計算壊れてないか？反省したのでちゃんとリマインダーを使うことにする。
ゼミが終わる。一般グラフの最大マッチングはとりあえず置いておき、最小費用流のライブラリを作ることにした。そもそもようやく自分のライブラリを作ろうと決心をした理由が GCJ で最小費用流が出題されたからである。自分は単純なので借り物のライブラリだと余りモチベーションが湧かないし、アルゴリズムが分かっていても具体的な実装を自分でしていないと弄れないし気持ち悪くて無理なのだ。どうしても使わなきゃいけない時のみこっそり人様のものを借りていたが、そんなんでは演習ができないため自分のものを作成することにした。あと結構大きい理由は、人のフローのライブラリって復元のためのメンバが用意されていなかったり、用意されていても自分に合わないインターフェースだったりする。ここが自分の納得のいくものにできるのは大きい。
とりあえず書き上げた。verify してない。
05/22 (SAT)
12:00 起床。最近睡眠習慣が崩壊している。体調は悪くない。朝食を軽くたべる（すぐ昼食のため）。 しかし、今日は一ミリも何をやる気も起きなかった。
ほどなくして昼食を食べる。マックを食べた。マックではいつもダブルチーズバーガーとチーズバーガーを両方たべる。トリプルチーズバーガーが常設されればこんな妖怪みたいなことしなくて済むのになあと思ったりもする。
本気でやる気が起きないのでしょうがなく蟻本でも読みなおすかと言う気持ちで、蟻本を読んで演習問題を解いたりしていた。POJ の C++ が旧石器時代なのがかなりストレスフルなことを久々に思い出した。アレ C++ じゃなくて C+ ぐらいだろ。
不機嫌な気持ちになったりしながら演習をしていて、油断して一瞬横になったのが仇となり夕飯の時間まで帰らぬ人となった。 夕飯を食べた。寝起きで食べたせいで胃が爆発しそうだ。
完全に自業自得なのだが胃にばくだんいわを抱えた状態で AISing Programming Contest 2021（AtCoder Beginner Contest 202） - AtCoder に出ることになった。脳みそ自体はそれなりに正常に動いているはずなので大丈夫だろう。
A 問題。$ 21-a-b-c $ python で送れば FA も狙えそうな問題だった。
B 問題。たまにある数字の $ 180 $ 度反転だ。幸いにもひっくり返すと Invalid になるような文字がなくリバースして $ 6 $ と $ 9 $ を入れ替えるだけ。
C 問題。ここにきて胃のばくだんいわのせいで冷静さを書いてしまう。$ i $ か $ j $ を固定すればいいのだが、脳を使わずにヒストグラムとっていじいじしてなんか合ったで提出した。$ 5 $ 分ぐらいかけた気がする。
D 問題。ばくだんいわがメガンテを唱えてしまった。マジでわからないと思い唸っていた。仕方なく a を $ 0 $、 b を $ 1 $ とみなすことで整数として扱うことができて、辞書順は普通に昇順になる。よって二分探索で桁 DP をすればよかった。実際は二項係数を使って手前から貪欲に埋めていくことができる。 ヤバすぎる。
E 問題。木のクエリと聞いて HLD を貼る準備をした。思ったより不思議な条件だなぁと思っていたが、根への最短パス上に $ U_i $ が存在するって先祖に $ U_i $ がいる、つまり $ U_i $ の部分木内ということをややこしく言っているだけだな。根への最短パスの長さが $ D_i $ と言うのも単純に深さが $ D_i $ ということである。まとめると $ U_i $ の部分木内に深さ $ D_i $ の頂点はいくつ存在するかと言う問題になり、Euler Tour と Wavelet Matrix の rank 関数で問題なく解ける。Wavelet Matrix を貼るのをやめて、vector を $ N $ 本持とうか悩んでいた時間が世界で一番無駄だった。後で Euler Tour + vector $ N $ 本をライブラリなしで書きなおしたところ普通にテキパキ書けたので、アホくさとなった。
F問題。最悪。凸包を構築しながら DP をして三角形の符号付面積の和のパリティが $ 0 $ のやつ数え上げていくのだと思った。脳が混乱して時間内に合わせることは不可能となった。こういう問題を時間内に合わせられるようになりたいな。
E までを早く解いていれば黄色になることができただろうが出来なかったため 1975 になった。ジワリジワリと近づいているが、こういうときの一回の事故はメンタルを崩壊させるためつらい。ARC 頼む。
コンテスト後 F 問題を書き続けているがサンプルすら合わない。人生が終了した。そうこうしているうちに TCO Round 2A の時間となった。
Easy。問題文が脅威的に長いし、明らかに不必要な部分が多い。open then rated でコレをやるの悪質な嫌がらせではないだろうか。最悪な気分になりながらも仕組み自体はそこそこ面白かった。証明されているけど一般に非自明に感じてしまうマジックって結構あるし、問題にできそう。
Med。大嘘を展開しており、記録するのも憚られるためノーコメントで。
うーん正直このコンテストでなくてよかったな。寝る。
05/23 (SUN)
12:00 起床。マジで起きられない病気になってしまっている。今日は活動をする。 人々がいてピアノができる雰囲気ではなかったのでパソコンでやるべきことを処理しようと思う。 始めたぐらいの時間に昼食の時間になってしまう。
昼食は確か昨日の残り物+α だったと思う。実家ぐらしなので出てくるのが有難い。喜んで残飯処理係になりまつ。 作業に戻る。しばらく作業をして、まあ日曜だしこのぐらいでいいかと言う気分になる。
競技プログラミングをすることにした。昨日の F を書いてみる。やはりサンプルすら合わない。一体どうしてだろう…これ故に赤 Diff なのだろうということを再確認しつつ、日を改めることにした。 そういえば昨日はボーっとしていて典型を見ていないことに気が付く。
https://atcoder.jp/contests/typical90/tasks/typical90_au
RGB からなる長さ $ N $ の文字列 $ S,T $ が与えられる。$ N \times N $ の表に $ S_i = T_j $ なら $ S_i $ を、そうでないなら $ S_i $ でも $ T_i $ でもない色でマス $ (i,j) $ を埋める。$ i-j = k $ のとなるような $ (i,j) $ が全て同じ色で塗られているような $ k $ を数え上げろ、と言う問題。
こういうのはとりあえず $ 0,1,2 $ に置き換えるところから始める。が、そんなにいい性質が見えてこない。$ S $ に対する $ T $ の位置が $ k $ に対応して、重なっている部分を見て色を塗るように考えられる。色 $ c $ で塗られるには $ c $ 同士か $ c $ 以外の二つの組しかないな～う～ん、なんとなく文字列アルゴリズムぽいなでもわからん～。みたいなことを一時間ぐらい考えてしまった。久々にわからない問題が来たのでワクワクしながら解説を読むことにした。
色 $ c $ に塗るためには $ c $ 以外の色が $ S $ に出現した際には、さらにもう一つ $ c $ でない色である必要がある。重なっている部分の文字の対応関係を 色→色 の写像として考えたときに全単射なので、$ S $ か $ T $ において $ c $ でない色同士を入れ替えてやれば、普通の文字列のマッチング問題として解ける。ちなみに全単射は必要条件ではなく、対応関係を二部グラフで考えたときに出次数が高々 $ 1 $ になっている方の文字列を書き換えることでマッチング問題に落ちると思う。
$ 3 $ 種類に文字列 $ T $ を変換することで文字列マッチング問題に落ちた。しかし、まだ問題は解決していなくて単純にマッチングすることを考えると効率のいいアルゴリズムでもマッチング文字列の長さの合計ぐらいの計算量がかかり今回は $ O(|T|^{2}) $ で明らかに間に合わない。よく考えるとマッチング文字列は $ S $ と $ T $ の prefix と suffix（逆も）が対応しているため、Z-Algorithm を使えば効率よくマッチングできる。解説にはローリングハッシュが書いてあったが怖いのでこちらかな？
この問題からは結構知見が得られて満足した。 色々しているうちに ARC の時間になる。
AtCoder Regular Contest 120 - AtCoder
A 問題。普通に難しい。困るも、最大値を足したら確実に最大値になるやつだということに気づいたら prefix max の寄与が $ k $ 回、それぞれの要素の寄与が等差数列になっているため累積和の累積和を前計算することで AC。
B 問題。これも難しい。作るグリッドは対称であることは間違いないな～と思って眺めていたら、$ i+j $ が等しいマスを全て同じ色にしなければならないことに気が付く。あとはちょっと場合分けして AC。
C 問題。難しい。位置と数字が大事だと気づく。目標の数字を目標の位置に入れるには 数字+位置 が同じでなければならないと気づきを得る。数字+位置 のヒストグラムが等しければあとは転倒数でできるが、重複ありで座圧と数字の変換が必要な転倒数の実装に不慣れで $ 30 $ 分近くかけた。反省。
D 問題。大きい数字から $ N $ 個をプラスに寄与させることができそうなことに気づく。しかし、何を思ったか偶奇で分けて昇順降順で対応させれば構築できると思ってしまった。これは意図通りに対応しない可能性があるだろ…コンテスト後に過ちに気づき、プラスに寄与させる数字に mark を付けて stack を用いて mark を付けているのとつけていないのを対応づけて AC。
EF は読んでいない。
明らかに本番の動きをしくじって 1955(-20) になってしまった。来週こそ黄色になる… 睡眠習慣が頭おかしいことになっているので今日こそぐっすり寝ることにした。レベルの高い睡眠をとるんだ…。
そんなで今週はうまく活動と競技プログラミングができなかった週だったように思える。 来週はもうちょっと睡眠をうまくなって活動をしようと思う。 あと来週はちゃんと昼食の写真を撮る。
P.S. ここまで書いて、金曜に書いた最小費用流の verify をしていないことに気が付いた。すみません…
