09/11(月)

午後4時過ぎ起床。半からインターン先定例会に参加した。今週の進捗も昨日寝る前に稼働した分だけである。

勉強会は現場で使われているシェルスクリプトを読むというものだった。2年ほど前に自分が行った勉強会で少しシェルスクリプトの文法に触れたが、その資料の特にリダイレクト回りが役に立ったらしく嬉しい。フィールドの抜き出しにAWKが効いていたり、sedのsコマンドの区切り文字を/から変更したりと、思ったよりいろいろなものが使われていてワクワクした。

勉強会1115.pdf - Google ドライブ

普段より早く終わったので学食に行って夕食。帰宅してからはずっと週記を書いていた。先週のメインイベントWTFについては記述を充実させたかったのでコンテスト中の考察をずらずら書き並べておいたのだが、その分他のところに手が回らなくなってしまった。

穴あきだらけのまま午後11時半に投稿し、直後からCF #897 div.2。F問題に4000点つけられているとTLで知って少し腰が引けていた。

Dashboard - Codeforces Round 897 (Div. 2) - Codeforces

Aは $a$ の降順に $1\dots n$ を割り当てるとよい。直感だけで提出したが、後から計算したところ $a_i\ge a_j$ なら $a_i-b_i\gt a_j-b_j$ となるため $c$ をpairwise distinctにできていたようだ。Bは $s$ に応じて $i$ ごとに $l_i=l_{n+1-i}$ または $l_i\ne l_{n+1-i}$ のどちらかが条件となる。あとは $n$ が奇数の時に気を付けつつ算数。

Cは常に $S$ のMEXを追加するとよい。初手以外はBobが直前に削除した数を追加することになる。追加した数よりも小さい値が抜けていると、その穴はいずれ塞ぐ必要があり、そのときに損してしまうようだ。

Dはfunctional graphに読み替えると操作が長さ $k$ のループを作ることに相当する。 $i\rightarrow b_i$ を辺とするグラフについて、ある連結成分に最後に関わる操作はその連結成分内でループを作るものでなければならないため、すべてのループが長さ $k$ であることが必要。ループ以外の頂点は $k\gt 1$ なら適当にできる。 $k=1$ は自明。

Eは $k=x+y$ なる $x,y\gt 0$ を取り $y$ だけずらして奇数回（ $c$ 回と置く）聞くと、長さ $x+cy$ ぶんの総XORが判明する。これを遷移としてdpしたら制約内のすべてのケースでクエリ回数50回を達成できたので、E2まで一気に解けた。

問題の4000点、F。一つ $P(G)$ に含まれない部分木があったら、残りの頂点はその上にパスグラフを作ると全部 $P(G)$ に含まれなくなって最適である。よって $P(G)$ に含まれないような頂点数最少の根付き木を求める問題になった。分割の列挙とdpで数えると頂点数18で10⁶個より多くなったので、この辺りまで列挙できれば十分。実際には頂点数 $c$ の部分木が $P(G)$ に $n/c$ 個しかないことを使ってもっと評価を小さくできる。

これだけ小さいサイズなら、木のハッシュとして何か乱数を持ち出す必要はなく括弧列にエンコードしてしまってよいはず。まず $P(G)$ に含まれる小さな部分木の括弧列を列挙した後、先ほどのdpを具体的な木の構成を列挙するものに書き換えた。これまで作った木に番号を付け、一つの木はそれぞれの子の下にどの番号の部分木があるかを列として持つことで表現する。この方法だと適当に再帰することで辺も簡単に求まる。

投げたら1500ms弱で通った。TLは4secなのでシステスも大丈夫だろう。実際、2secちょっとに伸びただけで問題なく通り、自分の上から一人落ちたため結果は全完6位であった。

実況動画は、途中パワーポイントを開いてしまい本名が映り込んだので、そのシーンにモザイクをかけてから投稿した。このひと手間のために手元で1時間近くかけてエンコードする必要があり大変。

www.youtube.com

それからはゴミ出しをしつつずっと週記を埋めていた。UC以外を書き終えて午前11時就寝。明日は久しぶりにゲーセンに行きたい。

09/12(火)

夕方くらいに目を覚ますも眠気が強く二度寝を決定。寝すぎないよう小刻みに目覚ましをかけつつ午後8時まで布団の上にいた。まだ眠いがこれ以上寝ているとゲーセンに行けなくなる。

天気が悪いので地下鉄に乗って街へ。立ち食い蕎麦を食べ、午後9時から閉店までで15クレ遊んだ。新曲の「セガサターン起動音[H.][Remix]」のAJが全然出なくて大変だった。この令和の時代に始点が黄タップになっていないスライドで言の葉カルマ配置をやらせるのはシンプルに嫌がらせだと思う。59小節以降も意味不明で、たまにある人を不快にさせることが目的の譜面なんだろうなと結論付けた。

油そばを食べて帰宅。シャワーを浴び、朝方まで日記を書いて布団に入った。1時間ほどラノベを読み午前6時半就寝。

09/13(水)

午後8時起床。布団に横たわったままハーメルンやカクヨムの更新分を読んでいた。

次回のUniversal Cupは09/30らしい。この日は第四回日本最強プログラマー学生選手権の決勝の日で、夜中にCF div.1があり、さらに自分は後泊するから夜更かしできない。よってフルで参加できるwindowがないようだ。WTFと被ったときはwindowが増えたので今回もそういう対応をしてくれないかと思うが、オンサイトの格が違いすぎてお願いするのが恥ずかしい。

午後11時半からCodechef Starters 100に参加した。

https://www.codechef.com/START100A

S100は右から貪欲に操作してよい。先頭の1より右を全部0にするとも言えるが、この場合先頭の1が右端2文字にあると何も操作できないのがコーナーケースになる。PRIMEPERMは $N=4,5,6,7$ を手で構築して組み合わせ、 $N\ge 4$ に対する答えを作った。 $N\le 3$ が不可能なのはすぐ確かめられる。

CONCUSSIVEはなんだか見覚えがある。要素を昇順に見て $1,3,\dots,2,4,\dots$ または $2,4,\dots,1,3,\dots$ へと配置すると良かったはず、と思って両方試したら通った。コンテスト後のTLでARC161Aが似た問題だと判明。こちらは前者の配置だけでよいが、今回は条件も制約も少し緩いので両方試す必要がある。それで十分なことの証明はしていない。

A - Make M

SWAP_はタイブレークを適当に決めて文字列ではなく $1\dots N$ のソートだと思って解いた。番号が連続している区間をブロックにまとめ、その数を1回の操作で1個減らせればよい。先頭要素が $1$ でない・末尾の要素が $N$ でない場合は簡単。そうでない場合、2回の操作で2個減らすことに成功した。

例えばブロックが $aXbYcZd$ のように並んでいるとする。ここで $a,b,c,d$ は一つのブロックで、 $a$ の直後に $b$ が、 $c$ の直後に $d$ が来るべきである。この場合 $[a]XbYcZ[d]\rightarrow[dX]bYc[Za]\rightarrow ZabYcdX$ で $ab,cd$ が一つのブロックになる。もう1パターン $aXcYbZd$ があって、これは $[aXc]Y[bZd]\rightarrow[bZ]dYa[Xc]\rightarrow XcdYabZ$ でよい。

ANTに進んだ。最初はこちらのほうがSWAP_より下に並んでいたはずだがいつの間にかsolved数が逆転していた。 $N=4,6$ でRRRDLLDRRDLLLUUUみたいな辿り方が条件を満たすことを確かめ、 $N$ が奇数の場合は不可能として出したら通った。

COMBI_IS_FUNはまあまあ面白かった。数え上げるのは多重集合なので、昇順に並べた列だと思ってよい。costの最小値を達成するのは連続部分列へ分割した場合であり、どこで切ればcostが小さくなるか考えると $F(A,D)=D+\sum_{i=1}^{N-1}\min(A_{i+1}-A_i,D)$ だとわかる。

$A_0=1$ 、 $A_{N+1}=M$ として階差数列 $d_i=A_{i+1}-A_i$ を考えると、求めるのは $\sum d_i=M-1$ かつ $d_i\ge 0$ かつ $\sum_{i=1}^{N-1}\min(d_i,D)=K-D$ なる $d$ の個数である。 $1\le i\le N-1$ のうち $d_i\ge D$ となる要素が $x$ 個あるとすると、残りの要素は $D$ 未満で総和が $k:=K-D\times(x+1)$ である。この数え上げは上限を違反する要素の数を考える包除原理で $O(N)$ でできる。

$\binom{N-1}x$ で並べ方を数えたら、あとは $d_i\ge D$ なる要素に対する $d_i-D$ と、さらに $d_0$ と $d_N$ の具体的な値を決めればよい。これについては和が $M-1-D\times x-k$ になればよいので単純な重複組み合わせで求まる。

残り20分でTREEDESTへ。元のゲームは直径を残すように操作すればいいんだろうなとは分かった。しかし木を構築しながら直径を管理するのすら実装が間に合わなそうだし、そこからすぐ答えが求まるわけでもない。

順位表への反映が遅れまくっていたがしばらく待っていたら全部処理され、最終結果は6完4位で2852→2878(+26)となった。

朝までかけてラノベ「ありふれた職業で世界最強」13巻を読んだ。好きなシリーズの最終巻。分厚い本の大半がラストバトルなんだろうと思ってひるんでしまい1年ほど積んでいたが、気合いを入れて読んでみれば面白くないわけがなかった。エピローグも100ページほどあって嬉しい。異世界召喚モノで本当に元の世界に帰還したのを見ると感慨深い気持ちになる。

元の世界に帰ってからの話も欲しかったなと思っていたら、アフターストーリーという形でなろうで連載が続いていると後書きにあった。それも刊行されるかも、とも書いてあったが13巻発売から1年経過して音沙汰がないし、シリーズ完結まで我慢していたなろうを解禁してもよいだろう。ということで満を持して読み始めた。300話近くあって最高すぎる。

https://ncode.syosetu.com/n8611bv/

読むのを止められないうちに学食の昼の部が開店して閉店してしまった。購買も閉まりかけたところで慌てて滑り込み、お菓子やパンを購入。帰宅した後もなろうを読み続けて午後4時半ごろ寝た。

09/14(木)

午後11時から午前2時半までなろうを読んでいた形跡がある。

09/15(金)

午前6時半起床。今日はセミナーの日だが何も準備ができていない。進捗ダメですと先生にメールしたらセミナーではなく1対1での打ち合わせをすることになったので、すべての準備を放棄してなろうを読み続けた。

正午くらいに「ありふれたアフターⅡ　光輝編」まで読み終えた。主人公はタイトル通り天之河光輝。このキャラクターは本編終盤で洗脳され敵方に回ったりと良いところが全くなかったが、自分にとって13巻より前の内容は忘却の彼方であり、悪印象はもう残っていない。まさに勇者を体現するような非常に格好良い姿が描かれて好感度がかなり上がった。

打ち合わせは午後1時からなので、急いでシャワーを浴びて登校。学食で昼食を摂り購買に寄ったところで先生と鉢合わせ、教室ではなく学食で話すことになった。

かなり長引き4時間ほど話した。直近でやってみたいことというのは一応存在するものの、相変わらずその意義を説明できないし、論文に求めようにも近いものがあまりないようだ。少し一般化した形の式が成り立たないか調べてみるということにして、そのための論文を1本、来週セミナーして発表することになった。

帰宅してからはずっとなろうを読んでいた。午前5時過ぎ寝落ち。

09/16(土)

午後3時起床。二度寝よりなろうを優先していたが、午後7時くらいになって急激に眠くなってきたので1時間ほど寝た。目覚ましで起床。

食事して午後9時からABC320。

Toyota Programming Contest 2023#5（AtCoder Beginner Contest 320） - AtCoder

Aはよい。ABC283Aは $A^B$ だけだったらしいが今回は少し面倒。Bは愚直の $O(|S|^3)$ 。逆に愚直以外で解こうとするならManacherくらいしか選択肢がなさそう。Cは答えが存在するなら $3M$ 秒未満である。止める数字を決め打った後、どのリールを止めたか状態に持つbitDPをした。

A - Power

Dは矛盾がないので適当に探索。辺 $A\leftrightarrow B$ で人1と連結でない人はundecidableである。Eはsetで列にいる人を、優先度付きキューで人が戻ってくるイベントを管理した。前者も優先度付きキューでよかった。

書く

www.youtube.com

午前5時くらいに寝落ちするまでずっとなろうを読んでいた。

09/17(日)

午前11時から午後1時くらいまで起きてなろうを読んでいたらしい。また寝て、午後6時起床。

明日は久しぶりにホスフィンとたいぺーと3人で昼食会からの家飲みをする。そのためのお酒やボドゲを金曜日にAmazonで注文し、今日届いていた。ところで、日程を決め店も予約した段階でCF combinedが生えてしまった。都合上飲み会をずらすこともできなかったのでどうしようか迷っている。昼から飲むのでいい感じに酔いを醒まして参加できればそれが一番良いが……。