07/04(月)

午後0時半の目覚ましで意識を取り戻し、眠気と戦って午後1時少し前に布団から脱出。

直後からミーティング。寝ぼけて開口一番の挨拶を「お疲れ様です」ではなく「おはようございます」にしてしまったが、笑って流していただいた。その後は普通に進んでいった。今日はメンターの方ともう一人とのミーティングで、そのもう一人の方が先に退出されてからも最近ご無沙汰していた1on1っぽく追加でいくらか話していた。あまりやることがないのでタスクをくださいということを伝えた。これまでやっていたことが一旦落ち着いており、しかもそこから大きな進展が見込める状態にはまだない。これは僕の問題ではない。午後2時半に終了。

ABC256の総合10位、学生5位の賞金でアマギフが一万円×2届いていた。ここ最近のABCでは結構Exが解けており賞金付きの回も多いため、かなり稼がせてもらっている。ついにギフト券残高が30万を突破した。もともとほとんどネットショッピングをしないため増える一方。

購買に行こうとしたが雨が降っていたため取りやめ、冷凍弁当を食べてからゲーム理論の課題に手を付けた。今週の課題は普段と比べ少し計算量が多かったように感じ、大変だった。先週以下のようなことを書いたが、今週はゲームの一部始終を考察するため、まさに表を埋めるような勢いだった。ゲームの種類が違うため一概には言えないのだが。

今週の課題も簡単で、定義に従って計算するだけ。ただ戦略形ゲームの表を埋めようとしたらこの計算をあと15回繰り返さなければならないので、ちょうどよい難易度の問題がなかったのかなと思ったりした。
週記（2022/06/27-2022/07/03） - kotatsugameの日記

午後4時半からインターン先定例会。今週発表する成果は昼のミーティングと、あとは先週の定例会後に少しだけ考察したのを思い出してそれを入れておいた。細かく書いたらそれなりの分量になってくれて安堵。

勉強会は双対について。いわゆる高度典型だと認識していて、いつか勉強しなければと思いつつずっとスルーしてきた話題。ところがつい最近CGR21-Gで出題されて、ついに自分の手が届く、あるいは届かせなければならないところに出てきた矢先だったため、大変タイムリーな発表だった。内容は軽め。最後に牛ゲーの双対を取って確かに最短路問題になっていることを確認したが、不等式だけ見ればすぐわかるのに双対を取った後だと式の解釈を結構頑張る必要があってかなり大変。その分、最後に綺麗にまとまったのは面白かった。

https://codeforces.com/contest/1696/problem/G

終わってから先週の週記を完成させにかかる。先週末はコンテストが少なかったため夜中のCFの前に校閲まで終えられるだろうと予想していたのだが、結局土日分に目を通す時間はなかった。いったん投稿し、午後11時半からCF #804 div.2に出た。

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

Aはまず偶数なら $n/2,n/2,0$ でよい。もしかして奇数ならできないのでは？と思い $(a\oplus b)+(b\oplus c)+(a\oplus c)$ の最下位ビットを確かめてみると、確かに常に $0$ になっていることが分かった。Bは、サンプル1の出力例がかなりそれっぽい構成をしているな……と思いつつ左上から埋めてみると、サンプル1を素直に拡張した模様が表れて拍子抜け。 $n,m$ は偶数なので、これでよいと分かった。

Cは解法はすぐなのに合わせるのになぜか時間がかかった。まず $0$ の位置が決定する。次に $1$ の位置も決定して、同時に $a$ において $0$ と $1$ の間にある $2,3,\dots$ が $b$ でも $0$ と $1$ の間になければならないと決まる。以降同様に、現在見ている区間に入っていない最も小さい数を含むように区間を伸ばして、その時新たに含まれるようになった連続する数たちを区間内のどこかに配置することを繰り返せばよい。

Dは難しかった。まず、ある区間を操作で完全に消せる条件は「長さが偶数かつ最頻値が全体の半分以下」である。証明は帰納法で簡単。 $O(n^2)$ かけることで消せる区間が全列挙できるので、これを使って、残す数を決め打った時最大何個残せるかでdpしたくなる。これは $O(n^3)$ なので間に合わない。残す数が必ず全体の最頻値であると思いそうになるが、サンプルで落ちる。

ここで、すべての数に対して先のdpを同時に計算することを考える。こんなことがなぜ可能かというと、 $a_i$ を見ているとき、これを残す場合は $a_i$ に関係する部分のみ更新すればよいし、ここからスタートする区間を消す場合は直前の要素を残していると考えてよいため、 $a_{i-1}$ （ただし $i=1$ のときは全部）に関係する部分のみ更新すればよいからである。隣接する区間をそれぞれ消せるなら、それらをまとめて消すこともできるのだ。よって $O(n^2)$ 状態のdpでありつつ遷移も合計 $O(n^2)$ になり、間に合う。

Eは解けず。素因数分解したものをmultisetに入れて、先頭から2個ずつ積にしてまたmultisetに戻すことを繰り返せば、分解後としてありうる最小値と最大値の組が全列挙できると思っており、WA。その後これではいけないことに感づき、代わりにそういうものを全部前計算するようにしたところ、MLEした。

ここでコンテスト終了。4完で74位と久しぶりに見るひどい順位を取ってしまった。普通にDすら遅かったのは反省。

とりあえず先週の週記の校閲を済ませ、更新。その後Eを解説を読んでupsolveした。MLEしてしまった前計算だが、各数についてその約数を全探索し、それらで割った数から今見ている数へ遷移してくるようなdpを考えるのは正しかったようだ。ただ、何個に分解したときどうなるかという的外れなことを考えていたので先に進めなかった。

最小値を決め打つことにして $L+1$ から $L$ に緩めたとき、分解後の最大値としてありうる最小値が変化しうるのは $L$ の倍数だけ、というのは結構びっくりした。コンテスト中はそもそも最小値（あるいは最大値）を最初に決め打つことを全然考えなかったため、その先の考察に衝撃を受けるのもやむなし。 $L$ を含むような形に分解しないほうが良いこともあるというのに気づかず、つまり遷移してきたdpの値をminも取らずに直接代入してしまって、2回ほどWAを出した。

少しコードゴルフしてから午前4時半に布団に。ネット小説の更新を確認していたら寝落ちした。午前5時半ごろだった。

07/05(火)

午後5時起床。もっと寝ようかどうしようか迷いながらYouTubeを見ていた。午後6時半に布団から脱出。今日も天気が悪いようなので、学食には行かないことにした。

面白いコードゴルフの更新が流れてきた。素直に感動。以前の最短コードではa b cという文字列をVimで編集してa*_1**5+_1*b>-cにしていた。ところがこの問題、制約に $-10^9\le c\le 10^9$ とあるものの、実は $f(1)=a+b+c\lt 0$ より $c\lt -(a+b)\lt 0$ であり、従ってa*_1**5+_1*b c>0という文字列を作ればcの負号が二項演算子として解釈されて上の式と同等になる。アハ体験。

atcoder.jp

課題に取り組む。まず離散数学。第11回目のこれが最後の課題になるらしい。課題は各回 $5$ 点満点で評価されており、その和を $a$ 、期末レポートの点数を $b$ としたとき、この講義の成績は $\min(a+\max(a,b),100)$ で定められる。これまで10回の課題を終え、初回提出期限に間に合わず $-2$ 点された以外は満点を保ってきたので、今のところ $a=48$ を確保している。ということで今回 $2$ 点確保すれば期末レポートを前にゴールインできる、が、ギリギリを攻める趣味もないためちゃんと全部解こう。

……と思ったら、最終問題がかなり難しかった。 $\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}$ が加算集合であることを（全単射を構成して）示せという問題。縦横に並べて斜めに辿るものが有名だが、ヒントに $h:\mathbb{Z}_{\gt 0}\times\mathbb{Z}_{\gt 0}\rightarrow\mathbb{Z}_{\gt 0};(m,n)\mapsto 2^{f(m)}g(n)$ という形で構成してみよと書いてあってたまげた。

しばらく考えて、ようやく素因数分解した後の素数を一つずつずらすような写像のことを言っていると気づいた。 $(9,2^3\times 3^2\times 7^1)\mapsto 2^{9-1}\times 3^3\times 5^2\times 11^1$ のような感じ。これを頑張って記述する。言葉で言うだけなら簡単だが書くのはかなり面倒だった。そもそもこういうことをするためにはまず素数を一つずつ全て並べた無限長の列が必要。まあそれはいいのか？一応そのような列の存在も具体的に構成することで示しておいた。

07/21追記：もっと簡単なものがあったらしい。賢しらに無限長の列云々など言い出してしまって恥ずかしい。

解答はg(n)=2n−1g(n)=2n−1だった。目から鱗。特に自分の作ったggがただ複雑なだけのZ>0→Z>0∖2Z>0Z>0→Z>0∖2Z>0であるということは、冷静になると当たり前なのだが、見た目からはすぐにはわからないと感じている。
週記（2022/07/11-2022/07/17） - kotatsugameの日記

主に最終問題のせいで3時間ほどかかった。何とか提出し、次にハードウエア基礎。組み合わせ回路が与えられるので、すべての信号線について単一縮退故障を検出できるような必要最小限の入力パターンを求めよという問題だった。講義スライドでは1本の信号線に対してそこの故障を検出できる入力パターンを列挙していたので、これを11本すべてに対して行うことにした。非常に面倒だった。そもそも入力パターンが2³通りしかないのだから、そちらから攻める方法もありそうなものだが、知らないのでしょうがない。

そのようにして列挙した入力パターンの集合が、11本の信号線それぞれ、0縮退故障と1縮退故障で都合22個ある。2³通りの入力パターンの部分集合であってそれらのどの集合とも共通部分が空にならないようなもののうち、サイズが最小のものを求めよという問題になった。えっ！手で最小頂点被覆問題を！？と思ったが、冷静に確認するとサイズ1の集合がいくつかあったためそれらをまず選び、残りは1パターンでカバーできたので、難しくはなかった。日付が変わる前くらいに提出。

疲れ果ててしばらくTLを眺めてからシャワーを浴び、インターンのコーディングを少し行った。以前書いたコードで、ほぼ等価なものがライブラリで用意されている部分があったので、それに置き換えることで高速化を図ろうとした。しかし実は他の部分の実行時間が支配的すぎたらしく、計測しても全然違いが出なかった。まあコードがシンプルになったのは確かだし、と言い訳してプルリクを作った。

ラノベを読み始めた。途中結構な時間をYouTubeに吸い取られ、午前11時前に1冊読了。「最強魔法師の隠遁計画」15巻。面白かった。帯にこの巻で今進行している話が一段落すると書いてあったので、前半の苦しいシーンもすぐ後で全部解決されると思えば耐えられた。ラノベ読者にはストレス展開に弱い人も多いということをよく知っていらっしゃる。主人公不在の学園が襲撃されるというのは個人的にかなり辛い展開。そもそも主人公が知らないところで状況が悪いほうに傾いていくのが苦手で、特に今回は位置的にも離れており、十中八九主人公は間に合わないんだという絶望感を得つつ読んでいた。そしてヒロインたちがかなり手ひどく痛めつけられる。そういう苦しさがあってこそ終盤の逆襲が輝くわけで、読み終わってみればバトルシーンと学園シーンがいい感じにミックスされた満足のいく巻だった。

学食に行って昼食を摂り、菓子パンを買って帰宅。1時間半ほど日記を書いてから布団に入り、なろうの更新を一つ読んで午後2時前に就寝。

07/06(水)

午後10時半起床。寝る前に買ってきた菓子パンを食べた。写真を投稿したところ、以下のような指摘があった。

これって6本じゃなかった？ https://t.co/NJTu46VM1Q
— しぶやん (@mathematicswim) 2022年7月6日

確かに先週買ったものは6本だった。値段が変わっていないので何も気づかなかった。パッケージをゴミ箱から探し出して確認したところ、6本入りの時は1本あたり86kcalだったのが5本入りでは101kcalになっていたので、1本ごとは大きくなっていたらしい。まあ、さすがに1本分まるまる減量という豪快なことはできないのだろう。

食事 pic.twitter.com/8NHknUrOou
— こたつがめ (@kotatsugame_t) 2022年7月2日

布団でハーメルンを読み始め、午前2時過ぎに1作読了。「遊戯王の世界で遊戯王プレイヤーたちが遊びだしたようです。」。主人公だと思っていた人が早々に管理人と名乗って出番を減らし、以降いろんなキャラがわちゃわちゃし出した。別にフィクサーっぽいムーブをしているわけではないものの、そういう設定も面白いなと思う。

syosetu.org

切り抜きを見た。おどおどしている名取さなさん可愛いね……。ところでこういう話題、見ている側は面白いけれど同時に結構ギリギリのラインで綱渡りしているような感覚も得てしまう。正直怖い。

www.youtube.com

明日のセミナーは僕は発表しない予定なので、こうやって前日深夜にも拘わらずのんびりしている。とはいえ少しばかり教科書を読み進めておくか、ということでスマホでPDFファイルを開いた。しばらく読んでいたら眠気が来たので逆らわず就寝。おそらく午前4時半ごろだった。

07/07(木)

午前8時半に目を覚ます。あんまり寝た気がしないので二度寝したい。また教科書を読んで眠気を待つことにした。ちょっと気になることが生じたため目をつぶって細かく考えてもいたが、これでも眠れなかった。

ちなみに気になることとは、DiestelのTheorem 2.1.4、任意に定められた全順序たちに対して○○が存在するという命題は半順序ではダメなのかという疑問。半順序でもwell-definedになるように少し定義を変え、改めて証明を一つ一つ確認していたのだが、冷静になると適当に拡張して全順序にすることができるため一瞬で言えてしまった。制約を弱めているのだから当然だった。

正午に布団から出た。チームメンバー・コーチの了承を得てICPCのチーム情報をJAGのページに書き込んだ。Twitterアカウントのリンクの貼り方をミスってしまい絶望したが、リプライで修正方法を教えてもらい一命を取り留めた。

2022/Teams/List - ICPC OB/OG の会

左上の編集ってとこから編集できます
— ⚡すく⚡ (@0214sh7) 2022年7月7日

シャワーを浴びてから少し日記を書き、午後2時半に出発。購買で菓子パンを買い込み、山に登った。

午後3時からセミナー。今日はずっともう一人の発表。やはり2週空くと忘れてしまった定義などがあって、確認したり教科書を見せてもらったりしつつ補っていた。今日は比較的何事もなく終了。先生が帰った後黒板発表の方法について少し話していた。それは彼の発表方法に思うところがあったからなのだが、そもそも自分の発表がどのように見えているのか、また自分が心掛けているつもりのことは本当に実現できているのか、主観ではよくわからないのに人に対して指摘するなどおこがましすぎた。反省。

学食で食事して帰宅。しばらくYouTubeに時間を吸い取られた後、午後8時からTCO22 R3に出た。Parallelでないほうにレジってから、そういえばStage3の結果はどうなったんだと思って見に行くと、いつの間にかページが更新されていてR4進出が確定していた。レジれてしまったものは仕方ないと自分に言い聞かせ、そのまま出場することにした。

https://tco22.topcoder.com/competition/algorithm?tracks%5balgo-tco22%5d=3&tracks%5balgorithm-tabs%5d=4

↑このURL、%5bと%5dはもともと[と]である。そのまま貼るとリンクが壊れてしまうため手動でURLエンコードする必要があり、面倒だった。

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

Easyから難しかった。サンプルの様子を見ると地獄みたいな実装が思い浮かんでしまうが、ぐっと耐えて盤面のサイズが $26\times 26$ であることに思いを馳せる。駒をうまくバラして各列に一つずつしかないようにできれば、あとは文字コードに応じて行を決めることで必ずソートできる。この各列一つというのを頑張る。ある行に注目しているとき、「その行の駒は左から順に $l\dots r$ 列目に配置する」と決め打ち、移動先が左の駒は左から順に移動、右の駒は右から順に移動させればよい。

Medは謎。問題文を読んだだけでは見当もつかないので、とりあえず与えられたファイルを眺めてみる。全部DFS木のファイルと全部MSTのファイルがあって、これはプログラムのチェックのほかに、手軽に2種類の木を比較するためにも使える。DFS木のほうでどのように探索していったか目で追ってみると、結構長い一本道がたくさん発見できた。これはMSTにはない顕著な特徴だ。ということで、DFS木であるかを判定することにした。

方法はもうちょっと考える。DFS木における行き止まりとは、つまりたどり着いたときすでに4近傍が訪れられていたような部屋である。このことからそれらの部屋を訪れた順番が確定して、これを使って枝分かれにおいてどのような順番で探索したかが決定できるのではないかと考えた。しかしこれはかなり面倒そうなので、簡略化を試みる。

行き止まり以外の部屋でも「進まなかった方向」というものがあって、その先の部屋は、今の部屋から先をたどって行った先で訪れたか、あるいは今の部屋にたどり着く前に訪れたか。前者は言い換えれば木における子孫であり、後者は、その部屋から今の部屋に向かって進んできていないことから「訪れたがまだ全方向を探索していない部屋」、つまり今の部屋の先祖であることがわかる。よって壁を挟んで隣接する2部屋について、それらの間には木の先祖・子孫の関係があることが分かった。

別に壁を挟んでいなくとも隣接する2部屋を全部見てよい。これを実装することにした。各頂点についてbitsetで先祖の頂点集合を持つ方針。実行するとサンプル・全部DFS木のファイル・全部MSTのファイルで全問正解したため提出作業に入った。bash スクリプトを書いて一括実行し出力をswitch-case文に成形して、コードにペースト。ファイル11は大きな入力しかなかったようでちょっと時間がかかったが、埋め込みなので問題ない。そういえばこのファイル実行の形式は、入力サイズを抑えられない上疑似乱数で与えることもできない以上仕方のない、苦肉の策だったのだろう。

Hardに30分弱残したものの、一切分からず。チャレンジフェーズではEasyしか落ちないだろうと考えて少し眺めていたところ、Medが大量に落とされてびっくりした。見るとファイル1に対してほとんど'D'を出力しているコードがいくつかあってびっくり。その他Easyもいろいろ落とされていたものの、自分は何もできず終了。

システスではEasyが落ちてしまった。注釈に「同じマスへの移動も許される」とあったため判定をサボって常に移動させていたのだが、この時すでに正しい位置に移動させ終わった駒をもう一度同じマスに移動させてしまうことがあったらしい。そもそも僕がデバッグのために盤面を出力しようとして、クソ真面目にわざわざ文字を入れ替えたりしていたからこういうバグを埋め込んでしまったのだ。残念。

結局Med1完で19位、2848→2854(+6)でhighest。助かった。Medは次数だとか葉の枚数、直径などいろいろな観点が考えられるようで、下手すると小さいケースが全然判定できなくなってしまうらしい。上で言及したファイル1はその小さいケースしかなく、偏った出力をしてしまいがちだったそうだ。

そこのところ、自分がたどり着いた判定方法はかなり本質的。ただしこれも解法ガチャに成功した結果というか、それ以外の判定方法と比較検討したわけではないためただ運がよかっただけという感想になった。一本道で答えにたどり着いてしまい他の判定方法があるとは思っておらず、チャレンジフェーズではMedは落ちないと考えコードを見もしなかったのだ。

しばらくTLを眺めてから日記を書き進め、布団に入って午前1時半に就寝。明日はICPC国内予選。

07/08(金)

午前7時半に目を覚ましてしまった。2時間ほど横たわりながら本を読んでいた。そろそろ二度寝したいと思って本を閉じたのに、そこからハーメルンを読み始めて結局眠気はやってこなかった。

1作読了。「バーチャルなんたらになることになった。」。一口サイズで特に感想はなし。エタっている。

syosetu.org

正午、TLにとんでもないニュース速報が流れてきた。日記に書くかどうか迷ったのだが、その日あったことを記録するという意味でこれに触れないのは嘘だろう。僕くらいの世代の人間は、その政治的立場を抜きにしても、彼の人の言動に多く触れ、また総理大臣であるとの印象を強く残しているはずだ。少なくとも僕はそうだった。だから、このどこか現実感のないニュースを目にして非常に大きな衝撃を受け、その後しばらくTLに流れ続ける関連ツイートや一色に染まっていくトレンドをぼんやり眺めていた。

午後1時頃布団から出て学食で昼食を摂り、帰宅。少し日記を書き進めて、ICPC国内予選参加のため午後3時に家を出発した。

この予選に関しては参加記を書くつもりである。投稿したらここにURLを貼ろう。

07/22追記：投稿した。

kotatsugame.hatenablog.com

予選終了後にTwitterのトレンドのページを開いたところ、治療の甲斐なく亡くなられたとの文言が目に飛び込んできた。コンテスト中は忘れていられた感覚、おそらくやるせなさという表現をするのが適当だと思うが、これがぶり返してきて苦しかった。

午後8時帰宅。しばらくチーム名でエゴサーチなどして、午後9時から仮眠を取った。午後11時半の目覚ましでギリギリ目覚め、直後からECR131に出た。

Dashboard - Educational Codeforces Round 131 (Rated for Div. 2) - Codeforces

Aは草が生えていなかったら $0$ 、全部に生えていたら $2$ 、残りは $1$ 。Bは直感的に $d=2$ と決め打ってよさそう。構築は貪欲でよい。Cは二分探索。まず各職人が自分の得意なものを優先して取り組んで、余った時間でほかの職人の手が回らなかったものを終わらせる。余った時間が偶数でないからと言って自分が得意なものを敢えて他の人に振るのは損。

Dはちょっと悩んだ。 $a_i=1$ なる $i$ が決まるので、そのまま小さいほうから決めていけるかと思ったがそんなことはなかった。各 $i$ について $\left\lfloor\frac i{b_i+1}\right\rfloor+1\le a_i\le\left\lfloor\frac i{b_i}\right\rfloor$ （ただし $b_i=0$ のとき $\frac i{b_i}$ の代わりに $n$ とする）であればよいことがわかるため、 $a=1\dots n$ の順でその値を含む区間のうち右端が最も小さいものに貪欲に当てはめるのが最適。

Eは削除する文字を決め打ったとき、どこかを境にして文字列の先頭からカーソルを動かしてきて削除する文字と末尾からカーソルを動かしてきて削除する文字に分かれるのが最適な操作になる。元の文字列においては「先頭からカーソルが来る範囲」「カーソルが来ない範囲」「末尾からカーソルが来る範囲」の順で並ぶことになるので、これで耳dpする。先頭から来る範囲では削除しない文字に $1$ 手、削除する文字に $2$ 手かかり、末尾から来る範囲では両者とも $1$ 手である。先頭からカーソルが来る範囲が空でない場合は、先頭に飛ぶ操作でさらに1手必要。

Fは $i\lt j\lt k\le i+d$ について $j$ を固定したとき数えられなかったため、 $i$ だけで数えることにした。ある $i$ に対して不等式を満たすペア $(j,k)$ の個数は、 $(i,i+d]$ の区間内にある点の個数を $c_i$ としたとき $\binom{c_i}2=(c_i^2-c_i)/2$ となる。この $c_i$ を区間加算で変化させたときに正しい答えが計算できるか考えてみると、区間に対して $\sum_i c_i$ と $\sum_i 1$ を持っておけば実現できることが分かった。ここで $i$ は区間内に存在する点を走る。よって遅延セグメント木に乗る。

Dでちょっと詰まったが、open hacking phase開始時点ではノーペナ全完で2位。

朝方まで日記を書いていた。木曜日のTCO22 R3を通過したとのメールが来た。

TCO22R3を通過したとのメールが来た。全盛期のこたつがめ伝説：1度のTCOで2回（Stage3とR3）R4進出を決める
— こたつがめ (@kotatsugame_t) 2022年7月8日

布団に入ってから2時間ちょっとネット小説を読んでいた。結構前に読み始めた作品をついに1作読了。「音使いは死と踊る」。ちなみにこの作品は、僕に対する質問を受け付けたときに送られてきた文章でおすすめされていたものである。感想を書こうとしたらどうしても終盤の話に言及したくなったので、以下ネタバレ注意。

https://ncode.syosetu.com/n9898cc/

前半、能力を鍛えたり組織の仲間と交流する普通の現代SFっぽい話は単純に面白くて好きだった。後半はつらい。これまで登場したキャラがどんどん死んでいくし、それにつれて主人公のどうしようもない考え方が明らかになっていく。こんなに受け入れがたかった主人公はちょっと記憶にない。ラストの展開は主人公にとっての救いだったのだろうか。彼の感情が理解できないため詳しくはわからないものの、僕はそうだと考えた。何もかも最悪なままの結末ではなくて良かったと思いたい。とにかく僕の好みからは外れた作品だったが、それでも読み進められるくらいに面白くはあった。

少しYouTubeの切り抜きを見て、午前8時半就寝。

07/09(土)

午後1時半過ぎに起床。昨日のCFのopen hacking phaseが終了していた。ちゃんと全問通って2位のままだった。

午後2時からDDCC2022のオンライン予選に出た。言及禁止らしい。別に予選が終了したら良いのではないかとも思うが、そもそも何か言う価値のある問題ではなかったため、日記にも何も書かない。生協の冷凍弁当を受け取ってから布団に戻った。

本を1冊読了。「転生義経は静かに暮らしたい」。源義経の記憶を持つ女主人公が、義経と関わりの深かった人の生まれ変わりである男性キャラたちから求婚される話。そう帯に書いてあったのでラブコメメインだと思っていたが、そうではなく主人公の前世について探る話だった。「静かに暮らしたい」というタイトルも、目立ちたくないという意味ではなく、前世由来の特別な力を振るいたくないという意味だったようだ。主人公が目立つシーンが好みである僕としてはちょっと残念。内容も思っていたのとは全く異なっていて、特に好みでもなかった。

午後5時半から午後8時半まで寝ていた。DMOJでコンテストが開催されているが、これのRated上限が前まで2999と書かれていたのに2599に下げられていたため、自分はRatedではなくなった。よって出ないことにした。

午後9時からABC259に出た。

AtCoder Beginner Contest 259 - AtCoder

Aはちょっとややこしい。生まれた時の身長が与えられておらずマジ？と言っていたが、 $N\ge X$ に注意すれば $T-DX$ で計算できた。ここから $D\times\min(M,X)$ だけ身長が伸びる。まとめると $T+D\times\min(M-X,0)$ が答えになるようだ。dcで書くときは $\max(\ast,0)$ の形が扱いやすいので $T-D\times\max(X-M,0)$ とし、実装。2分半ほどかかっている。

ここからはC++で解いた。Bは回転行列の形を思い出して実装。せっかく度数法を弧度法に直したのに直す前の変数を使ってしまうミスを犯し、デバッグでもたついた。Cはランレングス圧縮して比較。文字列 $T$ に対しても操作できると勘違いして1WA。DはUF。円の交差判定はライブラリを見ずとも記憶を頼りに導き出せた。2乗して整数のまま比較。

Eは最初の状態で最小公倍数の各素因数の指数を計算し、 $a_i$ ごとにそれを抜いた時指数が変化する素因数を列挙する。これのuniqueを取ればよい。要素の個数が全体で高々 $\sum m_i$ 個となるので、vectorたちのsort+uniqueで十分高速。Fは木dp。 $d_i$ 未満と以下の2状態を取り違えて手間取った。

Gは僕にとっては難しかった。ICPC国内予選のEを思い出して何か適当な貪欲が効くのではないかとしばらく疑っていた。どうしようもなさそうなのでフローの方針で進める。各行各列ごとに選ぶか選ばないかを決めることにして、燃やす埋めるだと思ってグラフを考えてみると、行でも列でも選んだマスのペナルティが書けなくなった。ここで二部グラフであることに思いを馳せ列だけ状態を反転させるとうまくいった。こうやって実際にグラフができてみると、「負の整数が書かれたカードを行でも列でも選ぶとペナルティ $\infty$ 」というのが燃やす埋めるで解けるようにするための人為的な制約に見えてきて、かなりあからさまだったなという感想。

Exは解けなかった。 $(a,b)\rightarrow(c,d)$ の移動経路が $\binom{(c-a)+(d-b)}{c-a}$ である、と言ってしまったのがよくなかったようだ。 $a$ と $c$ を全探索し、 $b$ と $d$ について高速に計算するため、それぞれのサイズが十分大きいときに畳み込みで $d-b$ の出現回数を見ようとしたものの、当然のようにTLE。実際すべてのラベルが同じケースでは手元で3sec弱かかっており、その後改善できずコンテストが終了した。

結果は7完61位。出来は相当に悪いが、これでも学生50位に入れると思うと気が楽になった。Eは $a_i$ ごとに列挙した素因数が空でなければ重複しないとわかるらしい。Exは一つのラベルに対して $O(N^2)$ のdpでも計算できることに気づいていれば解けただろうか。上で「サイズが十分大きいときに畳み込み」したのは、それでオーダーが落ちると確信していたわけではなく、ただACLの畳み込みが片方のサイズが60以下なら愚直に計算しているのに習っただけであった。

Dについて、うしさんの幾何ライブラリの設計が話題になっていた。円同士の交差判定をするためにintersectという関数を使うと、実は共通接線の本数が返ってくるため、単純にbool値にキャストしただけでは共通接線が4本のときに正しくない値になってしまう。実は以前の僕のライブラリでも全く同じ設計になっていて、全く同じようにハマったため結構前に直したのだった。

https://github.com/ei1333/library/blob/master/geometry/template.hpp#L181

元あったintersectをcount_tangentという関数名に変更して、新しいintersectは1<=count_tangent<=3を判定する。
週記（2020/11/02-2020/11/08） - kotatsugameの日記

コードゴルフ。Aは最初に出したdcコードが今のところの最短で、時間差でギリギリ勝ち。Bは複素数で回転させることにして、Rakuで書いたものが最短になっている。DはRubyでBFSを実装。一度たどり着いた円を除外するのにrejectを使うコードを提案したがその後の更新合戦で負け。EもRuby。微妙な差で勝っている。F以降は手付かず。

Cは面白かった。実は正規表現一発で書けてしまう。 $S$ において同じ文字が2文字以上連続している場所は、それと同じ文字がそれ以上連続しているなら何にでもなれる。つまり、例えば"aaa"は"aaa+"にマッチする文字列に変換可能。従って、このように同じ文字が2文字以上連続している場所の最後に+を挿入した文字列を作り、これをパターンと見て $T$ の全体がマッチするか調べることで判定できてしまう。

Perlで実装した。まず、 $T$ の全体と制限せず、一部分にマッチするかという判定でもよい。末尾は改行があるためちゃんと揃う必要があるが、先頭に関してはテストケースが弱いようだ。次に、提出するとマッチに失敗したときのバックトラックでTLEしてしまったため、+ではなく+?の非貪欲マッチとすることで回避した。実装の都合上 $T$ を加工して $S$ とマッチするか調べるほうがコードが短くなりそう。とはいえ、そのような正規表現を簡単に作る方法は残念ながら思いつかなかった。

午前1時からSRM833に出た。

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

Easyは遷移が行または列に対する区間加算で書けるので、それぞれimos法で管理。1歩、2歩進む場合は直接dpテーブルに加算し、4歩以上進む場合をimos法にしたため、終端を考えずとも足しっぱなしで良くなった。初期状態の兼ね合いから、 $X=Y=0$ だけ特別扱いする必要がある。サンプルにあって助かった。しかしそれ以外のケースで壊れないかを慎重に確認していたら結構時間がかかってしまった。

Medは区間の両端からそれぞれ最も近い石だけ考えればよい。各位置に対して左右それぞれ最も近い石の位置を前計算しておく。

Hardは文字種ごとに出現回数をカウントしたときそれぞれ偶数個である必要がある。例えばある文字が $i_1,\dots,i_{2n}$ に出現していたとき、 $i_1,\dots,i_n$ の行き先を $1,\dots,|S|/2$ から決め、残りは $i_k$ の行き先 $+|S|/2$ を $i_{n+k}$ の行き先としていくのが良い。これを全部の文字に対して行うことになるので、 $|S|/2$ 個のものを $1,\dots,|S|/2$ に割り当てるコスト最小の方法を求める問題になる。

つまり最小重み最大マッチング。二部グラフなので最小費用流で解けて、 $|S|+2$ 頂点 $|S|^2/4+|S|$ 辺になるため間に合う。最大重みだと勘違いしてポテンシャル計算を手動で行ったりしていたらかなり時間を食ってしまった。

正直問題は全部簡単。しかし丁寧にやっていたら点数がかなり下がってしまった。システスは全部通ったものの、17位でレートは2854→2828(-26)。残念。

しばらくABCのコードゴルフを続けた後、午前4時から午前8時までは日記を書いていた。その後布団に移動してラノベを読み、午前11時就寝。

07/10(日)

午後10時起床。少しコードゴルフした後シャワーを浴び、食事して、午後11時半からCF #805 div.3に出た。

Dashboard - Codeforces Round #805 (Div. 3) - Codeforces

Aはやるだけ。Bは先頭から4種類目の文字が出現する直前まで切り出すことを繰り返す。Cは $a$ が出現する最も左のインデックスが $b$ が出現する最も右のインデックス以下であるかチェック。mapを使ってそのまま実装し600msだったが、TLが3secなのでOK。

Dは値段が高い文字から消していく。どの文字が何個あるかの配列を作ってデクリメントする実装にすると、元の順に並べて出力するのも簡単だった。Eはグラフを作り、各頂点の次数が2かつ二部グラフであればよい。つまり偶閉路のみからなるグラフ。Fは最近のABCで既出。解法を覚えていたのに問題を探しに行ってしまい、しかも見つからず少し時間を無駄にした。

Ex - Multiply or Divide by 2

大きな数から決めたい気持ちになる。実際、最大の数が一致しているならそれらをペアにすることで全く損しないことが言える。一致していない場合、大きな方を減らすことになる。それがAA由来だったなら単に22で割って切り捨てればよい。BB由来だった場合、これを22で割ることはAAの要素を22倍することに対応しているので、奇数なら即座に−1−1を出力する。
週記（2022/05/30-2022/06/05） - kotatsugameの日記

Gは難しかった。適当に根付き木にしておいて、クエリで与えられた頂点たちを深さの降順にソートする。これらが単純パスに乗っているなら、その端点の片方を深さ最大の頂点に固定してよい。パスはその頂点からしばらく深さが小さくなり、残りは逆に大きくなっていく形をしていなければならない。よって、まず深さが小さくなる部分を求めるため、ソート後の頂点たちを順に見ていって先祖を辿る。辿れず残った頂点は今度逆順に見ていったときどんどん子に降りていくように並んでいなければならない。この先祖・子孫の関係は、毎回2頂点のLCAを計算して先祖となるべき方に一致するかでチェックした。

深さが小さくなっていく部分と大きくなっていく部分が切り替わる瞬間は少し注意が必要。最初に固定した頂点から先祖を辿っていって、最も根に近い頂点 $u$ が得られたとする。その直前に通った頂点と直後に通った頂点の両方が存在し、それらのLCAの深さが $u$ の深さより大きい場合だけダメ。この判定はできていたのだが、その後で $u$ とその直後の頂点が先祖・子孫の関係にあるかチェックしてしまい1WA。このタイミングだけはそのチェックに通る必要がない。

Fまではそこそこ速かったもののGに時間をかけてしまい、さらにG1とG2に分かれていたためペナルティに大きく影響してopen hacking phase開始時点で13位だった。

Gは典型90の35問目で見たAuxiliary Treeがパスになっているかチェックする問題。この方針で何も見えなかったため上のような解法に進んだのだが、Auxiliary Treeの直径が含まれる辺の数と一致するか判定すればよかったらしい。ただ、僕の解法でもこちらの解法でもクエリごとに $O(k)$ 回LCAを計算することになるのは変わらない。 $\sum k$ に制約があるものの感覚的にはちょっと多そうと思っていた。

その後は朝方までずっと日記を書いていた。今週は週末のコンテストが非常に軽かったため、何とか就寝前に投稿できそう。校閲に2時間かけ、完全に朝になった頃合いで完成。最近は火曜日になる直前までかかってしまうことが多かったので、初心に帰ってちゃんと毎日書き進めたい。