2023-01-30

週記（2023/01/23-2023/01/29）

01/23(月)

午後3時少し前に起床。すぐ集中講義のZoomに接続した。

今週1週間参加する講義の名前は「応用数理総論」で、これだけだと何のことかわからないが内容は数理論理学である。実は同じ講義が学部生向けとしても開講されていて、自分は去年それの単位を取得した。だから知っている内容だろうし単位も楽に取れそうという見込み、純粋に理解を深めたいという気持ち、さらに今期の専門科目で他に興味のある科目がなかったため、以上3要素により受講を決めた。

初回の今日は基礎の確認で、命題論理、1階論理、再帰的関数、不完全性定理などが予定されていた。実際は3時間に収まらず、不完全性定理は次回に回された。内容的にはほぼ同じことを去年もやったはず。去年は資料が配られるだけだったが今年はZoomで実際に説明されるので、そこで何か得られるものがあるかと思ったら、特に何もないまま終わってしまった。まあ聞いているだけでわかるなら苦労はしないということで。

午後6時終了。今日オンラインだったのは予定していた講義室が取れなかったからで、明日からは対面になるらしい。

直後にインターン先定例会の会議に接続した。勉強会発表が終わった後の質疑応答の時間で、発表を聞いていないため特に何も言えることはなく、スライドを眺めて30分ほどで終了。

それから日記を書いて午後9時半頃投稿した。書いている途中でちょっとTLを見たとき興味深い話題を見つけ、それに関して少し調べていたので日記に書いておく。

.#マシュマロを投げ合おう https://t.co/pj7FH7xEFF pic.twitter.com/GEQAes9Nlx
— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年1月23日

日曜日のARC-Dの話。std::stable_sortを使うと比較回数が足りるという話だったが、サンプルを試すと同じペアが2回聞かれてしまうらしい。本当にマージソートしているならこんなことは起こらないはずだし、余計な比較をしているのになぜ回数が足りているのかもよくわからなくなる。上のツイートでは解決しておらず、自分も気になったので調べてみた。

2727行目を見るとマージソートする前に7要素ごとに挿入ソートが行われるようだ。実はGCCの挿入ソートは同じ比較を2回行うことがある。逆にそれ以外の部分は普通のマージソートだから、これが理由だとわかった。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2727

挿入ソートは、要素一つずつに注目して、前の要素より小さければ交換してさらに前を見るということを繰り返す実装になっている。ところがこれをそのまま書こうとすると、見ている要素のさらに前に本当に要素があるか毎回判定する必要が出てきてしまう。それを避けるため、最初に先頭要素と比較する処理が1819行目に入っていて、この比較が挿入ソート本体の比較とダブる可能性がある。

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1819

以上のことは日記を書いているときに確認した。月曜日の時点では見る部分を勘違いしていて、数列の長さが短いと挿入ソートになるせいだと言っていたが、それはマージ用のメモリが確保できない場合のみ実行される関数だった。通常時は上のような理由で比較がダブるはず。

std::sortは高速化のためにいろいろ複雑なことをしているから、比較回数は多くなりがちらしい。まずクイックソートのパーティション用pivotを決めるために何回か比較している。次に、クイックソートの再帰が深くなるとヒープソートに切り替わる。最後に粗くソートした配列を挿入ソートして終わり。比較のダブりも至る所で起こりそう。

今日が期限の期末レポートがあるので書いた。確率モデル論という講義。講義中に出された問題から3問選んで解けという課題で、実は昨年末に出された時点で2問解いてあったので今日は追加で1問解くだけ。1時間で完成した。

教員のやる気がなさそうで講義スライドも講義動画も使い回しらしいが単位取得には問題ない。問題3問というのも実は全15問中3問で、しかも2回目・3回目の講義で3問ずつ出題されるという偏りっぷりだから、講義の序盤の内容だけ把握すれば期末レポートが書けてしまう。いわゆる楽単というやつだった。

しばらくなろうを読んだりニコニコ動画を見たりした後、かなり久しぶりにTUPCのテスター作業をした。そろそろ気合いを入れないとまずい。

一段落して午前7時頃布団に入り、しばらくなろうを読んで午前9時就寝。

01/24(火)

午後2時半起床。天気予報によれば夕方から雪が降るらしく原付で登校できない。仕方なく地下鉄で向かったら案の定遅刻、と思いきや先生が機材の設定に手間取っていたためギリギリ間に合った。

今日は去年やっていない2階論理の話。本当はもっと内容があったが、2階論理以外は理解が及ばなかった。そもそも理解しようとしていなかった気もする。眠気が強くウトウトしているうちに時間が過ぎていった。

学食で食事して帰宅。雪は降りそうだがまだ降っていなかった。疲れて布団に倒れこみ、なろうを読んでいるうちに寝落ちした。午後8時半。

午後10時に目を覚ました。改めて寝直すか迷っていたがECRがあることに気づき起きていることにした。なろうを読んで時間を過ごし、午後11時半からECR142。

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

Aは $h=1$ なるモンスターが2匹いれば一つ目の呪文で倒すべきで、それ以外は1匹ずつ倒していく。Bは最初にtype 1をすべて話し、次にtype 2とtype 3を交互に話すのが最適で残りは貪欲に取れる。場合分けを頑張る。

Cは、 $k$ 回操作するとき、 $2k$ 要素を一気に削除してから先頭と末尾に $k$ 要素ずつ振り分けると思ってよい。これで $p$ がソートできるのと $p$ の部分列として $k+1\dots N-k$ が現れることが同値。この判定を使って $k$ を二分探索する。

Dは $a_i\cdot a_j$ の先頭 $b$ 項が一致することと $1\le k\le b$ に対して $(a_i)_k=(a_j)_k^{-1}$ となることが同値。辞書順において $a_i$ より小さい $(a_j)^{-1}$ のうち最大のもの、あるいはその逆を試せば十分である。あらかじめ $(a_j)^{-1}$ をソートしておいて、 $a_i$ の位置を二分探索で求めるとよい。

Eは大変だった。 $m_1$ 、 $m_2$ を素因数分解した結果を使うと約数の全列挙ができる。これが $d$ になるので、 $d_1,d_2\le n$ によって $d=d_1\cdot d_2$ と表す方法のうち $d_1$ が最小のものを求めたい。 $d_1\le n$ は最後にチェックすればよいので、結局 $d$ の約数であって $n$ 以下で最大のものを求めることになる。

約数の全列挙の過程でさらにその約数も全探索することにしたら、最悪ケースである $m_1\cdot m_2$ が高度合成数の場合に1ケース0.5secくらいになった。微妙に間に合わないようだ。その後高速化しようといろいろ書き換えたもののむしろ遅くなる一方だった。

しばらく考えてまともな解法を思いついた。もし $d\le n$ なら $d=1\cdot d$ とするべき。そうでない場合 $d$ の素因数 $p$ を全探索し、 $d/p$ の結果を流用する。最適な表し方 $d=d_1\cdot d_2$ について、もし $d\gt n$ なら必ず $d_1\gt 1$ だから、 $p\mid d_1$ なる $p\mid d$ が存在して $d/p=(d_1/p)\cdot d_2$ もまた最適な表し方となる。

Fは4頂点あって初めて破綻するらしい。赤の辺でも青の辺でもパスグラフになるような塗分けがある。どうせこれが存在しないことが十分条件でもあるだろうと思ったが、そこから先にはまったく進めなかった。

5完33位。F1は赤の辺と青の辺が必ず存在するという条件を外した状態、つまり2を足したものをOEISに投げると見つかるらしい。FORMULAを辿っていくと $O(n^2)$ の式が見つかって、F1はすぐ解ける。F2も書いてあることを使って頑張ると解けるらしい。

A006351 - OEIS

しばらくTUPCのテスター作業をしていたが遅々として進まない。布団に逃げ込んで午前4時頃ふて寝。

01/25(水)

午前7時半くらいに目を覚まし、うっかり2時間ほどなろうを読んでしまった。

昼過ぎに目覚ましで意識を取り戻す。Classroomの投稿で今日の集中講義がオンラインになったことを知った。「悪天候により」と書いてあって、さてはと思って窓の外を見たら一面の銀世界だった。それはともかくとしてもう一度寝直した。

午後3時前に起床しすぐさま集中講義へ。講義資料が共有されていないのを休憩時間まで言い出せず、前半は内容を見落とさないよう必死に集中していた。資料を手に入れて満足した後半はあまり聞いていなかった。今日は様相論理やクリプキモデルの話で、去年の時点でそれなりに分かったと思っているから余裕をぶっこいていた。実際にはまだ意味不明な話も多いが単位を取るには不足しないだろうと信じている。

集中講義を終えてすぐ布団に倒れこんだが、今日は夜中のCFに備えてしっかり目覚ましをかけておいた。ひと眠りして起きたら午後11時過ぎ。半からCF #846 div.2に出た。

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

Aは奇数三つか奇数一つと偶数二つを使えばよい。判定だけだと思ったら出力も求められて非常に面倒。 $n\le 300$ なので3乗が通るように見えるが、マルチテストケースで $\sum n$ の上限が大きいためそれだとTLEしてしまう。しょうもない罠。

Bは $k=2$ と固定してよいので分割位置を全探索する。

Cは解法が壊れていた。一応問題概要から説明。 $n$ 人の人がいて、それぞれが好む料理の種類が $a_1,\dots,a_n$ で与えられる。テーブルが $m$ 脚あって、それぞれに座れる人数が $c_1,\dots,c_m$ で与えられる。ここで $\sum c\ge n$ である。今から $n$ 人の人を全員テーブルに座らせ、テーブルごとに配膳する料理の種類を一つだけ決める。座っているテーブルに配膳された料理が好きな種類のものだった人数を最大化せよ。 $n,m\le 2\times 10^3$ 。

自分は好む人数が多い種類の料理を座れる人数が多いテーブルに配膳していく貪欲を行った。計算量 $O(m\log n)$ に比べて制約が小さいのがよくわからないが、ともかくこれでpretestは通ったから、想定解も貪欲をしていただろうことがわかる。

しかしこれは大嘘である。コンテスト後に考えてみると、そもそも部分和問題を何回も解くようなケースを含んでいるからまともには解けなさそうだと分かった。結局このコンテストはunratedになり、C問題は後々削除された。

Dは下のbitからどんどん引いていくと操作後の値がわかる。直前のpopcountから1だけ減っていれば、もともとそのbitが立っていて今は立っていないということがわかる。そうでなければ逆。最後に引いた数を足して答える。

Eは辺の重みとして $g$ が現れることと $[l,r]$ に $g$ の倍数が二つ以上存在することが同値。後者の条件は $\lceil l/g\rceil\lt\lfloor r/g\rfloor$ と書ける。ここでうっかりfloor_sumを考えてしまった。sumを取るときに動かす変数 $g$ が分母に来ているので解けない。正解は $\lceil l/g\rceil$ を $O(\sqrt l)$ で列挙すること。ここで $l\le 10^9$ という制約が使える。

Fは選ぶ三つの数のうち最小でも最大でもない値はどうでもよいためソートすると「 $\min=a_l$ かつ $\max=a_r$ の三つ組が $r-l-1$ 個ある」と書けて寄与が分解できる。これで $\min$ と $\max$ がともに何かの倍数であるような場合の数が求められて、あとは約数で包除原理をすればよい。

GはまずSuffix ArrayとLCP Arrayを構築する。最初は同じ長さ $0$ の文字列がSuffix Arrayの $[0,n)$ に出現している状態だと捉え、そこから文字列の長さを増やしつつLCP Arrayを見て区間を区切っていくことで、長さに対して部分文字列が何種類、それぞれ何回現れるかカウントできる。

回数を頻度配列で保存することにしても更新は可能。この配列のうちインデックスが長さの倍数であるような位置について和を取ることで、特定の長さに対してdeliciousな文字列が数えられる。長さを全探索すると配列を見る回数は $O(n\log n)$ になり、十分高速。

全完したがC問題をうっかり通してしまったのはバカ発見器という感じで残念。コンテスト終了直後は4位と表示されていて、その後C問題が削除された結果10位になっていた。

システスについて、A問題をTLEで落とした人が上位にも少しいた。上で言及した罠がpretestに入っていなかったらしい。信じられないくらい性格が悪い。

今日のCFはまた音声入りで画面を録画していた。コンテストは破綻していたがせっかく撮ったので投稿したい。C問題に関してちょっと文章で説明を入れたりしてから投稿した。

www.youtube.com

Universal Cupというコンテストシリーズがもうすぐ始まる。中国で行われたclosedな5hのセットが出題されるらしい。1チーム3人なので参加するためにはチームを組む必要があるが、夏ごろのMulti-Universities Campとは違いOpenCupのSlackで何か募集が行われたり組まれたりはしないらしい。一人で出るには辛そうなので自分から探しに行く必要があった。

「チームどうしようかなあ」のようなツイートを行い、言及を待って突撃するという姑息な方法でチームを組むことに成功した。ぷらさんとかっつさんである。どうぞよろしくお願いします。

1st Universal Cup Announcement - Codeforces

朝までTUPCのテスターをしていた。午前9時に布団に入り、小一時間なろうを読んで就寝。明日の集中講義もオンラインである。

01/26(木)

午後3時前に起床。今日はTAを休んで集中講義に参加する。オンラインだしTAの教室に行くだけなら行けるな……とも考えたが、雪が積もっていて外に出る気にならなかった。

すぐさま集中講義へ、と思ったらZoomリンクが見当たらない。月曜・水曜に使ったものはそれぞれその日時のミーティング専用らしく今日は使えなかった。しばらく待っても音沙汰がなく他の人がどうなっているのかわからない。恥を忍んでClassroomにZoomリンクがないとコメントしたら、先生からは「自分は繋がっているのですが」という投稿があった。

言葉の感じからするに、これは先生しか繋がっていないという意味で、他の誰もミーティングに参加できていないのだろう。案の定Zoomリンクを送ってくれとのコメントがぽつぽつ付いた。しかしそれから実際にリンクが送られてくるまでにはさらに時間がかかり、結局講義が始まったのは予定時刻の30分後だった。

その待ち時間の間に新春TCB2023の賞品を選択した。ちょうど今日の昼前にメールが来ていた。自分に回ってきた時点で何の賞品が残っていたか公開するのはあまりよくない気がするが、自分が何を選んだかはここで言ってよいだろう。トラックボールマウスを選んだ。

2021年の新春TCBでもほぼ同じ機種を貰っておりこれで二つ目。HHKBも2台、PCも2台あるのでバランスがよい。そして、このキーボードとマウスはすべて競プロで得た賞品となる。

新春TechFULの商品であるトラックボールマウスが届いた。
週記（2021/03/01-2021/03/07） - kotatsugameの日記

集中講義の話に戻る。今日は様相論理の続きで、これも去年結構頑張って理解したはずの部分である。微妙に書き方が違う気もするが、まあ方言みたいなものだろう。ということで今日は最初から話を聞く気などなく、Zoomに接続だけしておいてこの講義の課題を解いていた。5日間毎日2題ずつ課題が出されていて、そのうち1題ずつに答えるのが期末レポートになる。

話は聞かないとしてもスライドには目を通している。参考文献として井上真偽「恋と禁忌の述語論理」が挙げられていたのが印象的だった。名前はよく聞くが別作品しか持っていないしそれも積んでいる。

午後6時に終了した後準備して外出。徒歩でゲーセンに向かった。TAのために外出するのは気が進まないがゲーセンに行くなら話は別である。

立ち食いそばを食べ、午後7時半から閉店まで4時間ほどプレイした。2週間ぶりなので新曲が結構あり、今日はほぼそれを埋めるだけとなった。

ただし大きな成果も一つ。「TiamaT:F minor」で5アタフルコンを出した。SSS+に少し届かなかったのが残念。実はこれは今日1回目なので、譜面が体に染みついておらず変なところでアタックを出してしまった。

ティアマトフルコン！SSS+寸…… pic.twitter.com/dKeA6j5P1f
— こたつがめ (@kotatsugame_t) 2023年1月26日

油そばを食べて日付が変わってから帰宅。TUPCのテスター作業をしたり、集中講義の先生に質問したいことをまとめたりしたら朝になった。ちなみに明日の集中講義は最後だからと対面の予定になっている。

午前6時に布団に入り、そこから2時間ちょっとなろうを読んで就寝。

01/27(金)

午後2時起床。生協でラノベを受け取りつつ地下鉄で山に登った。午後3時に微妙に遅刻したが、月曜日と同様今日もまだ講義は始まっていなかった。

今日の内容は逆数学と順序数。これは去年の講義では影も形もなかったものである。何も知らないし何もわからない。そのまま講義が終わってしまったので、昨日まとめてきた質問を聞いてから講義室を出た。

ホスフィンに誘われて夕食を一緒に摂り、次の飲み会の日程をすり合わせるなど結構話し込んで帰宅。家に着いたのは午後8時前だった。

今日は生命情報システム科学のレポートの提出期限。最終回である。Classroomの課題ページに期限が設定されておらず、講義スライドを見ないと失敗するのはいつものこと。

今回の課題は、講義で扱ったアルゴリズム・手法・データベースをどれか選んでレポートを書けというものだった。ゲノムアセンブリをグラフを用いて行うとき、頂点を並べる問題にするとハミルトン路を探すことになって難しいが、適当に変形して辺を並べる問題にするとオイラー路を探すだけになって簡単ということが説明されていたので、それについて書くことにした。

具体的には後者が簡単であることを示すつもり。グラフがオイラー路を持つ必要十分条件を示せば量としては十分だろう。十分条件は構成的証明によって示そうと思っている。これだとクラスPに属するというだけでなく実際に単純なアルゴリズムで解けることがわかる点で嬉しそう。

知っている話なので特に何か調べる必要もないはず。楽に書けそうに見えたため余裕ができたと勘違いし、うっかりなろうを読んで2時間弱をドブに捨ててしまった。それから慌てて書き始めた。グラフ理論の話を細かくするのは趣旨から外れるが、日本語だけで説明しようとするとかなり注意深くやらないと不正確になってしまう。説明を考えるのには思ったより苦労した。

さらに今日はCFがあるので、日付が変わるまでの時間をフルに使えるわけではない。午後11時半を目前にしてギリギリ完成し、急いで提出してCF #847 div.3へ。

Dashboard - Codeforces Round 847 (Div. 3) - Codeforces

Aはサンプルに30桁の情報があるのでコピペする。Bは最大値が $s-r$ だと決まる。残りは適当に構築すればよい。入力に対して必ず解が存在するという制約が嬉しい。

Cは先頭要素の多数決を取ることで $p_1$ がわかる。そして先頭に $p_1$ が来ていない列が $p_2,p_3,\dots,p_n$ になるため、 $p_1$ をくっつけて出力すればよい。

Dは貪欲に取ってよい。マトリョーシカをサイズの昇順に見ながら、今作っている最中であるようなsetの個数を管理した。

Eは結構時間がかかった。サンプルを2進数に直してみると、どうやら $x$ で立っているbitの一つ下のbitが必ず0なら構築できそう。逆にそうでない場合構築できないことも何となくわかって、出したら通った。

Fは謎。黒く塗られた頂点が増えたら答えも小さくなるだろうと思って、500頂点まではLCAを使って距離を求め、それ以降はdfsで探索するコードを書いたらTLE。そこでクエリ平方分割し、基本はLCAで距離を求めつつ適当な回数ごとにまとめてBFSすることで答えを更新するようにした。これも最初の提出はTLEだったが、BFSで答えを更新しなくなった瞬間打ち切るのと、答えがすでに1のときLCAで距離を求めないのを実装したら、TL 4secのところ2.6secで通った。

Gはちょっと面倒。頂点1から距離1以下の頂点にトークンがあればよい。そうでない場合、トークンの移動先は常にボーナスが置かれた頂点でなければならない。まず、頂点1からボーナスが置かれた頂点だけを通ってたどり着けるトークンを距離とともに列挙した。ただしトークンが置かれた頂点自体にはボーナスが置かれていなくともよいことに注意。

列挙したトークンのうちどれかを頂点1まで持っていくには、その距離から1引いた回数だけ別のトークンでボーナス頂点を踏まなければならない。ここで、辺で隣接するボーナス頂点に1手でたどり着けるトークンがあれば、それでボーナス頂点を往復することで何回でも踏むことができる。そうでない場合も、ボーナス頂点に1手でたどり着けるなら1回だけ寄与できる。これも別に数えておく。

どのトークンを頂点1に持っていくか全探索し、そのたびに先ほど数えた値を差分更新して、必要な回数だけボーナス頂点を踏めるか判定した。グラフが木だと思い込んでいて探索で1MLEしたが何とか通った。

全完31位。Fでかなりしてやられてしまった。Eは $a+b=(a\oplus b)+2(a\,{\rm AND}\,b)$ を使うと $x=a\oplus b=2(a\,{\rm AND}\,b)$ となって、自分がサンプルを観察して得た考察がストレートに手に入る。

Gは頂点1に持っていくトークンは候補が複数あるなら距離が最も近いものとしてよいらしい。距離2なら別の候補によってボーナス頂点を1回踏めばよい。距離3以上なら、別の候補によってボーナス頂点を往復することができてこれまた達成可能。

「黄金の経験値」の続刊が決定したらしくかなり嬉しい。2巻はおそらくちょっと苦しい展開が最初のほうにあるはずで、少し怖がってもいる。

皆様の応援（経済力）のおかげで、二巻の発売が決定いたしました！
ありがとうございます！

男装の吸血鬼っぽい新キャラ……
いったい何ランなんだ（ https://t.co/nEuWTnX77Y
— 原純【黄金の経験値】書籍第Ⅳ巻３月８日発売予定！　コミックも連載中！ (@harajun1001) 2023年1月25日

日記を書いて午前4時就寝。

01/28(土)

正午少し前に起きてAHC017に参加し、提出を行った。自分がこの時間に提出を行ったことは順位表からわかる情報である。

THIRD PROGRAMMING CONTEST 2022（AtCoder Heuristic Contest 017） - AtCoder

そのあと食事して日記を書き、午後2時からUniversal Cupの1回目に参加した。Discordで通話しつつHackMDで考察メモを共有する今期のOpenCupと同じスタイルで、ルールも同様コピペ・検索あり、コーディングは同時に一人まで。

今日のセットは中国のICPC由来でShenyang Regional。コンテスト後にQOJにも上がった。

The 2022 ICPC Asia Shenyang Regional Contest - Dashboard - Contest - QOJ.ac

チームでDCAEFLIHの8完。自分はCAEIHを解いた。最終順位はShenyang Regional参加チームも含めて24位。

コンテストが始まってすぐ問題を3等分して読み始めた。先頭から読んでいたところもうDにACが出始めたらしいので、かっつさんに読んでもらったところ、一瞬で通った。その後Cが通されているのを見て、すでに読んだものを改めて考えてみると自明。これもすぐ通った。

しばらくしてAFLが通され始めた。チームメイト二人がFLを考察しているらしい。一応問題概要は読んだが、Lは解けていそう、Fは天才構築に見えて何もわからなかったので、Aを考え始めた。絶対値記号を含む式を二重積分すればよさそうで、端点を集めて区間を区切りそれごとに計算すれば解ける。PCが空いていたので書き始めた。

書き始めてすぐ、積分範囲の点が有限個しかない場合の処理が思ったより面倒なことに気づいたが、PCを空けても使う予定がないとのことだったのでそのまま考え考えコードを書いていた。1時間以上経過してようやく完成。サンプルのほかにいくつかWolfram|Alphaで計算したものも試してから提出。見事一発で通った。

次にEを考え始め、結構すぐに残す橋の本数で包除原理をすることを思いついた。これは偶奇にしか興味がないので、状態数を別のことに使える。まだPCが空いていたので書き始め、頭が混乱したときに2乗の木dpになっていると指摘を受けたりしつつ何とかサンプルを合わせて出したら通った。

その後Fがぷらさんによって通された。相変わらず何もわかっていないので感動。さらにかっつさんによってLが通された。小数の出力なのに判定が絶対誤差 $10^{-9}$ 以下になっていて不安という話をしていたので、真の値が1以下だから相対誤差のほうが値が大きくなり、つまり普通の誤差ジャッジと変わらないということを指摘した。

実装の間にIの考察が完了していた。 $a-b$ の値の昇順に並べると0以下の範囲とそうでないところで購入戦略が変わり、前者はインデックスの $\bmod 4$ を、後者は $\bmod 2$ を見ればわかる。1点更新をどうしようか迷ったがクエリを先読みしておけばセグ木に乗る。ノードに、そこに入っている値の数と、入っている一番左の要素を0番目としたときのインデックス $\bmod 4$ に応じた和を持てばよい。実装したら一発でサンプルが合って、半信半疑で提出したらそのまま通った。

その後は皆でHを考えていた。 $|P|\le|Q|$ とすると $Q$ の一部に $P$ が含まれるので、 $Q$ だけ考えればよい。ユニークな回文は高々 $\sum|S|$ 個しかなく、重複の削除はロリハで行える。そうやって $Q$ を全探索したうえで、まず $|P|=|Q|$ つまり $P=Q$ のケースが一つあり、残りは $Q$ から $P$ を取り除いた部分も回文になっている必要があるので、 $Q$ を回文二つに分割する方法の数え上げとなる。

回文は $\gcd$ っぽいことができたはずだと口走ったらぷらさんからARCの過去問が送られてきた。解説を見るとその通りのことが書かれていてバッチリ。だから $Q$ の回文による周期が高速に求められれば良いことになる。 $|Q|$ の約数 $d$ を全探索しても時間的には問題なさそうで、 $d$ が周期であるかを見たい。

C - 足の多い高橋君

ここで閃いた。 $Q$ の先頭 $|Q|-d$ 文字と末尾 $|Q|-d$ 文字が完全一致すれば、 $|Q|$ は周期 $d$ を持ち、特にこの周期が回文になる。この判定はロリハで行える。誰もロリハのライブラリも回文列挙のライブラリも持っていないようだったので自分が書くことにした。コンテストは1時間くらい残っているが結構ギリギリそう。ペアプログラミングっぽいことをするつもりで画面共有をしてから書き始めた。

まず回文列挙をPalindromic treeを窃盗して行う。それっぽく書き換えたら望み通りのふるまいをしてくれた。ロリハは空で書く。小文字を整数に直すとき、うっかり $0\dots 25$ にマップしていたのを壊れると指摘され慌てて $1\dots 26$ に書き直した。これでとりあえず回文の列挙はできて、周期の判定も行える。

math314.hateblo.jp

あとは $|Q|$ の約数を全探索するだけ。全体で調和級数になり間に合うと思ったがそれには $1\dots 10^6$ に対して約数を前計算しておく必要がある。vectorにpush_backしていたらそれだけで1sec以上かかるらしく、大きめの周期を持つように作ったランダムケースでTLの3 secをギリギリ超えてしまった。

ロリハの法を2種類から1種類にして提出したところ、TLEはしなかったもののWA。実装ミスではなくハッシュの衝突だと信じ2種類に戻して、代わりに約数列挙を $1\dots 99$ まではその場で試すように書き換えたらなんと通った。コンテスト終了17分前だった。ロリハを構造体や関数を用意してきちんと実装したのが後から便利だった。

もう解ける問題はなさそうと終了モードに。全員時間に余裕があるとのことなので、1問ずつ振り返る感想戦をお願いした。自分の分については上に書いたので割愛。

Dはかなり素早く通ったなという感想だったが、問題文を確認すると結構長くてびっくり。どうやらほとんどの部分はLoLの世界大会とプロチームの話をしているらしい。その知識があると読み飛ばせて楽とのことで、分担が思いがけず良かったということになる。

Lは実装担当がかっつさんだったが、考察の初手はぷらさんらしい。1回の攻撃ごとに必ず1体死ぬというもので、結構非自明だと思う。一瞬で出てきたらしくすごい。それにしても早い段階で解けていそうと思ったのにその後なかなか実装されなかったのが気になる。自分がそう思っていると伝えるコミュニケーションが足りていなかったのかもしれない。

午後8時前に解散。食事して午後9時からABC287に出た。

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) - AtCoder

AはとりあえずC++で書いてから、Perlからgrepを呼び出して数えるコードを提出しておいた。Bは愚直に探索。最初に $S$ と $T$ を全部読み込んでから判定しなければならないのが面倒。 $T$ 、 $S$ の順に与えられていれば $S$ は読みながら処理ができるのに。

Cは次数1の頂点が二つで残りが次数2の頂点であることをまず判定。サンプルも合って提出しようとするときにサンプル3の説明画像でループを目にして、グラフが非連結の場合に間違えることに気づいて慌てて書き直した。

Dは $S$ の左右からどこまでマッチさせられるかそれぞれ探索し、その情報を組み合わせればよい。

Eは文字列を辞書順ソートして隣接する文字列のペアだけLCPを計算すれば十分である。LCPの計算も愚直に行ってよい。比較に $\min(|S_i|,|S_j|)\lt|S_i|+|S_j|$ だけかかると評価すれば $O\left(\sum|S|\right)$ だとわかる。Suffix ArrayからLCP Arrayを構築するのにアルゴリズム的工夫を要求されるのは $\sum|S|=N(N+1)/2$ だから。

Fは2乗の木dp。先ほどUniversal Cupでも見たので何を使うかだけはすぐわかり、意気揚々と書き始めたが、実装を終えてサンプルが合わないのに気づいてから部分木の根を使ったか使っていないかも状態に持つ必要があることに気づいた。思ったより面倒。

Gは解法は一瞬だが実装に苦労。得点を先読み座圧してセグ木に乗せ、どの得点のカードが何枚使えるかと総得点を持つ。そういえば座圧セグ木もUniversal Cupで見たばかりか。この上で二分探索することでどの得点のカードまで使うかが判定できる。それより大きな得点のカードは全部使い、足りない分を調整すればよい。得点や枚数の書き換えにちょっと苦労してしまった。

Exは微妙なサイズの制約が気になる。番号が小さい頂点から順番に見つつ、今見ている番号以下の頂点だけを使って行き来できる頂点のペアを管理する。具体的には $N\times N$ のテーブルを更新していく。これはbitsetを使うとワードサイズを $w$ として $O(N^3/w)$ で行える。代わりに、具体的にどのタイミングで行き来できるようになったかがわからないが、これは並行二分探索を行うことで対処できる。これで $O((N^3/w+Q)\log N)$ になった。

1WAを出した。頂点 $u$ を見ているとき、 $s_1\rightarrow s_2\rightarrow u\rightarrow t_1\rightarrow t_2$ というパスを考えなければならない。 $s_1\rightarrow s_2$ と $t_1\rightarrow t_2$ は前に計算しておいたテーブルで、 $s_2\rightarrow u\rightarrow t_1$ は入力されたグラフになる。ところが $s_2$ を抜かして考えていた。サンプルが弱すぎる……。

1WA全完で19位。賞金には遠いかと思ったら上位にそれほど学生がいないようで、ペナがなければ滑り込めていたらしい。

Exは新しい頂点を見るたびにクエリの処理を行う $O(N^3/w+QN)$ でよかった。 $QN$ の最大値を $2\times 10^7$ ではなく $2\times 10^8$ と計算間違いしていた。たとえそうだったとしても通りそうな気はする。さらに、行き来できる頂点のペアのテーブルに更新がある度bitsetの_Find_firstと_Find_nextを使って列挙することで、 $O(N^3/w)$ で全点対間の答えを求められるようだ。

コードゴルフ。AはVimに負けていた。多数決を取るときにソートしてから50%でカーソル移動して真ん中の行の文字列を見る方法があるのは既出だが、そこから答えの出力を分けるのは自分では書けなかっただろう。

BはRubyで、 $T$ をまとめて正規表現のORとして表現しマッチする方針を書いた。しかしその後、判定したい文字列の4文字目以降と同じものが入力された文字列に存在するか見る方針で縮められた。これだと $T$ の判定が必ず失敗するので、わざわざ避けておかなくてよい。

EはRubyで縮めてみたがPerlに負け。文字列のXORを取ってヌル文字を探すことで、先頭からどこまで一致するのか一発で判定できるのがめちゃくちゃ強い。他は手付かず。

今日も音声入りで画面を録画していた。少し編集して投稿。

www.youtube.com

ずっと日記を書いていた。午前11時半就寝。

01/29(日)

午後7時起床。

昨日のUniversal Cup-Hの話で、回文の長さの約数列挙が $S=\sum|S|$ として $O(S\log S)$ に本当になるのかと指摘された。例えば $S/2$ くらいの高度合成数を長さに持つユニークな回文が $S/2$ 種類あるケースはないのか。考えた結果、2種類の回文が交差していたらその部分の文字列があらかた固定されて3種類目が交差できなさそうに見えたので、そういう説明をした。正確な証明はつけられなかった。間に合っているのでヨシ！

布団から出て食事し、午後9時からARC155に出た。

AtCoder Regular Contest 155 - AtCoder

Aから難しかった。昨日のUniversal Cup-Hに引きずられて考察がまとまらない。とりあえず $K\lt 2N$ のケースは真面目に判定できる。 $K\ge 2N$ のケースは $S'$ が周期 $2N$ を持つので、 $K\lt 2N$ のケースと同様に両端の文字列を求め、それが整合するか調べればよさそう。もうちょっと簡単になりそうに見えたがどうにもならないので書き、一発AC。25分くらいかかっていて辛い。

Bも難しい。 $||x-a|-b|$ のグラフがどういう形をしているか調べ、高々4つの区間にある傾き $\pm 1$ の線分として表現できると分かった。この区間と出力クエリの区間の端点を全部混ぜてソートすると、区間の中では右端または左端しか見なくてよい。これは遅延セグ木に乗る。ノードに対して対応する区間の端点を持ち、切片を情報として更新すればよいのだ。

ほんまかと思いながら実装。1WAしたがこれは出力クエリで $a=b$ となるケースだった。対応するノードが1個もないので $\infty$ が返ってしまう。無理やりノードをねじ込んで対処した。結局端点の情報はノードが持っているから、それさえ正しい値なら良いのだ。

Cはスムーズに考察できた。操作が可逆なので、 $A$ と $B$ 両方を何らかの正規形に直して一致するか判定する方針を考えてみる。まず、奇数が1個もなかったり、あっても離れている・偶数が存在しないといった理由で奇数を含むような操作ができない場合は、間の偶数を適当にソートしたもので比較する。ただし偶数が2個以下だった場合は操作できないのでそのまま。

奇数を含むような操作ができる場合、操作を繰り返して奇数要素を先頭に集めることができる。そして今偶数が1個以上あるのだから奇数の隣接swapが可能、つまりソートできる。偶数は2個以下ならそのまま、3個以上あればソートできるので、これらを結合したものが正規形になる。出したら一発で通った。

Dは $G$ を状態として小さいほうからdpすれば答えは出ると思ったが、 $\gcd$ 操作による遷移先を列挙するのが難しい。約数を列挙したり包除原理したりして何とか実装できたと思ったものの、間に合わなかったしそもそもWAだった。

3完75位。Bはやはり想定解ではなかった。コードゴルフは何一つ行っていない。

コンテスト後30分ほどDと格闘した結果03_rand3_*.txtというケースだけ全部落ちるようになり、何もわからないままCF combinedに出た。

Dashboard - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

Aは $x^y\cdot y+y^x\cdot x=xy(x^{y-1}+y^{x-1})$ と変形。べき乗が嫌なので $x=1$ としてみると $2y=n$ となるから、 $n$ が偶数なら $y=n/2$ でよい。またこの式の値は必ず偶数になるようなので $n$ が奇数の場合解なしだともわかる。

Bは常に $p=1$ としても損しない。 $\sum a\cdot p$ の最大化のためには異なる素数はできるだけ積の形にして $a$ とするのがよい。同じ素因数を二つ以上含まないような数を貪欲に $n$ から取ればその和が答えとなる。

Cは各 $x$ が取りうる値の範囲がわかるが、もし最適解がこの範囲の端点にない $x$ を使っていれば、どちらかの端点に寄せても損しないとわかる。よって $x$ の取りうる値が範囲の左端・右端の二通りとなり、dpできる。

Dは、まずそのままの状態でループするなら、経路の途中からループしない点もしくは範囲外に飛ばす必要がある。ループしない点をあらかじめ数えておいて経路上の点を一つずつ見て足し合わせればよい。そのままの状態でループしないなら逆に飛ばしてはいけない点を考える。これはループする点もしくはループしないとしても今いる頂点にたどり着いてしまう点で、後者は逆向きの辺を張って探索し求めた。

Eは $\bigoplus_{i=1}^n i$ が $k$ の偶奇によって $0$ か $x$ か決まる。これが満たされていると、まず $k-1$ 個の部分列に分け、最後に余ったものをひとまとめにするという方法で構築できる。部分列に分ける際は $[i,x\oplus i]$ という2要素のものしか考えなくてよい。そうでなければ、適切に1要素選んでそれ以外をひとまとめにし、別の部分列の要素と交換することで2要素に直せるから。

Fは大変だった。本当は $a^{2^k}$ を考えなければならないのに $a^{k+1}$ を考えたまま実装まで終えてしまい結構時間を取られた。もともとの $a$ に長さ $l$ のループがあると、 $2^k$ ステップ後には $g=\gcd(2^k,l)$ として $g$ 個の長さ $l/g$ のループに分解されている。

逆に $a'=a^{2^k}$ に長さ $l$ のループが $x$ 個あれば、これを束ねて長さ $xl$ のループを作れそう。最小化すべき値は実はループの個数を数えているので、できるだけたくさん束ねるべきである。 $x$ の条件は $\gcd(2^k,xl)=x$ 、つまり $x\mid 2^k$ かつ $\gcd(2^k/x,l)=1$ 。 $a^{k+1}$ と誤読していたときは約数を見ながらdpしないと最適な $x$ が求まらなくて大変だった。それでも約数が少ないので一応解けはするはず。

今は単純な場合分けで分かってしまう。 $l$ が奇数なら $x$ は $2^0\dots 2^k$ を自由に選べる一方、 $l$ が偶数なら $x=2^k$ と確定する。復元は実際に $2^k$ 個置きに並べてループを作ればよい。実装が結構しんどかったが出したら一発で通った。

ここまではそこそこよかったが以降GもHも解けず。Hは $k$ の降順にソートすると $O(n^2)$ のdpが書けて、そこから先に進めなかった。

システスは全部通り6完50位、2887→2905(+18)。4か月振りに2900台に帰ってきた。結構長かった。

このコンテストも音声入りで画面を録画していたので、ノーカットで投稿した。3時間以上あってAviUtlの初期設定だと読み込み切れなかった。喋りながらRatedに出るのは初めてだったが、式を書きながら読み上げるだけでは何もわからない。やっぱり何とかして考察メモを画面に映す必要がある。

www.youtube.com

日記を書いて布団に入り、少しなろうを読んでいたら寝落ちした。午前9時過ぎだった。

2023-01-23

週記（2023/01/16-2023/01/22）

01/16(月)

午後4時起床。30分近くかけて布団から這い出てインターン先の定例会・勉強会に参加した。

先週の進捗は、金曜日の1on1でこの1週間何をするか決まったということのみ。まだ手を付けていない。簡単な修正なので、今週金曜日にある次の1on1までに終わらせることを期待されている。それくらいはさすがに達成したいものだ。

勉強会はKaggleの参加記だった。最近終了したコンペでめちゃくちゃ良い順位を達成されたらしい。機械学習は使わなかったとのこと。そして、機械学習を使わない解法が強いコンペだということが、順位表の上にいるチームの顔ぶれから分かりやすかったということが語られていた。競プロで順位表から得られる情報といえば問題の難易度がメインで、誰それが解いているから解法は○○だという推論は当てにならないと感じている。このあたりKaggleと結構違うのかも、と面白く思っていた。

とても好きな音MADが流れてきた。「テイキョウ・ヘイセィ・ダイガク」と言えば超有名な音MADだが、それとは別の人が勝手に裏バージョンを名乗って投稿している。正直ただの二番煎じだろうと思いながら見たらかなり完成度が高くてびっくりした。テンプレをなぞるだけではなく独自性もしっかりあって、しかも滑っておらずちゃんと面白い。このくらいネタが盛りだくさんのほうが好みだから、正直本家より好きかもしれない。

www.nicovideo.jp

先週の週記を書いていた。午後9時過ぎに投稿。いつものように校閲できていない。火曜日のセミナー準備のため月曜日に時間が取れないのがかなり厳しい。火曜日夜以降だと気持ちが離れてしまっている。

Amazonでパスタやパックご飯を購入した。少し前にお酒を買った時もそうだったが今日もAmazonポイントが使えず、なぜだろうと調べたところ、どうやらAmazonギフト券との併用ができないらしい。ほぼ確実に、自分のギフト券残高がなくなるより今のAmazonポイントが無くなるほうが早いだろう。今はほんの数百円程度なので諦めも付く。

セミナー準備を始めた。先週以下のようなことを言っていたが、今日に至るまで結局何もわかっていない。深夜までもう一度粘ってみるもどうにもならなかった。

昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

とりあえず助けを求めるツイートをして、明日のセミナーはここを飛ばして先の話を始めてしまおうかなと考えていたら、maspyさんからリプライを頂けた。そこにあった資料や方針を確認し、確かに行けそう！という気持ちに。ということでこれを発表することにしたのはいいのだが、その時間から読解して発表できる形に持っていくのに苦労し、午前5時までかけて何とか完成させた。

方針として、サイクル C、点 p に対して

f(p) = p から右方向に無限に進んだときに C を交わる回数

とて、f(p) の偶奇で内外を特徴づけることを目指します（競プロでもあるやつ）。

微小な回転により線分と辺が重なるなどが起きないとしてよくて、ぴったり頂点を通るところは適切に定義します。
— maspy (@maspy_stars) 2023年1月16日

ゴミを出して午前6時前就寝。布団に入ってから完成したと思ったセミナー準備の穴に思い至り、修正を考えながら寝入った。

01/17(火)

午前9時半起床。大学に向かい、購買でパンを買ってから教室に行った。購買が開店するのはセミナー開始と同じ午前10時なので、今日も微妙に遅刻ということ。

午前中は同級生の発表。今日はη-変換に関する定理を二つ示していた。証明はラムダ式の構成を見て丁寧に行う必要があり、大変そうだった。

午後0時半に終了し、購買で昼食を買って、食べている間に博士課程の方のセミナーが始まった。先週資料による定義の食い違いを発見したが、これは博士課程の方が本を誤読していただけのようだ。しかしそれ以外の部分も複雑で解釈に疑問が残る。定義がどう使われるかは別の論文を読む必要があるらしく、今日は解決されなかった。次回以降で解決されるのかもわからない。

本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

午後2時過ぎに終了。少し休憩して半から自分のセミナーとなった。昨日寝る直前に発見したミス以外の部分は問題なく発表できたはず。ミスは結局修正できていないので、今日は諦める気満々だったが、なんだかんだ先生と同級生は1時間くらい考えていた。自分は早々に諦めてmaspyさんにリプライを送っていた。結局解決せず、午後5時過ぎ終了。

すいません、「左から順にPi……」のくだりで詰まりました。3つのregionのどれかが非有界であることを示したりしたいのですがどうにもなりません。何か手はないでしょうか
— こたつがめ (@kotatsugame_t) 2023年1月17日

学食で食事して帰宅。自分が入店したすぐ後5限終了の時刻になり、レジ待ちの列が学食の外まで伸びていた。

疲れ果てて帰宅し、かなり長い間YouTubeを見たりTLを見たりしてボーっと過ごしていた。この後は何をしようかなと考えて、ふと思い立ってICPCの参加記を完成させにかかった。ほとんどの部分は年明け最初の週に完成していて、あとはまとめっぽい部分を書くのと文章の手直しをするだけ。相変わらず時たまYouTubeを見ながらの作業だったため結構時間がかかり、投稿は午前2時になった。

kotatsugame.hatenablog.com

今回は5年間の振り返り記事も同時投稿。といっても大会の成績と参加記をまとめただけで特に何か文章を書いたわけではない。本当は書こうとしたのだが、そういうのは横浜の参加記のほうにまとめて、振り返り記事は単なるまとめページの意味合いでできる限りシンプルにしておいた。

食事してからまたYouTubeに戻り、しばらくして布団へ。なろうを読んでいたら寝落ちした。午前4時くらいだった。

01/18(水)

午後1時から2時までは起きていた形跡がある。なろうを読んでいた。

午後6時起床。布団でしばらくスマホを触ってから起き上がった。

今日は生命情報システム科学のレポート提出期限。相変わらずClassroomの課題には期限が設定されていないが、講義スライドにそう書いてあった。まったく非道なことをする教員である。

今回の課題は与えられた二つのデータを観察し比較して考えを述べよというもの。扱うデータはFASTQ形式で与えられており、この形式は単純なのでライブラリに頼らずとも自分で簡単にデータ読み込みの実装ができる。比較にプログラムを使ったならそれも提出せよと言われていたので、せっかくならとColaboratoryでレポートを書いた。

特に何事もなく午後10時くらいに完成。Classroomの課題提出画面でGoogleドライブからColaboratoryのファイルを直接提出すると、そのファイルのオーナーが自分から教員に切り替わるようだ。つまり提出したものを後からこっそり修正することができなくなるわけで、連携が実にうまくできている。

ラノベを読み始めた。日付が変わるくらいに「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」3巻を読了。前半の運動会のシーンは主人公がこれでもかというくらい活躍していて、目立っていて、最高だった。その後のデートシーン二つもいい感じ。ストーリーとしてはいよいよ主人公の過去が明かされてかなり辛いが、好みのシーンが多かったため全体としてみれば良かったという感想になる。

来週は集中講義のためセミナーができない。そのしわ寄せが今週に来て、なんと明日もセミナーが行われる。朝方までそれの準備をしていた。昼からスタートで5限前に終わるため、時間が普段より短くなる。よって量も控えめでよいとのことで、昨日maspyさんに送ったリプライに頂いた返信をまとめた後、もう一つ補題を扱うだけで終えた。とはいえ今日も午前5時くらいまでかかっている。

まだ睡眠時間に余裕がある。ハーメルンやラノベを読んでいた。

今日のハーメルンは新作でも更新分でもなく、読み返し。主人公の設定もキャラも非常に好みで、この先の展開が楽しみで楽しみで仕方ない。U7のライブはおそらく行われるだろうが、どのように描写されるのだろうか。自分で妄想してニヤニヤしたりもしている。それくらい好きな作品だ。

syosetu.org

午前7時半就寝。

01/19(木)

正午過ぎ起床。大学に向かい学食で昼食を摂り、午後1時からセミナー。

前半は同級生の発表。今日は公理系をいくつか用意して何かする話。内容的にはそれなりに長くかかりそうだったが、ちょっと詰まったところで先生が切って90分ちょっとになった。

後半は自分の発表、の前に、同級生に火曜日の議論の穴を埋めるアイディアがあるらしいのでそれを聞いた。なんと見事に解決していた。一昨日maspyさんから教えて頂いた方法と異なったので、一応そちらも発表した。昨日準備した補題について少し触れて、こちらも90分くらいで終了。

購買でラノベを購入してから5限のTAへ。今日の発表は多次元空間における「球」の表面積や体積を求める話だった。この話題に関しては実は高校生の頃に調べていたことがあるので、自分にとってかなり懐かしいもの。当時は適当な座標軸に沿って切ることで一つ下の次元における球の表面積・体積に帰着して求めていたはず。今日はそうではなく、謎の等式から無理やり表面積の式を出し、それを積分して求めていた。

謎の等式について少し解説。 $n$ 次元の点 $x=(x_1,\dots,x_n)$ について $|x|=\sqrt{x_1^2+\dots+x_n^2}$ とし、値 $\exp(-|x|^2)$ を考えて空間全体で積分する。遠くに行くほど値が急激に小さくなるので、この積分値は有限。というか具体的には $\left(\int_{-\infty}^{\infty}\exp(-x^2)dx\right)^n=\Gamma(1/2)^n$ となる。

一方、 $|x|$ が同じ $x$ をまとめて計算すると、 $r=|x|$ で積分するとして $\int_0^{\infty}\exp(-r^2)S_nr^{n-1}dr$ となる。ここで $S_n$ とは単位半径の $n$ 次元球の表面積で、 $r^{n-1}$ 倍することで半径 $r$ の時の式になる。 $S_n$ は定数なので外に出せて、残りはこれまたガンマ関数で表すことができ、先ほどの式と比較することで $S_n$ が出るようだ。

なかなか難しかったが発表はかなりしっかりしていたように思う。板書の字もきれいで良かった。

学食で食事して帰宅。今日も疲れ果てておりTLやYouTubeで時間を無為に過ごした。2時間ほど経ってから2月のラノベ新刊チェックと注文の作業を行った。今回は26冊。嬉しい新刊情報を二つばかり記録しておく。

一つ目は「Vのガワの裏ガワ」2巻。1巻が出たのが11月だったから、たった3か月で新刊が出たということ。無事続刊してくれたことも嬉しいし、それがこんなに早く読めるというのはもっと嬉しい。

mfbunkoj.jp

二つ目は「世界で一番『可愛い』雨宮さん、二番目は俺。」。結構前にアイドルとかモデル、芸能人というキーワードでなろうを漁っていた時に読んだ作品で、結構好みだったという記憶がある。最後の更新から1年以上経過してほぼ忘れ去っていたところ、いきなり書籍化を知らされてびっくりした。

gcnovels.jp

その後日付が変わるまでゼミの後始末みたいなことをしていた。今日聞いた同級生のアイディアをちゃんと証明にまとめるという作業。紙に書き、スキャンして先生に送った。

ABC285-Exを解いた。形式的べき級数で表されている部分が重複組み合わせを使った和の形になって、一向に閉じた状態にできなかったため、解説を開いて結構読んでしまった。

Submission #38159986 - AtCoder Beginner Contest 285

朝方までインターンの作業をしていた。久しぶりに触ったら依存ライブラリのアップデートか何かがあって、ちゃんと動く状態にするまで結構時間がかかってしまった。それさえできれば今日実装するものは簡単……と思っていたら、ライブラリの仕様にない内部の変数を触っていた部分でうまく動かないケースがあって困ってしまった。そのライブラリのコードを読んで何とか修正したが、結局仕様にない使い方をしているままのため、これもいずれ動かなくなるのだろう。

外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。
週記（2023/01/09-2023/01/15） - kotatsugameの日記

1時間程度日記を書き、午前7時就寝。

01/20(金)

午後2時ちょっと前に起床。すぐ1on1が始まった。

自分からの進捗報告は昨日書いたコードの説明。特に問題なさそうでこれはすんなり終わった。ツールの下調べというタスクも振られていたので、残り時間はそれについて話していた。実はこのツールが要求するライブラリのバージョンと他のライブラリのバージョンが合わず、昨日もかなり苦労していた。結局どうやっても合わなさそうだと分かったが、合わないままでも動いたのでまあいいだろうということに。

終わってから大学に向かった。購買でラノベを買うだけのつもりだったが床屋が空いているのを見て思わず入店。散髪し、学食で夕食を摂って帰宅した。サークルはサボってしまった。

古典部シリーズの愛蔵版第1弾をAmazonで注文した。すっかり忘れているうちにリアル書店での予約は締め切られてしまったらしい。何はともあれ買えてよかった。Amazonギフト券を使えるのも嬉しい。

地元で買えるとそのまま実家に安置できるので嬉しいが、タイミングが合わなければ仙台の本屋で予約することになるだろう。限定生産とあるのでちゃんと予約を忘れないようにしたい。
週記（2022/12/12-2022/12/18） - kotatsugameの日記

しばらくラノベを読んで、午後9時からSRM844に出た。出場した赤以上23名のうち12名までもがRoom1に割り振られていた。

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

Easyはdp。状態と遷移を掛けると10⁸になってちょっと怖い。注意点としてcakesは昇順に使う必要がある。これをしないとサンプルで落ちるのは非常に優しかった。

Medは難しかった。 $A\times B\times C$ の直方体の表面積は $2(AB+BC+CA)$ なので、あらかじめ $N=\lfloor{\rm paperArea}/2\rfloor$ としておく。 $AB+BC+CA\le N$ が条件なので、 $A$ を最大化する場合整数という条件を無視すれば $A=B=C=\sqrt{N/3}$ となる。よって $1\le A\le\sqrt{N/3}$ がわかる。これくらいなら全探索可能。

ここからなかなか先に進めなかった。 $AB+BC+CA=(B+A)(C+A)-A^2\le N$ となるので $B+A=\left\lfloor\sqrt{N+A^2}\right\rfloor$ とするのがよいかとも考えたが、サンプルが合わない。しかし $B$ の範囲は $A\le B\le\sqrt{N+A^2}-A$ と分かった。この時 $C$ は単に最大値を取ればよいので、 $C=\left\lfloor\frac{N+A^2}{A+B}\right\rfloor-A=\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ 。

このような $B$ と $C$ に対して $ABC$ を最大化するのが目標である。 $C$ が整数という条件を忘れ、 $B\times\frac{N-AB}{A+B}$ が $B$ に対してどういうグラフになるか微分して計算してみると、 $B\lt\sqrt{N+A^2}-A$ なら微分係数が負になることが分かった。つまり先に求めた $B$ の範囲に対しては $B$ が大きくなるごとに単調増加する。

よって $B$ を降順に探索し現在の解を更新しなくなれば打ち切るという枝刈りが思いつく。解の初期値を $\left\lfloor\sqrt{N/3}\right\rfloor^3$ にしておけば十分高速そう。注意点として、 $ABC=AB\times\left\lfloor\frac{N-AB}{A+B}\right\rfloor$ ではなくあくまで $AB\times\frac{N-AB}{A+B}$ と解を比較しなければならないことに注意。オーバーフローが怖いのでfloorやceilを取って緩めに判定した。

計算量はわからないが乱数で試したところ十分高速だったため提出。この時点で20位ちょっととかなり低い順位だった。Hardには10分しか残せずそのまま終了。

チャレンジは自分は何もしなかったが、Medがボコスカ落ちていてびっくりした。さらにシステスでも大量に落ち、無事2完した自分の順位は8位まで上がった。レートは2894→2897(+3)でギリギリ耐え。赤が大量にいたRoom1はチャレンジで全部落とされ切ったようで、システス落ちが一人もいなかったのですごいなあという気持ちになった。

夜中はラノベを読んでいた。「完璧な俺の青春ラブコメ」を読了。非常に面白かった。主人公は顔も良く、勉強も運動もできて、おまけにコミュニケーション能力も高い。まさに完璧と言う他ない設定でかなり好みである。ストーリーについても、初めの方はいかにも不穏そうな空気を醸し出していたのに、恐怖していたドロドロした展開は最後までなく、純粋に楽しい気持ちで読むことができた。総じて最高。

朝まで日記を書いて午前9時前に布団に入った。ちょっとなろうを読もうとして、すぐ寝落ちしたらしい。

01/21(土)

午後3時頃に生協の弁当を受け取って、またすぐ寝た。午後6時半起床。布団でずっとなろうを読んでいて、午後8時を過ぎてようやく布団から脱出した。

昨日読んだラノベは本当に好きだったので読了ツイートに感想を書いていたが、それがアキバBlogで引用されたらしい。FFの方がツイートしていて見つけた。結構嬉しい。

「完璧な俺の青春ラブコメ」読んだ！非常に良かった、主人公が完璧すぎて最高！話も重そうな始まりだったのにドロドロしていなくて、最後までずっといい気分で読めた！
— こたつがめ (@kotatsugame_t) 2023年1月20日

blog.livedoor.jp

食事して少し日記を書き、午後9時からABC286に出た。

UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder

Aから面倒。変なことはせず素直にC++で実装したのに、区間の始点や長さを間違えまくって合わせるのに少し手間取った。Bはsedで一発。Cは文字の置換より先にrotate操作を全部行うとしてよく、その回数を全探索。

Dは個数制限ナップザック問題なので、何も考えず $B$ を2べきに分解して解いた。あとから単に $B$ 回遷移しても間に合うことに気づいた。

Eは問題文にある通りの値のペアを距離と見てワーシャルフロイド。辺の重みとしてそれが向かう先の都市で売られているお土産の価値も含めた。経路の始点については出力時に加える。

Fはfunctional graphにおいて各頂点から $N$ ステップ移動した後の頂点の情報から $N$ を復元する問題。グラフとしてはループの集まりしか考えなくてよく、このとき $N$ をループの長さで割った余りがいくらかという情報が得られる。ループの長さを互いに素にして、中国剰余定理で復元すれば良い。

難しいポイントは $N\le 10^9$ かつグラフの頂点数が110以下というところ。単に素数を並べるだけでは29まで使う必要があり、足りない。2²などべき乗を使えば良いのでは、と思いついて適当に全探索すると $2^2\times 3^2\times 5\times 7\times 11\times 13\times 17\times 19\times 23$ が見つかった。調べた範囲ではこれが唯一の解だった。

Gはちょっと面白い。歩道をマルチグラフと見ると、使った辺が全て連結で、次数が奇数の頂点が0個または2個しかない。そのように辺を選べればよい。ここで、 $S$ に含まれない辺をすべて2回通ることを考える。すると $G$ が連結という条件から自動的に使った辺も全て連結になる。あとは次数に関する条件を満たせればよい。

$S$ に含まれない辺たちからグラフを作ると、その連結成分の中ではある程度好き勝手できる。具体的には2頂点ずつ次数の偶奇を入れ替えられる。次数が奇数の点が奇数個あるとどうしても1個残ってしまうようだ。このチェックをすべての連結成分に対して行い、残った点の数が合計で2以下になっていればOK。そうでなければ不可能。

Exは結構簡単だった。線分 $ST$ が $C$ と交差しない場合は直線で向かえば良い。そうでない場合、 $S$ から $C$ 上の点に移動し、 $C$ 上で別の点に移動してそこから $T$ に行くということになる。真ん中の部分は多始点多終点の最短経路問題になる。グラフがループなので簡単に解けるが何も考えずdijkstraを使った。

問題は、 $S$ または $T$ から $C$ の内部を通らずに直線で辿り着ける $C$ 上の点をどう判定するかについて。1点の判定に $O(N)$ かかると思ってしばらく判定回数を減らす方向で考えていたが、そもそもの判定が $O(1)$ で行えた。 $p_i=(x_i,y_i)$ とすると、 $S$ から $p_i$ を見たとき右手に $p_{i-1}$ 、左手に $p_{i+1}$ がある場合 $S$ から $p_i$ に辿り着けないらしい。外積で判定できる。

出したら通った。1時間ちょっとでノーペナ全完、順位は9位。Fでループの長さの組を見つけるのに手こずっているが、それがなくても賞金には遠かった。Exは $S$ と $T$ を含めて凸包を取れば $C$ を経由するときの距離が簡単に出せるらしい。頭が良すぎる。

コードゴルフ。AはAWKで縮めていたがVimにボロ負け。行の範囲を指定すると、それを一気に別の行の下に挿入するmoveという命令があるらしい。これを知らないし、知っていたとしてもその周りの部分を縮めきれたとは思えない。

Bはやはりsedで速度差で勝ち。DはRuby。コンテスト中に自分で80Bのコードを書いたが、コンテスト直後に見ると同じ長さのコードがもう一つ提出されていて、そちらが3B縮み最短になっている。他は手付かず。

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

Dashboard - Codeforces Round 845 (Div. 2) and ByteRace 2023 - Codeforces

Aは操作で挿入される要素のparityが元の要素と変わらないため、単純に1要素削除だと思ってよい。

Bは $p$ の内部の転倒数、 ${\rm rev}(p)$ の内部の転倒数、 $p$ と ${\rm rev}(p)$ にまたがるペアによる転倒数の三つに分けて考える。前二つについては、 $p$ で転倒数に寄与するペアは ${\rm rev}(p)$ では寄与せず、逆も然り、ということで合わせて $n(n-1)/2$ になる。三つ目は明らかに $n(n-1)/2$ 。よって答えは $n(n-1)n!$ である。

Cはちょっと難しかった。smartnessを見ながら尺取り法のようなことを行う。各topicを誰が担当しているか管理し、逆に人ごとに担当するtopicの数も数えておいて、それが0になった人をチームから抜いていくという方法で行える。問題はチームに人を追加するときの処理について。

担当するtopicすべて、つまりsmartnessの約数をすべて見る必要がある。事前に $a$ の重複を取り除いておけば見る個数は十分少なくなるが、そもそも約数を列挙する部分で $O(\sqrt a)$ かかってしまう。どうしようもないので祈りながら提出したら爆速で通った。

Dはちょっと面白い。時刻 $t$ におけるある頂点の値は、そこから $t$ 段下った子に最初に割り振られた値のbitwise XORになる。そのような子が存在しなければ当然値は0。存在するとき、子から一つ選ぶと、それ以外の頂点にどんな値が割り振られていても選んだ子の値次第で0か1かが決定するから、1になる割り振り方は必ず $2^{n-1}$ 通りだとわかる。よって各頂点について値が1になり得る最大の $t$ を求めるだけになり、単なるdfsで解ける。

Eはちょっと苦労した。辺の向きを入れ替える代わりに逆辺を追加すると考えてもよい。その状態である頂点から他のすべての頂点に辿り着けるなら、通る有向パスたちは木になるように取れて、それに沿って改めて辺の向きを決定できる。

追加した逆辺込みで強連結成分分解したとき、入次数が0の成分が一つだけであるかをチェックしたい。最初に分解してあとはマージしていけば良いかと思ったら、マージで内側に飲み込まれてしまう辺を入次数にカウントし続けてしまうようで2WAした。コストで二分探索すると判定の度に真面目に分解できるためOK。

Fは分割統治。区間の最大値が固定できると、考える値は最大値と累積XOR二つのXORになって、そこから片方の端を固定するとbinary trieで最大値が求まりそう。しかしこのbinary trieには考えている区間の値だけを乗せておきたくて、少し難しい。

区間の最大値で分割すると区間の幅が抑えられないので、binary trieを構築する段階でTLEしてしまう。そこで区間の真ん中で分割することにした。ABC282-Exの解説を見ながら実装。1.8secで通った。

Editorial - HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282)

1時間17分で全完、25位。

ベッドのシーツや掛け布団がずっと春・秋用だったのを冬用に変えた。流石にもう耐えられなかった。ちなみにTwitterや日記でずっと布団という言葉を使っているが、これは自分にとって寝床一般くらいの意味合いで、実際はベッドで寝ている。

ABCの画面録画＋音声をYouTubeに投稿した。編集は一切行っていない。実況と銘打っている通りコンテスト中はあれこれ口に出しながら解いていたつもり。普段はわざわざ音声を入れないのだが、今日はたまたまその気になっていた。そういうタイミングで全完できたのも運が良かった。

www.youtube.com

朝までなろうを読んでいたが途中で放棄した。興味が薄れたのと、やらなければならないタスクが溜まっていたから。一応記録しておく。

https://ncode.syosetu.com/n7707gs/

日記を書き、さっきとは別のなろうを少し読んで午前11時就寝。タスクが溜まっているとは何だったのか。

01/22(日)

午後6時起床。そのまま布団でなろうを読んでいたら、午後7時半頃に今日の昼行われたJOIG本選の過去問が上がっているのを見つけ、飛び起きた。

JOIG 2022/2023 本選過去問 - AtCoder

Aはよい。Bはまともな性質がなさそうだが単に $O(N^2)$ でシミュレートすればよい。Cは音の強さが固定なので、家から最も近い座標を左右で求め、比較すればよい。

Dは葵が操作する行を全探索し、各列の表のコインと裏のコインの枚数を差分更新する。凛はそれを見て貪欲に操作すればよい。 $O(HW)$ 。

Eは $k$ を全探索すると左右が分割できるので、それぞれ解ければよい。実際、 $HW$ 頂点のUFを持って見ている範囲の頂点だけマージしていけば可能。

Fは解けていない。

コードゴルフ。Aは追加してから条件をチェックして削除すると書きやすい。sedで実装して満足していたらVimで縮められた。Bは真面目に数列の要素を一つずつ減らしていかなくても必要な値は計算できる。これで結構縮んだが、まだ隙があったようで取られた。CはOctave。以降は手付かず。

午後9時からARC154に出た。

AtCoder Regular Contest 154 - AtCoder

Aは $A$ をできるだけ小さくするのが最適とエスパー。桁ごとに数字を見て、 $A$ のほうが小さくなるようにswapしていけばよい。

Bは操作を分解し、最初に削除を全部行ってそれから挿入すると思ってよい。 $S$ と $T$ を構成する文字の種類・数が異なれば一致させることができない。そうでない場合、削除しなくてよいのは $S$ のsuffixであって $T$ の部分列になっているもののみだから、その長さの最大値を求める。

Cは $i=N$ で操作できるのでちょっと難しい。もしこの操作ができなければ、要素をコピーして区間を広げていくと思えるので、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっていることが必要十分条件になりそう。正確には要素が後ろにコピーできないので少し違う。

$i=N$ で操作するのは $A$ をrotateするのとほぼ同じに見えた。そこで、逆に $B$ をrotateしてから先程の判定を行うことにした。rotate状態が $N$ 種類あって毎回 $O(N)$ で判定可能なので、間に合う。しかしWA。

冷静に考えると、 $B$ のどの隣接する2項も等しくなければrotateはできない。この場合はそもそも操作後の状態としてはありえないので、最初に $A=B$ であるか判定するだけでよい。逆にそういう2項がある場合はそこを使って $B$ をいくらでもrotateできるので、最初にちょっと触れた「要素を後ろにコピーできない」制限も回避できる。これで出したら通った。

Dは難しかった。質問の回答がYesだとあんまり情報がないため、なんとかしてNoを見つける必要がある。 $i=j$ とすると見つけやすいのではないかと考えた。 $k$ を固定し、 $i=j\ne k$ に対してすべて聞くことで、 $2P_i\le P_k$ なる $i$ を集めることができる。これを何回か行うと $P_k=1$ なる $k$ を見つけることができる。

今度は再帰の帰りがけに各要素の値を決定していくのかと思っていたが、実はこの時点で $P$ をソートすることができる。 $P_l\ne P_r$ という条件のもと、 $P_l\gt P_r\Leftrightarrow P_l+1\gt P_r$ となるからだ。

最初に $k$ を見つけるとき、固定する $k$ をランダムに決めることで候補が4分の1になることが期待できる。後からソートする分も合わせるとクエリが微妙に足りない気もするが、とりあえずジャッジを書いて手元で試してみることにした。

std::sortを使うと全然足りなかったが、std::stable_sort、つまりマージソートを使うことでかなりいい感じになった。数回試して通りそうだったので提出。最初の提出では1ケース落ちてしまい、実際手元のランダム順列でも落ちるケースを発見したものの、乱択だから何回か出せば通るだろうと思って全く同じコードをもう一度出したら通った。

残り1時間はEとFを半々くらいで考えていた。Eは何もわからず。Fは下の記事と同様にして $k$ 種類持っている状態から新たに1種類ゲットするまでにかかる回数の確率変数を $X_k$ とおくと、 $f_k(x)=\sum_n E[X_k^n]x^n/n!$ という指数型母関数を $k=0\dots N-1$ で掛け合わせられれば解けることまではわかった。

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語

4完32位。コードゴルフはAをRubyで縮めたのみ。

今日も画面録画＋音声を撮っていたので、YouTubeに投稿した。E以降はバッサリカットした。最近新しい動画が見たいですというコメントを頂いたので、昨日今日とマイクに向かって喋りながらコンテストに出てみた。しかし編集する余力はない。ゆっくり実況など夢のまた夢である。

またUnratedのコンテストしか動画にしていないのもちょっと気にしている。本当はAGCの実況を作ってみたい。しかし今の形式だと紙の上での試行錯誤が動画に反映されず、面白くなさそう。板タブで書くのは面倒だし、紙に書くと動画で見えない。やはり手元を映してみたい。

www.youtube.com

実は、コンテスト参加時の画面の録画自体はここ2年ずっと行っている。今その動画ファイルが300GB以上あってPCのSSDを圧迫しているが、しかしこれはShadowPlayでキャプチャした動画ファイルをそのまま保存しているからで、適当にエンコードしておけば6分の1くらいになることに気づき、今日はそれからずっとエンコーダーを動かして圧縮に勤しんでいた。

エンコードしているPCはCPU使用率が100%に張り付いて使いづらいので、別のPCで日記を書いていた。また結構な頻度でなろうに気を取られていた。

午前8時過ぎに布団に入る。なろうを読んでいたら午前9時頃寝落ちした。来週一週間、午後3時から6時まで集中講義である。ただ明日はオンラインになったのでこの時間までのんびり起きていた。

2023-01-18

Aobayama_dropoutのまとめ

Aobayama_dropoutの5年間を振り返ります。

2018年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	31位（4完）
国内予選	40位（4完）	ICPC2018国内予選参加記 \| puzzleknot 公式サイト
JAG夏合宿		JAG夏合宿・ACPC2018 参加記 - kotatsugameの日記
		JAG夏合宿2018 参加記 \| puzzleknot 公式サイト
アジア地区横浜大会	21位（4完）	ICPCアジア地区横浜大会 2018 参加記 - kotatsugameの日記

2019年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	17位（4完）	ICPC模擬国内予選 2019 参加記 - kotatsugameの日記
国内予選	7位（5完）	ICPC国内予選 2019 参加記 - kotatsugameの日記
JAG夏合宿		JAG夏合宿2019 参加記 - kotatsugameの日記
		JAG夏合宿2019に参加しました - aokabic
アジア地区バンコク大会	19位（6完）	ICPC Asia Bangkok Regional 2019 参加記 - kotatsugameの日記
		ICPC Asia Bangkok Regional 2019に出場しました - aokabic
アジア地区横浜大会	16位（5完）	ICPCアジア地区横浜大会 2019 参加記 - kotatsugameの日記
		ICPCアジア地区横浜大会2019に出場しました - aokabic

2020年

メンバー

AokabiC
Yukly
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	10位（6完）	ICPC模擬国内予選 2020 参加記 - kotatsugameの日記
国内予選	13位（5完）	ICPC国内予選 2020 参加記 - kotatsugameの日記
模擬地区予選	12位（7完）	ICPC模擬地区予選 2020 参加記 - kotatsugameの日記
アジア地区横浜大会	10位（8完）	ICPCアジア地区横浜大会 2020 参加記 - kotatsugameの日記

2021年

メンバー

Yukly
ha15
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	5位（7完）	ICPC模擬国内予選 2021 参加記 - kotatsugameの日記
国内予選	8位（5完）	ICPC国内予選 2021 参加記 - kotatsugameの日記
模擬地区予選	8位（9完）	ICPC模擬地区予選 2021 参加記 - kotatsugameの日記
アジア地区横浜大会	8位（6完）	ICPCアジア地区横浜大会 2021 参加記 - kotatsugameの日記

2022年

メンバー

ha15
mine691
kotatsugame

記録

大会名	順位（完数）	参加記
模擬国内予選	2位（7完）	ICPC模擬国内予選 2022 参加記 - kotatsugameの日記
国内予選	13位（5完）	ICPC国内予選 2022 参加記 - kotatsugameの日記
模擬地区予選	14位（6完）	ICPC模擬地区予選 2022 参加記 - kotatsugameの日記
アジア地区横浜大会	9位（6完）	ICPCアジア地区横浜大会 2022 参加記 - kotatsugameの日記

2023-01-18

ICPCアジア地区横浜大会 2022 参加記

2022/12/27-2022/12/28に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーはha15さん・ホスフィンさん・僕です。

これが自分にとって5回目、また早生まれでないため最後のアジア地区大会です。さらに2019年以来3年ぶりにオンサイトで開催されたということで、なかなか感慨深いものがありました。

前日（12/26）

日付が変わるくらいまで持ち込むライブラリの準備をしていました。自分のライブラリほとんどに加え他の人のライブラリからいくつか、さらにACLから二分探索付きセグ木も持ってきてA4用紙10枚分くらいになりました。特に写経のことは考えておらず、コピペ前提の長大なコードもそのまま印刷しました。

GitHub - kotatsugame/library

他の人のライブラリから窃盗してきたコードは以下の通りです。ほぼお守りみたいな感じです。

その後チーム紹介ドキュメントのメイキング記事を書いていたら寝るのが午前4時半になってしまいました。

1日目（12/27）

無事午前8時に起床し、午前9時半の新幹線に乗りました。自由席のない速い列車なので東京駅までは1時間半ほどです。車内では爆睡していました。

東京駅に着いて新幹線ホームでコーチのむげんさんやチームsuzukaze_Aobayamaの三人と合流し、そこから横浜駅に向かって自チームの残り二人とも合流しました。ちょうどお昼時だったので、横浜駅のレストラン街で昼食を摂りました。

午後1時ごろに会場に到着し、当然チーム全員が揃っているためすぐ入場しました。開始まで1時間ほど時間があるので、チーム紹介ドキュメントを読んだり、他チームと交流したりしていました。

午後2時に挨拶があって、リハーサルが開始されました。今年は4問で、Aは簡単枠、Bはインタラクティブの練習、Cはちょっと前のアジア地区A問題、Dはもっと昔の過去問でした。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1400

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1379

ホスフィンさんがAをさっと通したあと、自分がBを通しました。US配列に慣れておらずかなり苦労しました。またこのとき、Vimを使う自分とhaさんで.vimrcに書く内容について合意を取っておきました。と言ってもタブ幅と自動インデントに関することだけなので、ほんの数行です。

その後は特にやりたいこともなさそうだったので、そのままPCを占拠しDを実装しました。この問題はリハーサルの場で何度か見たことがあって、記憶の通り書いたらFAでした。

残ったCはhaさんに押し付けました。問題なく通りましたが、実装されている間に順位表が凍結され、YesNoがあるわけでもないので、結局他チームがどのくらい解いたのかはわからないままです。

その後assertや副作用のない無限ループを書いてREやTLEがちゃんと出ることを確認していました。また印刷も色々試しました。メモ用紙が欲しい場合は適当なファイルを印刷してくださいとのことだったので、/dev/nullを印刷したところ、1文字以上あるファイルを印刷しないと紙が出ないと言われました。

オンサイト豆非知識ですが、実は0バイトのファイルを弾くという処理が1日目終了後に追加されました
— くりんぺっと (@climpet) 2022年12月28日

リハーサル後はチーム紹介です。自チームのスライドが表示された瞬間笑い声が上がったので、作った側としては報われた気持ちになりました。

チーム紹介の時間です。各チーム、ユニークなスライドを送ってくれました。 pic.twitter.com/75SD69TOdf
— ICPC2022JP (@icpcjapan) 2022年12月27日

全チームの紹介が終了し、解散してホテルに着いたのが午後5時半ごろでした。今日泊まるホテルは単にsuzukaze_Aobayamaと揃えただけですが、たまたま3年前と同じでした。ホスフィンさんと同室です。

1時間くらいしたら東北大勢全員で中華街に夕食を摂りに行くことになっていて、それまでの間に昨日書いたチーム紹介ドキュメントのメイキング記事を微修正して投稿しました。

再三強調しておきます。このコードは実行すると自分自身のソースコードをそのまま出力するプログラムになっているので、ぜひお手元で実行してみてください。チーム紹介に「Quine」と書いておきましたが、この語彙は一般的でなく、あまり伝わっていない感触がありました。

kotatsugame.hatenablog.com

中華街では当然中華を食べました。

食事
・青島ビール
・コーンスープ
・牛バラ肉の醤油煮込み
・マーボー豆腐 pic.twitter.com/OyAFeJiHZT
— こたつがめ (@kotatsugame_t) 2022年12月27日

・炭火焼きチャーシュー炒飯
・ゴマ団子
・愛玉子（オーギョーチー）←自分
・マンゴープリン pic.twitter.com/a7rkqLgyFr
— こたつがめ (@kotatsugame_t) 2022年12月27日

ホテルに戻ってから、US配列に慣れるため持ってきたキーボードを使ってPCKの問題を解いていました。このキーボードは2019年、アジア地区横浜大会の企業賞で獲得したものです。

LegalForce様からUS配列のキーボードをいただくことができました！
ICPCアジア地区横浜大会 2019 参加記 - kotatsugameの日記

午後11時半ごろ就寝しました。その時間からCF div.2がありましたが、流石にパスしました。

2日目（12/28）

午前6時半に起き、ホテルの朝食を摂って、部屋に戻ってきてからは昨日のCF div.2を解いていました。結局チームで集合する午前8時半までに解き終わらず、ホテルから会場に向かう途中で実装を終えてテザリングで提出しました。なんとか通りました。

午前9時前に会場入りし準備をして、いよいよコンテスト本番です。

コンテスト

問題文：https://icpc.iisf.or.jp/2022-yokohama/wp-content/uploads/sites/9/2022/12/all_with_cover.pdf

順位表：https://icpcsec.firebaseapp.com/standings/

序盤

全員で使うようなテンプレもないので、序盤の動きについてはあまり細かく決めていませんでした。.vimrcについては、自分が書くときにはいつの間にか必要なものが整備されていました。

ホスフィンさんがシステムへのログインとAを、haさんがBを担当し、自分はC以降を順に読んでいました。以下、読めた分までの各問題の印象です。

C：明らかにフローっぽい見た目をしていますが、どうすればいいかは全くわかりません。シャッターを「2枚」壊すというのはどうやって表現するのでしょうか。

D：ずらすコインを全探索して、平行移動はバウンディングボックスを見る、ということをしたくなりました。しかし実装もコーナーケースも辛いし、そもそもこの全探索は間に合いそうにありません。

E：dpの高速化を考えます。最近ABCで見た分割統治をしてみたくなりました。 $\bmod{998244353}$ が2べきを強調する形で書かれているので、統治部分では畳み込みをするのではないかと疑いましたが、効きそうな形にできませんでした。

F：適切な言い換えができるかどうかという問題に見えます。すぐには思いつきません。

G：木から辺を1本削除し、1本追加してできた新しい木において、特定の2頂点間の距離を最大化します。説明のため2頂点を $s$ 、 $t$ とおきます。削除する辺はもともと $st$ パスに乗っていたものとしてよいです。どれを削除するか全探索すれば解けそうに見えました。

Gを詰めているうちに、グリッドという問題設定を完全に忘れ去ってしまいました。どういうことかというと、どんな辺でも追加してよいと勘違いしたのです。この場合、辺を削除してできた二つの連結成分それぞれで $s$ 、 $t$ から最も遠い頂点を選び、結ぶのが最適です。実装もやればできます。

このあたりですでにAは通っており、Bも提出が行われました。残念ながらWAだったのですが、ただの出力形式ミスだったのですぐ直り無事2完となりました。インタラクティブではこういうミスはありがちで、まあどうしようもなかったと思います。

G問題

Gの考察をうまく伝える自信がなかったので、自分で書いてしまうことにしました。順位表を確認すると、AB以外にACが出ているのはDEFのみのようで、FAが狙えるかもとワクワクしました。

しばらくして書き上がるも、サンプルが合いません。ここでようやく勘違いに気づきました。それと同時にまだACが出ていないことにも納得が行きました。諦めてPCを空けようとしましたが、その時点では特にすることもなかったため、そのままPCの前に座っていました。

冷静になると、追加する辺 $uv$ を全探索する方針が生えます。 $st$ パス上で $u$ から最も近い頂点を $p_u$ 、 $v$ から最も近い頂点を $p_v$ と置くと、 $p_u\ne p_v$ を満たす場合のみその間の辺を削除することで $st$ パスが $uv$ を経由するようになります。

各頂点 $u$ に対し $p_u$ 、 ${\rm dist}(p_u,u)$ 、 $st$ パスにおける $p_u$ の位置が求まれば解けます。頂点 $s$ を根とすると $p_u={\rm lca}(t,u)$ と書けるため、ここから他の値はすべて求められました。

LCAライブラリを貼りたくなりますが、写経が面倒です。今はクエリの片方が $t$ と固定されているので、単にdfsするだけで求まることに気づきました。これを使って再度実装するとサンプルが合いました。

途中の計算も出力し丁寧に確認してから提出すると見事通りました。71分時点のことで、なんとFAが取れていました。結局勘違いしていたときのコードはほぼ使いませんでした。

D問題（1）

自分が実装している間に残りの問題はすべて読まれたようです。相変わらず解かれているのがDEFのみということで、多人数で詰めたほうが良さそうなDについて議論を始めました。

とりあえず、マッチ先のパターンを回転させて平行移動だけの問題にします。どれだけ移動するかをバウンディングボックスを見ることで決めたいのですが、コインの移動によって変わってしまうのが問題です。

ここで、マッチ元のパターンも回転させることで元のバウンディングボックスの左上をそのまま使えるようにするというアイディアが出ました。実はこれは正しくなく、コインを動かして置くことで4辺すべてが変化し得るのですが、気づかずに解けているものと判断しました。

細部の詰めと実装を二人に押し付け、自分は別の問題を考えに行きました。

E問題

E問題の分割統治を改めて考えます。他の $\bmod{998244353}$ の問題も2べきを強調して書かれていたので、この書き方だから畳み込みを使うというようなことはなさそうでした。

分割統治ですから、 $(l,r)$ があったとき $m=(l+r)/2$ として、 $S[l,m)$ のsuffixと $S[m,r)$ のprefixで足すとICPC-ishとなるものを考えたいです。prefixやsuffixに含まれるI、C、Pの文字数を、前者は $(I,C,P)$ 、後者は $(i,c,p)$ と置き、関係を考えます。

まず、Iの文字数がCの文字数と等しく、それよりPの文字数が多いケースを考えます。条件は $I+i=C+c\lt P+p$ で、 $I-C=c-i$ かつ $I-P\lt p-i$ と分割できます。 $(I-C,I-P)$ のようなペアを用意してsuffixとprefixを適切にソートすれば、分割方法に関するdpの遷移が簡単にまとめられました。

$(l,r)$ に対する計算量が $O( (r-l)\log(r-l))$ なので全体では $O(|S|(\log|S|)^2)$ ですが、TLが6secもあるので間に合うでしょう。

この間にDは、先程の勘違いを修正した上で実装に入っていました。印刷して一旦離れるタイミングがあったのでPCを借り実装しました。すぐサンプルが合って、ランダムケースも手元で3secだったため自信を持って提出しました。ジャッジにはしばらく時間がかかりましたが、無事通りました。

F問題

残りで解かれているのはDFKです。Dの実装が再開されたのを横目に、F問題の考察に入りました。このあたりで昼食が配られたため、すぐ食べました。

言い換えとして、それぞれの孤を始点から終点までの有向線分とみなすのを試しました。こうすると、元のループは角がすべて直角であるようなループと対応します。線分が縦横の向きになるよう全体を45度回転しておきます。

ループになるための条件の一つとして、当然ながらちゃんと始点に戻ってくる必要があります。これは、右向きの線分の長さが左向きの線分の長さと等しいこと、上向きと下向きについても同様であることが必要十分条件です。

またもう一つ、線分から孤に直した際にスムーズに繋がっている必要があります。孤に直す際には線分の向きに対し右側に膨らませるか左側に膨らませるかで2通りあって、線分の接続が直進・右折・左折のどれであるかによって規則が異なり扱いづらいです。

4方向の線分がそれぞれ奇数個ずつあれば、1回転するだけで見事に繋げられます。偶数個ずつあれば2回転すればよいです。 $N$ は偶数なので、残りは2方向が偶数個、2方向が奇数個となるケースです。

ここで、サンプル3が見事にそのケースであることに気づきました。このケースの答えがNoであることから一般に構築できないだろうという予想が立ちます。また、実は一つ目の条件の判定がそもそも難しいので、ここで変な条件は出ないだろうというメタ読みもありました。

結局、問題は次のように書き直されました： $r$ たちを四つのグループ $L,R,U,D$ に分割し、 $\sum L=\sum R$ 、 $\sum U=\sum D$ 、 $|L|\equiv|R|\equiv|U|\equiv|D|\pmod 2$ となるようにできるか。

OpenCupで4分割を2分割2回にするアイディアを見た気がするので、その方向で考えていたところ、見事に成功しました。

$r$ たちを総和が等しい二つの「サイズ偶数の」グループに分割する方法が、 $(A,B)$ と $(X,Y)$ の2通りあるとします。ただし $(X,Y)\ne(A,B),(B,A)$ です。このとき $L=A\cap X$ 、 $R=B\cap Y$ 、 $U=A\cap Y$ 、 $D=B\cap X$ とすれば条件を満たします。逆に $A=L\sqcup U$ 等とすれば $(L,R,U,D)$ から $( (A,B),(X,Y))$ を作れるので、これが必要十分条件です。

つまり分割方法を数えるdpをすれば良いです。ホスフィンさんに考察を聞いてもらって、実装はそのまま押し付けることにしました。Dが空いたタイミングで書いてもらい、横から口出ししていました。 $(X,Y)=(B,A)$ のケースを数えてしまうようでサンプルが合いませんでしたが、単に必要な分割方法を倍にすれば対処できて、無事通りました。

D問題（2）

Dは難航しているようです。印刷されたコードを少し読みましたが、時間をかけて読む必要がありそうだったので、この時点ではそのまま任せきりにすることにし、自分はKを考え始めました。

イベントの並びをbitDPで計算し、コストは折れ線のまま管理することで解けると思いました。折れ線の並行移動、累積MIN、折れ線同士の足し算・MINが必要で、それぞれ頑張ると実装できそうです。Dが通ったらすぐ書けるよう、しばらく紙コーディングしていました。

しかし、コンテストが残り30分くらいになってもDはサンプルすら通っていませんでした。この時間からKに手を付けても両方通らず終わるだけだなと確信したため、以降はDを通すことに全力投球することにしました。

今の所少なくとも、回転後の座標を回転前の座標に復元する部分にバグがあるらしいです。書かれていたコードのロジックが理解できなかったので自分の思いついた方法を伝え、さらに結局実装を奪い取って自分で書いてしまいました。

左上の $2\times 2$ マスを見ると、縦横それぞれについて回転前の座標の増分と回転後の座標の増分の対応が取れます。ただしそういう $2\times 2$ マスが取れるとは限りません。入力の受け取り、またバウンディングボックス外の切り詰めの際に、2行・2列に満たなければ右下に伸ばしました。左上さえ揃っていれば良いのでこの拡張は問題になりません。

10分程度かけて実装するとなんとか動き、出力も正しいものが出ました。後から考えてみればそういう対応は90度回転した回数からわかり、もともとそうするコードが実装されていたはずですが、多分マジックナンバーが間違っていたのでしょう。

見つかったコインの動かし方を一つだけ出力するのではなく全部出力してみてサンプルに対し想定通りの挙動をしているか確かめる、という方法で丁寧にチェックしました。少しだけ修正すれば残りは良さそうということで提出すると、なんと一発で通りました。

10分ちょっとの残り時間は順位表を見てワイワイ話していました。

コンテスト後

解説会まで1時間弱時間があったため、ホスフィンさんと一緒にスポンサーブースを回りました。LegalForce、現LegalOn Technologiesさんのブースがあったため、3年前に頂いたUSキーボードのお礼と感想を一方的に喋ってきました。半分くらい回ったところで時間になりました。

解説ではHが中難度枠だったということに衝撃を受けました。実は自分も目を通していたのですが、不等式が大量にあることを認識した段階で諦めてしまっていました。不等式の対称性についてはhaさんのメモにそれらしいことが書いてあったものの、真面目に考えようとはしませんでした。

またEの想定解がかなり天才寄りで面白かったです。分割統治を使わない場合でも、結局I、C、Pの個数を見てBITか何かで頑張った人が多いのではないでしょうか。自分はあまり理解していませんが、後からsuzukaze_Aobayamaに聞いた解法がそういうものでした。

CでS、T、Uが出現する位置は、問題文中で「outermost」と表現されていました。自分はこれを単に「外周のマスに存在する」と解釈したのですが、実はもっと強く、四隅のみを指していたようです。

YesNoの結果は6完9位でギリギリ一桁を達成しました。企業賞はありませんでした。

すべてのプログラムを終えた後、まずスポンサーブースの残りを回り、その後はずっと懇親していました。基本的には自分から名乗って特攻していたのですが、中にはTCO Finalsの際に公開された自分の顔を覚えていて話しかけてくださった方もいて感動しました。

午後6時くらいに会場を出ました。とうの昔に会場を去った東北大の他の人々は近くのビアバーに集まっているようだったので、そちらに合流してさらに午後8時過ぎまで喋っていました。

食事 pic.twitter.com/T2vg2pHmlW
— こたつがめ (@kotatsugame_t) 2022年12月28日

現在地から東京駅までの移動を考えると、実はこの時間は予定していた新幹線に間に合うギリギリです。酔っ払った状態で急いで移動し、何とか間に合いました。新幹線ではまた爆睡していました。

日付が変わる前に家に帰り着き、JAGへ入会メールを送りました。

帰宅しました。現役最後のICPCだったらしいです。Aobayama_dropoutをご愛顧いただきありがとうございました
— こたつがめ (@kotatsugame_t) 2022年12月28日

結果

先ほども書きましたが6完9位でした。昨年の順位は8位だったため、これまで順位を単調減少させてきたのが最後の年にして失敗してしまったということになります。これは残念でした。

しかしコンテスト中の動きには満足しています。特に3人全員が2問ずつ実装していること、冷えている時間がなくコンスタントに問題を解き続けられたことが良かったと感じました。実際は冷えていないと思っていたのは自分だけかもしれません。他の二人にはDの考察・実装を押し付けてしまったので、苦しい時間が長かったかと思います。

今回のコンテスト環境に関して、コマンドラインからファイルを印刷できるのはとても便利でした。何ならモニターにかじりつかなくてもよいし書き込みも自由にできるので、これについてはオンラインでやるより快適だったかもしれません。

やはりオンサイトは非常に楽しかったです。最後の年にこのような形で大会に参加できて嬉しく思います。これまでの5年間でチームAobayama_dropoutに関わった皆様、特に自分と組んでくださったチームメイトの方々に感謝します。

kotatsugame.hatenablog.com

2023-01-16

週記（2023/01/09-2023/01/15）

01/09(月)

午後2時過ぎ起床。半から指導教員の先生が海外の先生とオンラインでミーティングをするのに同席させてもらった。

かなり辛かった。話の流れでこういうことになったはいいが、あくまで先生の専門であって自分が今勉強しているグラフ理論からは微妙に遠い。事前に頂いた資料もあまり目を通せておらず、理解度が微妙な感じになった。終了時刻が決められていないのも応えた。結局2時間程度で終了。海外の先生が退室されてから指導教員の先生と少し話し、辛うじて理解できた部分について少し質問したりした。

じゃりみちさんのゆっくり実況シリーズ「ありきたりな惑星緑化」の最終回が投稿された。このシリーズは最初から最後までほぼリアルタイムで追っていた。終盤は単調な作業がかなり続いていそうだったが、動画ではほぼ全てカットされている。駆け足だったという印象もあるものの、最後まで濃密な内容が楽しめたのは嬉しいことだった。

www.youtube.com

夜までずっと週記を書いていた。午後10時投稿。相変わらず校閲はできていない。

食事してセミナー準備。今回から平面グラフの章に入る予定で、明日のセミナーではその準備としていくつか幾何学の用語の定義をしたり性質を見たりする。直感的に明らかなことでも直感を使わず示す必要があって、その匙加減が難しい。何が言えて何は言えないのかがうまく掴めず、結局二つほど証明を完成させられなかった。準備の時間も限られているため諦めることに。

午前4時頃終了。布団に入るもうまく眠れなかった。しばらくハーメルンの更新を読んでいたら午前5時半ごろに寝落ちした。

01/10(火)

午前9時過ぎ起床。布団から出るのに30分くらいかかった。

外は雪がちらついているようだが昼からの降水確率は低め。帰りには晴れているだろうと見込んで、冬タイヤに履き替えていない原付で山に登ることにした。午前10時ちょっと前に到着。すぐ教室に向かえば間に合うところを、空腹に耐えかね購買でパンを買ってから向かった。先生も少し遅れていて、数学棟の1階で鉢合わせた。

購買にて。年明けから生協の組合員証がスマホアプリに切り替わっている。アプリ登録は全員行う必要があって、そのアプリで決済もできるため便利というわけらしい。自分はスマホにそういう機能を持たせるのを嫌っていて、以前のカードも一部のレジで使えるという話だったから決済時はそうしようと思っていた。しかしこの「一部のレジ」というのは本当に一部らしく、今日寄った購買には置いていないようだ。仕方なくスマホで決済した。

【重要】HagiCo・ミールの利用には大学生協アプリの登録が必要になります | 東北大学生協

スマホをカードの代わりにすることを嫌っている理由についての自分語りをする。自分は、自分が組合員証などのカード類を忘れる・落とす・無くす確率より、スマホの充電を切らす確率のほうが高いと見積もっている。なぜなら、カード類は自分の注意力次第でどうとでもなるのに、スマホの充電に関しては何もできないから。満タンで家を出ても切れるときは切れる。

午前10時過ぎから午後0時半までは同級生のセミナーだった。今日はラムダ計算のη-変換。Unlambdaをやっているとき、λx.fxをS(Kf)Iではなくfと書けるということでかなりお世話になったが、これこそが関数の外延性であるということは意識していなかった。η-変換のほうが弱いように感じてしまう。

昼食を買いに購買へ。昼休みも半ばなのにかなり混んでいてびっくりした。どうやらレジ待ちが長いらしい。見ると、2台あるレジのうち片方を一人が結構な時間占有していた。スマホアプリでの決済に苦労しているようだ。その人が悪いわけではなく、レジが悪いわけでもなく、アプリが悪い。いろいろ不具合があることはTLに流れてきて知っていた。

食事をとっとと腹に収めてすぐ、自分ではなく博士課程の方のセミナー。証明にグラフを持ち出す定理があるらしく、昨年末から話だけは聞いていた。今日は大量に登場した添え字を追うのに時間を使ってあまり進まなかったが、終盤、本に書いてあるものと論文に書いてあるもので定義に食い違いがあっておかしいということを発見し、指摘した。来週に持ち越し。

セミナー中に外を見たら思いっきり雪が降っていてひっくり返った。原付を押して帰らなければならないのだろうか。

午後3時過ぎに終了し、その後休憩なしで自分のセミナーを行った。今日は準備してきた量も少なく、また後述する理由で急いでいたため、1時間半で話し終えてしまった。昨日完成させるのを諦めた証明二つについては、片方は議論しているうちに思いつくことができたが、もう片方は何もわからず。自分で考えるのも苦しいためネットで誰かに尋ねたいところだ。

セミナーの終了を急いだ理由は、午後5時に閉まる山の下の購買で予約したラノベを受け取りたかったから。教室を出た時点で残り20分くらいで、歩いていては間に合わないような時間だった。幸い雪が降っているとは言え路面には積もっていなかったため原付に乗って移動。下り坂で神経をすり減らしつつ何とか閉店前に滑り込むことができた。無事受け取りに成功し、学食で食事して帰宅。

生協でラノベを20万円分くらい買ってるので、もう顔パスで注文した本が出てくる
— こたつがめ (@kotatsugame_t) 2023年1月10日

今日はまず1冊出てきたので「あと8冊あるはずですが……」と言い放ち貫禄を見せつけた
— こたつがめ (@kotatsugame_t) 2023年1月10日

実は今日はインターン先定例会の日でもあった。昨日が休日のためずれていた。会議に接続すると勉強会の発表の終わり際で、その後の質疑応答だけ1時間ほど聞いた。線形代数とニューラルネットワークの話らしい。スライドを見るだけでもかなり難解な内容だったのがわかる。そんな中でも質問を通して何かを学び取る参加者のテクニックが印象的。自分からは、ニューラルネットワークの数式表現がうまく解釈できなかったので、何かノードと矢印の図はないかと聞いた。

しばらく部屋の掃除をしていた。以前言及した家飲みの日が明日である。注文した酒類やボードゲームは無事すべて到着した。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

午後8時過ぎからCF #843 div.2。開始が10分こどふぉった。

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

A1は全探索できる。A2に15分かかった。正確には、A2で入力される文字列がaとbしか含まないということに気づくのに15分かかった。今日は難しい回か、と思ってのんびりやっていたのが馬鹿すぎる。順位表を見たらみんなBどころかCまで通っていて一気に冷や汗が出た。解法は、両端以外にaがあればそれだけを真ん中にする、なければ両端1文字とそれ以外に分ける。

Bは $a$ を元の数列全体、 $b$ を $a$ から一要素取り除いたものとして条件を満たせるかチェックする。Cは $m$ を増やすことで $n$ の下のbitから順に消していく。次に消すbitを決めると $m$ をどんな値にすればよいかがわかる。

Dは各素数を表す超頂点を作り、それと数の間に辺を張った。復元がかなり面倒。数値からインデックスを求めるあたりが辛そうと考え、最初に $a_s=a_t$ のケースを取り除いておいたら、 $a_s=a_t=1$ かつ $s\ne t$ のケースにやられてしまった。

Eは二分探索。マイナスのために使った値は次はプラスのためにしか使えない。逆も然り。

Fは苦労した。 $u=1$ のケースは何とでもなるため問題は $u=2$ 。自分は最初「 $n$ より少し小さい長方形を作り、足りない分を付け加える」という方針で解こうとしていたが、これだと例えばサンプルの $n=7$ で、 $3\times 3$ の左上と右下を消したような形を数えられない。

今何気なく使った表現「 $3\times 3$ の左上と右下を消す」が解法。つまり、 $n$ より少し大きい長方形を作って過剰な分を消せばよい。ラボの形は凸だと思ってよく、この場合の周長は元となった長方形と一致する。長方形の縦横と、その長方形が答えの元になりうる $n$ の組み合わせは、ギリギリ全探索できるくらいの個数らしい。

あとは長方形とそこから消すブロック数に対し、凸を保つような消し方の数を求める方法について。凸を保つためには四隅から消し始める必要があって、実は四隅をそれぞれ独立に考えてよい。気になるのは消し方が干渉しないかだが、もし干渉するほどたくさん消せるなら元の長方形としてより小さなサイズのものが取れるため、考慮する必要がない。

同じ理由で長方形のサイズも気にしなくてよいので、まず削るブロック数に対して消し方を数え、上で述べた全探索の際にそのテーブルを見ることにする。四隅の一つについて解き、それを多項式と見て4乗するとテーブルが作れる。消すブロック数は最大で1000にも満たないようなので、これはどちらも特に工夫のないdpなり畳み込みで行える。

1度目の提出はWAだった。そこから30分近く理由がわからずに苦しんでいたが、適当に探索範囲を増やして出しなおしたら通った。元となる長方形のサイズが $n$ の上限 $4\times 10^5$ を超え得るのを見落としていたようだ。

遅めの全完で47位。Eは二分探索の判定をよく見ると貪欲でよいようだ。さらに実は、累積和の最大から最小を引くことでも答えが求まるらしい。累積和を取った状態での操作を考えると分かった。衝撃的。

全完に2時間かかってしまった。本当はとっとと切り上げてゲーセンに行こうと考えていたが、もはやそのような時間ではない。明日家飲みの前に行くことにする。

チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。
週記（2023/01/02-2023/01/08） - kotatsugameの日記

明日に備えて早く寝るべきだが、今日の深夜に新春TCB2023が終了して結果が出るということで、その時間までTLを眺めたりYouTubeを見たりしつつ起きていた。

https://techful-programming.com/user/event/3814

午後11時55分に終了し、結果は4位。1問テストケースの不備で採点対象外になるので、もしかしたらずれるかもしれない。全完者の中では結構時間がかかっているほうだった。失点は124ptで、すべてタイムボーナスを失ったことによるものである。3位は遠く、5位は近いので、ペナルティを出さなかったのはかなり偉かった。以下各問題の感想。

天邪鬼な石取ゲームは、 $\max a$ が $\sum a$ の倍より大きいなら先手がその山を選び続けることで勝てる。それ以外のケースは実は全部の石が取られ、 $\sum a$ の偶奇だけで決まるのではないかとエスパーした。変なケースが思いつかなかったので出したら通った。制約が微妙に小さいため結構怖かった。

Restricted Gridは結構難しかった。条件を式で書き眺めていたら、全部足すことで答えの $M\sum x+N\sum y$ を上から抑えられる。勝ったなガハハ！と思っていたらサンプル4が合わなかった。冷静になるとそんなピッタリにはできない。さらにしばらく式を眺めて、 $\sum y$ を全探索すると全部計算できることに気づいた。少し時間オーバーして-5pt。

Sum Mod M againは非常に難しかった。まず $i$ が固定されているとして、 $j$ を求めることを考える。これはつまり全体を $B$ で割ろうとしている。すると $Ai+C$ が $\gcd(B,M)$ の倍数という条件が出てくるが、これを満たす $i$ はある $q$ 、 $r$ と適切な範囲を動く $k$ によって $i=qk+r$ という形で表せる。この $i$ を元の式に代入することで $B$ で割ることが達成できる。今の操作は問題を $B=1$ のケースに帰着したことに相当する。

$i$ と $j$ を入れ替えてもう一度行えば $A=B=1$ にできるぞ！と思い込んだが、残念ながら $B$ を変えるときに $A$ も変わるためうまくいかない。しかし実は $B=1$ とできた時点で解けていた。 $i$ を固定すると、 $Ai+j+C$ は $Ai+L_2+C$ から $Ai+R_2+C$ までの値を取る。このうち $M$ の倍数であるものの個数は冷静になると $\lfloor(Ai+R_2+C)/M\rfloor-\lceil(Ai+L_2+C)/M\rceil+1$ と表せて、 $i$ に関する和を取るのがfloor_sumで行える。

考察が一直線には進まず、迷走していた時間が長い。86分かかったようだ。タイムボーナスはすべて溶け消えて-56pt。ここまでは日曜日のECR前にやっていた。特にこの問題が解けたのは15分くらい前と結構ギリギリだった。タイムボーナスが残っていないからあまり関係はない。以降はECR後。

初夢スコアアタックは一つ前の問題と難易度が同じなのに、非常に簡単だった。使える限り多くの魔法を使いたい。使える魔法を増やす方向で考えると計算量が抑えられないが、減らす方向で考えれば、単に使えなくなったものを消していくだけでよい。問題文を把握するのに少し時間がかかるも14分で解けた。

Worst Conjectureはもう大変。 $c$ と $T$ で2重積分する。被積分関数の形が複雑なので、それを決定できるよう $c$ と $T$ の範囲を細切れにしてそれぞれ計算する。行った工夫としては $(c,T)$ の代わりに $(c,2T-c)$ で積分したことが挙げられる。 $X$ に関する条件がこの2数の間にあることと書けて便利。

$2T-c$ の積分を外側に持ってきたのは失敗だった。 $c$ の範囲に対する期待値はサンプルに書いてあるが、これをデバッグに使えず自分で積分計算する羽目になった。しかも結構最後のほうまで条件の不等号を逆だと誤読していて計算がやり直しに。非常に苦しみながら4時間と計算用紙10ページをかけて通した。当然タイムボーナスはないので-63pt。

しばらくTLを見て午前1時過ぎ就寝。

01/11(水)

午前8時半起床。布団から出るのに30分かかった。準備して出発。

まずゲーセンでチュウニズムデュエルを終わらせにかかった。「凛として咲く花の如く」の理論値が出た。曲も譜面も好きなので結構うれしい。時間的に7クレしかできず、クリティカルが全く出なかったためデュエルは終わらなかった。昼食後にまた来る。

凛として咲く花の如く理論値 pic.twitter.com/yvDiofitpJ
— こたつがめ (@kotatsugame_t) 2023年1月11日

午前11時半前にたいぺー・ホスフィンと待ち合わせして、ホスフィンが予約してくれたフレンチの店に入った。今日はフルコース。量的にはそれほどでもないなと思っていたが、2時間かけてゆっくり出てきたので満足感はかなりあった。ツイートに記された料理の名前は説明を聴き取れなかったりして不正確である。

食事
・いろいろ温野菜の菜園風サラダ
・ソーセージ、パテ、スモークサーモンのマリネ
・パン
・きのこのポタージュ pic.twitter.com/FoyNtJhdD3
— こたつがめ (@kotatsugame_t) 2023年1月11日

・メカジキのソテー
・牛ハラミのステーキ
・デザート（ガトーショコラ、りんごとカスタードのケーキ、ムース）＋紅茶 pic.twitter.com/XiQLVaf9do
— こたつがめ (@kotatsugame_t) 2023年1月11日

どれも明らかに美味しかった。サラダは飾りのドレッシングのほかにも野菜に薄く塩味がついているようで、丁寧な作業に感動した。きのこのポタージュは一口飲めば非常に濃厚なきのこのうま味が口の中に広がって圧倒された。たまにインスタントのスープパスタを食べていて、これもきのこが美味しいなと思っていたが、やはりモノが違う。牛ハラミのステーキは横の橙色のソースがわさびのソースだった。結構辛みが強く、わさび醤油が好きな自分にとっては非常に嬉しかった。

クノール®スープDELI® ポルチーニ香るきのこのクリームスープパスタ（容器入）｜商品｜味の素株式会社

食後、二人がドンキに買い出しに行っている間にゲーセンでチュウニズムデュエルを終わらせた。追加で2クレ使った。TiamaT F:minorはラストまでかなり上手かったのに、つまらないアタックやミスを出してSSS+もフルコンも逃してしまった。

あああああアウトロで切ったあああああ pic.twitter.com/gSXsPCi32C
— こたつがめ (@kotatsugame_t) 2023年1月11日

帰宅して飲酒開始。

飲酒します pic.twitter.com/k5AGKMEW7I
— こたつがめ (@kotatsugame_t) 2023年1月11日

購入したボードゲームをプレイした。最初は「ギャンブラー×ギャンブル！」。結構面白かった。各プレイヤーが0または1のカードを場に出し、その総和が当たりの数字になっているプレイヤーがコインを獲得する。獲得したコインで自分の当たりの数字を増やしたりしつつ勝利条件を満たすゲーム。カードを出す際には実際はもうちょっと手順があって、考えようと思えばいろいろ考えられる。出すときにブラフで何か言うだけでもかなり戦略ゲームっぽくなって楽しかった。

このゲームは3人または4人用とされていたが、3人だとゲームの展開が制限されると感じた。本来はゲームが進むにつれ手持ちのカードに2や3が増えるようだ。しかし3人でプレイしていると、それらのカードを手持ちに入れるメリットはあまりなさそう。似通った展開になるのを避けるため、最初から2を持ってみたり、少しルールを変えて何度かプレイした。

次に「タギロン」。個人的にこれは大当たりだった。数字と色の書かれたタイルが20枚あって、3人プレイだと一人5枚配った後、互いに質問し合って残りの5枚を特定するというゲームになる。残りの5枚に対しては何も質問できないため相手二人が持つタイルをすべて特定する必要があって、結果として誰か一人に質問が集中してもそれだけでは勝敗は決まらない。このバランスの取り方に感動した。

質問は、場にある質問カードを一つずつ消費しそこに書かれた内容を聞くことで行われる。数字に関する質問より色に関する質問のほうが少なく、それを一人にほとんどぶつけた結果もう一人の色がなかなかわからず苦労するという場面もあった。

購入したボードゲームは3種類で、最後は「ito」。1から100までの数字を一つずつ持ち、その大小をお題に沿って言葉で表現することで、大小関係がどうなっているのかを特定するゲーム。プレイ人数10人までのところを3人でプレイしたためか、前二つに比べるとちょっと微妙という感想。もしかしたら単にお題が合わなかっただけかもしれない。95と96の順番を当てた回があって、かなり嬉しかった。

一通りプレイしてからはいつものようにおすすめ動画（MAD）を見たりまたボードゲームをプレイしたりしていた。今日見たMADで印象深いのは以下の三つ。

www.nicovideo.jp

「背中の傷は剣士の恥ィ」。これは自分が紹介したやつ。最近結構な頻度で見ている。何もかもが好き。「ウソップはこの島に置いていく！帝京魂！」のセリフが特に意味不明で良い。

www.nicovideo.jp

「みゃー姉が死んだ回」。原作では死んでいないらしい。ホスフィンによる各シーンの解説があって、構成の巧みさに驚かされた。RubikunさんのTwitterアイコンになっているキャラはこの作品由来らしく、アニメではアイコンで見たことのない表情も多く違和感がかなりあった。

www.nicovideo.jp

「デスノートで人が死んだ回」。出オチ。先ほどの作品とさらにその元作品「おジャ魔女どれみで人が死んだ回」を見た直後だったため、落差で笑いが止まらなかった。

午前4時頃にラーメンを食べに行った。腹が減っていると思ったものの、食べたら食べたで少し気持ち悪くなってしまった。その後解散。正確には、たいぺーとは帰り道で別れ、ホスフィンとは帰宅して一休みした後別れた。

今日はキレートレモンやお茶をたくさん用意し積極的に飲むようにしたため、このように全員で外に出るような元気を残すことができた。今後も心掛けたい。用意したお酒のうちではカルーアミルクを結構な量飲み残してしまった。ミルク系の甘いお酒は好きだがだからと言ってたくさん飲めるわけでもないようだ。

47度のジンが一瓶空いたのはびっくりした。このジンをストレートで口に含んでみたところ、よく小説などで目にする「喉が焼けるような」という感覚を得ることができた。そんな感じだからきっと飲み切れないと思っていたのに、適当にジュースと混ぜると苦みがなく非常に飲みやすいお酒になってどんどん杯が進んだ。

少し部屋の掃除をして午前6時くらいに布団に入った。何かスマホを触ろうとした記憶はあるが、すぐ寝落ちした。

01/12(木)

午後3時起床。シャワーを浴びて準備し、大学に向かった。TA。

年が明けて初めての講義となる。内容は昨年最後の講義で行われた発表の続きからだが、その時特に難しいことをやったわけでもないため復習などはなかった。

30分次の人の発表を行ったところで時間になった。これで今年の講義は終わり。
週記（2022/12/19-2022/12/25） - kotatsugameの日記

超多面体の話。特に $n$ 次元の特別な超多面体に含まれる $k$ 次元単体の個数を数え上げるのがメインだった。 $n$ と $k$ に関する漸化式を立てて、それを解く。解くと言っても答えは教科書に載っているため、適当に帰納法で示すだけになる。

変数が二つあって混乱しているようだったので、その周りでいくつか指摘したり助言したりした。シンプルに $n$ だけ見ても解けるし、変わり種として $n+k$ についての帰納法を使ってもよい。そもそも前者がおぼつかない様子だったので、後者については特に何も言わなかった。

午後6時過ぎに終了し学食に向かった。5限終了直後でもないのに3台稼働しているレジにそれぞれ10人弱並んでいて驚愕。一体何をしているのかとよく見たら、現金払いが多いらしい。生協のアプリ登録に失敗した人々だろうか。またアプリを用意していた自分も決済バーコードの読み取りに微妙に時間がかかって、まんまとレジの詰まりに寄与してしまった。どうしようもない。

午後7時帰宅。メールを確認したらABC277の賞金が届いていた。アマギフ60000円分だった。この回は賞金がかなり高額な回だったらしい。額面がメール文面に書いていなかったためびっくりした。

生協のアプリについては今もTLにそこそこ愚痴が流れてくる。そんなツイートの一つに以下のようなリプライがついていた。これが本当なら少しだけ納得も同情もできる。不便になったのは覆しようのない事実のため、もうちょっと何とかならなかったのかとは思うが。

失礼します。大学生協で学生理事をしていたことがある者です。
もはや学内から人がいなくなり、生協の経営が悪化しました。これまでの野村総研のPOSレジは保守費用が高額だったので、簡易なレジを導入することになりました。そのため、電子マネーがカードからスマホアプリになりました。
— えぐっちー (@soki124) 2023年1月12日

日記を書いて午前6時就寝。

01/13(金)

午後1時45分起床。15分後から1on1。

結局年末年始は何もしなかった。その間に自分ができるタスクがいくつか用意されたらしく、今日はその説明。まず一つ、昨年後半に携わっていたコードで大きなエクセルシートを処理すると実行が終わらなくなってしまうことの解決。二つ、昨年末に話題に上がったツールを本格的に使い始めるための下調べ。前者がかなり難題で、もっぱらそれを解決する方針決めに時間を使い2時間ほどのミーティングとなった。

大きなシートといっても真っ当にデータが多いわけではない。手作業のミスによって右・下方向限界ギリギリのセルに値が入っているようなシートが存在して、それを処理できないらしい。読み込みにはopenpyxlというライブラリを使用していて、そのデータにすること自体までは特に時間もかからない。なぜなら、値が入っているセルのみをdictとして保持しているだけだから。

しかしそこからうかつに行を取得したり列を取得したりした瞬間、一番端のセルに合わせてその間の値が入っていないセルも全部新たに作成してしまうらしい。この一番端というのは取得した行・列の一番端という意味ではなく、シート全体の一番端という意味である。つまり、セル $(1048576,16384)$ に値が入っていれば、すべての列が高さ1048576になるし、すべての行が幅16384になる。

こういう大きなシートでは、端にあるセルは単に無視することになった。しかしそれを実装するだけでも値が入っているセルだけを一つ一つ見ていく必要があって大変。そういうことをするメソッドは用意されていないようだったため、外から触られることを想定されていなさそうな_cellという変数を直接見ることになった。

たいぺーが水曜日に空けたジンの瓶を引き取りに来た。可愛いので取っておきたいらしい。洗って乾かしておいたのを引き渡し、ついでにその他の瓶をゴミ捨て場に持っていく手伝いをしてもらった。キレートレモンの空き瓶が10本あって一人では面倒だった。

午後4時40分からサークルバチャ。5問目はかなり最近の問題だから覚えていて、6問目は条件をいくつか集めたら通って、7問目は「二つの要素が同じタイミングで操作されると以降どちらが先に並ぶかは半々」というクリティカルな考察がスムーズに出てきた。結果35分で全完し、Estimated　Performanceが5029と見たことのない数字になった。

https://kenkoooo.com/atcoder/#/contest/show/57415d67-4fc2-4e97-a222-3e24052aaecd

解説をチェックしたりして時間を過ごし、バチャ終了後に少し感想戦をして解散。

日付が変わるまで今日期限のレポートと格闘していた。昨年末に受講した集中講義「理論言語学研究演習I」の課題である。最近の自然言語処理はニューラルネットでポンという感じで、言語学的知見が活かされているとは言えないとのこと。活かすにはどうすればよいか意見を書けという課題だった。

自分はまず、LSTMとAttentionという講義で扱われたニューラルネットのブレークスルーを達成した仕組みについて元の論文を当たり、本当に言語学的知見が活かされていないのか調べた。長距離依存という用語が出てきているのだし何かあるだろうと思ったのだ。しかし事実として何もなかったため目論見が崩壊。今更レポートの方針を変えるような時間もなく、適当なことをモゴモゴ書いてお茶を濁した。しかも提出が数秒間に合わなかった。まあこのくらいは十分許してもらえるはず。

その後はずっとラノベを読んでいた。午前3時頃「クラスで2番目に可愛い女の子と友だちになった」3巻を読了。ダダ甘。ついにヒロインたちとクラスでも関わるようになり、見せつけるような感じになって読んでいて非常にニヤニヤできた。タイトルにもなっているヒロインと恋人同士になったにも関わらず、結構な頻度でその友達を含む男1女3で行動していてこれも好きな展開。しかし主人公は一途なので、ちゃんと恋人を特別扱いしていた。偉い。

別のラノベに手を出したが、急激な眠気に襲われ午前5時くらいに寝落ちした。

01/14(土)

午後4時頃に冷凍弁当を受け取った。その前後1時間ほどは起きてスマホを触っていた記憶がある。二度寝した後、午後6時起床。

ラノベを読んで過ごし、午後9時からARC153に出た。

AtCoder Regular Contest 153 - AtCoder

Aは $(S_1,S_3,S_4,S_5,S_7,S_8)$ を辞書順に探索すればよい。6重ループを書いた。

Bは操作を把握した瞬間「全体をいくらかシフトして180度回転したもの」になるとの直感を得て、実際そうと確認できたところまでは順調だったものの、実装方針にかなり苦しんだ。何を計算すれば盤面の状態を表現できるのかわからない。最終的にはマス $(1,1)$ の行き先を追った。

Cは実装が面倒だと思ったら整理するうちにどんどんシンプルになっていった。最初の考察として、 $i\lt j$ について $(A_i,A_j)=(-1,+1)$ だと必ず $A_ix_i+A_jx_j\ge j-i$ になり、 $(A_i,A_j)=(+1,-1)$ だと $A_ix_i+A_jx_j\le-(j-i)$ になるというものがある。つまり、どちらかのペアだけで $A$ の要素をすべて使い切れた場合、条件を満たす $x$ は存在しない。そうでない場合を考えたい。

先ほどのような $i\lt j$ によって $(\pm 1,\mp 1)$ のペアを作った後、まだ $A$ が余っていればそれを使って調整、余っていなければ $(+1,-1)$ のペアと $(-1,+1)$ のペアを使って調整すればよさそう。ペアを適当に組むと考えにくいため、左からstackを用いる方法で固定した。これだと2種類のペアが固まって現れるため調整しやすい。

$A$ が余っている場合は簡単。例えば余っている要素で最も左にあるもの $A_j$ を選ぶと、ペアの作り方からそれより左はそこだけでペアが完結しているため、 $x_1\dots x_j$ から一気に $X\gt 0$ を引くことで、 $x$ が狭義単調増加であるという条件を満たしたまま $\sum_i A_ix_i$ から $A_jX$ を引くことができる。最も右にあるものを選んでも同様。最初に $x_i=i$ と決めておき、 $X=\left|\sum_i A_ix_i\right|$ としてどちらかを選べばうまくいく。

$A$ が余っていない場合も最初に $x_i=i$ としてみた。 $X=\sum_i A_ix_i$ が正だった場合のことを考える。 $(A_i,A_j)=(+1,-1)$ というペアを探して、 $x_j-x_i$ を今より $X$ だけ大きくすることで調整可能。ただし大きくしたときに他のペアと干渉するとまずい。

区間 $(i,j)$ が交差しないペアなら適切にずらせばよい。交差する場合、ペアの作り方から完全に内側にあるか、完全に外側にある。内側は関係ないため無視。外側はどうしようもないが、そもそも包含関係で最も外側にあるペアを選べばよい。復元はちょっと面倒だった。ペアに対して $x_j-x_i$ がいくつになるべきかという値を管理し、左の要素から順番にペアの相方と一緒に決めていった。

D。 $f(A_i+x)$ は $f(A_i)+f(x)$ から繰り上がりが起こった回数の9倍を引いた値となっている。また、 $A_i+x$ の計算時に $10^k$ の桁で繰り上がりが起こることと $(A_i\bmod{10^k})+(x\bmod{10^k})\ge 10^k$ であることが同値。さらに $x\ge 10^9$ のとき $x\leftarrow x\bmod{10^9}$ としたほうが得だと示せたため、繰り上がりの起こる桁は $10^0\dots 10^8$ のみだと考えてよい。

よって $x$ を決めるごとに9回の二分探索で $\sum_i f(A_i+x)$ が求められるようになった。 $x$ としては、ある $i$ に対して $A_i+x$ の下数桁を0にする最小の値だけが候補になると考えたが、証明できない。とりあえず書いてみたらサンプルは合ったものの、出したら当然のように落ちた。

$x$ の下5桁を全探索し、上4桁はデータ構造で決めるという方法を考えていたら、頑張ればできることに気づいた。こうやって別々に考えるとき問題になるのは下の桁からの繰り上がりが上の桁の繰り上がりに関係するケース。例えばサンプル4なら下5桁が46847以上のとき、そうでない場合に比べて上4桁が「8で終わる」「68で終わる」「468で終わる」「8468で終わる」ものそれぞれに対し繰り上がりが1回ずつ追加される。

上4桁を逆順に並べてインデックスとすると、これは区間加算で対応できる。例えば「68で終わる」数はインデックス $[8600,8700)$ に対応する。下5桁を昇順に試しながらこういう更新をしていけば答えが出る。逆向きにしたり68や468といった繰り上がり直前の値を求めるところで頭を壊してしまい、残念ながら5分ほど間に合わなかった。

結果は3完120位。今回は画面録画に加えマイクに向かって喋りながらコンテストに出ていたのだが、結果がひどいため動画データは即座に消去した。コードゴルフはAのみ。99999を足すと $S_1S_3S_4S_5S_7S_8$ という6桁の数が得られるため、適切に数字をコピーして求める数を作るという解法。Vimで実装した。

ずっとラノベを読んでいた。午前5時に「黄金の経験値」を読了。やはり面白かった。以下、微妙に書籍の先のネタバレを含む感想。

なろう版からの大きな修正として、ブラン視点がすっかりカットされていた。これは個人的には読みやすくなって良かったと思う。物語が軌道に乗る前から複数の、それも独立しているように見えた視点があると、それはほとんど別作品を並行して読んでいるのと変わらなくて話の進みが遅くなりちょっと辛い。

なろう版を読み主人公レアのキャラクター性を知っている状態で最初から読むと、ちょくちょくあったそれらしい描写を見つけることができて非常に楽しかった。レアのキャラクター性というのは、自分の捉え方ではわがままだったり、肝心なところでポンコツだったりというもの。この主人公、いかにも魔王然としたビジュアル・行動なのに性格にはそういうところがあって、そのギャップが可愛らしい。

また作品の設定も改めて上手いなと思った。PCとNPCの違いは「システムメッセージを受け取れるかどうか」のみであると最初に明確に説明され、以降の設定はすべてここに絡んでいる。例えばNPCがリスポーンできないのは、リスポーン用のシステムメッセージが受け取れないから、だろう。これが他キャラに「使役」されると自動的にリスポーンできるため、NPCも不死身になる。

別のラノベを読んで午前9時前に就寝。

01/15(日)

午後6時起床。食事してしばらく日記を書き、午後9時からコンテストに参加した。

今日は午後9時からABC285があり、午後9時5分からCF #844 combinedがあった。両方参加した。

AtCoder Beginner Contest 285 - AtCoder

Dashboard - Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) - Codeforces

まずABC。Aはよい。Bは $i$ ごとに $l$ をインクリメントしながらチェックすると高速。Cは適当にやれば合う。Dはよくわからなかったが、雰囲気から $S_i-T_i$ 辺にループがあるかどうかで判定できるだろうと思った。

Dの実装中にCFが始まってしまったが、A問題のページ読み込みに時間がかかっていたのでこれ幸いと書き上げた。結局ABCは4完の状態でCFへ。

Aは上方向の移動は必ず必要なので、それを無視して平面の問題として解く。床・天井を表す長方形のどれかの辺にタッチしつつ2点間を移動することになり、どの辺にタッチするか全部試せばよい。

Bは人数を全探索する。 $k$ 人だとすれば、 $a$ が昇順に並んでいるとして $a_k\le k-1$ かつ $a_{k+1}\gt k$ が必要。合わせるのに少し手間取った。

Cは何種類の文字を使うか全探索。 $k$ 種類だとすれば $k\mid n$ が必要で、各文字は $n/k$ 回ずつ使う。元の文字列における出現回数が多い順から $k$ 個使うことにして調整すればよい。復元が面倒。

Dは平方数になる最小のインデックスを $i$ とすると、適当な $x$ 、 $t$ によって $a_i+x=t^2$ と表せることになる。このときもし $j\gt i$ なる $j$ について $a_j+x$ も平方数となるなら、ある $d\gt 0$ が存在して $a_j+x=(t+d)^2$ 。展開して $t^2$ を先ほどの式で置き換えると $a_j-a_i=d(2t+d)$ となる。

すべての $j\gt i$ に対して $t$ の候補を求め重複を数えると、 $a_i+x$ とともにいくつ平方数にできるかがわかる。 $t^2\ge a_i$ が必要なことに注意。これを $i$ を全探索して行う。 $O(n^2)$ 回10⁹オーダーの値の約数を列挙するのは十分間に合う。

Eは面倒。覆う面積の最大値なんて簡単にわかりそうもない。自明な上界としてもともと覆われていた面積があって、実はこれが達成できるのでは？と考えたら達成できた。まず高さ2の長方形だけ考えて、覆う面積を変えないようにしつつ重ならないように変化させる。長方形を一つずつ追加することを考え、追加の際完全に覆うものは取り除き、他と重ならないよう縮めるという方法で行える。

残りは高さ1の長方形で、上の行と下の行それぞれ独立に先ほどの操作をすればよい。長方形を取り除く際、それが高さ2だった場合高さ1に縮めるという処理に置き換わる。面倒に見えて、同じことを3回やるだけなので実装は案外簡単だった。入出力が閉区間なのに注意。サンプル1が強いので適当に投げてもペナになりにくい。

ここまで1時間で、現在20位台。あらかじめこの辺りでABCに戻ろうと思っていたため、Fを頭に入れてからABCのEに戻った。

Eは曜日1を休日と固定してよい。休日1日とそれに続く平日何日かをまとめて生産量を計算し、それを組み合わせる遷移でdpした。

Fはかなり苦労した。結論から言えば、区間 $[l,r]$ が昇順に並んでいること、区間 $[1,l)$ と $(r,N]$ に $S_l$ より大かつ $S_r$ より小な文字が存在しないことが条件となる。セグ木にいろいろ乗せるとできる。具体的には、区間の両端の文字、区間にどんな文字があるかのデータ、昇順に並んでいるかどうか。

焦っていたら条件列挙も実装もミスしまくり、5ペナの末コンテスト終了4分前に通った。うっかりABCに30分弱も使ってしまったがCFに戻る。

Fは括弧列をいつもの累積和に直すと、 $x$ を取り除き、その位置に確率 $p$ に応じて $x,x\pm 1,x$ を挿入するという操作になる。これを3分木みたいに見ると状態がまとめられるのではないかと考えた。ノード $x$ があって、それ以下の部分木で $k$ 回操作するという場合、まず1回操作してノード $x,x\pm 1,x$ を作り、それらで残り $k-1$ 回操作するということになる。 $k$ を固定する必要があるため特に畳み込みにはならない。

ノードを選択する確率が計算できず困ってしまったが、冷静になると操作方法に依らず $i$ 回目の操作では $\frac 1{2i-1}$ となる。これを最後に掛けるだけでよい。

フレンド順位表を見てH1に進んだ。 $k=0$ は単なる包除原理でよい。 $k=1$ もシグナルのバウンディングボックスのサイズを決め打ち、シグナルを表示するために少なくとも1マス消灯させる必要のある領域を調べてこれまた包除原理を行うと求まる。しかし $k=2$ がどうにもならなかった。

6完29位で2841→2887(+46)。昨年秋にドカンと下げたのを多少は取り戻せただろうか。点数の差がかなり詰まっていたので、Fをもう少し速く解けるだけでも順位はそこそこ変わったようだ。この順位帯だとレート変動も大きく変わる。途中でABCに戻ったのは、やる前から明らかだったことだが悪影響しかなかった。

後悔しているかは微妙なところ。なんだかんだ言ってCFのレートは結構上がったし、ABCも250位でそこまでみすぼらしい順位というわけではなかったから。ただしABCに無理して参加した目的であるコードゴルフ的には、もう全然ダメだった。以下はそのコードゴルフの話。

Aは $2a\le b\le 2a+1$ という条件を見て縮まないなあと言っていたが、 $a=\lfloor b/2\rfloor$ でよい。明らかにdc。Bは愚直に書くとRubyもPerlも間に合わないところ、Perlで文字列XORをした後ヌル文字を探す方法だとかなり高速になった。その周りをかなり縮められて負け。Cは自分が見たときにはすでにコードゴルフされきっていて、言語を変えても縮まなかった。DはAWKでこれも大敗。以降は手付かず。

時系列は前後するが、CFの終了直後にABC-Gをupsolveした。結構素早く解けたとは言え10分ちょっとかかっているから、コンテスト中にGに進んでも間に合わなかっただろう。

そのまま二部マッチングにすると2を使い切るという条件がうまく表現できなかったため、頂点を倍加してみる。すべての2を使うようなマッチングが存在すればよいと考えた。ここは注意が必要で、 $1\times 2$ のタイルを置く際は覆う2マスを倍加したものが互いにペアになっていてほしいのに、そうでない可能性がある。

しかしこれも適切に修正できそう。そういう食い違ったペアを辿っていって、もし途中で途切れたらそこから遡って修正していけるし、サイクルができたら偶閉路だから全体を一気にずらせばよい。出したら通った。Nyaanさんのユーザ解説が同じことを言っている。

昼間までずっと日記を書いていた。合間にラノベを2冊読了。

1冊目は「ガリ勉くんと裏アカさん」。クラスのアイドルであるヒロインが裏垢女子であることに気づいて……という導入。しかしむしろ裏垢云々以外の部分が面白い。特に主人公のキャラクターが好み。自分の中に一本芯があって、いろんなことを自分には必要ない・関係ないとして排除するというかなり極端なものだが、自分にとっては望ましいものだった。

2冊目は「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」2巻。1巻を読んでから10か月、2巻が出てから6か月くらい経っているが、昨年末に出た3巻にかなり好みのシーンがありそうだったため今更読むことにした。周囲の人間の行動が主人公にとってかなり都合が良いと感じるものの、それ以外の部分は良い。日記を読み返すと1巻を読んだ時はネガティブな印象を抱いていたらしく、それを忘れ去っていたのも良い方向に作用しただろう。

正午就寝。

2023-01-09

週記（2023/01/02-2023/01/08）

01/02(月)

午前11時ごろに起こされた。多少の二日酔いで軽い気持ち悪さがあるが、今日は昼から中華料理を食べに行くらしい。

幸い、車に乗っていても食事しても気分が悪くなることはなかった。ここでもコーンスープを頼んだ。かなりコーンポタージュに近い。

pic.twitter.com/6KR0EOLz7i
— こたつがめ (@kotatsugame_t) 2023年1月2日

百貨店に寄って帰宅。

夕食までは麻雀をしていた。この年末年始は自分の他に二人実家に来ていたため、父を加えるとちょうど四人になる。この二人というのは、片方は姉で、もう片方は……詳しく説明する理由も権利もないため、名言は避けておこう。

夕食は午後6時ごろだった。食後、先ほど述べた二人が帰るので見送った。

先週の週記を書き始めたが集中力がない。なろうから「剣聖と大賢者の正体が、落第貴族と呼ばれる俺な件について～しょうがないから守護神してるけど、さっさと変わってほしい暗躍学院ライフ～」を読了。

https://ncode.syosetu.com/n8008hz/

正体を隠す方法として、完全に影に隠れているのも好きだが、こうして複数の人間を演じるのも好き。最近投稿が始まった作品なのでこれからに期待。複数の人間を演じると言えば「セブンキャストのひきこもり魔術王」というラノベを思い出す。こちらは一人七役。設定がかなり好みで、今でも時たま思い出してはニヤニヤしている。

日付が変わる直前に週記を投稿した。せっかくの年明け一発目なのに時間に追われすぎて大したことが書けず、残念。できれば加筆したいものだが、校閲にすら手が回っていない以上実現可能性は低そう。

その週記の中で、2年前に読んだ本「〔少女庭国〕」に言及した。記憶が曖昧なので念の為確認しておこうとしたが、本棚を漁っても見つからない。レーベルに共通して本の背が少し高いので、見落としたということはなさそう。よくよく思い返してみるとたいぺーに貸した記憶があって、聞いてみたらどうやら返し忘れていたようだ。思い出せて良かった。

入浴し、午前1時半くらいからDMOJのコンテストに出た。明日の午後2時までなのでギリギリ。しかしここにコンテストの感想を書けるという利点もある。

DMOPC '22 December Contest - DMOJ: Modern Online Judge

P1は、 $N$ または $M$ が偶数の場合、相手が塗ったマスの点対称の位置を塗れば必ず半々になりそう。ヒカルの碁で見たことのある戦法だ。両方奇数なら中央のマスの分先手が1増えるな、と思って提出したらWA。

考え直してみると、中央に壁を作る感じで塗れば、先手は後手より1行または1列まるまる多く獲得できる。行と列のどちらであるかは後手が選べる。これで通った。

P2はかなり面倒。順列をサイクルに分解してから考えた。連結成分数は、サイクルの頂点全部が選ばれたら1減り、そうでない場合は選ばれた頂点だけ見たときの連結成分の数に分裂する。選ばれた頂点と選ばれていない頂点を結ぶ辺を、差分更新で数えることで求められた。

P3は非常に難しかった。答えを $H$ とし、 $H-h_i$ を1と2で埋め、1とそれより右の2をうまくペアにして全部使い切ることを考える。

もし $H$ と $h_N$ の偶奇が異なれば $i=N$ として操作しなければならないがこれは不可能。よって $H$ の偶奇が決まり、同時に必ず一度は1インクリメントする必要のある要素もわかる。そういう要素を右から順に見て行って、本当にペアが作れるかをチェックした。右に2がなければ $H\leftarrow H+2$ として無理やり作り出す。

さらに $NH-\sum_i h_i$ が3の倍数になるように $H$ を調整しておく。 $N$ が3の倍数だと不可能なケースも生じる。後は $H$ と $\sum_i h_i$ からわかる操作回数の分だけ、左から優先的に1で埋めていけばよさそう。

残りは1と2が入り混じる箇所でペアを作れず破綻するケースのみが問題。そのような位置を二分探索で求め、破綻するかどうかをチェックする式を作った。なかなか複雑だが $H$ の一次式になったので、この式を満たすくらい大きな $H$ が簡単に得られる。それをもとに $H$ を再調整すればよい。

ここまでも結構な回数のWAを重ねてきたが、最後のWAが一番衝撃的だった。最初の処理で1だけインクリメントする要素をチェックするとき、それとペアになる2インクリメントするインデックスも適当に固定していた。そのほうが後から操作回数などが扱いやすいから。しかし、この固定するペアも慎重に決めなければならないらしい。右のほうから貪欲だと落ちて、左のほうから貪欲だと通った。

すでに残り1時間しかなくかなり焦っていた。幸いP4はスムーズに解けた。解の構造を考えると、まず値札を動かさずに購入する商品を決め、その後一番高い値札を一番安い使っていない値札に付け替えるのを高々 $K$ 回行うことになる。値札を安い順にソートしておくと、この操作で使っていない値札が安い方から使われるため、ある位置が存在して「それより安い値札はすべて使われている」「それより高い値札で使っているものは付け替えていない」が満たされる。

この位置を全探索し、さらにいくつ付け替えたかも全探索する。付け替えた数が $K$ 未満なら、固定した位置より右側にはもう使った値札はないとしてよい。あったとすると、適当に付け替えたり、あるいは位置をずらすことでそのケースを考慮できる。従ってこのケースでは、右側から価値の高い順に付け替えた数だけ貪欲に取ることができる。左側は $O(NK)$ のdpで全部計算可能。

ちょうど $K$ 個付け替えた場合は、右側から値札を $K$ 個動かした後、余った金額でさらに品物を購入する可能性がある。 $K$ 個までタダにできるとした金額に関するdpを行いたいが、状態 $O(NC)$ で遷移がそれぞれ $O(N)$ となり当然不可能。しかしタダにするのは高いほうから $K$ 個なので、どの品物までで $K$ 個の権利を使い切るか全探索し、品物は価値を見て貪欲に取るという方法で状態 $O(C)$ に落とせる。これで間に合う。

残り20分ちょっとでP5とP6の部分点をかき集めた。P5は0を1にする以外値を増やす手段がないことに注意しながら値の大小に関するチェックをし、さらに0を1にするために必要な1をその左側から抽出できるか調べれば1行のケースは通る。P6は始点と周期を全探索する愚直で部分点1。部分点2は、周期を調べるときに探す文字列自体が周期的だったらスキップするという枝刈りを入れたら通った。計算量解析はよくわかっていない。

残り数分でP5がフローではないかと疑ったものの、コンテスト後にしばらくやっても通らなかった。450点。順位表を見ると、思ったよりP4が解かれておらず、代わりにP5とP6がたくさん通っていた。P6はrun列挙というやつだろうか。コンテスト中も頭を過ったが性質を知らないため手が出なかった。

それからラノベを1作読了。「あたしは星間国家の英雄騎士！」。「俺は星間国家の悪徳領主！」の外伝。モブ視点で本編主人公が語られるシーンは楽しめたが、それはごく一部にしかない。当然外伝主人公の話が多く、そちらにはあまり惹かれなかった。

午前8時過ぎ就寝。

01/03(火)

午後5時起床。

昨日参加したDMOJのコンテスト期間が終了していた。最終順位は9位で、レートは2854→2897(+43)。

夕食を食べた後、少しだけ買い物に行って、帰ってきてからはこたつに入ってラノベを読んでいた。テレビの音声で集中できず終いには眠くなってくる始末。よっぽど深夜のコンテストまで寝て過ごそうかと思ったが、スマホを弄っていたらそのタイミングすら逃してしまった。

入浴し、午後11時くらいに軽食をお願いしたところ、お雑煮と焼鯛が出てきた。思ったよりガッツリ食事して半からCF。今日はHello 2023。

Dashboard - Hello 2023 - Codeforces

Aは正規表現で書くと/R.*L/にマッチするのが条件、に見えて実は/RL/でよい。文字列がLのみまたはRのみの場合だけ不可能。

Bは、とりあえず $n$ が偶数のケースは $+1,-1,+1,-1,\dots$ とすることで構築できる。サンプルを見た感じ $n$ が奇数のケースは不可能だろう、という気持ちになったが、念のため証明しようとしたら構築できてしまった。まずすべての $i$ について $s_i=s_{i+2}$ であることがわかる。よって数列が $a,b,a,b,\dots$ とおけて、 $a+b=\lceil n/2\rceil\times a+\lfloor n/2\rfloor\times b$ が条件になり、 $n\ne 3$ なら $a,b\ne 0$ なる解が存在する。

Cはちょっと面白い。条件が $\dots+a_m\le 0$ と $a_{m+1}+\dots\ge 0$ で表現できて、左右それぞれ似た感じに解ける。例えば前者については、 $m$ 項目から左に値をどんどん足していって、どこかで正になったら値が一番大きなものの符号を反転するというのを繰り返せばよい。値の取得は優先度付きキューで行った。

Dは言われたことを丁寧に実装するだけ。 $x\lt b_i$ なる $i$ を含まないように区間を取って操作する。 $b_i$ が大きなほうから見て、含められない $i$ はsetで管理した。最初から $a_i=b_i$ であるような $i$ に注意する。

Eは面白かった。求めたいのは強連結成分であって成分外からの入次数が0なもの。トーナメントグラフをSCCに分解するとパスグラフになるので、その始点と言ってもよい。出次数で降順ソートするとSCCと同じ順番で並ぶことに素早く気づけたのがよかった。これはクエリ $n$ 回で求まる。どこまでが始点の強連結成分になるかは、さらにクエリを $n-1$ 回使って調べた。

Fはサイズが偶数の部分木を全部0にできる。これを元にした自明な木dpで判定が行え、それを丁寧に復元する。遷移はXOR畳み込みで、愚直に $32\times 32$ 回計算したがかなり高速だった。

Gはエスパーした。三角形を適当な辺を下にして置くと、上から一つ、三つ、五つ、……の三角形が一つの行をなし、積み重なっているように見える。各行には上下方向の辺がいくつかあって、例えばこの辺がすべて同じ向きだと、明らかにその行を境に行き来できなくなってしまう。よって、どの辺を下にしておいた時の行を見ても、上下方向の辺の向きはどこかで食い違っている必要がある。

これは必要条件だが、実は十分条件でもあるのではないかと考えた。当然一般には十分ではないものの、今回の状況から最小手数で達成すれば実際に強連結になるらしい。出したら通ってびっくりした。以下では証明を考えず、単に最小手数を求める。

まず三つの $s$ の末尾が等しければOK。そうでない場合、適当に回したり反転することで $s_1$ 、 $s_2$ の末尾を1に、 $s_3$ の末尾を0にできる。いちばん外側の辺の状況をイラストと合わせたということ。このとき左下向きの行は両端の辺の向きが異なるため、考えるべき行が水平のものと右下向きのものの二つに絞られる。

基本的に1辺の向きを変えたら条件を達成した行が一つ増えるが、辺を共有している行があった場合はそこを変えることで一気に二つ増やせる。後者をできるだけ行うと手数が最小になる。条件を満たしていない行の検出はインデックスを丁寧に考えると簡単な条件になる。辺を共有しているかの判定はもともと簡単。

Hはラウンド2回を一気に行うことでサイズ $n$ の問題をサイズ $n/4$ の問題に帰着できそうに見えたが、それでも全然間に合っていない。

7完20位でかなり良かった。レートは2705→2841(+136)。Dはおそらくバリカンで髪の毛を刈る操作を表していて、昔それをchminと言っていたのを思い出した。Eはソートした列をどこかで切ったときに末尾のほうから先頭のほうに向かう辺があるかどうかが末尾側の出次数の和を見ることで判定でき、クエリ回数が $n$ になるらしい。

CFの問題言い当ててしまったな https://t.co/PvvwXR1zW9
— こたつがめ (@kotatsugame_t) 2023年1月3日

システスを見届けた後はラノベの続きを読んでいた。午前5時半就寝。

01/04(水)

午前11時半起床。軽くお雑煮を食べて、父の車で外出した。

まず、昨年末に購入した礼服の裾上げが完成していたので受け取った。ついでに真っ白のワイシャツと真っ黒のネクタイを買ってもらったので、これでいつ葬式があっても準備は万端というわけ。もちろん葬式なんてないほうがいいから、せっかく買ってもらってなんだがこの先10年くらいは実家で塩漬けにしておきたいものだ。

外出。礼服を購入してもらう。自分くらいの年齢になると一着持っておくべきらしい。
週記（2022/12/26-2023/01/01） - kotatsugameの日記

その後富山駅で下ろしてもらった。午後1時半、よことKRmei氏と合流。今日は夜までこの三人で遊ぶ予定。

最初に駅前に新しく経ったMAROOTというビルを見て回った。昔マリエに入っていたはずの書店がこちらに移動してきておりびっくり。

次に、駅に入って回転寿司を食べた。あまりお腹が空いていなかったため控えめに。二人の近況だったり高校同期のその後だったりが聞けて面白かった。自分は高校以前の交流がほぼ途絶えてしまっているのでこういう機会は貴重。

その後ゲーセンに移動。駅前のゲーセンといえばゲームインさんしょう富山駅前店だったがすでに閉店している。ところが最近、駅ビルにGiGOが入ったらしい。駅から非常に近いためかなり便利そう。チュウニズムは旧筐体と新筐体が1台ずつだった。2種類の筐体が混在している店舗を見るのは何気に初めてである。よくTLに新筐体の待ちでトラブった人のツイートが流れてくるため良い印象がない。

ゲームインさんしょう富山駅前店が今月末で閉店するというツイートが流れてきた。
週記（2021/10/25-2021/10/31） - kotatsugameの日記

混んでいたので、2時間弱で切り上げて夕食へ。ラーメン一心という店に行った。ここは富山地方鉄道の駅の裏にあって微妙にアクセスが悪い。雨も降っていて大変……と思っていたら、KRmei氏が駐車場などを辿って濡れずに移動する経路を教えてくれた。

さっきのゲーセンがある駅ビルに戻って、1階上のブックオフに行った。ゲーセンと同様これもつい最近入った店舗。しばらくうろついていたらよこが帰る時間になったため、KRmei氏と共に見送った。このまま新幹線で東京に戻るらしい。

KRmei氏も今日富山を離れるが、出発は3時間ほど先のようだ。せっかくなのでカフェに入り、時間になるまでしこたま話していた。自分は何でもかんでもツイートするがKRmei氏はそうではない。私生活についての話が興味深かった。おすすめの動画などを教えてもらった。

どういう経緯だったか忘れたが競プロの話になって、何やら興味がありそうだったのでしこたま布教した。なんとすでにPythonを少し勉強したことがあるらしい。おあつらえ向きすぎる。問題文をそのままコードに起こすのはできそうなので、最近の傾向だとABC-Bまでは問題なく通せるだろう。そこから先は知識が必要になってくるが、教材ならいくらでもネットに転がっているからぜひ頑張ってほしい。

午後10時前にKRmei氏を見送り、自分も父に迎えに来てもらって帰宅した。すぐ入浴。

THE名門校という番組が母校を取り扱った回の録画を見た。いろいろあったが今は素直に懐かしさを感じる。壁が黒板なりホワイトボードなりになっていたのは、大学にも同様の設備があるから、かなり便利だったのだろうということがわかる。それほど活用できた記憶はない。

その他、今日おすすめされた動画をいくつか見てからSRMの準備に取り掛かった。都合よくこどふぉっていたのでノートPCの環境を整えようとしたが、Appletを起動した後プラグインの設定中に時間切れ。結局Web Arenaで参加した。SRM843。

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

最初に、EasyとMedを落としたことを明記しておこう。下にある解法はコンテスト中の自分のもので正しくないということに注意されたい。

Easyは、まず一周聴いても退店しないケースを除いた後、入店タイミングを各曲の開始時間として全探索した。これで何曲聴くかはわかって、さらに次の曲が始まる直前までずらすことでそのようなタイミングがどれくらいあるかも計算できる。

Medは+がいくらでも使えるので数の表現を考える必要がない。値の小さなほうからdpした。遷移は $+1$ 、 $+5$ 、あとは自分以下の数との掛け算で、最後のものは全体で $O(N\log N)$ となる。

Hardは謎。連結成分を頂点数で表現しその列を状態としてdpしたところ、TLには間に合わないが手元でそこそこ高速に動くコードが完成した。入力パターンがかなり少ないので、全部埋め込んで提出。

Medがチャレンジで落とされ、Easyはシステスで落ち、Hard 1完で10位。レートは2912→2894(-18)で何とか軽傷といったところか。

Easyは最初に取り除かなかったケースでも必ず全曲聴くことになるケースがあって、この場合入店タイミングはいつでもよい。自分の解法だと次の曲が始まる前に退店するケースしか考えていないため、「入店直後と退店直前で同じ曲を聴いている」ケースを考慮できていなかった。

Medは大きな数と大きな数を足し算する必要があり、上に書いた遷移では考慮できていない。やけに簡単に解けたから提出前に結構疑う時間を取ったはずなのに、何を考えていたのだろうか。

Hardは頂点数が $S$ を超えた連結成分を全部マージして扱うと十分高速になるらしい。これが1000点ってマジ？

朝までラノベを読んでいた。「現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変」4巻を読了。3巻巻末で2021年冬発売と予告されていたのが1年遅れたわけは、後書きによれば「昨今の情勢と諸事情」らしい。昨年はなんともすごい年だったからわからないでもない。何であれ続刊してくれて嬉しい。

この巻は、これまで破竹の勢いでグループを拡大していた主人公が負ける話だった。なろう版でも読んだので展開は知っていたはずだがやはり辛い。ただ、改めて読んだことで前後関係への理解が深まり、納得はできたと感じている。

この先は金融以外のシーンも多くなりそう。なろう版では話がとっ散らかっていた印象もあるが、結局幼い主人公は金融に関して表舞台に立てないのだから、その分の無双を別の話で補給していく感じで楽しみたい。5巻出版は決定しているようだ。気長に待つ。

それに合わせてですが、五巻決定をご報告させていただきます。
　五巻は来年中に出せたらと思っているのですが、昨今の情勢から確実な日時が言えない事についてはお詫びさせてください。
　これも読者の皆様の応援の結果でございます。
　どうかこれからもよろしくお願いいたします。
— 二日市とふろう　(旧名:北部九州在住) (@hokubukyuushuu) 2022年12月25日

午前6時頃、父の朝食に便乗して自分の食事も用意してもらった。

布団に戻ってハーメルンを1作読了。「ナンジャモさんのお隣さん」。まだ3話しか投稿されていないが、転生前の手持ちがそのままということで、なつき度やレア度に関してニヤニヤできる設定が多い。

syosetu.org

午前7時頃寝落ち。

01/05(木)

午後1時半起床。久しぶりにメールの確認をしたら、指導教員の先生から一昨日届いたものを発見した。しかも返信を求められている。もはや謝るしかない。

そのまま布団でハーメルンを読んでいた。午後4時から午後6時半までの二度寝を挟みつつ、2作読了。

1作目、「消えた天才が喫茶店やってる話」。過去のバンド名をひた隠しにしているように見えて、早々にポロっと明かしているのが読んでいる側としては手っ取り早くて嬉しい。「音楽チートで世に絶望していたTS少女がSIDEROSの強火追っかけになる話」を読んでからオリ主が有名人なものを漁ってばかりいる。

syosetu.org

2作目、「ジム廃業して飛んでパルデア」。いろんな地方の、つまりいろんな世代の特殊なワザや能力を使っているのが面白かった。ポケモンのスカーレット・バイオレットが舞台だとナンジャモで配信者要素が摂取できるのがうれしい。

syosetu.org

今日の夕食は外食だった。どこに行くか決まっていないらしかったので焼肉と言い放ったら本当に連れて行ってもらえた。以前焼肉を食べた後の腹痛で救急車を呼んだのは記憶に新しい。今日はしっかり焼くことと、生肉を掴むトングと焼けた肉を食べる箸を使い分けることを意識した。

食事 pic.twitter.com/DGGs5TRUtt
— こたつがめ (@kotatsugame_t) 2023年1月5日

帰宅してハーメルン。「官能小説の世界に転生したらお隣さんが陵辱される直前の母娘だった件」を読了。R-18にならないくらいの淫靡さでよかった。

syosetu.org

入浴し、昨日のSRMのEasyをupsolveして、午後11時半からCF #842 div.2に出た。

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

Aは $x!+(x-1)!=(x+1)(x-1)!$ なので、 $x=k-1$ とすることで必ず条件を満たし、さらに明らかに最大。コーナーケースがあるのではないかと怪しんで $k=2$ など念入りにチェックしたが本当に何もなかった。

Bは要素の削除と追加を $k$ 個ずつ行うのではなく、一気に削除して一気に追加すると思ってよい。できるだけ多くの要素を削除しないままにしたいので、 $1,2,\dots$ の列がどこまで $p$ に部分列として含まれるかチェックし、その部分列以外の要素を動かす。

Cは値の降順に構築した。値 $i$ を埋める際は $a$ に出現する $i$ を数えて、3か所以上なら不可能、2か所なら $p$ と $q$ でそれぞれ置いてもう一方のマスを空きマスとしてチェック、1か所なら $p$ も $q$ もそこに置き、出現しないなら以前チェックした空きマスに埋める。

Dは操作後の数列 $n-1$ 通りを全探索する。完全に昇順に並べるケースとほとんど差がないので操作回数の差も小さい。具体的には $\pm 1$ になるので、どちらになるか判定。例えば $i$ と $i+1$ を逆転させて並べる場合、逆に最初の $p$ で $i$ と $i+1$ を入れ替えていると思うことができる。これを使って判定した。

Eは高々3回でソートできる。0回、1回、3回を数えて補正した。0回なのは最初から $p$ がソートされている場合で、1通り。1回なのは前 $n$ 要素または後ろ $n$ 要素がソート済みの場合で、 $2(2n)!$ から両端 $n$ 要素がソート済みの重複 $n!$ と全体がソート済みの場合を取り除く。

3回はちょっと面倒。前 $n$ 要素に後ろ $n$ 項に行くべき値があり、かつ後ろ $n$ 要素に前 $n$ 項に行くべき値があるケースである。包除原理で、全体 $(3n)!$ からどちらかを満たさないケース $2\times{}_{2n}\mathrm{P}_n(2n)!$ を引き、両方満たさないケースを足した。最後のケースは真ん中 $n$ 要素にいくつ前 $n$ 項に行くべき値があるか全探索すると求まる。

Fはジャンプする際 $\min(a_i,a_{i+1},\dots,a_j)=a_i,a_j$ になると分かったがそれ以上先に進まず。5完14位。

R-18のハーメルンを1作読了。「投げ銭アクメ系バーチャル配信者」。ちょっとついていきにくい描写もあるが序盤や番外編はなかなか好みである。

https://syosetu.org/novel/273699/

今日起きた時に発見した先生からのメールに今更返信。その後朝方までほかの人のブログ記事や動画を見ていた。午前6時頃に今日の昼食として用意されていたものを食べ、しばらく日記を書いた。

市役所の業務が始まるのを待ってマイナンバーカードを受け取りに行った。パスワードの設定は、希望の文字列を紙に書いて提出し、それを職員が見てPCに打ち込むことで行うらしい。パスワードを他人に見せるのが前提となる仕組みを、誰もおかしいとは思わなかったのだろうか。

帰宅して就寝。午前9時半だった。

01/06(金)

午後3時起床。

そのまま布団でR-18のハーメルン「セックスごっこをしてくれた幼馴染みとガチセックスする」を読了。腐れ縁なのでやり取りの口調が乱雑だが、盛り上がるとちゃんと引っ込んでくれるのは好み。

https://syosetu.org/novel/270067/

身を起こしてラノベを開いた。午後8時前に「紅蓮戦記」2巻を読了。面白かった。魔法でできることがかなりシステマチックに設定されているため、ファンタジー戦記モノとして読みやすいし、主人公の強さが魔力量のみでなく戦い方の点からもしっかりと感じ取れる。その二つを軸に面白いように勝つので、シンプルに楽しくもあった。

新しく出てきた敵国の王女様についてはちょっと消化不良気味。主人公を低く見積もる様子が念入りに描かれたので、終盤でスカッとした勝ち方をするのかなと思っていたが、そうではなかった。上で述べた魔法の制限もあって、王女様との戦闘は無双できるような状況ではなかったのが残念。

それ以外はスッキリまとまっていた。あまりにもまとまりすぎているためさてはと思ったら、案の定この巻で完結だった。ラストでその後について少し語られたのがありがたい。概ね満足していると言って良いだろう。

食事と入浴を済ませ、午後9時20分からyukicoder 372に出た。

yukicoder contest 372 - yukicoder

Aは $\max(A_1+A_2+A_3+B,3\max(A))$ 。 $A_1\le A_2\le A_3$ という条件に気づいていなかった。Bは和の中身が $n\ge M$ なら必ず0になるので計算しなくてよい。

Cは $a$ と $b$ を全探索。 $x=a(p^{-1}+p^{-3}+\dots)+b(p^{-2}+p^{-4}+\dots)=\frac{pa+b}{p^2-1}$ となるため、これが $1/N$ より大という不等式を解けば $p$ の範囲が求まる。分数が出てくると扱いが面倒なので、全体を4倍して $(2p-Na)^2\lt N^2a^2+4Nb+4$ と変形した。

Dはよくわからなかったので8次元累積和を計算した。値を周囲から包除原理のように集めてくる方法で計算したため、1マスのために $2^8$ マス見る必要があって1100ms。後から考えてみれば8方向に累積和を取るほうが簡単かつ高速だった。

Eは惑星の距離がいかついが実はギャグ。 $T_i\ne T_j$ ならどこかのタイミングで恒星から一直線に並ぶため、円運動の半径の差になる。 $T_i=T_j$ の場合は位置関係が変わらないため $(X_i,Y_i)$ と $(X_j,Y_j)$ の距離になる。これを使ってコストが $\max$ のdijkstraを行う。後者はもともと根号がついているため、それを外すだけでコストが求まる。前者は誤差が怖いので適当な範囲を調べて求めた。

Fを見て逃亡を選択。より多く解かれていたGに逃げ込んだ。いかつい式を丁寧に解釈すると $\sum_{n=L}^R\sum_{i=1}^{n-1}\binom{n}{i}^2$ になって、内側の和をWolfram|Alphaに投げたら $\binom{2n}{n}-2$ となった。あとは $\binom{2n}{n}\bmod M$ を一つずつ丁寧に求める。

$M$ を素因数分解して $\bmod{p^e}$ ごとに計算し、中国剰余定理で復元した。すべての値を「素因数 $p$ の個数」と「残り」の組として保持する。階乗をこの形式に直すのはルジャンドルの公式っぽく行えて、除算も「残り」の部分だけ真面目にやればよい。その「残り」は $\bmod{p^e}$ で計算する必要がある。うっかり $\bmod p$ で計算していたため、全然合わずかなり長い間苦しんだ。

Gに時間を取られこれ以上は解けず、6完9位。

何もやる気が出ずラノベに手を出した。「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」8巻を読了。主人公が、政治的な事情もあってヒロインの一人と結婚した。そんなメインを張るようなキャラだとは思っていなかったためかなり衝撃的だった。そして次巻、完結らしい。ずいぶん急だと感じたが、実際未解決で残っている話は少ないのかもしれない。よく覚えていない。

仙台には明日帰る。乗車券の有効期限が明日までなのとABCがあるから。仙台から持ってきた本が1冊、帰省の道中で買った本が7冊だった。今読み終えた本で帰省中に7冊読んだことになるから、仙台に持ち帰るのはたった1冊。完璧。

午前5時まで日記を書き、布団に入ってハーメルンを1作読了。「グロリアス軽戦車」。途中絵が描けず逃亡したあたりで苦しくなって少し間が開いていた。読んでみると案外すぐに回復して、結局はハッピーエンドになってくれた。

syosetu.org

午前6時半就寝。

01/07(土)

正午過ぎ起床。なかなか起きられなかったため昨日考えていたスケジュールは破綻してしまった。まあABCまでに仙台に着けばよいので余裕は結構ある。その上年末年始だから臨時列車が走っているらしく、ちょうどよい時間にかがやきがあった。来るときも乗ってきた途中停車が全然ない速い新幹線。

食事して荷物をまとめ、出発。富山駅までは父の車で送ってもらった。残り20分で特急券を買う必要がある。改札横の券売機は1台が修理中で残り1台に数人待ちがいたが、みどりの窓口の中に3台あってそちらは待ちなしだった。無事購入に成功。父と別れ、乗車した。

持ち帰ってきた本を開いたが眠気が強く、大宮まではずっと寝ていた。乗り換えて仙台までは、今度はなろうをずっと読んでいた。結局本はほぼ進まず。

午後5時半ごろ仙台に到着し、即座にゲーセンに向かって午後8時前まで11クレプレイした。新曲を埋めたのと14+のSSS+が一つ、また新年初の理論値も出した。チュウニズムのグッズキャンペーンは今最後のキャラクターと引き換えられる期間で、今日で無事必要ポイントを集め終わった。一安心……と思いきや、チュウニズムデュエルが終わっていない。01/11までにあと10クレほどプレイする必要がある。

まぜそばを食べて帰宅。途中で、新幹線で読んでいたなろうを読了した。「Killer Queen～FPSで幼馴染(美少女)を最高に幸せにする方法～」。

https://ncode.syosetu.com/n7715hb/

主人公が強くてよい。現実感との兼ね合いかポロっと負けてしまうことも何度かあったが、FPSの競技シーンを知らないのでもうちょっと無双してくれたらなあとか考えていた。配信をサポートするのに会社を立ち上げたり、過去のしがらみが顔を出したり、風呂敷は結構広がっているものの残念ながらエタっているように見える。後者についてはしっかり向き合うと辛そうだし、順調なところで途切れているのはむしろ読みやすかったかもしれない。

午後8時半ごろ帰宅。準備して午後9時からABC284に出た。

AtCoder Beginner Contest 284 - AtCoder

Aは1行読み飛ばして残りはtac。readを無引数で実行するとジャッジの環境では何も読まれないらしく、 $N$ が出力に残って1WA。手元と挙動が違う。bashで通したあとVimで書き直したら縮んだ。

ここからはC++。BCはやるだけ。Dは $\sqrt[3]N$ まで調べると $p$ または $q$ が見つかる。 $p$ が見つかればよい。 $q$ が見つかれば $p=\sqrt{N/q}$ とわかるが、うっかり $q+1$ から順に試し割りで見つけようとしてしまいTLEを出した。続けて行っているから合わせて $O(\sqrt[3]N)$ だと思ってしまった。

Eはよくわからないが10⁶本見つかった瞬間打ち切るdfsで通るだろうと思って提出。案の定通った。Fは $T+{\rm rev}(T)$ と ${\rm rev}(T)+T$ それぞれにZ-algorithmを適用すれば解ける。

Gは $A$ をfunctional graphと見たとき、 $i$ からスタートしてループに入るまでの長さが $S_i$ になる。 $S=S_i$ となる $i$ と $A$ をまとめて数え上げた。ループの長さを $L$ とすると、まず頂点を $S$ 個選んで並べ、その後にループの頂点を $L$ 個選んで並べ、残りはなんでもよい。つまり ${}_N\mathrm{P}_{L+S}\times N^{N-L-S}$ 通り。これに $S$ を書けて足し合わせたい。

$S$ と $L$ でループを回すのではなく $S+L$ と $S$ でループを回すとよい。上の場合の数は $S+L$ ごとに一定で、 $S$ の寄与だけ別に計算することができる。 ${}_N\mathrm{P}_{L+S}$ は割り算を使わず計算できるので $\bmod M$ でも安心。

Exには手も足も出ず、残り時間はコードゴルフをしたりシャワーを浴びたりしていた。7完15位。水曜日に競プロを布教したKRmei氏も無事コンテストに出ていただけたようだ。今回はグラフを扱うテクニックを知らないとCが解けないので、解説を読むなりしてぜひ頑張ってほしい。

コードゴルフ。AはVim 9Bが最短でよさそう。提出時間の差で勝ち。Bは今のところdc。CはPerlで、負け。Dはfactorを使うまではよくて、文字列置換で答えを作れることに気づいてVim 35Bでホクホクしていたらdcに投げたほうがもっと短くなるらしく大敗。EはPerlがTLEしたので放置。以降は手付かず。

午後11時からTROC #30に出た。

https://tlx.toki.id/contests/troc-30

Aは $\max(N,\lfloor N/Y\rfloor\times X+(N\bmod Y))$ 。Bは $A$ の値を区間に伸ばすと見なせるやつで、 $B$ から隣接する重複要素を取り除いたものが $A$ の部分列になっているかチェックすればよい。FA。Cはいくつか手で試し、どうせ $2\min(N,M)$ だろうと提出した。

Dは $-1$ を全部取り除いた列と同じ値が達成可能で、当然最小。そこに $-1$ を入れると、bitごとにどのタイミングで切り替えるかの自由度が生まれる。それを掛け合わせたものが答え。

Eは最初に最小全域木を求め、その上のimosで必要な辺をチェックした。reading-zeroをつけないようにするなど出力が面倒。

Fの操作は $K$ 項まとめてswapすると読み替えられる。そこからかなり時間がかかった。結論から言えば、要素を $i\bmod K$ でグループ分けしたとき、それぞれをソートするだけで全体もソートされることと、各グループで転倒数の偶奇が等しいことが条件になる。

1項だけずらして2連続で操作することであるグループだけ転倒数をちょうど2変化させることができ、1変化させようとしたら1回の操作で全グループ一気に変える必要がある、ということから後者の条件が出る。前者のチェックし忘れで1WA。

順位表を見てHに進んだ。最初に $A$ 全部のbitwise ANDを全体から引いておくことで、両方のグループのbitwise ANDを0にする問題になる。2段階の包除原理を行った。つまり、まず最初の包除原理で一つ目のグループのbitwise ANDを固定し、二つ目のグループのbitwise ANDが0になる場合の数を数えるためにさらなる包除原理を行うということ。

決め打った二つのbitwise ANDは共通のbitを持たないため、全体で3²⁰通り調べればよい。しかし手元で2.5secくらいのものを提出したのにサンプルでTLEしてしまった。3²⁰通り全部計算するわけではなく条件のチェックなどが入るため、計算をまとめるのも難しい。

いろいろ見方を変えた結果、「 $i\subseteq j\subseteq i\cup I$ なる $j$ に $+1$ 」というクエリを2²⁰回処理できればよくなったが、解けただろと思っていろいろ試しても全然高速にならず愕然。そのままコンテスト終了。

終了3分後にHが通った。上のクエリが微妙に高速化できたようだ。 $i$ と $I$ のサイズを比べて小さいほうの部分集合を全探索する。 $I$ のほうが小さい場合はそのまま $+1$ すればよい。 $i$ が小さい場合は20次元のimos法、つまりゼータ変換を考えると、 $i$ の部分集合と区間の終端を表す $\pm 1$ を置く場所が対応していて、最後にゼータ変換することで必要な $+1$ だけがうまく行える。

Hが思ったより解かれており6完23位、2786→2771(-15)。優しい。ジャッジがAtCoderくらい強くてHの3²⁰を通してくれたらもっと優しかった。

しばらくYouTubeを見たりハーメルンの更新を読んだりした後日記を書いた。午前7時半就寝。

01/08(日)

午後4時起床。布団に横たわったままハーメルン「お辞儀様の娘はTS転生人外幼女」を読了。

syosetu.org

主人公以外の視点がちょくちょく挟まるのが嬉しい。ホグワーツとどう関わるのか楽しみにしていたが、最新話の時点でハリーは5歳。まだかなり遠そう。しかもすでに原作からかなり外れていて、全く先が読めない。

午後7時過ぎに布団から脱出して食事。

01/11にホスフィン・たいぺーと遊ぶ。いつものように外で食事してから我が家で家飲み。そのための酒類やボードゲームをいくつかAmazonで購入した。ボードゲームについては有識者に意見を聞き、「ito」「タギロン」「ギャンブラー×ギャンブル！」を注文した。

3人で遊べてAmazonで買えるボードゲームを探しています
— こたつがめ (@kotatsugame_t) 2023年1月8日

午後11時半からECR141に出た。

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

Aは降順に並べると大体うまくいく。最大値が二つ以上あるケースが問題で、特に全要素が等しい場合不可能。そうでない場合は最大値でない要素を一つ先頭に置けばよい。

Bは $1,n^2,2,n^2-1,\dots$ と並べるだけであり得る差がすべて得られるらしい。行列をジグザグに埋めた。

Cは勝利回数 $k$ を全探索。基本的にコストが安い人から $k$ 人に勝つことを目指すが、 $k+1$ 番目の人だけは勝利回数が $k$ 回または $k+1$ 回となって自分の順位に影響するため、その人に勝つか負けるかは両方試す必要がある。

Dは次の操作に使う項の値を持ってdp。それが0なら2種類の操作のどちらを選んでも列は同じ。0でないなら他の列と重複しない新しい列が二通り得られる。

Eはちょっと手こずった。すべての $i$ で $\left\lceil\frac{a_i}k\right\rceil\le\left\lceil\frac{b_i}k\right\rceil$ を満たすことが条件。最初、商列挙で調べようとしたが、 $O(n\sqrt n)$ が2.5secくらいかかって間に合わない。改めて式をよくにらみつけると、これは $[b_i,a_i)$ に $k$ の倍数がないことと同値。この区間にチェックを入れておき、 $k$ ごとにその倍数のチェックを全部見に行くと $O(n\log n)$ で解けた。

Fは順列が一つの場合、それをfunctional graphと見たときの連結成分数を $n$ から引いたものが答え。 $i$ で操作すると $i\rightarrow i$ というサイクルが独立するが、すべてのサイクルがそのような1点のみのものになるまでの操作回数なので、各サイクルにつき一つずつ操作しないインデックスがある。

順列が二つの今も同様に、操作しないインデックスの個数を最大化することを考える。そのようなインデックス集合の条件は「どちらの順列でも一つのサイクルに二つ以上乗っていないこと」と書ける。これは最大流で表現できる。

Gは手も足も出ず、6完9位。Eを商列挙で通した人がいるらしい。どうやったのか見に行くと、 $\sqrt{b_i}$ で処理を分けるちょっと面倒な書き方だった。商列挙自体は、商が $q$ となる最大の除数が $q$ で被除数を割ることで求まるのを使うとシンプルに書けるのだが、こちらだと割り算の回数が少し多いようだ。

新春TechFUL Coding Battle 2023に参加した後日記を書いて午前9時半就寝。火曜日までなのでここには何も書けないし、正確な時刻を記録するのも躊躇われる。実はECRが終わってからTechFULを解き始めたというわけでもない。とりあえず点数が見える部分は理論値で通せた。

https://techful-programming.com/user/event/3814

2023-01-02

週記（2022/12/26-2023/01/01）

工事中

12/26(月)

午後2時半ごろ起床。布団でしばらくハーメルンの更新を読んでいた。小一時間経ってようやく布団から脱出。

大学生協に向かい、菓子パン等と予約していたラノベを購入した。これが年内最後となるはずだ。本来は12/28に発売されるラノベも数冊予約しているが、その日はICPCで仙台にいないし翌日から生協が年末休業に入るので、受け取りは年明けになる。

帰宅してインターン先の定例会に参加。今週も進捗は特になく、タスクは先週金曜日に言っていた軽いもののみである。

勉強会はマネジメントの話だった。質問することの心理的安全性については数学のセミナーでも覚えがある。自分の疑問が学部レベルの知識かもしれないと思うと聞くのを尻込みしてしまうが、今はたった4人でやっているので気軽にセミナーを止めることができる。

終わってから先週の週記を投稿した。年内最後だが今回も校閲できていない。この後の時間はICPC準備に充てるつもりだったのに、開放感からうっかりYouTubeを見て1時間以上の時間を無駄にしてしまった。

ICPC準備、特にライブラリの印刷に取り掛かる。コロナ禍前と同じく以下のツールを使った。以前印刷したときのファイルを見るとタイムスタンプが2019年11月の日付になっていて、かなり懐かしい。

GitHub - maze1230/Library-TeX-Generator: 競プロのライブラリからTeXファイルを作る

手持ちのライブラリから必要なものを抜き出し、さらに自分では持っていないが持ち込みたいライブラリを用意する。ei1333さんのライブラリとbeetさんのライブラリを眺めていくつか窃盗した。さらにACLからも $O(\log N)$ 二分探索付きセグ木を持ってきた。

https://ei1333.github.io/library/

https://beet-aizu.github.io/library/

全部集めてツールを動かす。日本語が含まれると壊れるらしく、さらに一度動かすとTeXの機能でキャッシュか何かが残ってしまうため、解決に結構手間取った。なんとかコンパイルしてPDFを用意し、印刷。20ページを両面印刷して、A4用紙10枚ぶんとなった。

シャワーを浴びてからチーム紹介ドキュメントのメイキング記事を書いた。明日印刷されたものを手に入れたら写真を撮って貼るだけで公開できるようにしておきたかった。

すでに午前3時。そこから明日の持ち物の準備をして、就寝は午前4時半だった。

12/27(火)

今日明日がICPCアジア地区横浜大会だった。この期間のことは大体参加記の方に書いてある。日記では、ICPCにあまり関係ないと思って参加記に書かなかったことを補足するだけに留める。

01/18追記：参加記を投稿した。

kotatsugame.hatenablog.com

午前8時起床。この15分前にも目覚ましをかけていたはずだがそちらは気づかなかったらしい。ちょっと危なかった。

朝食は午前9時過ぎ、仙台駅の立ち食いそば屋で、肉うどんだった。

昼食は正午ちょっと前に横浜駅のレストラン街のパスタ屋。朝食が思ったより腹に残っていたため、サラダとデザートのみをそれぞれ単品で頼んだ。自分たちが入店してすぐ正午を回り、それから一気に行列が伸びた。かなりタイミングが良かったらしい。

夕食は午後7時から、中華街の中華。2018年も中華街で食べたはずだが、どの店で食べたか最早記憶にない。お酒を少し飲んだ。やはりビールは苦手である。中華のコーンスープは好物なので、また食べられて良かった。

夜解いていたPCKの問題は、具体的には2021年予選の6問目から11問目。

11問目は多分 $O(HW(R+C)\log(R+C))$ で解いたはず。考慮する長方形領域をずらして差分更新することを考えると、値の追加・削除・下から $K$ 番目の取得が $O(\log)$ くらいでできれば嬉しい。 $K$ が定数なので下位 $K$ 個とそれ以外に分割して値を保管すればよく、multisetで可能。

しかしこれは手元で5.5secくらいかかってしまった。高速化ポイントが2箇所。まず、multisetをやめて削除可能priority_queueを使った。削除用のキューも持っておいて、値が一致する限り取り出すテクである。

次に、領域をずらすとき、以前は左端から右端にずらし終えたらまたリセットして左端から開始していたのを、ジグザグにずらして一切リセットしないようにした。以上を実装すると1.3secで通った。

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7256954

午後10時ごろにシャワーを浴びた。午後11時半くらいに上の問題が通って、それから少しだけ今日の行動記録をつけて就寝。今日はツイートもブラウザの閲覧履歴も少ないので、日を置くと何をしていたかわからない時間帯が増えてしまうのだ。

12/28(水)

午前6時半起床。昨日解いた問題についてSSRSさんからリプライが来ていた。 $O(\log)$ が落とせるらしい。更新回数 $O(HW(R+C))$ 回に対し取得回数が $O(HW)$ 回なので、取得の方に計算量を押し付けると良さそう。

朝食は午前7時、ホテルのビュッフェだった。

食事 pic.twitter.com/1VKMhiN9bK
— こたつがめ (@kotatsugame_t) 2022年12月27日

朝のスキマ時間に昨日のCF #841 div.2を解いた。参加記にも書いたように、そんな短時間では解き終わらなくて集合時刻に少し遅刻してしまった。

Dashboard - Codeforces Round #841 (Div. 2) and Divide by Zero 2022 - Codeforces

Aは一つの要素以外全部を1に揃えるのがよい。Bはできるだけ対角線に近いマスを通るべきで、 $\sum_{k=1}^n k^2+\sum_{k=1}^{n-1}k(k+1)=2\sum_{k=1}^n k^2-\sum_{k=1}^n k$ が答え。

Cは累積XORを見れば揃える平方数を決め打つごとに $O(n)$ で数え上げられる。考えるべき平方数はだいたい $\sqrt{2^{18}}$ 個しかない。

Dは二分探索。判定が $O(nm)$ で行えて、答えとしてあり得る範囲が $[1,\min(n,m)]$ なので思ったより高速だった。

E。コストに対して辺の候補を数えるのは、約数包除で $O(n\log n)$ になる。そこからどうすれば良いか迷ったが、貪欲に取ったら通った。未証明。

Fは和の和なので寄与を考える。 $i$ 、 $l={\rm lsl}(i)$ 、 $g={\rm grr}(i)$ を固定し、 $a_i=x$ に対し何通りの列があり得るかを計算してみると、 $x$ の多項式になった。 $x=1\dots k$ に対してその和を取るには、あらかじめ多項式補完で $\sum_{x=1}^k x^j$ の形の値を求めておけばよい。

午前0時前に帰宅し、一息ついてシャワーを浴びてからJAGにメールを送った。ここまでが参加記に書いてあること。

結構な時間TLを眺めて過ごした後、スポンサーブースを回って集めてきたものの整理をした。大きなものとしてはやはりKLabさんの技術同人誌だろう。パラパラめくって感想をツイートした。

スポンサーブースでKLabさんの技術同人誌を2冊いただきました！めちゃくちゃ手広くて興味深い内容ばかり、特に
・CPythonにおけるitertoolsの実装
・Makefile
・Pythonのマイナー文法
・Jupyterカーネル（実はWhitespaceが題材）
が好きです pic.twitter.com/OfQh2KImti
— こたつがめ (@kotatsugame_t) 2022年12月28日

その後何故かハーメルンの捜索掲示板を開き、朝方まで1作読んでいた。昨日と同様に今日の分の行動記録をつけ、午前7時就寝。

12/29(木)

午後1時起床。2時間ほどハーメルンを読んでから布団を脱出した。今日は帰省する日。インターンの12月分の稼働記録を整理し、ゴミを出してから、荷物をまとめて午後4時半ごろ出発した。

これまでずっと自由席で帰省していたが、今回は指定席。仙台から大宮まで1時間強、乗り換えが10分で大宮から富山までが2時間弱と、合計しておよそ3時間で着いてしまった。かなり速くてびっくり。混雑の度合いはなかなかのもので、満席とアナウンスされていたことを記憶している。道中はずっとラノベを読んでいた。

富山駅からは迎えに来てもらった父の車で移動。途中本屋に寄ってもらって、大学生協で注文せず残しておいた本を買い揃え、帰宅した。新幹線車内で読んでいたものはこのうちの一冊で、それだけ仙台駅の本屋で購入していた。

年末帰省した時に買って読む用として、ちょうどその時期に出版される本のうち何冊かはわざと注文しないままにしておいた。楽しみにしているシリーズの続刊があり、生協の開店を待たず入手できるという点でも嬉しい。
週記（2022/12/12-2022/12/18） - kotatsugameの日記

夕食を摂ってからリビングのこたつに潜り込んだら、小一時間出られなかった。なんとか脱出して入浴。午後11時過ぎに布団に入り、しばらくラノベを読んで午前1時前に就寝した。

12/30(金)

午後2時過ぎ起床。少し日記を書いてから昼食を摂った。

THIRD プログラミングコンテスト 2022（AHC017）のトップページが公開されていた。インターン先がまたしてもコンテストを開いてくださるらしい。AI開発部についてまず最初に書かれることがメンバーのレーティングというのは、前もって確認させてもらったときから思っていたがやはりインパクト抜群。TLでもそういう反応を見つけてニヤニヤしていた。

AtCoder Heuristic Contest 017 - AtCoder

外出。礼服を購入してもらう。自分くらいの年齢になると一着持っておくべきらしい。

帰宅して夕食を摂ってからラノベを読んでいた。「最強魔法師の隠遁計画」16巻を読了。前の巻でストーリーが一段落し、この巻はその後始末と次の展開への助走という感じだった。実はこれまで数巻かけて進行してきたのは書籍版オリジナルストーリーで、なろう版としてはまだ第4部が終わっていない。第5部冒頭のアルスが第1魔法学院を視察する話はかなり好きなので、早く本で読めないかとかなり前から心待ちにしている。

https://ncode.syosetu.com/n5606cq/

入浴し、午後11時半からCF。Good Bye 2022に出た。

Dashboard - Good Bye 2022: 2023 is NEAR - Codeforces

書く

5完298位で2773→2705(-68)。勘弁してくれ。

失意にまみれてラノベを1冊読了。「俺は星間国家の悪徳領主！」6巻。相変わらず面白かった。記憶によれば、この作品のなろう版を読んだときはこの巻かその少し後のストーリーまでしか投稿されておらず、その後読み進めてもいないため、7巻からは真に知らないストーリーが展開されるのではないだろうか。期待している。

YouTubeを見たりハーメルンの更新を読んだりして、午前6時半就寝。

12/31(土)

午後2時半過ぎ起床。昼食を摂ってからは夕方までずっと日記を書いていた。まだ月曜日の分も書き終えられていない。火曜日に突入してからはICPC参加記と並行して書き進めていた。参加記と日記の内容の違いについては、火曜日冒頭に書いた通りである。

午後6時半に夕食。年越しそばだった。

食休みのつもりでこたつに吸い込まれつつ、今年1年のレーティングhighest変化とこれまで解いた問題数をツイートした。結局CFのhighestは更新できず、なんならだだ下がりしたままの年越しとなる。今年解いた問題数は、カウントされているだけでも1500問程度らしい。

今年のレーティング最高値変化
AtCoder：2852→2882(+30)
Codeforces：2998→2998(+0)
CHUNITHM：16.90→17.00(+0.10)
— こたつがめ (@kotatsugame_t) 2022年12月31日

Solved By kotatsugame
AtCoder: 4228
Codeforces: 2197
AOJ: 1347
yukicoder: 1510
Library Checker: 25
CodeChef: 147
TopCoder: 156
Total: 9610https://t.co/0T2dyMlczx
— こたつがめ (@kotatsugame_t) 2022年12月31日

よくよく思い出してみれば、今年はLGMタッチしかけたことがあった。9月はじめの問題剽窃でUnratedになった回である。結局その後からずっと調子を落としたままだったので、せっかくのチャンスに余計なことをしてくれたなという気持ちがふつふつと湧き上がる。

昨日のCFで問題の剽窃が発覚し、Unratedになっていた。
週記（2022/09/05-2022/09/11） - kotatsugameの日記

普段AtCoderでの自分の動向を見守ってくれている父だが、それ以外のサイトは見たくてもよくわからないと言っていたので、CLISTを教えた。

kotatsugame - Coder - CLIST

日付が変わる直前まではまた日記、もとい参加記を書いていた。年が変わる少し前に今月・今年の読書記録を集計し、ツイート。なんと今年買った本の過半数を積んでいるらしい。もうどうしようもない。

12月の集計
買った：28冊
読んだ：10冊
積読：+18冊
積読（累積）：+134冊
— こたつがめ (@kotatsugame_t) 2022年12月31日

2022年の集計
買った：265冊（前年比-5冊）
読んだ：131冊（前年比-26冊）
積読：+134冊
— こたつがめ (@kotatsugame_t) 2022年12月31日

以下は年が変わる前後のツイート。毎年同様のツイートをしていたのに、去年はPASTを解いていて失敗したのだった。

明けます
— こたつがめ (@kotatsugame_t) 2022年12月31日

明けました
— こたつがめ (@kotatsugame_t) 2022年12月31日

年が変わったので、2023年用の読書記録と買った本の記録の記事を作った。

読書記録（2023） - kotatsugameの日記

買った本の記録（2023） - kotatsugameの日記

またしばらく参加記を書き、午前2時半ごろ布団へ。ブロク記事をいくつか読み1時間ほどしてから寝た。読んだのは他参加者のICPC参加記と、おすすめなろうまとめ二つ。後者についてはありがたくも自分のものを参考にしたと言っていただけている。リンクを貼っておく。

furutsuki.hatenablog.com

turtle0123-kyopro.hatenablog.com

01/01(日)

午前9時半起床。朝食はお雑煮とおせちだった。食べてからしばらくして外出。

まず祖母の家に言って挨拶した。車から降りる際にスマホを落としてしまい、後から確認したら貼っているガラスフィルムにヒビが入ってしまっていた。幸先が悪い。

次に、少し遠くの神社に初詣に行った。1999年生まれの自分は今年満25歳。本厄に該当するので、本殿に上がって厄除のご祈祷をしてもらった。実はこのためにスーツを着てきていた。

初詣 pic.twitter.com/ztLp1OCgQw
— こたつがめ (@kotatsugame_t) 2023年1月1日

最後に昼食を摂って帰宅。

大晦日に「沼ですが（しばし沈黙）。」から始まるツイートをしようと思って、忘れてしまっていた。同じ考えの人がいないか探したら見つかって救われた気分になった。

沼ですが（しばし沈黙）。正月は休むと言っていましたが、もう12月31日です。いつ研究室に来るのですか？
— null (@null_music_n) 2022年12月31日

日付が変わる前までずっと本を読んでいた。「11文字の檻」を読了。ノンシリーズ短編集と言って、著者の青崎有吾さんがいろんなところで発表した短編・ショートショートを集めているらしい。特に関連しない短い話を立て続けに読むのは思ったより疲れた。また、ミステリ要素のない作品はどれもあまり好みではなかった。

ただそういう感想を全部覆い隠してしまうくらい、書き下ろしの「11文字の檻」が面白かった。閉鎖空間での試行錯誤はワクワクするし、日数が記録されてどんどん経過していくのも良い。後者については、何かがカウントされているという点で「〔少女庭国〕」や「二〇〇〇一周目のジャンヌ」を思い出した。

本を読んでいる間に行ったことについて。夕食は午後7時だった。また午後9時からしばらくの間、「笑わない数学」というテレビ番組の録画を見た。確率論の回と、ガロア理論の回。

確率論の回はモンティ・ホール問題に多くの時間が割かれていて、知っているならそれ以上特に目新しいことはない。

ガロア理論の回はよくわからなかった。ある程度講義で習ったはずだがあまり覚えておらず、曖昧な記憶や知識との食い違いばかり気になってしまった。正四面体の対象変換は12種類で、図でも12個描いてあったのに、これを表す群が $S_4$ とされていた。それは4次の対称群で、サイズは24ではなかっただろうか。

入浴後、飲酒しながら参加記を書いていた。一合瓶で3本分空けてフラフラになった。

飲酒します pic.twitter.com/MAzUjz5WVR
— こたつがめ (@kotatsugame_t) 2023年1月1日

午前3時に布団に入り、少しなろうを読もうとしてすぐ寝落ちした。