2022-04-04

週記（2022/03/28-2022/04/03）

03/28(月)

先週の週記を投稿してから布団に入るまでは早かった。しかしすぐには眠れず、少しハーメルンを読んでから午前5時過ぎに就寝。

目覚ましのスヌーズを繰り返し、午前8時50分に起床。午前9時からパ研合宿2021第2日「SpeedRun」に参加した。

パ研合宿2021 第2日「SpeedRun」 - AtCoder

AはText。Bはdc。CはRaku。Dはすぐ短くなりそうには見えないので、とりあえずRuby。Eはdc。Fも最初からdcで書こうとして、 $\frac 1 N\lt \frac 1{N-1}\lt\frac 2 N$ を出力したところほとんどWA。こりゃ難しいぞとしばらく紙の上で考える。とりあえず $\frac 2{N(N-2)}$ は達成できそうだったので、ペナルティもないことだしとりあえず出してみるかと思ったらACした。 $\frac{N-3}{N-2}\lt\frac{N-2}{N-1}\lt\frac{N-1}N$ である。 $N$ が小さいケースは良しなに。この問題を含め、以降はSpeedRunと言ってもコードゴルフ向けではなさそうだったので、C++で書いた。

GはbitDP。Hは各条件についてそれを満たす数の範囲が二分探索で求まるので、共通部分があるか調べる。Iはよくわからなかったので、連結成分ごとに全域木を取って葉から揃えた。それも、いったん根まで値を持ち上げてから再度下に持っていくという、いかにも無駄なことをしていそうな操作。そういう簡略化をしても実装が面倒なことに代わりはなく、さらに操作回数を上から抑えられたわけでもない。適当に $N$ が最大のケースでチェックした後エイヤと提出したら通った。Jはdpを睨むと値が2通りしかないことに気づく。Kは対応する括弧のペアに対して、それらの内側を作る操作を他と独立に考えてよい。その方法の数は、内側の括弧列をまた独立したいくつかに分解して、それぞれの操作回数を掛け合わせたものと、操作順序の決め方の積になる。実装で少し悩んだが、stackを使う簡潔なコードが思いつけて良かった。

Lは、辺とそれを通る向き、またジグザグにおける山か谷かを状態として、それぞれコストを求めていくdijkstra。本当に何も考えていなかったので毎回次の頂点から出る辺を全部見ているため、ウニグラフで $O(M^2)$ になってしまう。テストケースが弱かったらしく爆速で通り、後からTwitterを見ていて気付いた。正しくは頂点ごとに辺の重みでソートして、隣接する辺にだけコストを移すというようなことをしないといけない。Mは、順列 $P=(P_1,P_2,\dots,P_N)$ が与えられたとき、 $P_i$ を $Q$ に追加したときの転倒数の増分がそれまでの $Q$ の構築によらず $\min(\#\{j\lt i\mid P_j\lt P_i\},\#\{j\lt i\mid P_j\gt P_i\})$ になることに気づく。あとは挿入dpを考えればよい。転倒数の和のほかに場合の数も持たなければならないように見えるが、実はただの階乗であるためその場で計算してもよい。

Nは $f(k)-g(k)$ を最高次から計算していった。 $i+1$ 次以上の項だけを計算した状態から $i$ 次の項を計算に含めるには、それまでの計算結果を $v\leftarrow vk+a_i-b_i$ のように更新する必要がある。ここで $|a_i-b_i|\le 2\times 10^5$ のため、 $|k|\ge 2$ の場合ひとたび $|v|\ge 2\times 10^5$ になれば二度と $|v|\lt 2\times 10^5$ にはならず、したがって $v$ の符号だけ見ていればよいとわかる。 $|k|\le 1$ の場合は普通に計算していけばよい。日記を書いているときに、ACしたはずのコードでしきい値を間違えていることに気づいた。OはSuffixArrayと高さ配列を使うことで、各 $l$ に対し $S[l:r]$ が良い文字列となるような最小の $r=r_l$ が求まる。クエリ $(L_i,R_i)$ に対しては $R_i\le r_l$ なる $l$ のみを考えたいので、 $R_i$ や $r_l$ で降順ソートして順に処理する。 $r_l-l+1$ をセグメント木のインデックス $l$ に置いて区間最小値を取った後に、 $l\le L_i$ かつ $r_l\lt R_i$ なるもののうち $l$ が最大のものを見つけて $R_i-l+1$ も計算に含めることで答えが求まる。

Pで30分くらい粘ったものの全く光明が見えず、最後10分程度はコードゴルフなどしていた。聞いたところによると1600点問題の強化版らしい。無理だ。結局PのACは出ず、それ以外を全問解いて優勝。Lで完全に頭がついていなかった以外は良かった。

コードゴルフ。A、B、Eは特に変なことをする必要もなく、速度差で最短を取れた。Cはコンテスト中のRaku 39Bに対し、Rubyでも39Bが出るらしい。これも速度差で危ないところだったな、と思いつつ眺めていたら1B縮んだ。Fはdcで $\frac 1 N\lt \frac 1{N-1}\lt\frac 1{N-2}$ 。 $N$ が小さいときの場合分けや、出力でfなりpなりを使って何とかいろいろ流用するのを頑張った。Mもコードゴルフしてあって、Ruby。これらと以下で述べるD以外は手付かず。

DはRakuでTLEしてしまったためRubyを書いておいたら普通に負けた。.tally.valuesした列をソートして $-M$ 番地にアクセスし、nilだったら代わりに $0$ を出力すればよいらしい。まったく同じことを、.tally.valuesの部分をシェルスクリプトで、残りをPerlで書いたら縮んだ。夕方になって、数列を空白区切りから改行区切りにする部分はdc -e?fよりfactorのほうが短いという更新で取られたため、Rakuでもうちょっと粘ってみた。いったんwordsで全部読んでから2行目だけ[2..*]で取り出していたのが遅かったらしく、2行目だけwordsで読んでそのまま.Bagに投げると2secギリギリで通った。

3回目のワクチン接種は今日の午後2時15分に予約してあった。仙台駅近くのヨドバシカメラまで行かなければならない。午後1時半過ぎに家を出た。

途中クリーニング屋に寄り、卒業式のときに着たワイシャツを預けた。このクリーニング屋は平日も休日も午後7時まで開いているらしいので、取りに来るのは結構簡単そう。オタク早口に加え、店の奥で人が電話していたので思わず小声になっていたこともあり、これだけの情報を聞き出すのにしばらく時間がかかった。

仙台駅東口についた時にはワクチンの予約時間を過ぎていた。構わず丸亀製麺で腹ごしらえしてから会場に向かう。特に何か言われることもなく、ガラガラの会場をスイスイ進んで10分程度で完了。経過観察を終えて出た。副反応に備え、駅の薬局で買い物。ゼリー飲料は必須として、薬は2回目のものが残っているので良い。冷えピタが残っているか全く覚えていなかったので、念のため買っておいた。また無関係な買い物として、ついに柔軟剤のボトルを見つけたので買ってしまった。先週せっかく洗ったボトルだが、めでたくお役御免となる。

柔軟剤は、いつの間にかリニューアルされてしまったのに店頭では詰め替え用しか見当たらなかったので、仕方なく現在使っているボトルを洗って詰め替えることにした。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

しばらく駅前をうろうろしてから帰宅。棚を開けると冷えピタの箱がデンと鎮座していた。基本買い得だろうと思っていたのだが、部屋に2箱ある状態を眺めると明らかに邪魔。失敗。

帰宅してすぐインターンの定例会。木曜日のミーティングで出たタスクに手を付けられていないので、先週の進捗はミーティングをしただけ。お先真っ暗。今週の勉強会はAHC009の話題で、全然考察できなかったな～と思いながら聞いていたのだが、途中急激な眠気に襲われしばしば意識を飛ばしてしまい、さらに申し訳なかった。気づいたこととして、コスト計算が経過ターン数 $t$ に対して $S=401-t$ のところ、 $S=201-t$ だと勘違いしていた。ゴールさえすれば $S\gt 200$ になるので、手数を多くしてでもゴールする確率を高められれば得ということになる。この事実が、先週の週記で触れた以下の方針（いわゆるハイパーロボット）でそこそこ点数が出た理由なのだろう。

できるだけまっすぐ進むような経路を作るのは、それなりに良い方針だったらしい。通路のつきあたりまで進むような移動でゴールにたどり着けない場合も、できるだけ近寄ってからフラフラ移動することを考えれば、疑似的にスタートとゴールの位置を近づけるという意味で十分効果があるようだ。
週記（2022/03/21-2022/03/27） - kotatsugameの日記

勉強会まで終わったあたりで、すでに腕の痛みが強くなってきていた。自転車で駅前から帰ってくるのも、ワクチン接種後に避けるべき激しい運動の一種だったのかもしれない。キーボードは打てるのでこのままコーディングし、先ほど述べたタスクをこなすことにした。改善案の実装はすぐ終わり、手元のデータで試した感じも問題なさそうだったので、デプロイ作業に入る。事前に用意してあるテストを走らせて、正常終了することを確かめる必要があった。しかし、触れていないはずの部分でめちゃくちゃエラーが出てしまった。しかもコンパイル時に警告が出たり出なかったりする。どちらも何が原因か全然わからないため、SlackにHELPを書き込んで今日は諦めることにした。

布団に入ってしばらくラノベを読み、午前0時半就寝。午後11時くらいに測ったときは熱は出ていなかったが、頭痛があったので冷えピタを貼っていた。

03/29(火)

副反応ツリー↓

ワクチン接種3回目 14:54
— こたつがめ (@kotatsugame_t) 2022年3月28日

午前3時、目を覚ます。明らかに熱が出ている。38.1度。薬を飲んですぐ寝た。午前5時半、再度起床。体温はあまり変わらず。布団をひっかぶっているのに汗が全然出ていないのが気になる。またすぐ寝た。午前7時、三度起床。まだ体温変わらず。今度は眠れなくてラノベを読んだ。

1冊読了。「私より強い男と結婚したいの」。陰キャだけど実は喧嘩がめちゃくちゃ強いヤンキー主人公のラブコメということで、つい最近同じようなラノベを数冊読んだ記憶があり、さすがに短期間に出すぎじゃないかという気持ちになった。それらと比べると喧嘩シーンの描写は結構短い気がしたが、書いてあることはなかなか過激で、ヒロインが殴られたり蹴られたりしていた。この作品のヒロインはこれまたヤンキーだったという事情もあるか。1巻の中にヤンキーを倒すことで問題を解決するシーンが複数盛り込まれており、インスタントな爽快感が得られた。ところで、このラノベも「漫画動画」が原作らしい。これまた最近本当に多い。

別のラノベを開いて少し読み進め、午前9時就寝。午後2時半起床。37.1度と微熱程度に落ち着いた。午後3時からパ研合宿2021第3日「パ研杯」に参加した。

パ研合宿2021 第3日「パ研杯」 - AtCoder

まずHに0を提出しておく。Aはdcで書いた後、grep -c 1111で良いことに気づいた。ただこれは答えが0のとき正常終了しない。同じ現象が発生した最短コードはほかにも複数あって、dcからシェルスクリプトを呼び出すことで+1Bで対処できる。ここからはC++。Bは列を2倍にして尺取りした。Cは5のべき乗を桁ごとに眺めて、周期が2のべき乗になっていることをエスパーした。

Dは難しく感じた。前提として、使う問題は2人とも解くか、太郎くんのみ解くとしてよい。まず、部分点は $A$ でソートして順に使うか試していくdpで解ける。ただここから先に進む方法がわからない。直感的に $A_i\gt B_i$ なるものは使わないのではないかと感じたものの、証明できなかった。実際これは正しくないようで、満点を取ったコードにこのフィルターを入れるとWAになった。 $A$ の昇順に見ると、 $A$ は使うなら見た順番に使えばいいので、 $B$ を使う基準を設定したい。適当なしきい値 $L$ を設定して、 $B\lt L$ なるものだけ全部使うようにすることを考えたが、これもダメ。しばらく苦しんで、ふと $B$ の昇順に見ることを思いついた。dpにおいて、 $A$ は使うか使わないかを全探索していると考えられる。だから $A$ の昇順に並べずとも答えは出せて、一方 $B$ を昇順に並べておけばそちらは順番に使っていくことができる。部分点のコードでソートの比較関数を変えると通った。

Eも難しい。小課題1はクエリごとに $O(N\log N)$ かけることができて、 $s/A_i$ をDSTに乗せ、二分探索でGCDが $1$ であるような区間を求めて数えればよい。小課題2は最初に全区間のLCM（ただし $10^9$ 以下）をカウントしてmapに持っておける。これまたDSTに乗せて、LCMが変化するタイミングは各左端に対して $O(\log N)$ 回しかないことを利用する。ここまでで350点で、Gに移った。

Gはオイラー路の存在判定。出現する頂点の次数が偶数であることと、連結であることを判定したい。小課題1は愚直にやってよい。小課題2は連結性とほとんどの頂点の次数が偶数になることがわかるので、 $i\lt j$ なるペア $(i,j)$ であって $u_i=v_j$ であるようなものの数を数えればよい。小課題3は辺を必ず2本ずつ使う必要があって、このとき頂点の次数は必ず偶数なので、逆に連結性が判定できれば良い。辺数が半分になるので $O(M^2\times\alpha(N))$ の定数倍8分の1が通らないかと思って出したが、当然のようにTLEした。この問題も350点で終わり。Fに移った。

Fは部分点の意味がよくわからないうちに直接解けた。 $u\rightarrow v$ （ただし $u\lt v$ ）という移動が $M-1$ 個あって、それぞれ $S-T$ 間のワープ路でどれだけ縮むかがわかればよいことになる。 $u,v,S,T$ の位置関係で場合分けしてみる。先に言っておくと、解法では区間内の値の個数とその総和を持つセグメント木を使う。

$u\lt v\lt S\lt T$ 、 $S\lt T\lt u\lt v$ のとき

縮まない。

$u\lt S\le v\le T$ 、 $S\le u\le T\lt v$ のとき

$u\lt S\le v\le T$ について、 $(v-u)-(S-u+1+T-v)=2v-(S+T+1)$ だけ縮む。 $u$ と $S$ の昇順でソートし、 $u\lt S$ という条件を満たす $(u,v)$ だけを考えた状態で、それぞれセグ木のインデックス $v$ に値 $v$ を入れればよい。取得する区間は $[\lceil(S+T+1)/2\rceil,T]$ である。 $S\le u\le T\lt v$ も左右反転して同様に行える。

$u\lt S\lt T\lt v$ のとき

$(T-S)-1$ だけ縮む。これも上と同様に値を入れたセグ木で、個数だけ取得することで求まる。

$S\le u\lt v\le T$ のとき

$(v-u)-(u-S+1+T-v)=(T-S+1)-2(v-u)$ だけ縮む。難しい。まず $v\le T$ のみを考えた状態で、セグ木のインデックス $v-u$ に値 $v-u$ を入れておく。取得する区間は $[\lceil(T-S+1)/2\rceil,N-1]$ である。これで、大小関係でいえば $uvST+uSvT+SuvT$ が得られた。次に、 $u\lt S$ のみを考えた状態で同じことをし、取得した値の符号を反転する。今度は $-(uvST+uSvT+uSTv)$ が得られた。互いに打ち消しあって $SuvT-uSTv$ が残る。

最後の $uSTv$ 、つまり $u\lt S\lt T\lt v$ について、この時実は $v-u\gt T-S+1$ なので、 $(T-S+1)-2(v-u)$ は必ず負になる。それらのキャンセルをキャンセルすればよいので、 $u\lt S$ のみを考えた状態で、セグ木のインデックス $v$ に値 $v-u$ を入れておき、区間 $[T+1,N-1]$ で取得することで必要な値が求まる。

以上ですべての場合が尽くされた。各 $(S,T)$ ペアについて、元の距離からの減少分が全 $(u,v)$ まとめて対数時間で求まることがわかる。最後のキャンセル以外を考察して書きあげたのがコンテスト終了20分前で、そこから詰めの解法をひねり出し、何とか終了10分前に通すことができた。

残り時間はE問題の小課題3を考えて、更新のたびに左右を見てLCMの変化をチェックすればよいなと考えつつ実装もせず終了。3000点で4位だった。マラソンを手付かずの0点にしておいたのは思想である。

コードゴルフ。Hは速度差で負け。Aは深夜になって、1111にマッチする行を抜き出すのではなく0にマッチしない行を抜き出すという方法で縮められていた。完全に頭から抜けており、縮められているのを見て放心した。他は手付かず。

インターンの業務を進める。昨日出ていた警告とエラーについて。まず警告が出たり出なかったりしていたのは、コードに変更がない限り再コンパイルしないというプロジェクト管理ツールの親切設計が原因だったらしい。詳細表示のオプションを設定して、コードに適当に変更を入れつついろいろ試していたら解決した。JavaのGenericsでComparableインターフェースを実装していることを要求するとき、<T extends Comparable>と書いてコンパイルが通ったので安心していたが、そこを咎められていたらしい。<T extends Comparable<T>>にしたら解決した。調べた感じ<T>ではなく<? super T>にするのが標準的に見えるものの、そんないろいろな型で使いまわす予定のコードでもないのでOK。

エラーについては結局わからなかった。昨日Slackに書き込んだHELPから進展がないうちに、エラーが出ずに正常終了することが何度か続くようになり、少なくとも今回の更新の問題ではないものと判断された。他の人の環境では再現しなかったらしく、かなり謎である。まあともかくデプロイは終了した。

37.3度。布団に戻ってハーメルンを読んだりYouTubeを見ていたら、chokudaiさんからリプライが届いていた。僕をあーだこーだーのゲストとして呼んでほしいという希望が来たらしい。chokudaiさんもリプライしてくるぐらいだから乗り気なのだろう。僕ももちろん悪い気はしないため可能であるとの返事をした。結構すぐになりそう。

@kotatsugame_t あーだこーだーゲスト希望来てますよ！！！！！！ pic.twitter.com/5vY6TMdFQN
— chokudai(高橋直大)🍆@AtCoder社長 (@chokudai) 2022年3月29日

午後10時にまた就寝。ここで日記の日付を切り替えておこう。

03/30(水)

午前0時、目覚ましで起床。SRMを逃したかと思ったが、午前1時開始だった。もう30分ちょっと寝てから改めて起きた。体温は36.1度と平熱に戻った。まだ腕が痛いのと、さらにそれを庇うような姿勢でいたからか全身が微妙に痛む。

午後1時からSRM826。直前、また証明書チェックに失敗していた。3か月周期か？という話が出ていた。

SRMにレジろうと思ったらアプレットが開けなくなっていた。証明書の確認に失敗している、というエラーが出る。PCを再起動するといけるという話を聞いて試すも効果なし。結局、Javaの設定を変えて証明書失効チェックを「チェックしない」にすると開けた。
週記（2021/12/27-2022/01/02） - kotatsugameの日記

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

Easyはさいころの出目を全探索したくて、実際できるので簡単。決めた出目数に対して勝ちパターン数と負けパターン数の差を計算して、これの和でdpを書く。Medは謎。問題文が微妙に長い。猫2匹とネズミの位置関係すべてに対して、問題文中に示されたターン数以内にネズミを捕まえるための、次の猫の移動方法をそれぞれ定めるということらしい。ある状態から勝ちパターンへの移動方法の列を出力するのではなく、状況ごとの最適解をそれぞれ見つけよということだと気づくのに少し時間がかかった。状態の遷移が有向グラフと見なせるので、トポロジカルソートの要領で書いた。少し怖かったのでテストを書きたかったが、あまりに面倒だったので諦め、祈って投げた。ターン数の制限もチェックしていない。これについては、BFSみたいな書き方をしているから必ず最短で、どうせ制限を満たしているのだろうと思えた。

Hardは面倒。まず適切な処理を行って、「各 $1\le i\le N\le 13$ に対して整数 $0\le x_i\le r_i$ を決めて $L\le\sum_i x_i\le R$ とする通り数を求めよ」という問題に帰着できる。ここは単なる面倒パートなので、問題の評価を下げるだけ。解法に至るまでの僕の思考は、 $x_i$ に関する条件を多項式 $\frac{(1-x)^{r_i+1}}{1-x}$ として表し、これらの積について次数 $L$ 以上 $R$ 以下の項の係数を足し合わせればよいというもの。 $1-x$ で割るのは累積和を取るのと同じだと思い出せば、 $\prod_i(1-x)^{r_i+1}$ の項 $2^N$ 個それぞれ独立に考えることができ、累積和を $N+1$ 回取った後の係数を組み合わせの形で書くことで $L$ 以上 $R$ 以下における和を求められる。コンテスト後のTLで見たが、これは包除原理の計算と同じであるようだ。 $r_i$ の制限を外すことを考えれば、そちらのアプローチになるのか。

サンプルを合わせて出したものの落とされた。ミスは2点。1点目は、負号の存在を忘れていたこと。2点目は、これらを任意modで計算しなければならなかったことによるミスである。組み合わせ $\binom{n}{r}$ を、 $r\le 13$ の範囲で求める必要がある。任意modなので割り算はできないため、 $n\times (n-1)\times \dots\times(n-r+1)$ が $r!$ で必ず割り切れることを利用する。 $n,n-1,\dots,n-r+1$ という列を用意して、 $1\le i\le r$ とのGCDを計算したりして割れるだけ割っていくのだ。最後は分母が $1$ になったような形になるため、分子だけmodを取りつつかけ合わせればよい。僕はここでGCDを使わなかったのでダメだった。

EMの2完で11位、レートは2587→2613(+26)でhighest。昨年の最後に記録したものをようやく上回れた。今年初めの-133が大きすぎた……。

CLISTに登録して、競プロサイトのアカウントをいろいろ紐づけてみた。826回コンテストに参加しているらしい。

https://clist.by/coder/kotatsugame/

TCO22 Stage3の結果が今日のSRM826で確定していた。僕はSRM825に参加していないのでちょっとひやひやしていたが、それ以外の成績がまあまあ良かったので問題なくRound4への進出が叶った。TCOの予選はcombinedのratedなので、毎年通行料などと言われて評判は良くない。Topcoderのシステムでcombinedにするのはさすがに時代遅れ。ナウなヤングはFull-Feedbackにしか出ない。

https://clist.by/standings/tco22-algorithm-stage-3-28608402/

朝からは日記を書いていた。調べものでYouTubeを開いた結果、午前10時から2時間ほどを適当な動画を眺めるのに費やしてしまい後悔。正午あたりにAmazonから荷物を届けたというメールが来た。部屋のチャイムが鳴らなかったので外に見に行くと、宅配ボックスに入れるでもなく地べたに放り出してあった。いわゆる置き配というやつらしい。どうやらデフォルトでは何もかも置き配になってしまうようで、アドレス帳から切り替える方法を教えてもらって設定しておいた。

また日記を書きつつ、ラノベやハーメルンを読む。途中で隣室に引っ越してこられた方とのエンカウントがあった。いい機会だと、自分が四六時中パソコンから出している音声が漏れていないか聞いてみて、特に何も聞こえていなそうなので大丈夫だった。ただ、初対面でいきなり騒音について気にするのは過去のトラブル（もちろんそんなものはないわけだが）を想起させるかもしれず、かなり良くない行動だったかもしれない。今になって悶々している。

集中を切らしてひたすら脱線しながらも、夜になってなんとか今日の部分まで追いついた。すでに1万文字を超えている。シャワーを浴びてから少しコードゴルフした。

パ研合宿3日目のB問題で、僕が尺取りで解いた問題。現在の最短コードは累積和を取った配列 $S=\left(S_0=0,S_1,\dots,S_N=\sum_i A_i\right)$ を用意して $S_i-X$ や $S_i-Y$ がまた $S$ に含まれるかチェックするという方針で、賢い。配列に要素を足しつつ逐一チェックしなくても、 $S$ と $\{S_i-X\}\cup\{S_i-Y\}$ をそれぞれ用意して共通部分を見ればよい。RubyのArray#&を用いて実装したのだがTLEした。まさか各要素が含まれるかチェックしていて遅いのか？と思うもさすがにそんなわけはなく、 $\{S_i-X\}\cup\{S_i-Y\}$ を作るのにflat_mapの代わりに使ったsumメソッドが遅かっただけだった。ここを修正してとりあえずAC。その後、 $S_0=\sum_i A_i$ から引いていく形で累積和配列を作ったり、flat_mapではなく普通のmapで済むように用意する配列2つの役割を入れ替えたりして縮めた。引いていく形の累積和配列だと最後に $S_N=0$ であるかチェックするだけで $A$ の総和に関する条件がチェックできて便利。加えて少しだけテストケースハックもしている。

atcoder.jp

午後9時就寝。

03/31(木)

午前4時起床。しばらくハーメルンを読んで、昨日まででほぼ最新話に追いついていたものを2作読了した。

1作目、「魔法科高校の劣等生・来訪者編クリアＲＴＡ」。基本的には面白かった。来訪者編という、原作で1年生時代終盤となんとも微妙な位置にあるシナリオをクリア目標にするのは目新しい。ただ、そこに至るまでのイベントがかなりすっ飛ばされがちだったのと、終わってからも原作が続いたことを知っている以上中途半端な終わり方に感じられたのがちょっと残念。シリアスなシーンでも主人公が語録ばっかり喋っているのが気になった。

syosetu.org

2作目、「たまに寄り添う物語」。ウマ娘二次創作でトレーナー主人公。8話しかないぞと軽い気持ちで読み始めたら、1話1話が長くて読むのに気合いが要り、大変時間がかかった。時間がかかったせいで内容を覚えていない……。何やら裏設定があって徐々に明かされている気配を感じるが、さすがにこのペースでは何かが判明する前にエタるだろうと思ってしまう。

syosetu.org

食事し、さらにハーメルンを読んで、午前9時頃再度就寝。次に午後3時半起床。またしばらくハーメルンを読み続ける。

午後5時過ぎに布団から出た。サークルの今年の入部届に関する質問が現サークル長から来ていた。僕も昨年、同じ問題に突き当たったので、そのとき碧黴さんとやり取りした文面をそのまま横流しすることにした。ちょうど1年前の日記に当時のことが記録されている。どういう質問かも書いてあるので、それごと以下に引用しておく。

弊サークルの入部届は、formの回答を送信すると記入したメールアドレス宛にメールが届き、そこに記載されたSlackの招待リンクやサークルで使っているGoogle ドライブへの招待を通じて活動に参加するという形になっている。どうやら去年のものをコピーしてきただけの入部届ではうまく動いていないようだった。そもそもどういうシステムでそのような連携が可能になっているのかわからなかったので碧黴さんに確認して、返信を待つことにした。
週記（2021/03/29-2021/04/04） - kotatsugameの日記

頭痛も腕の痛みもほんの少し残っているが、それ以外は回復したと考えてよさそう。今日はゲーセンに行こう。ついでに、今週月曜日クリーニング屋に預けたワイシャツがもう受け取れる状態になっているので、それも受け取ろう。そう思いつつシャワーを浴びたりしていたら、クリーニング屋閉店の10分前になっていた。慌てて家を飛び出し、チャリで爆走して、ギリギリで駆け込んだ。そんなピッタリに店を閉めているわけでもないらしく、問題なく受け取ることができた。ハンガーが大きくてリュックに入らなかったので取り外してもらい、畳んで持って帰ることにした。

クリーニング屋の近くに一風堂というラーメン屋があることを知っていた。普段の行動範囲から微妙に外れていたため、これまで入ったことがない。いい機会だと思い、今日はここで食事した。

その後ゲーセンに向かい、閉店までプレイした。先週火曜日の開店直後からいろいろ物が増えていて、チュウニズムの待ち椅子だったり、荷物入れやおしぼりが置かれていたりして、なかなか遊びやすそうな設備が整っていた。今日はもっぱら低難易度の99AJ埋め。12で12譜面、12+で1譜面、13+で8譜面、14で1譜面。特に12は全99AJを達成した。

Lv.12 全99AJ pic.twitter.com/SJUYquGGQ3
— こたつがめ (@kotatsugame_t) 2022年3月31日

「祈 -我ら神祖と共に歩む者なり-」を解禁した。昨年9月末に追加された楽曲なので、ちょうど半年遅れか。走るべきマップが多すぎる。譜面動画も手元動画も、何なら公式音源も何度も聞いていたのだが、やはり筐体で聞くと各別に感じる。譜面はクソ難しいとはいえ、3分で4444ノーツとかいう頭のおかしい密度をしているので、何もわからないまま適当にやっていても案外失点せず、僕が目指していたSSの難度としては特別高くもない。3回で乗った。

祈 SS出た！ pic.twitter.com/ycS42Mlc0q
— こたつがめ (@kotatsugame_t) 2022年3月31日

いい汗かいて帰宅。そういえば日付が変わったので、身分はついに大学院生か。もしかして大学生協の会員カードも切り替わって、新しいものが届くまでラノベを割引価格で受け取れないか……？と思って焦る。調べると、学部生時代のカードをそのまま使えるらしかったので一安心。

YouTubeを見たりラノベを読んだりしていた。午前5時頃今年のJOI春合宿の過去問が公開されたが、特にコードゴルフできそうでもないためスルー。

午前6時頃にラノベを1冊読了した。「継母の連れ子が元カノだった」8巻。相変わらず面白かった。ここ数巻、主人公たちだけでなく、彼らを取り巻く人間関係の間にあった恋愛模様も一緒に描いていた覚えがある。この巻ではそれらをまとめてゴールインへと推し進めるような向きが感じられた。実際、ほとんどのペアは少なからず前進している。ほとんどと言ったが、では進まなかったのはどのペアか。……主人公たちである。もちろんイチャイチャシーンもそこから生まれた葛藤もあり、しかし何か具体的な成果に結びつきはしなかった。伊理戸きょうだいだけ、本当に一歩も進んでおらず、読みながら作者の良い意味での悪意を感じていた。ラスト、ヒロインの心にほんの少しの勇気が描かれるも、直後に特大な不穏の種が言及され、次巻が怖くも楽しみである。

布団に入ってハーメルンを読んだ。「東方遺骸王」の作者は感想にも逐一返信しているが、内容は肉まんと呼ばれるAAに鳴き声で統一されている。今日四月一日は、一年で一日だけその返信が日本語になる日だ。昨年はすっかり忘れていたので、今年こそ何か質問をしようと思い、しかし特に思いつかなかったので応援コメントだけ残しておいた。ちなみに設定としては、作者が日本語を喋っているのではなく、我々が作者の言語を理解できる（してしまう）ようになっているというものらしい。徹底している。

https://syosetu.org/?mode=review&nid=37761&volume=610

午前8時就寝。

04/01(金)

午前11時くらいに、隣室に引っ越されてきた方からご挨拶があった。寝起きで頭が回らないまま対応したため、あまりコミュニケーションをうまくできず残念。またすぐ寝た。

午後4時起床。ちょうど今年のJOIG春合宿の過去問が公開されたばかりなのを発見。どうせ難しいだろうと思ってあまりコードゴルフする気もなかったが、念のため確認してみると最初の問題は簡単だったので、縮めようと思い布団から出た。YouTubeを見たりしつつ、深夜までかけてA-Fをダラダラ解いた。

JOIG 2021/2022 春合宿過去問 - AtCoder

Aは簡単。適当に選んだ3人をどのように並べるのが最適か考えると、 $B$ が最小のものは $A$ が、それ以外は $A+B$ が記録に寄与する。よって $B$ の降順にソートし、 $B$ が最小のものを全探索することで解ける。これだけコードゴルフしておいた。Rubyで、ソートだけシェルスクリプトで書く。Bも簡単。次に行く地点の候補が複数あるなら左右それぞれ一番近いところだけしか考えなくてよく、それを4回繰り返しても16通りにしかならないため全探索できる。E問題もすぐ解けた。まずダブリングを思いついて、書き始めてから、後ろから見れば1ステップだけ進めた後は先に計算した答えを流用できることに気づいた。

残りは全部難しい。次にFを解いた。各予定が占有する時間をチェックしたとき、同じ時間に $N$ 機より多い飛行機のスケジュールが入っていなければよい。とりあえず決まっているスケジュールを入れた後、隙間にできるだけ離陸の予定を詰めたい。スケジュールを入れる方法が問題で、例えば滑走路1番から順に空いたところを使ってみるとサンプル4で上手くいかない。しばらく考えて、「離陸の予定でも埋められず無駄になってしまう時間」が最小の滑走路から離陸させればよいと気づいた。直前の飛行機が時刻 $prv$ に滑走路を占有し終わり、今新たに時刻 $A$ から飛行機が着陸することを考えると、間に詰められる離陸の予定は $\lfloor(A-prv)/K\rfloor$ 個で、無駄になる時間は $(A-prv)\bmod K$ となる。この値が最小になる滑走路は、使用可能な滑走路の $(prv\bmod K,prv)$ をmultisetで持っておけば二分探索で容易に求めることができる。あとはその滑走路が再度使用可能になるまで適当なvectorに退避させておけばよい。時刻 $T$ に $N$ 機の飛行機が着陸するとしておくと実装がシンプルになる。

次にC問題を2次元のデータ構造でぶん殴った。 $X$ 最大を固定する方針だと、1点更新と領域MAXができればよくなる。解説を読んでひっくり返った。言われてみれば簡単なことに見えるのに、全然気づけないものなんだなあ。代わりに、2次元のデータ構造に対する理解が深まった。

あらかじめ更新する点を列挙しなければならない代わりに座標が10⁹などでも使える2次元セグ木について。とりあえずX座標だけ集め（て座圧し）、セグ木を作る。領域クエリが来たら、そのX座標の区間を $\log$ 個の区間に分割する。あとは、その区間に対応するY座標たちでもセグ木が作ってあれば、そちらから値をクエリのY座標の範囲で取得しまとめることで答えが得られる。この「各区簡に対応する点のY座標たち」をあらかじめ集めておくために、更新する点を列挙する必要があった。逆に更新する点が分かっていれば、各点のX座標は高々 $\log$ 個の区間にしか含まれないので、全セグ木の要素数の和が元の点の $\log$ 倍で抑えられる。

まったく同じ要領で、今セグ木だった部分をBITに変えることで定数倍が良くなる。今回は両方BITに変えられるタイプの取得クエリだったが、実装を簡潔にするためX座標のみBITに変えている。1500ms。

解けた問題としては最後、D問題。最後の状態における $Y$ は $S$ の部分文字列（空文字列を含む）である。またその $Y$ を $X$ に作った時の $Y$ もまた $S$ の部分文字列となる。このことから、 $Y$ は常に $S$ の部分文字列だとわかる。よって「 $X$ に $S[l:r]$ を作るための最短時間」をdpで求めればよい。遷移は、 $l$ を1文字左にずらすか、 $r$ を1文字右にずらすか、または $Y=S[l:r]$ として、 $l$ スタートの部分文字列を作るときに貼り付け操作を何回か行うか。貼り付ける位置は $l$ から貪欲に決めてよく、操作回数を全部試しても全体であまり大きくならない。なので、貼り付けられる位置を高速に取得できればよい。

$r-l$ の昇順に状態を見て、各インデックス $l$ に対し $S[l:r]=S[i:i+(r-l)]$ なる $l\le i$ の集合をsetで管理する。削除タイミングはZ-Algorithmで $l$ ごとにまとめて計算できる。貼り付けられる位置の取得にsetの二分探索を使うとTLEした。そこで、最初の1回は二分探索を行い、その先はその位置で二分探索したときの結果を保存することで定数時間で取得できるようにした。これで何とか通って2100ms。解説を見ると、Z-Algorithmの結果から直接次に貼り付けられる位置が出る、つまり $i$ ごとに線形時間かけることで、各長さ $k$ に対し $S[i:i+k]=S[j:j+k]$ かつ $i+k\le j$ であるような $j$ のうち最小のものが求められるらしい。これを実装すると500msと爆速になり、コードも縮んだ。

CDEFのFAである。さらにCとDはJOI春合宿と共通の問題だったようで、そちらに提出してもFAだった。問題idが異なるので、一問解くだけで一気に2つのFAを取得できてしまった。部分点が違うらしいので、問題idを変えてあるのはその兼ね合いだろうか。いやC問題は全く一緒の問題だな……。

解く合間に行ったことをいくつか。まず3月分の読書記録をまとめてツイートした。先月もハーメルンに時間を吸い取られてカスみたいな結果に。

3月の集計
買った：27冊
読んだ：9冊
積読：+18冊
積読（累積）：+15冊
— こたつがめ (@kotatsugame_t) 2022年4月1日

午後6時頃、大学院入学手続きを完全に完了した。学務情報システムにログインして記入する箇所は、アカウントが大学院のものに更新される4月に入ってからでないと行えなかったのだ。試しに単位取得状況を確認してみると、学部時代に必死でかき集めた単位のリストが影も形もなく、ああ卒業したんだなあと感慨深かった。

昨日寝る前に「東方遺骸王」につけたコメントに返信が来ていた。これからも更新は続いていくということだ。今この作品は、特に曜日を決めず大体週に1回くらいの間隔で更新が続いている。これくらいのペースが一番安心感があるし、もう7年以上連載しているので、エタる心配はまったくしていない。逆に、つい最近まで毎日更新していた作品が急に止まったりするのに数回遭遇したので、そういうペースには少し不安感が出てきた。エタるときは本当にパッタリ止まる、と感じたが、よくよく考えてみれば更新の間隔を「頻繁」か「皆無」でしか把握していないからな気がしてきた。

夜中から朝にかけてはハーメルンを読みつつ日記を書いていた。午前9時くらいに今日の分に追いついて、ちょうどGCJ2022のQualification Roundが始まったところだったので参加した。

codingcompetitions.withgoogle.com

Aはいかつい見た目をしているがAAを出力するだけ、Bは各色で使えるインクの量を計算して貪欲に使う、Cは面数が少ないサイコロから順に使う、Dは木dp。どれも自明レベルとはいえ20分弱かかった。E問題はGCJあるあるの確率解インタラクティブで、全然わからない。しばらく考えているうちに椅子の上で意識を飛ばしてしまったので、諦めて寝ることにした。午前10時就寝。

04/02(土)

午後6時起床。ABCまでは昨日のGCJ-Eを考えたり、食事したりしながら過ごした。

GCJ-Eについて。適当にテレポートを繰り返して頂点の次数の平均を見るのがよいかと考えた。これはローカルテスターでは全ケース通るものの、提出するとWA。ローカルテスターをよく読むと乱数シードが常に固定されていたので適当に弄れるようにしたが、全ケース通るのは変わらない。グラフがランダムグラフなので、次数に偏りがあるグラフで困っているんだろうなと感づいた。次数がメチャメチャ大きい頂点は、適当にテレポートした頂点から何歩か動いたらほぼほぼ到達できるので、その事実を使ってチェックする方針だろう。しかし具体的にどう考慮するのかは上手い手が思いつかず、放り出した。

午後9時からABC246。

AtCoder Beginner Contest 246 - AtCoder

Aはパッとは縮まない。C++でmapを使った。Bはdcで書いて、一瞬コードゴルフして少し縮めた。そこからまたC++に戻る。Cは無駄にならない範囲で使った後、値段のあまりをクーポンのあまりで貪欲に処理する。Dは $a^3+a^2b+ab^2+b^3=(a+b)(a^2+b^2)$ と因数分解してみてどうにもならないことに気づき、 $a$ を全探索する方針に修正。 $b$ は二分探索してもよかったが、 $a$ を増やすと $b$ が減っていくことに気づいたので、適当にループでデクリメントすることにした。

Eは、ビショップの動きは下に書いてありすぐ角行のことだと思い出せた一方、ポーンの動きはどこにも書いておらず困った。困りつつ問題文を読み進めると、そもそも動かす必要のない壁役だとわかり安堵。今いるマス目に加えて直前の移動の方向を持つ探索を思いつき、それが01BFSで書けることもすぐに気づけた。Fは包除原理。Gはとりあえず答えを二分探索して、判定問題を解く。追加で必要な手数を持つ木dpで書けることの見当はついていたが、その頂点で移動をストップする場合にどうするかなど考えていると、木全体（つまり根の部分木）とそれ以外の頂点の部分木で解くべき問題が異なるような気がしてきて、合わせるのに時間がかかった。根にも整数 $0$ が書かれていると考えればわかりやすい。TLが6secでかなり謎だった。Exは左からdpを考えると行列積の形で書けるので、セグ木に乗る。公式解説が3行3列行列で書いていたところ、自分は2行2列行列を掛けて2行1列行列を足すという形で書いてしまったので、遷移を記述するのが少し面倒だった。

ノーペナ全完で5位。Exがすぐ解けたのはよかった。一方Gに20分以上かけているのは意味不明なので反省。

コードゴルフ。Aは列ごとに対称差集合を取る方針を考えていたが、bitwise XORでよい。演算子(^)が+^となり1B縮む。2要素のリスト3つを列ごと、つまりインデックスごとにこの演算子でfoldするのは、演算子にメタ演算子Zを前置したものでfoldするのと等しい。Rakuの機能をふんだんに生かして23B。Bは、コンテスト中は $\frac{A}{\sqrt{A^2+B^2}}$ と $\frac{B}{\sqrt{A^2+B^2}}$ をそれぞれ計算していたのだが、 $\frac{A^2}{A^2+B^2}$ と $\frac{B^2}{A^2+B^2}=1-\frac{A^2}{A^2+B^2}$ を作ってそれぞれ平方根を取るのが短くなるようだ。コンテスト後に他の提出を見て気づいた。

CはRuby。 $K$ の値を使った分だけ減らしていき、最後に残った端数のうち大きいほうから $K$ 個を取り除いて和を取りたい。下手なことをするとすぐnilが帰ってきたりREになったりするので困っていたが、ソートしたリストに[..~K]でアクセスするとよいことに気づいて結構縮んだ。DはAWK。普通にやると精度が足りずWAになるので、bashから--bignumオプション付きで呼び出している。Fは毎回リストの共通部分を求めるとTLEになるので、泣く泣くビット列で表現してbitwise ANDを求めている。Crystalを持ち出すことも考えたものの、そちらはmod付きべき乗が言語機能にないため短くならない。そのほかは手付かず。

午後11時半からCodeChef、April Cook-Off 2022。DとFを縮めたのはこのコンテストの後である。

https://www.codechef.com/COOK140A

CHEFSHOPPINGから難しかった。Noteの部分に「各要素は2種類の操作をそれぞれ1回ずつしか行えない」という新しい情報が書いてあり、五度見くらいした。問題文から読み取れないことをNoteの欄に書くのはやめてほしい。隣り合った要素しか消せないことを見逃したりして時間を費やし、最終的には使う操作が左から見てR...R_L...Lのように分解できることに着目して耳dpした。SORTDISは簡単。 $A_i\lt A_{i+1}$ なら $K\le\lfloor(A_i+A_{i+1})/2\rfloor$ 、 $A_i\gt A_{i+1}$ なら $K\ge\lceil(A_i+A_{i+1})/2\rceil$ が必要な条件なので、それぞれセグ木に持ってチェックする。

次にDINTに進んだ。bitsetで部分和dpを書いて、その値が全体のmax以下であれば達成できると考えるもWA。あきらめてSEQCOSTに進む。 $X$ で三分探索できそうなことは見えたものの、コスト計算にどうしても時間がかかってしまいそう。これもしばらくして諦め、LCASUMを読んだ。この2問はsolved数が同じくらいだったのだ。普段2頂点の距離をLCAを使って求めるのと逆のことをすれば、LCAの深さは2頂点の距離と2頂点の深さで書ける。この事実を使うと思ったがどうにもうまくいかない。また諦めて、先ほど少し進んだSEQCOSTのほうに注力することにした。

$X$ を決めたとき、遅延セグメント木を使えば $N\log X$ くらいでコスト計算が書ける気がしたので、とりあえずこれを出してみようと思った。しかし $X$ ノードの遅延セグメント木は冷静に考えて不可能。そもそもコスト計算がどのように行えるか説明する。まず $X$ 個の列 $B$ を用意して、各インデックス $i$ ではそのうち $\min(A_i,X)$ 個の列の後ろに $i$ を挿入できる。この時、 $B$ の末尾のインデックスが小さい方から $\min(A_i,X)$ 個選ぶのが最適なのでそうする、というもの。ここで、末尾が同じインデックスである列を圧縮して保持すればよいのではないかと思った。逐一マージすれば、圧縮した塊は1回見るたびに削除され、さらにその塊は各インデックスで高々2個しか増えないので、見る回数が全体で線形になる。見るべき塊も、直前のインデックスで見た塊の直後からスタートするので探索の必要がない。自分は連結リストを用いて実装した。これでも三分探索の $\log$ はつくのでかなり怪しく、TL 1secに対し手元では2.5secくらいかかっていたが、祈るように出すと0.8secで通った。コンテスト終了10分前であった。

3完22位でレートは2744→2640(-104)。ダメダメ。

コンテスト後のTLより。CHEFSHOPPINGは、 $\min(L_i,R_{i+1})$ の和になるらしい。確かにこのようにペアにすると、操作はどちらかしか行えず、しかも全体で $N-1$ ペアしかないのでどちらかは操作しなければならない。どのように選んでも全部消せるという事実は、操作して消すのではなく操作して要素をマージすると考えれば明らか。この考え方も目から鱗であった。SEQCOSTで連結リストを使った部分は、dequeで実装したという話も聞いた。これだとイテレータを先頭に戻したりする必要がなくて楽そう。

LCASUMをupsolveした。片方の木でマージテクをすることで、そちらのLCAが固定できる。マージするときに集合から集合へ移動させる頂点を $u$ だとすると、 $v$ はマージ先の集合のどれかになる。つまり、もう一方の木に対して「1頂点と頂点集合のLCA」が計算できれば良い。実はこれはLCAをオイラーツアー＋RMQで計算することを考えれば可能である。深さが最大となりうるLCAは、考えている頂点集合と $u$ をオイラーツアー順で並べたとき $u$ に隣接している必要があるので、その高々2つをチェックすればよいのだ。集合として持つのを頂点番号ではなくオイラーツアー順のインデックスにすることで、setの二分探索で取得できる。普段LCAはダブリングで求めていたので、その隙を突かれたという感じがした。

ラノベを1冊読んだ。「公女殿下の家庭教師」11巻。前巻に引き続き主人公とヒロインはあまり動かず、2人の描写も少し減って、代わりに年少組の活躍が描かれていた。今進行している戦争では、基本的に主人公の属する陣営が勝ち続けている。ただ勝ち続けるのも本当は本意ではなく、何とか講和しようと努力していたのに黒幕に引っ掻き回されて勝たざるを得なくなっているというのが正しいらしい。そうやって攻め入った結果、相手方で交戦派の意見が強まっており、このままでは戦争が終わらなさそう。また前巻ラストで主人公とヒロインは黒幕一味の幹部に手ひどくやられているので、今のところ苦しい展開。あとがきによれば次巻で大きく動くらしいので、楽しみである。

午前9時前就寝。

04/03(日)

午後2時少し前に起床。即座にOUPC2021に出た。

https://onlinejudge.u-aizu.ac.jp/services/room.html#OUPC2021

まずAを読んで、先頭に簡単枠が置いてあるわけではないことに気づいた。どうせ解くので頑張ってみることにする。探索するのは不可能なので、何らかの不変量を調べるのだろうと予想がつく。今回の場合、凸と凹の数は一致している必要があるので、それだろう。与えられたピースの凸の数引く凹の数 $d$ を求めて、あとは普通の辺の数にも気を配って場合分けしてみる。

まず、パズルが1行あるいは1列である場合。これは普通の辺を3つ持つピースが必ず与えられるのでチェックできる。 $-2\le d\le 2$ があり得て、 $d$ が奇数なら3つが、偶数なら2つが普通の辺になり、残りは $d$ から復元できる。以降パズルは2行以上かつ2列以上なので、全体で普通の辺が2つあるピースが4つ、1つあるピースが偶数個存在する。

普通の辺が2つあるピースが3つしかない場合、 $d\in\{-2,0,2\}$ で、復元できる。普通の辺が1つあるピースが奇数個だった場合は $d$ だけでは決められない。ここで、普通の辺に隣接する辺の状態だけ見た時の凸の数引く凹の数 $d'$ を考えてみると、これも本来は $d'=0$ となるべきであるとわかる。つまり今 $d'\in\{-2,0,2\}$ となって2辺が決まり、最後の1辺は $d-d'\in\{-1,1\}$ で決まる。

いよいよラスト、求めるピースの4つの辺がすべて凸か凹である場合について。 $d\in\{-4,-2,0,2,4\}$ で、このうち $d\ne 0$ のケースは回転や裏返しによって全部一致するのですぐわかる。最後の $d=0$ のケースだけ、凸凸凹凹と凸凹凸凹の2通りがあって、これは $S=0$ と $S=1$ に対応する。

以上で場合分けは完了。普通の辺に隣接する辺だけ見る部分でミスして1ペナ付けつつ、26分時点で通しFAとなった。

以降はsolved順に解いた。BFGは簡単。Eは $20$ 以下に含まれる数で素因数の重複度がどれくらいになるか考えると、 $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19$ が最大なので、LCMとしては $(4+1)(2+1)(1+1)^6=960$ 通りしか考えなくてよい。それらを列挙せずとも、頂点ごとにそこにたどり着けるLCMをsetで持っておけば十分高速になる。Cは先頭車両から足りない強さをカウントして、見ている車両を守れる鬼狩りのうち守れる車両の範囲の端が一番右である人をドーピングすればよい。

Hは面白い。直接色を塗りながら数えることにする。 $dp_{i,j}$ を、色 $i$ まで塗ってボールを $j$ 個使ったときの、順列の決め方も含めた場合の数としよう。使ったボール $k$ の行き先 $P_k$ もまた $j$ 個のどれかであることがわかるため、このような定義ができる。すると $dp_{i,j}$ は、 $\sum_{0\le k\le \min(j,A_i)}dp_{i-1,j-k}\times\binom{j}{k}\times k!$ と書ける。二項係数はボール $j$ 個のうち色 $i$ を塗る $k$ 個の決め方であり、それらを $P$ で飛ばしても色 $i$ を塗る $k$ 個から外に行ってはいけないので、 $P$ の決め方は $k!$ 通りになる。二項係数を分解すると累積和が取れる形になるので解けた。 $k$ の上限をミスして1WA。後から気づいたが、これらの階乗や二項係数は最終的に打ち消しあって $N!$ になるので、普通に累積和だけ取って最後に $N!$ を掛けるのでも正しい値が出るようだ。

Iはちょっと面倒。スコアの定義から、長さの和がスコアの積になる。よってクエリ $(x,y)$ は「 $x$ から見た $y$ の部分木に対する $\sum_u 2^{dist(y,u)}$ 」と、その $x$ と $y$ を入れ替えたものを掛け合わせて、さらに $2^{dist(x,y)}$ を掛けることで答えられる。上のような $\sum$ は、根をずらすことによってその辺の両端についてしか変化しないため、全頂点まとめて全方位木dpで管理することができ、 $x$ の頂点にいるときに $y$ の部分木に対して $\sum$ を取得、逆も同様にすればよい。

ただこれはコンテスト後に思い付いたことであって、コンテスト中はそのまま $y$ から見た $x$ の部分木についても考えようとしてしまった。このとき、 $x$ から $y$ の方向に1歩進んだ頂点を取得して、その分キャンセルする操作が必要になる。この「1歩進んだ頂点」を取得するのに、最初隣接する全頂点を試して距離を比較するという方針を取り、TLEしてしまった。「dfs順で $y$ のほうが $x$ より先に出現した場合、求める頂点は $x$ の親になる」という事実に気づいてAC。

Dは難しかったが、簡単な実装方針を選べたと思う。二分木の下から、持っている情報の範囲を管理しつつマージしていく。範囲のマージには、範囲の両端、コストの和、さらに左から・右からのコストの累積和「の総和」が必要になる。そのような範囲は各ノード高々2個なので十分高速。

107分で全完、最初Aに26分かけたペナルティが響いて5位まで落ちた。

OUPC終了時間とOpenCupの開始時間が一致していたので休憩なしを覚悟していたのだが、思いがけず時間が空いたので食事したりしていた。午後5時からOpenCup。

まずKが通された。次に僕がBを通した。整数の平方根を $10^6$ 回求める必要があって、二分探索は少し怖い。sqrtlにかけてから微調整する方法を教えてもらい、それで実装した。見落としていた条件があり1WA。次にGが通された。Cを解けた気がしたので書いて、サンプルが合わなかったのでいったんPCを開けて考え直す。その間にEが書き上げられ、投げられた。ちょっとしたミスがあったらしいが、Cの修正もすぐ終わったので先に書き上げさせてもらい、投げた。Eも直後に投げられ、どちらも通った。ここからしばらく時間が空く。

I問題が通っていたので、考える。長さ $N$ の順列 $P$ であって、「 $l\le \forall i\le r.\;P_i\ge h$ 」という形の条件 $M$ 個のうち $M-1$ 個以上を満たすようなものを構築せよという問題。各 $i$ に対し関係する $h$ を大きいほうから2個（ $h_1\ge h_2$ ）持って考えていたら、チームメイトに「 $h_1\gt h_2$ ならば $l\le i\le r$ かつ $h=h_1$ な条件は1つしか存在しない」ことを指摘された。このとき、各条件についてそれを削除することで値の下限が変化するインデックスを毎回全部見ても全体で $O(N)$ になることがわかる。あとはまあ良しなにできるはず。実装はそのチームメイトにお願いした。

Hに進んだ。先に言っておくが、この問題はかなり面白い。funnyのほうである。 $q$ （素数）桁の $n$ 進数（ただしleadgin zeroを許す）がluckyな数であるということを、各桁の積と各桁の和の和が $\bmod n$ で $s$ に等しいこととして定義する。luckyな数 $a_1 a_2 \dots a_q$ のスコアを $(a_1+1)(a_2+2)\dots(a_q+q)+2^0 a_1+2^1 a_2+\dots+2^{q-1}a_q$ と定義したとき、すべてのluckyな数のスコアの和を $\bmod q$ で求めよ、という問題。

まずこのバカみたいなスコアの式を何とかする。数 $a_1 a_2 \dots a_q$ がluckyなら、それをrotateしたもの $q$ 通りも全部luckyであるから、それらを全部足して $q$ で割ってみる。すべてのluckyな数に対し、それぞれrotateしたもの $q$ 個を集めてくると、同じ数が $q$ 個ずつ出現するので、それを $q$ で割ればスコアが求まるからだ。……と思っていたのだが、後から見ると $q$ で割ったり割らなかったり、ちょっと怪しい部分が多い。ひとまずコンテスト中の考察を述べる。

$(a_1+1)(a_2+2)\dots(a_q+q)$ について。適当に実験してみると、 $\bmod q$ で消えないのは $\prod_i a_i$ と $\frac{(q-1)!}{q}\sum_i a_i\equiv-\frac 1 q\sum_i a_i$ に見えた。次に $2^0 a_1+2^1 a_2+\dots+2^{q-1}a_q$ について、 $\frac 1 q\left(\sum_{i=0}^{q-1}2^i\right)\times\sum_i a_i=\frac 1 q(2^q-1)\times\sum_i a_i\equiv \frac 1 q\sum_i a_i$ となる。足し合わせると $\prod_i a_i$ だけが残る。

あとはluckyな数の定義について考える必要がある。この「各桁の積と各桁の和の和」という条件は本当に何も良い性質がなく、かなり無理な雰囲気が漂っていた。しかしよく見ると、luckyな数 $a_1 a_2 \dots a_q$ の $q$ 通りのrotateが被ることがなければ、スコアは全部で $q\times \prod_i a_i\equiv 0$ だけ増えることになる、つまり考えなくてよいということが分かる。つまりluckyな数であってrotateが重複する数のみを考えればよい。今 $q$ は素数なので、そのような数は必ず $a_1=a_2=\dots=a_q$ になる！！！

よって $a_1$ を全探索して毎回チェックしても間に合うことが分かった。実装してAC。さて、怪しい部分について正しい考察の道筋を与える。まずrotateに関する考察を最初に行う必要があった。ここでrotateが重複しない数のみを考えると、それらの全体はrotateで移り変わるもの同士を集めたサイズ $q$ の集合に分割できて、それぞれで上のようにスコアの和を取ることで、 $q$ で割ることなく即座にスコアの和が $0$ になることが導ける。

残り時間はDを考えつつ、チームメイトのJを眺めていた。よくわからない二項係数の和を高速化することになって、WolframAlphaにいろいろ式変形してクエリを投げていたらしい。最後に投げた提出はTLEで、そこから手作業の式変形でmodintの割り算を減らしたら通ったようだ。7完。Hは振り返ればギャグだった。考察を重ねて、最後のステップがギャグだったのでしてやられた感があって良質だなと感じた。luckyな数の定義もスコアの定義も嫌な形をしているので、こういう風にしか解けないのだろう。

G問題は一瞬で通っていたが、後から考察メモを見て僕の知らない高度典型であることを知った。長さ $n$ で要素が $[0,2^{19})$ の数列が与えられるので、 $1\le k\le n$ に対し「 $k$ 要素の連続するとは限らない部分列であって、bitwise ANDが $0$ になるもの」の数を求めよという問題。包除原理を考える。あるbitマスク $mask$ について、それを含むような数の個数 $c$ を数え、 $\binom{c}{k}$ に $mask$ のpopcountによって符号をつけて足し合わせる。 $c$ を一気に求めるのは上位集合に対するゼータ変換で行え、 $1\le c\le n$ に対し掛けるべき符号を集めて $a_c$ としておくと、結局各 $k$ に対し $\sum_{c=k}^n a_c\binom{c}{k}$ が求まればよいことがわかる。

そんなの無理だろという見た目をしているが、ここからが高度典型ポイント。 $f(x)=\sum_{c=0}^n a_cx^c$ とすると、答えの母関数は $f(x+1)$ になり、多項式のTaylor Shiftというやつで求まる。言われてみればそう、 $a_c$ から $f(x+1)$ の次数 $k$ への寄与は $a_c(x+1)^c=a_c\sum_{k=0}^c \binom{c}{k}x^k$ を考えればちょうど $\binom{c}{k}$ になる。これに気付いて感動した。聞けば少し前のARCのボス問あたりでも出たらしい。

今日のOPUC-Iについて。木で $u$ から $v$ の方向に1歩進んだ頂点は、ダブリングでLCAを求める前計算から $O(\log N)$ で求まるらしい。 $depth_v-depth_u-1$ 回 $v$ から登ってみて、その頂点の親が $u$ ならその頂点が、そうでないなら $u$ の親が答えになる。これはさらに一般化できて、 $uv$ パス上で $k$ 番目の頂点を求めるのは、 $u$ からLCAまで登る途中にあるか、LCAから $v$ まで下る（ $v$ からLCAまで登る）途中にあるかで分けられる。今LCAも「頂点 $u$ から $k$ 回上った頂点」、つまりlevel ancestorも $O(\log N)$ で求まるので、全体でも $O(\log N)$ 。

これが $O(1)$ になるらしい。LCAはオイラーツアーした後RMQをsparse tableで求めることで $O(1)$ になる。一方level ancestorを $O(1)$ で求めるのはなかなかすごいことをしているようで、理解していない。前計算 $O(N\log N)$ と前計算 $O(N)$ があるとのこと。

GCJのqualが終わっていたことに気づいた。出したものは全部通って当然通過。E問題の考察は、次数がメチャメチャ大きい頂点に着目するところまで合っていて、「テレポート→1歩動く」を繰り返せばよかったらしい。1歩動いてたどり着いた頂点はランダムに選択したものではないため次数を見積もるための平均には入れない、などすると通るようだ。

A問題はパンチカードの問題だったが、その言語を使って提出できたらしい。

GCJパンチカードで解答できたの気づかなかったなこれで全問解くのは狂気すぎる pic.twitter.com/zhiROQUGBa
— ゆきだるま (@yuki_prog) 2022年4月3日

今日はこれ以降コンテストがないのに日付が変わっていないのを見て、結構自由な時間があるなと思っていた。しかし午前0時半ごろ急激な眠気に襲われ、椅子の上で意識を飛ばしてしまった。1時間くらいして目を覚まし、こりゃまずいと思って日記も書かず布団に移動。そこからは朝までぐっすりだった。

2022-03-28

週記（2022/03/21-2022/03/27）

03/21(月)

先週の週記は、せっかく観光してきたので奇跡の一本松の写真をサムネ画像に設定しておいた。スマホを縦にして撮ったものであり、はてなブログの記事管理ページから見るとちゃんと縦向きになっている。しかしツイートのカードでは横向きになってしまっていた。残念。

はてなブログに投稿しました #はてなブログ
週記（2022/03/14-2022/03/20） - kotatsugameの日記https://t.co/Qim1xKIynE
— こたつがめ (@kotatsugame_t) 2022年3月20日

ICPCの参加記と週記を続けざまに投稿した後、比較的すぐ布団に入った。午前9時就寝。

HUPC day3が始まる午後1時に目覚ましをかけてはいたものの、あまりの眠さに何もかも諦めて二度寝した。午後3時起床。

週記のうち以下の記述について、ホスフィンから「付属のスプーンがあるのではないか」との指摘があった。改めてパッケージを読み直すと、確かにそういう記述がある。粉を掘り返してみると見事に見つかった。これを使ってすりきり3杯を溶かして飲むと、ほのかな甘みが感じられて飲みやすくなった。粉っぽくもある。

水に溶かして恐る恐る飲んでみると、まったく味がしなくてびっくり。スプーン3杯と書いてあったが、使ったスプーンが小さかったのだろうか。
週記（2022/03/14-2022/03/20） - kotatsugameの日記

ABC244Cが取られていた。最初に $1$ を出力して、以降は ${\rm input}\oplus 1$ を出力しているらしい。ジャッジのハックかと思ったもののそんなこともなく、正当な解法である。つまり、 $\{1\dots 2N+1\}=\{1\}\cup\{2,3\}\cup\dots\cup\{2N,2N+1\}$ と分割して初手で $1$ を宣言しておくと、以降は ${\rm input}$ と対になっているものが存在してそれを常に出力できるということ。なるほど……。Perlだったのをdcに書き換えて取り返しておいた。

午後4時過ぎに家を出発し、一番町のあたりに向かう。今日はたいぺーとホスフィンと3人で飲む予定を立てていた。集合時刻が午後5時ちょっと前で、ゲーセンに寄るかかなり迷ったものの断念して早めに集合場所へ。2人は少し遅刻してきたので、結果的に僕も1クレくらい遊ぶ余裕はあった。まあこういうすれ違いが起こるのも、これまで僕が遅刻しまくってきた報いである。

ホスフィンが予約しておいてくれた焼き鳥屋で3時間ばかり飲み食いした。今日焼き鳥にしようとしたのは僕の希望だったので、それが叶ったのは嬉しい。美味しかったはず。人手が足りていないようで、店員が常に忙しそうだったのと、頼んだものが出てくるのが結構遅かったのは気になるが、一方僕らの方もあまり頼まなかったのに延々席に居座り続けていたのは申し訳なく思う。

食事 pic.twitter.com/KfBEtaUCpW
— こたつがめ (@kotatsugame_t) 2022年3月21日

帰り道、ドンキでお酒やおつまみを買い、僕の部屋に行って本格的に飲酒を始めた。

飲酒します pic.twitter.com/r0c74PkMOv
— こたつがめ (@kotatsugame_t) 2022年3月21日

アニメを見るのも途中で飽きるし、僕の部屋には他にすることもないため、結局毎回YouTubeやニコニコ動画でお互いにお薦めの動画を見せ合うことになってしまう。アニメに途中で飽きてしまうのはモニターが小さい（あるいは遠い）からだと思って、脚立を引っ張り出して頑張ってセッティングしてみた。かなり近づいていい感じになったと思う。ジョジョの奇妙な冒険の第1部を観た。

いい感じや pic.twitter.com/SHRT2hV0Yr
— こたつがめ (@kotatsugame_t) 2022年3月21日

途中一休みで適当なMADを挟みつつ、午前2時くらいまでかけて10話見終わった。めちゃくちゃ面白かった。ネットミームとして聞いたことのあるセリフやシーンがちょくちょく出てきたものの、話の流れとしてはもちろん自然なものに感じられて、ややオーバーな表現も画風にマッチしてより強くストーリーに引き込まれた。熱くてよい話だった。その直後から第1部の素材を使ったMADを見始めて余韻もクソもなくなったが、それはそれでつい先ほど見たシーンが出てきたのがわかるため笑えた。

今日家を出る前に縮めたABC244Cが再度取られているのを見つけた。今度は $2N+2-{\rm input}$ らしい。その解法も発見していたものの、dc力が足りず自力では縮められていなかった。完敗。

その後も適当な動画を流し見つつ、ねるねるねるねを作ったりしていた。午前5時前に急激に気持ち悪くなり、洗面台でしばらくえずいた後布団に誘導されて、そこからぐっすりだった。

日記の最後に一番面白かったMADを一つ。ジョジョではない。

www.nicovideo.jp

03/22(火)

午前11時過ぎに起床。2人ともいなくてびっくりした。頭痛はないが気持ち悪さが残るため、水分を取ってまたすぐ寝た。

午後3時過ぎに再度起床。自分の記憶では、買ってきたお酒のうちカルーアミルクがボトルに半分くらい残っていたはず。見るとさらに半分になっていたので、僕が潰れた後も2人はしばらく飲んでいたらしい。聞いてみると、ホスフィンは早朝のうちに帰宅して、たいぺーはひと眠りした後朝になってから研究室に向かったそうだ。たいぺーが家を出るとき僕も少し反応を返したと聞いたが、一切記憶にない。部屋を出た直後に中に鍵束を忘れたことに気づいたたいぺーが再度インターフォンを鳴らしても反応がなかったらしいことから、本当に一瞬だけ意識が浮上していたのだろう。

いつも飲酒を始めるとすぐに腹を壊すのに、昨夜はそんなことはなかったため、調子が良いなと感じていた。一方潰れる直前の吐き気はしばらく感じたことのない強いもので、結局苦しむ羽目になるのかと絶望した。酒量をセーブすることを覚えなければならないのだろう。思えば昨夜はアニメに集中していて、スローペースで飲んでいたかもしれない。それで腹を壊すことがなかったのだろう。

微妙な気持ち悪さを抱えつつ部屋を掃除。せっかくモニターを一度取り外したので、接続するケーブルを取り換えて、以下の現象の解決を図った。真ん中のモニターと左端のモニターをPCに接続しているケーブルを交換することで、起動時に特別な操作をすることなく、無事真ん中の画面をキャプチャできるようになった。

これまで真ん中のメイン画面をキャプチャできていたのが、いつの間にか左端の画面をキャプチャするようになってしまっていた。調べたところ、regeditでモニタの設定をいったん削除し、改めて番号順にモニターを1枚ずつ増やしながら接続→再起動を繰り返すと正しく設定できるらしい。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

午後5時からインターン先の定例会に出た。先週木曜日のコーディングの成果を発表。今日の勉強会はデザインの話で、フォント選定にも触れられていた。明朝体は縦棒の太さに比べて横棒を極端に細くすることで字を美しく見せている一方、細い字が読みにくいタイプの人には辛い。一方教科書体というフォントは縦横の太さをほぼ同じにしているのでそういう人にも配慮している、という話を聞いたことがあった。今日の発表ではさらに、ゴシック体などに比べてフォントの端を丸めることで、目に優しい印象を与えてもいるということを知った。実際にフォントを切り替えた様子を見せてもらって、確かにかなり印象が違うなと体感した。

上に書いたように、たいぺーが部屋に鍵束を忘れていったので、それを取りに来ることになっていた。聞いてみると研究室での用事がまだ終わっていないらしい。大変そう。しばらく人の日記を読みつつ待って、午後8時過ぎにやってきたたいぺーと家を出た。ラーメンを食べに行く。まだ気持ち悪さが残るのに替え玉をしてしまって後悔しつつ、何とか食べ切った。ラーメン屋を出たところで別れ、今日開店した新しいゲーセンに行くことにした。

「スーパーノバ仙台一番町」本日３月２２日１５時よりオープンしました！
一番町アーケードのサンシャインビル１階になります！
お店は年中無休！朝９時～夜２４時までになります！
ご来店をお待ちいたしております！#ゲームセンター #開店 #オープン pic.twitter.com/RrPuc5BfMq
— スーパーノバ仙台一番町 (@nova_ichibancho) 2022年3月22日

音ゲーは、太鼓の達人が1階にある以外は地下にまとめられていた。チュウニズムのゴールドモデルが4台に、あとはメジャーなものが2台ずつ。個人的にはチュウニズム4台というだけで感謝の念が強い。ただチュウニズムのように筐体に種類がある他の機種はあまり力を入れられていないようで、TLで「チュウニズム屋さんが増えただけ」と言われているのを見た。これも理解できる。コロナ禍でアーケード音ゲーが振るわない状況なのは論を俟たず、その中でもひとまず人気があるチュウニズム以外はどうせ集金力も高くないだろうという判断がなされている。そのような現状を見聞きすることは多いが、音ゲー全体の栄枯盛衰には興味がない。自分はチュウニズムさえプレイできれば満足で、そのサービスの進退が問われるのはアーケード音ゲーが全体として終焉を迎えた後だろうと思っているからだ。これ何か英語の熟語みたいだな……チュウニズムは最後にサービス終了するアーケード音ゲーです。

音ゲーの成果は、新曲を埋めただけ。1曲、初見で理論値を出すことに成功した。譜面動画を1回だけ見た記憶はあるが誤差だろう。MASTERで初見理論値は初めてなのでかなり嬉しい。

ヴァンパイア　初見理論値！ pic.twitter.com/q3AcsP9rBa
— こたつがめ (@kotatsugame_t) 2022年3月22日

腹を壊してトイレに駆け込んだら、トイレットペーパーが切れていて青ざめた。ポケットティッシュを持っていたため難を逃れた。

「クーネル・エンゲイザー」という曲を気に入ったので、しばらく詰めていた。結構すぐ1落ちは出たのに以降ウンともスンとも言わず断念。

助けて〜〜〜〜〜〜〜〜〜〜〜！！！ pic.twitter.com/lpFv4H8Fs8
— こたつがめ (@kotatsugame_t) 2022年3月22日

午後12時の閉店まで適当な譜面を触って帰宅。セガ仙台より閉店が遅いのはありがたいところ。ただ開店当日なのに音ゲーコーナーはガラガラで、大丈夫かという気持ちになった。平日深夜はさすがにしょうがないのか？

帰宅して少し日記を書きつつYouTubeを見ていた。今日チュウニズムでプレイして気に入った「クーネル・エンゲイザー」の本家PVを探して見てみると、楽しげな曲調に反して歌詞が重苦しく、ひっくり返った。

www.youtube.com

本を1冊読んだ。「かくりよの宿飯」12巻。これまで特典などで出ていた短編をまとめたもので、ストーリー完結前の話が多く懐かしい気分になった。大旦那様が現世に来る話もいくつかあったので以下のようなシーンがまた見られることを期待したが、主人公とイチャイチャするだけだったのでちょっとばかり拍子抜け。天神屋の社員旅行はまた別の外伝という形でそのうち出版されるらしいので、そちらも楽しみに待ちたい。

主人公と大旦那様が現世で一緒に買い物をしているとき、大学の同級生と遭遇して、大旦那様がキャーキャー言われる……というのは非常に僕好みの1シーンだろうが、回想という形でサッと流されてしまった。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

またしばらくYouTubeを見ていた。百万年後でも情報を伝達できるような、核廃棄物の最終処分場を示すのにふさわしい標識についての話。非常に面白かった。現代文明からの情報の伝達が途切れた後の世界というのは、想像するのは非常に楽しい。非常に長い時間の経過を感じさせるような話が好みだからである。

www.youtube.com

布団に入り、午前7時くらいに寝落ちした。

03/23(水)

午後3時ちょっと前に一瞬起床。メールで注文していたラノベが生協に届いたことを知るも、もう閉店時間に間に合わないので諦め、またすぐ寝た。次に午後6時半に起床。

しばらく布団に横たわったままネットサーフィンをしていた。午後8時過ぎに起き上がって、シャワーを浴びたり食事したりした。一念発起して3回目のワクチンを予約する。週末は絶対に副反応を残したくない。4月に入ってからだと大学院がどうなるのか全然わからないので、来週月曜日を選択した。インターン先の定例会は、熱が出ていたら最悪休むことになる。

izrytさんがYouTubeで見たということでツイートしていた問題が流れてきた。 $x,y,z\gt 0$ として、以下の連立方程式を解く。

$\displaystyle \begin{cases} x^2+xy+y^2=49\\ y^2+yz+z^2=144\\ z^2+zx+x^2=169 \end{cases}$

適当に2式選んで引くことで、 $(x-y)(x+y+z)=25$ のような式が3つ作れるのが天才パート。Y.Y.さんのリプライを見て感心していた。ここから一度 $x-y:y-z:z-x$ のような比に持ち込んでしまうと計算が苦しかった。一方 $x+y+z=k$ と置くことでも解けて、こちらのほうがストレートだがいずれにしても値の大きな計算を必要とし、答え $(x,y,z)=\frac 1{\sqrt{13}}(17,12,36)$ が出る。

月曜日の残りのカルーアミルクと牛乳を消費しつつ、ノクターンノベルズから1作読了。「エッチできるＶＲＭＭＯで性奴隷にした美少女たちがリアルでも知り合いだった件」。物語としての評価は別として、良かった。

https://novel18.syosetu.com/n8146gy/

カルーアミルクはほんの少ししか残っていないように見えたのに、薄めに作って飲んでいたら牛乳を1L空けてしまった。腹を壊しまくってしばらくトイレに出たり入ったりしつつ、コードゴルフをしていた。いわゆる牛ゲーを解いていて、networkxではあえなくTLEしたため、現在の最短コードを見て同じ方針を取った。ACLのmincostflowを持ち出し、流量1のフローを流すもの。

朝方からはハーメルンを漁っていた。「RTA」で検索してよさそうなものを1作見つけ、読み進めた。

昼前に、大学生協に行ってラノベを受け取ってくることにした。うっかりヘルメットを忘れたまま原付にまたがるも、エンジン音の聞こえ方の違いからなんとか気付くことができた。大学の前の道路が工事で道幅が狭くなっており、えらく渋滞していた。交差点の前で信号待ちをしていたら、交通整理の方から押して歩いたほうが早いと言われるくらいだった。ラノベを受け取り、ついでに昼食のパンを買って帰宅。

と、日記を書いていて初めて気づいた。そういえば今日はお酒を飲んでいたのではなかったか。気づかないくらい体内のアルコールが抜けていたと考えたい一方、一度はヘルメットを忘れて家を出たことなど、ちょっと危うい感じがする。お酒を飲み終わったのが午前4時で、原付に乗ったのが午前11時半なので、適当に調べて出てきた目安である7時間は何とか経過している。しかし問題は体内に保有しているアルコールの分量であって、実際にどうだったのかはもうわからない。正直このことを日記に書くのも迷ったが、気づいてしまったものは仕方ない。

帰宅してからまたハーメルンを読み続け、午後2時くらいに寝落ちした。

03/24(木)

午後5時半起床。

今朝コードゴルフした問題が縮んでいるのを見つけた。そのときの最短コードに引きずられて、pairを受け取るのにstd::tieを使っていたが、普通に構造化束縛でよい。別のところで1B縮めて何とか取り返した。

午後6時からミーティング。先週書いていたコードは、2月末にデプロイしたものの機能拡張である。なので、現在デプロイされているものを使ってみた感触がどんなものか聞くのと、新しいものに置き換えたいのですがどうですかと確認するための時間。相変わらず機能が評価されていてうれしい。置き換えたものについても使った感触をフィードバックしていただけることになったので、話し合いで判明した改善案を実装して再度デプロイするのが直近のタスクになった。

先週金曜日のミーティングを受けて、ひとまず今できている部分を使ってみようという話になっていたのだ。
週記（2022/02/21-2022/02/27） - kotatsugameの日記

結構気を張っていたので、終了したとたん疲れが出た。いろいろやるべきことは残っているし、実装にもとっとと手を付けたいところだが、睡眠不足を理由にすぐ布団に戻ってしまった。しばらくハーメルンを読んで、午後9時半ごろ寝落ち。真夜中からCF combinedがあったことは、一応知ってはいた。しかしやる気がない。

午前1時半起床。CodeChefからメールが届いていて、以前僕にかかったコピペ疑惑が間違いだったこと、ペナルティが解除されたことが知らされた。一安心。

僕のコードがACLに由来すること、またACLがコンテスト前に利用可能だったライブラリであることを証明すればよい。英作文してメールを送った。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

またハーメルンを読み続け、午前4時前に1作読了。「万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい」。面白かった。やはり天才トレーナー視点は面白い。担当するウマ娘をポンポン増やしているのも、たぶん現実的ではないのだろうが見ていて楽しい。他のハーメルンで主人公陣営だったウマ娘をこちらでは外側からの視点で見たり、その逆を行うことで、それぞれのウマ娘の原作における性質らしきものがなんとなくわかってきた気がする。原作を知らないなりの楽しみ方である。

syosetu.org

別のハーメルンを少し漁って、午前5時くらいに布団から出た。食事してシャワーを浴び、洗濯機を回した。一人暮らしを始めてから使っている柔軟剤は、いつの間にかリニューアルされてしまったのに店頭では詰め替え用しか見当たらなかったので、仕方なく現在使っているボトルを洗って詰め替えることにした。

ゴミ出しをして、午前7時くらいに布団に戻った。明日、というか今日は卒業式なので昼前に起きる必要がある。午前8時までハーメルンを読んでから寝た。

03/25(金)

午前11時、執念の起床。

眠い目を擦りつつ、先日両親に実家から持ってきてもらったスーツを着用した。ネクタイをうまく結べず、鏡の前でモジモジしているうちに時間がヤバくなってきた。それなりの結び目で妥協して、急いで家を出た。

先週木曜日の日記でも書いたように、地震の影響で卒業式の会場が変更された。定員がずいぶん少なくなってしまったようで、溢れた人はサテライト会場などと言って、講義棟の教室から遠隔で参加することになっていた。東北大学の大学院に進む人はできるだけサテライト会場から参加しろとのお達しが出ていたので、僕も最初からそちらに向かった。午前11時40分まで集合と言われていたところ微妙に遅れてしまったが、特に問題ないようだった。普段講義を受けていた教室にスーツなり着物なりで集まって卒業式に参加するのはどこかシュールである。席を詰めて座らせられたので、感染症対策も大丈夫かと心配になった。

これが4年間の集大成か…… pic.twitter.com/CjnOYd3RVa
— こたつがめ (@kotatsugame_t) 2022年3月25日

式は正午開始。途中で地震があった以外は特筆すべきこともなく進んでいった。その間はハーメルンを読んでいて、1作読了。「幻想郷の接触」。文章がカス。設定は面白かった。

syosetu.org

30分くらいで終了。寝坊したたいぺーから連絡が来ていて、写真だけ一緒に撮ろうぜとのことだったので合流した。会場のどこかに「学位記授与式」みたいな看板がないものかと探していたのだが、聞いてみると感染症対策で設置していないらしい。施設の名前が書いてあるところの前で撮った。その後たいぺーは友人と遭遇し、僕も数学科で集まっているようだったのでそちらに向かうことにして別れた。

数学科は十数人集まっていた。すでに一度集合写真を撮ったらしいが、また集まってきたので再度撮影することになった。撮影場所が空くのを待つ間、久しぶりに会う人々といろいろ話をしていた。チラッと聞いてみると、大学院に合格した後すぐ担当教員にメールを出している人が多く、かなり焦った。また、4年ゼミで一緒に何度かスカルをプレイしていたうちの1人が、実際にスカルを購入したという話を聞いてびっくりした。

解散し、今日も生協でラノベを受け取って帰宅。スーツ姿を見てか、生協の店員さんにも卒業をお祝いされて嬉しくなった。

スーツ姿の自撮りをツイートした。入学式の日にほぼ同じ構図で自撮りした写真がスマホに残っていて、日付でツイートを検索してみると見つかったので、それへのリプライとしてみた。こういうところにも4年間の流れが感じられて感慨深い。

押忍 pic.twitter.com/oAIrIy73tI
— こたつがめ (@kotatsugame_t) 2022年3月25日

しばらくYouTubeを見てから午後3時半に布団に入り、寝た。

午後8時半起床。PayPalでCodeChefの賞金が受け取れるようになったとのメールが来ていた。

PayPalにCodeChefから賞金が贈られてきた。ただ、この送金のリスクが高いとされていて、すぐに受け取れるわけではないようだ。
週記（2022/03/14-2022/03/20） - kotatsugameの日記

布団でハーメルンの更新を漁ったり、新しい作品を読み始めたりした後、午後11時くらいに布団から出た。ラノベについて、3月の初めに注文した分で受け取っていないのは残り2冊だけとなったため、また新刊を予約する。4月分をいろいろ探して、とりあえず19冊予約した。タイトルからは似たような設定の話に見えるのに、一方はタイトルを見て即座に購入を決め、他方はあらすじを確認して取り止めたりと、思い返すに買う基準がバラバラであった。

日付が変わってからまた布団に戻り、ハーメルンを読んでいた。午前2時過ぎに寝落ち。

03/26(土)

午前5時起床。2時間ほどハーメルンを読んでまた寝た。次に午後1時半、目覚ましで起床。眠気をこらえつつハーメルンを読んで、午後3時前に布団から出た。AHC009。ちょうど大学生でも大学院生でもない微妙な時期で、所属をなんと書くか迷った。結局大学生にした。

Monoxer Programming Contest 2022（AtCoder Heuristic Contest 009） - AtCoder

とりあえず1B解を提出してから考察。できるだけまっすぐ進むような経路を作って、それぞれの直線で何回か余計に操作することで予定通りに進む確率を高めるとよいのではないかと考えて少し実装していたが、まっすぐ進むような経路は必ず通路のつきあたりまで行かなくてはならないし、操作回数も平均的に長くなってしまうので、普通に山登りなどをしたほうが強いのかも知れないと考え、面倒になってシャワーを浴びたり日記を書いたりしていた。

コンテスト終了時刻である午後7時の20分前になってから、さすがに0点のままはまずいと思って適当な貪欲の実装を開始。毎回どの位置にどれくらいの確率でいるかを計算しておいて、4方向それぞれ進んだ時にゴールまでの距離の変化がどのくらいかの期待値を求め、最も小さくなる方向を出力し続けるというもの。これで2528180402点が出て、ゴールまでの距離の変化 $-1,0,+1$ に対する重みを適当に変えてさらに2回提出し、最終的に2555201986点になった。

401位で1834→1836(+2)。できるだけまっすぐ進むような経路を作るのは、それなりに良い方針だったらしい。通路のつきあたりまで進むような移動でゴールにたどり着けない場合も、できるだけ近寄ってからフラフラ移動することを考えれば、疑似的にスタートとゴールの位置を近づけるという意味で十分効果があるようだ。あとは案の定山登りした人も多そうだった。実装していないのに適当な考察だけで案の定とか言っちゃダメか。

その後も日記を書き続け、午後9時からABC245に出た。

AtCoder Beginner Contest 245 - AtCoder

Aで1WA。 $A\lt C$ とすべきところを $A\le C$ にしていた。コードゴルフは少し面倒そうに見えたのですぐ先に進む。Bは適当にRubyで、その先からはC++で書いた。Cは先頭から見て、直前を $A$ 、 $B$ 由来の数にできるかのフラグをそれぞれ持つ。Dは端から1つずつ決めていく。うっかり $A_0$ を使って $B_0$ から決め始めてしまい、1WA。これだとゼロ除算が発生しうる。 $A_N$ を使って $B_M$ から決め始めるのが正解。Eは縦の長さでソートして、使える横幅をmultisetで持ち、貪欲に消費していく。FはSCCして、サイズ2以上の強連結成分にたどり着ける頂点の数を数える。

Gで2WA。まず想定解と同じdijkstraを書くも、queueに入っている余計な要素を無視する部分で、関係ないところのコストと比較してしまいTLE。次に、「その頂点と同じ国・違う国」で分けてコストを持つという大嘘を書きWA。ここでようやく先ほどのミスに気付いてACした。Exは解けず、前半のコードゴルフをしている間にコンテスト終了。7完25位。

コードゴルフ。Aはコンテスト中にdc 32Bを書き、コンテスト後に1B縮めて満足していたら朝方さらに1B縮められた。無理やり引き算してvで正負を判定していたところを、普通の大小比較に書き直すという更新。なぜ気づけなかったのか。BはRaku。Cは、 $A$ 、 $B$ が使えるかのフラグを持つ代わりに使える要素を直接保持すればわかりやすい。これをPerlで実装。DはOctaveの多項式除算が通らず、Pythonとnumpyを使うコードが提出されていて万事休すかと思ったが、自力でループを回すと短くなった。Perlで縮め、AWKで書き直すとさらに短くなった。EはCrystalなら線形時間のinsert・eraseが間に合う。位置は二分探索する必要がある。FはPerl。これも単純なミスで取られてしまいかなりショック。

真夜中から午前6時までずっと日記を書いていた。週の初めからずっと溜めてしまっていた。

今日の部分まで追いついたところで布団に入り、ラノベを1冊読了。「異世界でチート能力を手にした俺は、現実世界をも無双する」10巻。1巻で主人公がとんとん拍子にチート能力を手に入れられた理由付けがなされた。主人公はこの巻で過去に飛ばされたのだが、そこでチート能力を主人公に受け継いだ賢者と会って契約を交わしていたということらしい。そういう時間軸をぐるぐる回るような展開が思いもよらないところで出てきたので、大変驚いた。ただ、このラノベの作者はあとがきで行き当たりばったりで書いていると何度も述べているから、これも伏線回収でもなんでもなく、そういう話にできるからそうしてみたという感じなのだろうか。それはそれですごいことである。過去編なんて9巻まで影も形もなかったと記憶しているので、余計に驚きが増したのかもしれない。

午前8時半就寝。

03/27(日)

目覚ましのスヌーズを繰り返し、午後0時50分ごろ起床。10分後からUTPC2021に参加した。

UTPC 2021 - AtCoder

Aは面倒。最初、長さ4の連続部分文字列を全部試して、"UTPC"と一致しない文字数の最小値を出力しようとしていた。ただ提出の直前に、部分文字列内でswapすることで操作回数を少なくできることに気づいた。swapで2文字一気に揃えられるケースにも対処して提出。しかしWAだった。swapで2文字一気に揃えられるのは長さ2のループだと思うことができて、長さ3や4まで考えられる。かなり面倒。再帰関数で操作を全列挙し、ようやくACできた。

順位表を見るとM問題にACが出ていた。優先度付きキューを使い、その時々で最も当たりである確率が高い鍵を試すようなコードを書いたらサンプルが合って、そのまま通った。あまり深く考えていない。この時点で一瞬1位になっていた気がする。ほかに解かれている問題がないので、しばらくB問題に取り組んでいた。値でソートして、swapできるものを区間とみなし、その区間の重なり方でswapの影響を分類できることまで考察したが、その先に進めず、適当に2ペナ付けて諦めた。

C問題が解かれているので見る。とりあえず符号が同じ数は絶対値が大きなほうからペアにしていってよいだろう。残りを適当に決めるとサンプルで落ちた。残りのうち $k$ 個取ると決め打ったとき、絶対値の小さいほうから $1$ 番目と $k$ 番目、 $2$ 番目と $k-1$ 番目……のようにペアにしていくのがよさそう。いったん愚直に書いて部分点を取りつつ正しいことを確認。さて高速化するぞと気合いを入れたが、ちょっと冷静になると畳み込みで書けることに気づいたので、満点もすぐに取れた。

次はG問題。行と列に分割してそれぞれ解ける。最大値の位置から左右にマージしていくのがよいと考えるも、貪欲に操作するとサンプルで落ちてしまったため、いったん区間dpで部分点を取っておいた。しばらく考察していると、貪欲に操作していたのが悪い気がしてきた。目先の得点を捨ててでも遠くにあるより大きな数とマージさせたい気持ちになる。実装としては、区間dpで分割を全探索していたところを、左端・右端で分割するパターンだけ試すようにした。これで通った。実は考察が不正確で、最大値の位置が複数ある場合などどこからスタートするか決められなくて壊れてしまうのだが、書いたコードは正しい。実装方針を選ぶときの運がよかった。

Eが結構解かれているのに全然わからない。I問題に進む。今どのカードを食べたかと最後に食べたカードを持つ $O(M2^M)$ 状態のdpが考えられて、最後に食べたカードが $i$ の状態から次にカード $j$ を食べる遷移のときは、「カード $k$ がカード $i$ とカード $j$ の間にある山の数」をまだ食べていないカード $k$ すべてに対して求められればよい。 $O(NM^3)$ の前計算をしておけば、毎回 $k$ を決める $O(M)$ のループでコストが求まる。これを実装して部分点。

コスト計算のループが一番内側で、 $O(M^3 2^M)$ かかっているので、ここを高速化したい。 $2^M$ 状態それぞれで、まだ食べていないカード $k$ に応じていろいろ値の和をとる必要がある。このとき、直前の集合との差分だけ更新すればよいのではないかと考えた。このアイディアを実装するとジャッジで6sec強だったが、配列アクセスが飛び飛びだったのに気づいて次元を入れ替え、#pragma GCC optimize("Ofast")すると爆速になった。4.5secで通った。

しばらくコードゴルフした後、ようやくEと向き合う。 $K=1$ の時は明らか。 $K=2,3$ の時は、あらかじめ符号を決め打った状態で累積maxを取っておくと無理やり求められる。これで $K\ge 4$ としてよく、このとき四方向それぞれ最も遠い頂点を必ず選ぶことができる。 $c$ の値で降順ソートし、順に点集合に入れていく。点集合のサイズが $K$ を超えた場合は、 $X$ 、 $Y$ の最大最小が変化しないような点であって最も $c$ が小さいものが存在するので、代わりにそれを削除する。ただこの計算だとサンプルから合わない。点集合のサイズが $K$ を超えた場合に削除すべき点より $c$ が小さい点は高々4個なので、それらを代わりに削除してみるのも毎回試すと通った。日記を書いているときに気付いたが、 $K=3$ の場合で1点がほかの2点からなる長方形から完全に含まれる場合を考慮し損ねていた。

OpenCup後に解説などを読んだ感想。Iはかなり頭が良い。食べる順番 $\{p_i\}$ を決め打ったとき、カードの山の上から下まで見るのを何度も繰り返して正しい順番で食べていると考えられる。結局全部食べてしまうのだから、毎回必ず一番上から一番下まで見ていると考えてよい。この時、操作1の回数はカードを見たのに食べなかった回数であり、山の一番上に戻ったときにまだ食べていないカードの数を求めるとその和となる。山の一番上に戻るのが $1\le i\le M$ 番目のカードを食べるときだとすると、その時まだ食べていないカードは $M-i+1$ 枚で、そのような $i$ は「カードの山において $p_i$ の位置が $p_{i-1}$ より上にある」という条件を満たす。あとはdpのためにコストを $(p_{i-1},p_i)$ ごとに分解すればよい。

Eは最大・最小の条件を緩めても報酬が大きくならないことを利用するらしい。考えもしなかった。あとはコードゴルフ。MはPythonのheapqを使わずとも毎回線形時間で最大値を求めてよい。Aはとりあえず多始点の幅優先探索を書いておいた。

Eが通ったのが午後5時2分。午後5時からOpenCupだったので、急いでそちらの問題を読み始めた。久しぶりのOpenCupである。

チームメイトの二人がUTPCに吸い込まれていたので、開始から1時間は一人でやっていた。まずBが解かれ始める。読むとやるだけだったので通す。次に解かれていたCは全然わからないので、こちらも少しsolvedが出てきたEに移った。dpを考えると遷移の計算に時間がかかりそうに見えたが、遷移先をずらしながらコストを更新していくと全体では十分高速になることに気づく。こちらもすぐACできた。

そのままCを考えていた。数列 $\{A_0,A_1,\dots,A_{2^N-1}\}$ が与えられるので、 $A_i+A_j\lt A_{i\;{\rm AND}\;j}+A_{i\;{\rm OR}\;j}$ なる $(i,j)$ があれば出力せよという問題。他の2人が戻ってきて考察が進み始める。 $i-(i\;{\rm AND}\;j)=(i\;{\rm OR}\;j)-j$ であるという気づきがあって、この差 $d$ を全探索したい。 $d\subseteq i\subseteq i'=(i\;{\rm OR}\;j)$ について $A_i-A_{i-d}\lt A_{i'}-A_{i'-d}$ であればよい。ここで式をよく見ると、 $d$ としては2べきのもののみ考えればよいことがわかる。2べきで見つからなかった場合、 $d=d_1+d_2+\dots$ と2べきの和に展開できて、 $A_i-A_{i-d}=(A_i-A_{i-d_1})+(A_{i-d_1}-A_{i-d_1-d_2})+\dots\ge(A_{i'}-A_{i'-d_1})+(A_{i'-d_1}-A_{i'-d_1-d_2})+\dots=A_{i'}-A_{i'-d}$ という式変形から必ず条件を満たさないことが確認できるからだ。感動しつつ実装に立候補して書いた。 $i\subseteq i'$ という条件を見逃して1WA。

残り3時間はL問題と格闘していた。燃やす埋めるっぽいのに、どうやってもペナルティをうまく定義できず、惜しそうな気配を感じつつも一歩も進まなかった。念入りに椅子を温めている間にA問題が通っていてすごい。結局4完と完数ではかなり少ないものの、崖が大きかったので全体で24位だった。BECがたくさん解かれて、Aは40チーム、Lは25チーム、残りのsolvedは1桁。12問5時間でこれってマジ？

Aの解法はすごい。多重集合 $U$ と $V$ があって、すべての $(u_x,u_y)\in U$ と $(v_x,v_y)\in V$ の組み合わせに対して $\max(u_x+v_x,u_y+v_y)$ を計算したものの最小値を答えるのを、 $U$ と $V$ を更新しつつ行う問題。 $u_x+v_x\le u_y+v_y$ と決めて、 $u_x-u_y\le v_y-v_x$ と式変形する。 $u_x-u_y$ や $v_y-v_x$ をインデックスとして、 $u_y$ と $v_y$ をそれぞれ保持する。大小関係を意味している左右の位置関係を崩さないように気を付けつつ $U$ 由来の数と $V$ 由来の数の和を取って、それらの最小値を求める。これはセグ木に乗る。 $u_x+v_x\ge u_y+v_y$ も同様に行える。見た目に反してかなりスマートな解法だし、コードを見る限り実装も簡潔で感動した。

日記を書いて午前4時前。明日はワクチン3回目接種、明後日は一日布団で倒れていようと思っていたら、いつの間にか明日明後日とパ研合宿のコンテストがAtCoder上で開催されることになっていた。特に明日はSpeedRunとかいうコードゴルフ専用コンテストで、しかも開始時刻が午前9時。ヤバい！

2022-03-21

週記（2022/03/14-2022/03/20）

03/14(月)

先週は週記を投稿してからすぐ布団に入った。横になりつつハーメルンを漁って、午前5時半くらいに寝落ち。

午後0時半起床。またしばらく布団の中でハーメルンを読み続けて、午後2時を過ぎてから起き上がった。

食事してインターンのコーディングに取り掛かる。アルゴリズムの実装をする前の、設計を考える段階に時間を使い、行数的にはあまり進まずに定例会の時間になった。今日発表する進捗は、先ほど1時間ばかり取り組んだ内容のみとなる。先週は頑張って書くぞというようなことを日記に書いていたのに、一週間ずっと怠惰だった。コードを書く以外にすることがないので、コードを書いていないということは一切稼働していないということ。今月はヤバい。

コードを書く以外のことはしばらくする必要がなさそうなので、どこかで気合を入れてガーッと書く必要がある。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

今週の勉強会は数学の話だった。極限を厳密に定義するというテーマで、位相空間を定義してその言葉で極限を書き直したところで終わった。位相空間とは極限（あるいは収束）を定義するのに必要十分な性質だけを取り出したものだ、ということでこのような流れになっている。そのこと自体は、Wikipediaの冒頭にも同じことが書いてあってまあそういうものかと納得はできるが、少なくとも自分にとっては全く明らかではなかった。位相空間を見て収束を定義しているんだなあと思うためには、一度ユークリッド空間での収束を知って、それが開集合系で書き直されることを見るというステップが必要だと考えている。

勉強会が終わってからもしばらくインターンのコーディングを続けて、ひとまずメインのアルゴリズム以外を書き上げた。あとはそのメインの部分を実装すれば動いてくれるはず。今日はこのあたりで切り上げる。

午後9時から6時間くらいFastestやShortestを漁っていた。特にFastestの、C言語における入出力について。これまではreadとwriteを使っていたが、yukicoderでFastestを大量に保持しているtailsさんのコードを読んで、入力にmmapというものが使えることを知った。つい最近Dirty Pipe脆弱性に関するはてなブログの記事を読んだので、なんとなくやっていることが理解できる気がする。標準入力をメモリ上に展開してそこへのポインタを取得しているのだろうか。確かに速そうであり、試したところ実際に速かった。

第73章 mmap の使い方

knqyf263.hatenablog.com

tailsさんのコードを元にいくらか調べて、何とか動くようになった。char*mmap()というプロトタイプ宣言は、削除するとCEではなくREになってよくわからない。とにかく、今後使えるような状態のひな型が以下のように得られたので、これをブックマークしておいて以降機会があれば使いまわすことにした。ポインタをインクリメントすることで入力を読んでいるが、これは別にポインタに対して添え字を付けてもよいようだ。

atcoder.jp

TLに、Linux カーネルで使われているリストの実装方法についての話が流れてきた。リストの各要素は任意の構造体であり、要素としたい構造体にlist_head型の変数を用意して、それを繋ぐことで双方向連結リストとしているらしい。これを聞いた時の一般的な疑問として、構造体の中のメンバ変数だけが繋がってても意味ないだろ、というものがあると思う。少なくとも僕はそう思った。この疑問の背景には、「メンバ変数は構造体自体を知らない」という暗黙的な了解があると考える。

ところが、実はこれが一般に知れてしまう、つまり構造体の中に定義されているだけのlist_head型の変数からその構造体自体のポインタを取得できてしまうらしい。これにより、リストの構造はlist_headによって保ちつつ、必要になるたびにlist_headから元の要素を復元するという操作が可能になり、見事双方向連結リストが実現されることになる。その鍵となるマクロがcontainer_ofというものだ。

container_of(ptr,type,member)は、memberという名前のメンバ変数を持つ構造体typeについて、type*型のポインタpであって&p->member==ptrとなるようなものを返すマクロである。つまりメンバ変数のポインタptrから大元の構造体のポインタを取得している。実装は言われてみればなるほどという感じで、メモリ配置における構造体の先頭からメンバ変数memberまでのオフセットを計算して、ptrを逆向きに同じだけずらすというもの。ヌルポインタをtype*として解釈することができて、このとき構造体の先頭が0番地になるので、memberのアドレスを取得するとそれが単純にオフセットになるようだ。

布団に入ってしばらくYouTubeを見て、午前4時半就寝。

03/15(火)

午前11時起床。今日はICPC 1日目ということで、正午に山の上の研究室に集合らしい。天気も良く、原付で行くことを考えれば、まだ少しだけ余裕がある時間だった。しかし、その時間で昨日縮めた問題がどうなっているか確認してみようとパソコンの前に座ったのが運の尽き。見事に縮められたものを発見し、これを縮めようと試行錯誤しているうちに集合時間が過ぎてしまった。結局縮まないまま出発し、30分遅れで研究室に到着した。

ここから帰宅までのことは、ICPCの参加記に書いた。

kotatsugame.hatenablog.com

午後5時半に帰宅。そこから、今日も6時間程度FastestやShortestを漁っていた。昨日mmapで取ったFastestのうちいくつかが埋め込みで取られていたので、こちらも対抗し、atcoder_testcasesから落としてきた入出力ファイルを食わせると入力の先頭を必要なだけ読んで場合分け＋出力するPascalコードを生成するコードを書いた。これを使ってまたいくつかFastestを取った。

「データ構造」という名前の、データ構造の試し斬りによく使われている問題。試しにC++でvectorのinsertやeraseを使うコードを提出してみると、1secかからず通ってしまった。insert位置を取得するのにlower_boundではなく線形探索を使用するとTLEしたが、逆にそこで二分探索さえ使えばCrystalでも通るのではないか？と思って投げたら通ってしまった。しかもC++より少し速い。さてはと思ってRubyで投げると、1900ms弱と多少余裕を持って通ってくれた。

atcoder.jp

明日はICPC本番。予定起床時刻は午前8時前なので、そこから逆算して午後11時には寝る準備を始めようと思っており、実際に入浴などをこなすことができて、日付が変わる前には布団に入っていた。しかし眠れない。ちょっとくらいならいいだろうと思ってラノベを開き、そのままずるずる読み進め、午前2時半までかけて1冊読了してしまった。

「超能力に目覚めたボッチが政府に呼び出されたらリア充になりました」。設定が違和感だらけだった。ほとんど現実に準拠しているので、この作品独自の部分の粗が目立つように思う。超能力者が特に珍しくもなくなった世界と言っているのに、超能力関係の法整備がガバガバなのがよくわからない。行使に関する制限もなさそう。それでいて、「主人公のテレポート能力は犯罪に容易に応用できるため危険である」という危険性の大小に関する意見を、「人は誰しも犯罪を犯しうる」とゼロイチの話にすり替えてやり込めている描写がある。そのあとでちゃんと監視をつけていることも言っているのだから、そちらだけ描いておけばよかったのに。と、ほぼこき下ろすような言い方をしたが、読後感は悪いわけではなかった。単純なもので、ヒロインが大量にいたり主人公が強かったりのシーンは好みだったのだ。

まだ眠れない気がしてハーメルンの更新を漁っていたが、午前3時くらいにはちゃんと寝落ちしたらしい。

03/16(水)

午前7時半、目覚ましで目を覚ます。10分スヌーズして40分くらいに身を起こした。うかうかしていると通勤ラッシュに巻き込まれてしまう。それなりに急いで準備して、午前8時過ぎには出発した。

ここから午後9時過ぎの懇親会Gather終了までのことはほとんどICPCの参加記に書いた。ICPCに関係ないことをいくつか補足する。まず、研究室から帰宅する際に大学生協に寄って注文していた本を4冊受け取っている。次に、Gatherで通話を繋ぎながら遊んだGartic Phoneについて感想を書いておく。初めて遊ぶので勝手がわからず、テーマ決めの際に恐らく一例として薄く書かれていた文章に回答しようとしてしまった。イラストが何を意味するのか分からず空欄で回してしまい残念に思っていたら、実はこの場合前の文章がそのまま渡るらしくて、あまりの優しさに感動した。TLでたまに流れてくる謎のGIF画像の意味がわかってスッキリした。

kotatsugame.hatenablog.com

終了後は参加記を書こうとしつつ、コンテスト中のムーブを復元したり解法を言葉にしたりがかなり面倒に思えてダラダラTLを見ていた。

午後11時半ごろに2回、地震があった。以下の自分の2ツイートはそれぞれ、揺れが収まったころに机の下から出てきてツイートしたものである。逆張りすぎて「ゆれ」とツイートできない。文面では何とかふざけたが、実のところこれまで体験したことがない強い揺れに、それなりに浮足立っていた。

【地震 23:34】
［震度５弱］宮城中部、福島浜通り
［震度４］宮城北部、宮城南部、福島中通り
［震度３］岩手沿岸南部、岩手内陸北部、岩手内陸南部、秋田内陸南部、山形庄内地方、山形最上地方、山形村山地方、山形置賜地方、会津、茨城北部、茨城南部、栃木南部、群馬南部
— 特務機関NERV (@UN_NERV) 2022年3月16日

わが心は不動
— こたつがめ (@kotatsugame_t) 2022年3月16日

【地震 23:36】
［震度６強］宮城北部、宮城南部、福島中通り、福島浜通り
［震度６弱］宮城中部
［震度５強］岩手内陸北部、岩手内陸南部、山形村山地方
［震度５弱］青森三八上北、岩手沿岸北部、岩手沿岸南部、秋田内陸南部、山形最上地方、山形置賜地方、会津、茨城北部、茨城南部、栃…
— 特務機関NERV (@UN_NERV) 2022年3月16日

しかして自由にあらねばならぬ
— こたつがめ (@kotatsugame_t) 2022年3月16日

揺れこそ大きかったものの、被害は全くと言っていいほどなかった。揺れのピークで一瞬部屋の電気が消えただけで、PCはシャットダウンすることもなくずっと元気に動いてくれている。水道もとりあえず問題なさそう。机の下から恐々と本棚を眺めていたのだが、突っ張り棒が役目を果たしたのかほとんど揺れることもなく、落ちてきた本も入りきらなくて横に積んであったものばかり10冊程度だった。後から確認してみたところ、ただ1冊だけ角が折れ曲がっていた。許容範囲内。

本棚がグラグラ揺れているのに気づき、思わず押さえに行ってしまった。突っ張り棒は設置してあるものの、多少ゆるみがあったようだ。これは良くない行動であったらしい。
週記（2021/02/08-2021/02/14） - kotatsugameの日記

前回の地震の際、本棚に取り付けてある突っ張り棒のゆるみに気づいて直していたおかげか、今回は特に本が落ちてきそうになることはなかった。
週記（2021/03/15-2021/03/21） - kotatsugameの日記

また、前回の大きな地震から部屋で変わった点として、モニターアームの設置が挙げられる。縦に2枚並べるタイプのモニターアームを2本取り付けて、しかも上部にだけモニターを設置しているという現状から、重心がかなり高くなっており大きく揺れるのではないかと心配していたが、びくともしていなくて安心。

水道が確実に生きているうちに、と思ってシャワーを浴びた後、食事してICPCの参加記を書く作業に戻った。しかしほとんど進まないうちに眠気から椅子の上で意識を飛ばしてしまったので、布団に移動して就寝。午前3時半だった。

03/17(木)

起きてからPixiv小説をしばらく読んでいたことを覚えている。閲覧履歴やその時刻を復元できないため、いつから起きていたのか定かではない。布団から出たのは午後1時だった。

ラノベを1冊読了。「リモート授業になったらクラス1の美少女と同居することになった」。最近になってリモート授業を取り扱ったラノベを見るようになった気がする。ちょっとタイミングを外している感じもあるが、やはり本にするとなるとタイムラグがあるのだろう。そして、そのようなラノベを僕があまり面白く感じられないことも明らかになってきた。僕がリモート授業を受けたことがないという理由かもしれない。リモート授業を扱う場合どうしても主人公とヒロインが半同棲っぽい感じになる必要があって、それが食傷気味だからかもしれない。いずれにしても内容があまり記憶に残らなかったのは確か。イラストは良かった。

PayPalにCodeChefから賞金が贈られてきた。ただ、この送金のリスクが高いとされていて、すぐに受け取れるわけではないようだ。少しでも早めるためには、この送金が何の対価であるかをPayPalに伝えて、PayPalからCodeChef側に確認を取るというステップを踏む必要があるらしい。物理的な物の対価であるならば発送情報を提出するところ、当然こちらはCodeChefに何も送っていないため、今回はデジタルサービスの一種であるとすることにした。発送日は、おそらく対象となったコンテスト、November LunchTime 2021の開催日にしておいた。うっかり操作をミスってよくわからない状態になったが、まあ最悪気長に待っているだけでも決済されるだろうと呑気に構えている。

午後5時からインターンのコーディングに取り掛かった。月曜日の続きで、メインのアルゴリズムの実装。とりあえず実装が完了して、コンパイルが通るようになったはいいものの、全然意図した挙動をしてくれていないことに気づいたところで1on1の時間になった。そこでコードの意図を説明して、メンターさんのほうにも時間があるようだったのでお言葉に甘えてデバッグを始めた。デバッグ出力を眺めていると他にも思わぬ挙動をしているところが見つかったりして、結局想定通りの結果物が確認できたのは1on1開始から3時間後だった。ただ、ここで集中的にコーディングしたことによってひとまず他の人に見せられるような状態まで持って行けたのは嬉しい。相変わらず集中して取り組めばすぐ終わることを放置しすぎていることに変わりはないが、今は一段落ついたという安堵のほうが強い。

Topcoderでコンテストがあるらしい。CLISTにも書いておらずなんだか怪しいし、正直面倒なのでサボることにした。

日付が変わる前くらいにハーメルンを開いて捜索掲示板を漁り始め、そこから1作読み始めた。午前2時寝落ち。

03/18(金)

午前8時起床。TLにハーメルンの読了ツイートが流れてきて、一口サイズだったのでサッと読み切ってしまった。「よう実　最速Aクラス卒業RTA Aクラス綾小路籠絡ルート」。

syosetu.org

「よう実」の原作は人から聞いて面白そうということは分かっていて、いつか読もう読もうと思っていたのだが、新作ラノベばっかり買っているうちに、ついに二次創作に手を出してしまった。多分これ原作では重要な要素なんだろうな、と思うようなこともRTAなので容赦なく明かされていく。ただハーメルンとしてはめちゃくちゃ面白かった。やはり走者視点とキャラクター視点の対比はRTA小説の醍醐味であると感じた。原作主人公を籠絡するというのも目新しく感じられて良い。

午前10時半ごろに二度寝して、午後4時に再度起床。

来週金曜日の卒業式の会場が、先日の地震で使えなくなったらしく、変更になっていた。

🟠会場変更のお知らせ
3/25(金) 学位記授与式の会場として予定していたカメイアリーナ仙台（仙台市体育館）が、地震後の施設点検の結果、使用不可となったと報告がありました。

これに伴い、会場が変更になります。
詳細が決まりましたら、大学HP、および学位記授与式特設サイト等でご案内いたします https://t.co/NyPyPcMkwl
— 東北大学 (@tohoku_univ) 2022年3月18日

昨日寝る前に読んでいたハーメルンの続きを進めようとした。遊戯王の二次創作である。ただ、最初の数話こそオリ主が大胆な活躍をしていたものの、以降は原作主人公陣営をメインとして話が進み、デュエル描写もめちゃくちゃ濃密で、ただでさえ影のフィクサームーブをしているオリキャラがあんまり登場しなかったので、これは求めているものと違うのではないかと感じて早々に放り投げてしまった。

syosetu.org

午後7時くらいに起きて食事。週末は忙しそうなので、溜めている日記やICPC参加記を書いておかなければならない。ただ腰が重い。ずっとぼんやりしながらYouTubeを見ていた。そのうち、今月ぶんのTCB45がすでに始まっており、これまた今週末までであることに気づいた。日記とは違ってそれなりに元気があるときに参加しておく必要があるので、今からやってしまうことにした。例のごとくこの日記が公開される頃には結果が出ているので、ここに各問題の感想を書いておく。

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

3問目は制約から、 $B_i$ として出現しないただ一つの頂点を見つけてそれを出力すればよいことがわかる。ただすぐには思い至らなかったので、提出では愚直に全頂点試している。BFSをイチから書いてもACまで3分切っていたのでセーフ。5問目は辺をソートして判定。6問目は葉を2つ選ぶか、葉とその親を選ぶかしかない。7問目は思考停止して全方位木dpを書いたが、コードを読み返してみれば普通に木dpで解けるとわかる。8問目は木上のimos法をしてパスに含まれる辺を列挙し、連結成分数を数える。ここまでは22分ちょっとで理論値だった。以降2問は激ムズ。

9問目は、辺の重みが高々 $30$ で、また出現頻度にも明確な特徴があるので、それを使うのではないかと考えた。辺を重さでソートして、辺を追加するごとにその辺を通るパスについて答えを求める。重み $w$ の辺 $(u,v)$ を追加するときには、頂点 $u,v$ をそれぞれ根として各頂点にたどり着くまでの辺の重みの出現をbitで持って、それらをカウントした配列をOR畳み込みすることで答えが求まる。配列長は $2^w$ あれば十分で、重み $w$ の辺は高々 $N/2^w$ 本しか存在し得ないので、掛け合わせるとうまく消えてくれて計算量が抑えられる。ただ、「頂点 $u,v$ をそれぞれ根として」が問題で、この部分に毎回 $O(N)$ かかる。

2種類の計算方法を併用することにした。まず、 $w\ge 10$ の辺は高々 $400$ 本弱しかないので、上の計算をそのまま実行する。畳み込みまで含めても間に合う。 $w\le 9$ の辺は、包除原理（実際はゼータ変換の逆変換みたいな計算になる）を使う。使う辺の重みの組み合わせ $msk$ を全部試すと、その重みの辺を全部張った後連結成分のサイズを求めることで、「最短パスに含まれる辺の重みの集合が $msk$ の部分集合となる」ようなペアの数が求まる。こちらも $O(N\alpha(N))$ の計算を $512$ 回行うことになるが、間に合う。2.5secくらいで通った。だいたい100分に1ペナもついて、-59pt。

10問目は謎。まず、候補となる頂点を隣接する別の頂点に移した時の総疲労度の差分を考えてみる。この値は、正しい頂点（のどれか）に近づいたとき、またその時に限り負になる。なぜなら、まず2つ以上の方向で負になることはなく、さらに正しい頂点の場合は隣接するどの頂点に動かしても非負であることから、連鎖的に正しい頂点でないすべての頂点においてただ1つの方向、つまり正しい頂点に近づく方向でだけ負になることが言えるからだ。

という証明を考えて、それ以上全然わからないので、ひとまず正しさを確認しようと思った。最初に候補とする頂点を適当に決めた根とし、そこから常に子に向かって進んでいくことにすれば、木をオイラーツアーしたものをセグ木に乗せることで、差分の計算が高速に行える。これを提出したら爆速で通ってしまった。ただ1ペナ付けてしまったので、73分かかったことと合わせて-62pt。

4時間くらいかかって、終わったころには日付が変わっていた。いつの間にか卒業式の新しい会場が決まっていた。家から近くなってラッキー。

🟠#情報更新（3/18 22:30）
令和4年3月東北大学学位記授与式について、
【川内萩ホール】に会場が変更となりました。

詳細は下記URLよりご確認下さい。

🔻東北大学HP (ニュース)🔻https://t.co/Zzzyam1JLy

🔻学位記授与式特設サイト🔻https://t.co/Ase0xO7c2I #学位記授与式　 #卒業式　 #東北大学 https://t.co/NyPyPd3nyl
— 東北大学 (@tohoku_univ) 2022年3月18日

そこから午前5時くらいまでかけてICPC参加記を書いた。最後のほうに結構ネガティブなことを書いたので、しばらく寝かせてから投稿しようと思う。またしばらくYouTubeを眺めてボーっとして、午前8時くらいに布団に入った。新しいなろうを開いて少しだけ読み、午前8時半に寝落ち。

03/19(土)

午後0時半起床。食事せずにHUPC2021 day1へ。

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2021Day1

Aはちょっと面倒。CEを3回くらい吐いてから、そういえばAOJでは型なしのmainがCEになるんだったと思い出した。Bでちょっと詰まってビビる。ここまで難易度順。次にCに進んだ。左右から破綻しないようそれぞれ貪欲に修正した列を用意して、適当なところでつなぎ合わせ対応した括弧列になったらコストを更新、としたら通った。謎。

ここからはsolved数に従って解いていた。Jは、まず $6$ を並べて、その間に順番を壊さないように $2,4,8$ と $3,9$ をそれぞれ並べ、残りを自由に並べればよい。この自由に並べてよい部分の計算を間違えて1WA。Hは毎回畳み込んで $O(NK\log K)$ 。Eは、まず $K=1$ の場合 $1$ 色で、次に $K\ge 3$ の場合 $P$ 自体と任意の2つを選ぶことですべての集合の色が異ならなければならないとわかるため $2^N$ 色。 $K=2$ の扱いを間違えて2WAし、最終的には $N\le 4$ での実験結果から $N+1$ をエスパーした。

Gは連立方程式を立てて解く。 $0$ 、 $1$ 、 $2$ の個数をそれぞれ決め打つと $(N+1)(N+2)/2$ 状態あり、 $N\ge 3$ ではこれらはすべて互いに行き来できるようで、そのまま計算して解が求まる。ただし $N=2$ の場合だけ、3状態のループが2つできる形になり、何も考えず掃き出し法をすると $0=1$ という式が出現してすべてが壊れてしまう。この場合だけ埋め込んで通した。エラー出力があるとREになるようで、2ペナ付けてしまった。Iは標高の降順に見て、すでに見た点のうち最も近いものをチェックし、その点を計算した時に見えた最も遠い点をチェックし……というループを書いたら爆速だった。このループを $O(N)$ 回行う頂点が $O(N)$ 個あるようなケースも作れそうなので、嘘に見える。

Fに取り組むも8ケース目を超えられずコンテスト終了。結果は8完13位だった。微妙。Fの考察はほとんどできていて、ただ $a=(3,2,1)$ 、 $b=(4,5,6)$ から2手で完全勝利できることに気づけなかったのが敗因。一般マッチングが出てきて嘘だろ……と思っていたのだが、想定だったようだ。

午後3時くらいに両親が来ていた。コンテストも終わったので、部屋の片づけをする。特に今回は、大学入学時に持ってきたはいいものの一切着なかった服や、たくさん溜まったコンテストTシャツを全部実家に持って帰ってもらうことにしたので、それを整理していた。衣装ケースもスッキリしたところで、仙台駅まで行って牛タンを食べた。今日はARCがあるが、もうunratedなのであんまり気にしなくていいかと思いお酒を一杯飲んだ。

食事 pic.twitter.com/ZKyjwKPzUe
— こたつがめ (@kotatsugame_t) 2022年3月19日

イオンで買い物をして帰宅。両親と別れ、午後9時からARC137に出た。

AtCoder Regular Contest 137 - AtCoder

Aは素数砂漠が短いことを利用するのだろうなと思い、念のためどのくらい長いか確認しようと思ったが、検索しても $10^9$ までの情報しか出てこなかったので諦めて書いた。実行は爆速。Bは適切に累積和を計算することで区間をflipした時の差分が $O(1)$ で求まるようにできる。この差分の最大最小も同時に求めることができて、その間の数は全部達成可能であると感づいた。Cは難しい。たまたまエスパーが成功して、結構な速度で解けた。ソートした時の隣接する要素の差 $A_i-A_{i-1}-1$ （ただし $A_0=-1$ ）の変化を見たくて、それを表示するようにした状態で小さいケースで実験してみると、「 $A_N-A_{N-1}-1=0$ 」かつ「差の和が偶数」の場合のみ後手勝ちに見えた。もっと大量に実験してもこの事実は揺らがないようだったので半信半疑で提出、AC。

順位表を見るとすでにDが10人以上に通されていてたまげた。 $k$ に応じて $A_i$ から $A_N$ への寄与を求めたのだが、二項係数になっていることに気づかなかった。 $\bmod 2$ で様子を見るとフラクタルな感じになっているとわかったので、それを利用する。 $k=1\dots 2^L$ で答えを求める際には、 $L\leftarrow 0\dots L-1$ がそれぞれ計算できれば良い。この時、列を分割して適切にXORを取ることで、計算対象の列の長さを縮めることができる。計算量解析を行わずに実装に入った。一番最初は常に $L=20$ として計算を開始するようにしたので、サンプルが手元で高速に動くのを確認すれば十分。450msくらいで通った。この時点で45分。

Eを見て、しばらく考えてもわからなかったので、残り1時間はコードゴルフをしていた。結果は4完39位。

コードゴルフ。Aは今のところ答えと $R-L$ の差の最大値が $7$ らしく、Rakuでも全く問題なく通る。gcd演算子にZを付けることで複数のペアのgcdを一気に求められて便利。BはAWK。各要素に対して計算すべきことが多く、中かっこを嫌って1つの式に詰め込むよりは、RSを弄って要素ごとのループにしたほうが短くなった。Cはdc。上で述べた「差の和が偶数」は「 $A_N+1-N$ が偶数」に言い換えられるので、後ろ2要素と $N$ しか見る必要がなく、かなり短くなった。Dは解説を読んでたまげ、Rubyで通しておいた。

明日に予定されていたOpenCupが1週間延期されていた。これまでずるずる延期されてきたこのコンテストであるが、03/27開催は最終決定らしい。どうせずれるだろうと思って明日は両親と1日観光に行く予定を入れていたので、こうして現実に延期されているのを確認して一安心。

よくわからんけどさすがに3/20のOpenCupはないだろと予想立てて1日旅行の予定入れた。頼む
— こたつがめ (@kotatsugame_t) 2022年3月9日

今日買ってもらったプロテインを飲んでみた。思ったより高くてビビる。ふたを開けるとバニラのにおいがブワッと広がって非常に驚いた。しかし水に溶かして恐る恐る飲んでみると、まったく味がしなくてびっくり。スプーン3杯と書いてあったが、使ったスプーンが小さかったのだろうか。

日付が変わってからはCodeChefをサボり、ずっと日記を書いていた。途中で、今日のARCで最短コードが1900問に到達していたことに気づいた。

Shortest 1900 pic.twitter.com/ERweSVBXGi
— こたつがめ (@kotatsugame_t) 2022年3月19日

午前4時くらいに切り上げ、実家に持って帰ってもらうために既読ラノベを箱詰めし、午前4時半就寝。

ハア……ハア…… pic.twitter.com/KZvOptui9P
— こたつがめ (@kotatsugame_t) 2022年3月19日

03/20(日)

午前8時半起床。迎えに来た両親と午前9時に出発。HUPC day2はサボる。

まず1箇所目、気仙沼市東日本大震災遺構・伝承館。津波に飲まれた高校の校舎を遺構として保存しているところ。到着して車から降りたとき、まず視界の広さに衝撃を受けた。周り中ほとんど何にもなくて、海も山もはっきり見えてしまうのだ。ここにあったものは一度すべて流されてしまったのだと、そうはっきりわかる光景だった。

f:id:kotatsugame:20220321061241j:plain — 校舎屋上から

校舎の中は当時の状態のままに残されていた。1階の隣り合う部屋は、片方は天井の一部も窓枠も残っているのに対し、もう片方は何も残っていなかった。何が違ったのだろうか。

f:id:kotatsugame:20220321062108j:plain — 左右の部屋の違い

校舎4階、津波の最高到達点。左側のレターボックスの錆が顕著だが、右に積み重なった戸棚にも注目したい。上の戸棚のガラスは割れていない、というのが印象的だった。

f:id:kotatsugame:20220321062535j:plain — 津波の高さ

もっと直接的に津波の威力を示すものもあった。以下の2つのうち前者は、単に重いものがぶつかったというだけではこうはならないだろう状態だから、波そのものの力を示していると考えられる。

f:id:kotatsugame:20220321061829j:plain — 津波に押されて巻き付いた屋根の一部

f:id:kotatsugame:20220321062018j:plain — 曲がった防火扉

そのほか、津波に流されて積み重なったり、3階教室に激突したまま残された車などもあった。それらや映像資料を見て、またつい先日の地震でも津波注意報が発表されていたことを考え合わせ、津波とはなんと恐ろしく身近な災害だろうかと深く思い入っていた。ただ、この遺構・伝承館で最も心に残ったのは上に挙げた展示ではなく、映像で流れていた、震災から11日後に行われた階上中学校卒業式の生徒代表の答辞だった。検索するといくつかニュース映像が見つかる。震災後に一から書き直したという答辞の文章が素晴らしいことで有名になったようだが、個人的には震災当時の映像だったため、人の生の感情に触れたような気がして自分の感情も大きく動いたという側面が強い。

次に高田松原津波復興祈念公園。奇跡の一本松と言えば有名だろうか。すでに枯れてしまって一部レプリカに置き換えられたようだが、それでも、だだっ広く開けてしまった場所に一人聳えているのは、なるほど希望の象徴となるのも頷かれる様子だった。

f:id:kotatsugame:20220321065942j:plain — 奇跡の一本松

ここには岩手県東日本大震災津波伝承館がある。そこも一通り見てきた。この地域は過去何度も津波に襲われてきたらしい。そのたび高台に家を構えるような運動が発生するのだが、10年もすれば便利さを求めたり、津波を経験しない人が流入してきたりして、また元通りになるということが書かれていた。「此処より下に家を建てるな」という石碑の写真が印象深い。過去の津波の記録を見るに、どう考えても定期的に津波は発生している。しかしその発生のスパンは、人間の記憶が薄れるには十分長いのだ。

「此処より下に家を建てるな」石碑の警告守る【宮古・姉吉地区】

最後、とおの物語の館。閉館まで1時間しかなかったこともあり駆け足で見回ることになった。遠野物語は京極夏彦によるremixしか読んだことがなく、またそれも幾分昔のことであるから内容はほぼほぼ覚えていなかった。全体的にあまり印象には残らず。近くのカッパ淵にも寄った。遠野は雪がまだ結構残っていて驚きだった。

f:id:kotatsugame:20220321073720j:plain — 高善旅館

午後8時半に帰宅。僕を下した両親はラノベを積み込んですぐ去っていった。本棚に空きができてスッキリ。ただ残った本は全部未読ということで、将来どうするんだろうと少し考えてしまう。

今この本棚、未読本しか入ってないらしいです pic.twitter.com/IOKADmAVf2
— こたつがめ (@kotatsugame_t) 2022年3月20日

午後9時からABC244に出た。CF combinedと被っていたが、ABCを優先した。

AtCoder Beginner Contest 244 - AtCoder

A、B、Cはよい。Dはよく見ると常に転倒数の偶奇が変わり続けるので、それが一致しているかチェックすればよい。Eは $X$ が任意の頂点かと思って一瞬詰まったが、よく読むと入力で与えられていた。それなら自明。Fも適当にbitDPやるだけ。Gは少なくとも木で構成できる必要があって、自分と子を往復することで子の状態を好きに弄ることができる。最後に根が残って少し困った。子、根、子と移動することでこれもクリア。実装はDFS木を取りながら見ていくと楽。提出時、配列サイズを1<<17にするべきところ17にしていて1RE。

Exは難しく見えた。いつかmaspyさんが凸包云々と言っていたな、と思い出し、検索で該当のツイートを発見するも、実装がよくわからない。ここで一旦Aに数回提出した後戻ってきて、記憶がはっきりしてきた。つい先日のTUPC2021関連の話題だったはずだ。TUPCは03/12だったから、03/13以前のmaspyさんのツイートを検索して見てみると、見事提出まで見つかった。そこからコードをコピーしてくる。オフラインのデータ構造なので、クエリを平方分割して無理やりオンラインにする。ちょっとコードを書き換えて点の追加が可能なようにし、適当にランダムケースでバケットサイズを調整して提出、3500ms程度でACした。

Ex問題　解き方：
1.「from:maspy_stars until:2022-03-13」と検索する。この日付はTUPC2021の次の日である。
2.以下のツイートを見つけて、提出を拝借してくるhttps://t.co/4mMAKewRRz
3.クエリ平方分割する
— こたつがめ (@kotatsugame_t) 2022年3月20日

全完優勝。ABC187以来、およそ1年ぶり3回目のABC優勝である。画面キャプチャを録画していたのは初めてなので、これはぜひともゆっくり実況にしたいと思っている。

ABC244優勝 pic.twitter.com/F8z0EQbmHV
— こたつがめ (@kotatsugame_t) 2022年3月20日

一方今日のコードゴルフは大敗。A問題はVimの5Bを39秒で提出したところ、21秒の提出があって負けた。このレベルだと手元で試さないと挙動がわからないようではダメらしい。BはRubyで、複素数で座標を保持する方法。方向を変えるのにd*=-1iをしていたら、d/=1iに縮められて負けた。言われてみれば……。CはPerlでシコシコ縮めたものがdcに8B負けていた。ただそこから1B縮めることに成功。DはRGBを012に変換してスペースを消したものを数値として読めば、27で割ったあまりで分類できることに気づき、これは短いだろ！と思って提出したのに、コンテスト後に見たらVimにめちゃくちゃ短いものがあった。片方の文字列を2倍にして、もう片方の文字列が含まれるかチェックすればよいらしい。全然気づかなかった。3要素の転倒数の偶奇にはいい性質が大量にありそう。以降は手付かず。

TCB45の結果が出ていた。理論値-121ptで3位。1位は9完でマジか……となった。微妙に惜しい点差。

今日もプロテインを飲んだ。相変わらずにおいだけすごくて味はしない。よく考えると、ダイエット飲料でもあるのに甘かったら台無しか。その分香料でごまかそうとした結果がこのにおいかもしれない。

日付が変わってから朝まで、6時間以上ずっと日記を書いていた。明日も昼から予定があって睡眠時間がまずい。

2022-03-21

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

2022/03/15-2022/03/16に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーはゆきのんさん・ha15さん・僕です。

今年はサークルから2チーム出場するということで、顧問の先生の研究室を2部屋貸していただけることになりました。もうサークル運営からは退いているので、交渉は全部現サークル長にぶん投げました。お二方ともありがとうございました。

1日目（03/15）

研究室に正午集合ということになっていました。十分間に合う時間に起きたのですが、うっかりコードゴルフを始めてしまい、集合時間を過ぎてから家を出ることになりました。

到着してみるとすでに使用する部屋が振り分けられていて、他にすることもないので購買で買った昼食を食べたりPCの準備をしたりしました。今日使うのは普段研究が行われている部屋のようで、すべての席にモニターとケーブルがあったので、全員がデュアルディスプレイにしていました。

受付を問題なく済ませます。起床に失敗した人をしばらく待っていたらしく、開会式は少し遅れて始まりました。コンテストのデモで取り扱われた、 $1$ から $n$ までの和を求めるという問題文なのに実は $n\le 0$ のケースが入っているというあまりに性格の悪い問題に震え上がりました。開会式の遅れが響いて、リハーサルコンテストも20分遅れで始まるようです。

例年ならば4問のところ、今年はなんと11問もありました。適当に眺めてみると、昨年の横浜大会の問題が全部そのまま出題されているようです。昨年の問題と聞くと、C問題「Short Coding」といういかにも楽しそうな問題に特攻して、単純なミスに気付かずFAを逃したことが思い出されます。リベンジのチャンスだと捉えて、まずこの問題を解くことにしました。

CのFAはonionsの43分なので、ギリギリ負けたことになります。改めて以前のサンプルに対する出力を確認してみると、サンプル1から正しくない解を出力していることに気づきます。行数だけじゃなくてちゃんと内容にまで気を配っていれば……と後悔することしきりでした。
ICPCアジア地区横浜大会 2020 参加記 - kotatsugameの日記

解くと言っても解法を覚えているので、その通りにコーディングするだけです。慣れないswitch文を使ったのでコンパイルを通すのに少し手間取りましたが、サンプルはすぐに合って提出、無事FAを取りました。どのくらいの時間がかかったかは忘れてしまいました。

次にH問題に取り組むことにしました。これも昨年僕が解いた問題らしいですが、あまり覚えていません。解法も再度ひねり出しました。ただ、 $10^3$ より大きな素数に対して昨年より定数倍が悪い方針を取ってしまい、TLEを解消するのにかなり苦労しました。区間に対して素数とその出現回数のペアを管理し、出現回数の大きなほうから3つ管理すればよいというものです。マージ関数をいろいろ書き換えるのはあまり効果がなく、最終的にセグメント木の初期化を $O(N)$ で行うとそこそこ高速になり、1WAを挟みつつコンテスト終了直前にギリギリ通りました。

H問題のWAは、投げてからかなり時間が経って出た結果だったので、どこか大きなケースで落ちているものと思ってずっとデバッグしていたのですが、実はサンプルからすでに出力が異なっていました。どうやらICPCのジャッジは、WAの場合は全テストケースを実行してからその結果を出してくるらしいです。明日は気を付けようと考えました。

今日書いたコードをAOJに提出してみました。C++14とC++17で実行結果が違い、かなりモヤモヤしましたが、結局解決できないまま帰宅しました。夜はずっとコードゴルフなどをしていて、午後11時くらいには寝る準備が整いましたが、乱れた生活リズムですんなり眠れるはずもなく、うっかりラノベを1冊読んでしまいました。結局眠れたのは午前3時頃でした。

2日目（03/16）

今日は余裕を持って家から出られましたが、朝ご飯を買おうと思っていた購買が開いておらず、ちょっと離れたコンビニまで往復していたら思っていたより遅くなりました。午前8時45分頃に部屋に到着してPCの準備をします。今日は家からキーボードとマウスも持ってきました。Zoomを聞いているとコンテスト開始が遅れるとのことだったので、その時間で腹ごしらえをしました。午前9時10分、コンテスト開始です。

コンテスト

問題：https://icpc.iisf.or.jp/past-icpc/regional2021/problems-2021.pdf

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

J問題

初動は他の2人がAとBで、僕は後ろの方の問題を眺めるという分担でした。J問題にたどり着く前にIとHを順に読んだ記憶があります。Iはハマったら辛そうだったので、HはTL 30secに恐れをなして、それぞれ解くのを諦めました。その次にJ問題を読んで、見た目にはいかつく感じましたがとりあえず少し考察してみることにしました。

2次元平面上の点が $n\le 2\times 10^5$ 個与えられるので、点のペア $( (x_p,y_p),(x_q,y_q))$ であってすべての点 $(x,y)$ が $x_p\le x\le x_q$ または $y_p\le y\le y_q$ を満たすようなものを数えよ、という問題です。 $x$ 座標と $y$ 座標がすべて異なるのがかなり優しい制約です。とりあえず点が $x$ 座標の昇順にソートされているとしても問題なく、このとき $p\lt q$ がわかります。 $p$ を決め打って $q$ を数えようとしたときの条件を整理してみます。

まず、 $y_p\lt y_q$ です（後からわかりましたが、これは嘘です）。さらに、インデックスが $p$ 以下の点のみを考えたとき、 $y$ 座標の最大値が $y_q$ 未満であり、かつ最小値が $y_p$ である必要があります。インデックスが $q$ 以上の点についても同様、 $y$ 座標の最小値が $y_p$ より大であり、かつ最大値が $y_q$ である必要があります。逆に、これらが満たされていればペア $(p,q)$ は問いの条件を満たします。

文字をいくつか導入して式で表してみます。「インデックスが $p$ 以下の点の、 $y$ 座標の最大値」を $y_l$ 、「インデックスが $q$ 以上の点の、 $y$ 座標の最小値」を $y_r$ とすると、 $y_p\lt y_q$ 、 $y_l\lt y_q$ 、 $y_p\lt y_r$ が必要です。このうち1番目の式は2番目や3番目の式から自動で満たされるので、考えなくてよいです。また「～の最小値が $y_p$ 」・「～の最大値が $y_q$ 」という条件については、それを満たす点のみ計算に含めることで常に成り立っていると扱って構いません。結局、ペア $(y_q,y_r)$ の列に対して、 $(y_l,y_p)$ よりどちらの要素も大きなペアを数えるクエリと、ペアを追加するクエリが高速に処理できれば良いです。

よく考えると値を追加するクエリは考慮せず、最初からすべての値のペアが与えられているとしてよいです。なぜなら、 $q\le p$ の場合、 $y_l$ の定義より $y_l\lt y_q$ が満たされることはないからです。もともと2次元平面における矩形内の点のカウントクエリでしたが、更新がない場合はもうちょっとシンプルなデータ構造でぶん殴ることができます。僕は蟻本p.171にある列を持つセグ木のライブラリを貼りました。

1WAしました。 $y_p\le y\le y_q$ の代わりに $y_q\le y\le y_p$ を満たしていてもよいと誤読したからでした。この場合は単純に上のコードを倍にすればよいです。逆に修正は、答えに余計な値を足している部分を消すだけで済みます。40分時点で通り、順位表ではFAに見えました。ただし、 $p$ と $q$ を列の両端に取ることで、 $y_p\lt y_q$ という条件が必要なくなる場合があります。逆に $y$ 座標の最小と最大を選んでもよいです。これらのケースを考慮しないまま通してしまいました。その後修正が入ったそうですが、僕の提出はすでにACを得ているためリジャッジの対象にはなりませんでした。

D問題（1回目）

僕がJ問題を解いている間にA問題を通したゆきのんさんは、B問題がややこしいということでそちらのヘルプに入っていました。僕はガン無視して、他に唯一ACが出ていたG問題に進みました。番号の降順に見て現在の木の数とまだ何が来るか決まっていない子の数を持つdpはすぐ思いつきましたが、ループを作ってしまうケースでどうしたらよいかわかりません。そうこうしているうちにB問題が通り、またsuzukaze_AobayamaによってD問題が通されたので、G問題は他の2人に任せてD問題に移ることにしました。

作った木の直径の最大化というのは、パスを一番長くなるように取ることを考えればよいです。パスのうち最も標高が高い点で分割するとよさそうに見えました。標高の昇順に見て、そこを端点とする最も長いパスの長さを管理しつつ、そうして作った2つのパスを接続してみます。

結論から言ってしまうと、この方針はダメダメでした。パスを最も標高が高い点 $i$ で分割したとき、 $i$ と隣り合う点 $j$ 、 $k$ が $j\lt i\lt k$ を満たすと思い込んでいましたが、そんなわけはありませんでした。例えば $j\lt k\lt i$ の場合、ある位置 $j\le l\lt k$ が存在して、 $j$ から続くパスは $l$ 以下の点のみを使い、 $k$ から続くパスは $l+1$ 以上 $i$ 未満の点のみを使うことになります。そのように分割されてしまった場合を高速に計算するのはどう考えても不可能でした。

3WAくらいしてからどうやらダメそうだということに気づきました。それからもしばらく唸っていましたが、解ける気配がないため、頭を切り替える意味でも別の問題に取り組むことにしました。

G問題（1回目）

まず、まだ解けていなかったG問題を再度考えてみます。番号の降順に見て失敗したのだから、昇順に考えてみるということを思い立ちました。すると、番号を昇順に見たときは常に木が1つしか存在できないという真っ赤な嘘を思いついてしまいました。そのような事実が存在するなら、特に深いことは考えず $O(n^2)$ のdpが行えます。制約が $n\le 300$ と $O(n^3)$ を許容しているのを訝りながらも、この方針をゆきのんさんに伝えて実装してもらうことにしました。

C問題

他に唯一ACが出ていたC問題を考えます。こちらはすでにhaさんが取り組んでいました。操作がちょっとややこしいですが、読み解いてみると、デコード後の文字列が与えられているならコードを後ろから解釈して正しくデコードできるか確かめられることがわかりました。例えば $(A_1,L_1)$ を決めたとき、エンコードした文字列を反転したものでは、この操作は $(A_k,L_k)=(L_1,A_1)$ と解釈されます。この $(A_k,L_k)$ の操作によって文字列 $s$ が完成する必要があるのですから、文字列 $s$ の後ろのほうをちょっとチェックすれば本当にそのような出力がなされるかわかります。

この考察をもとに、とりあえず答えとなる文字列のうち最短のものの長さがわかります。「正順に読んでデコードしたとき、文字列 $s$ のどこまで出力されるか」と「逆順に読んでデコードするとしたとき、文字列 $s$ のどこからがすでにエンコードされているか」の2つを持つdpは、状態数が $(|s|+1)^2$ で、遷移は $0\le A,L\le 9$ を全部試しても $100$ 通り、チェックにかかる時間を考えても十分間に合います。ただ、辞書順最小を求めるのはちょっと難しいです。

ここで、dpの状態を頂点、遷移を辺だと思うと、 $(|s|+1)^2$ 頂点の有向グラフが得られます。このグラフ（の辺を反転したもの）でゴールからBFSしておくと、スタートからどの遷移を選ぶことで最短でゴールにたどり着けるかがわかるようになります。そのような遷移であって特に辞書順最小であるようなものを常に選びつつ文字列を構築すれば、全体としても辞書順最小になるので、これで解けました。

実装がちょっとややこしいと感じたので、haさんに解法を伝えることを勝手に諦め、一人で書き始めました。幸い一発で通りました。3時間6分時点と、B問題が通ってから実に2時間以上動きがなかったことになります。

G問題（2回目）

嘘解法を実装してもらっているG問題は、当然まだ通っていません。次はこれを何とかすることにしました。書いてもらったコードを隅から隅まで読んで、 $n=3$ を全通り手で試して比較しても、何が違うのかわかりませんでした。考察に間違いがあるのではと何度も思考の過程をなぞり、ようやく先ほどの嘘、つまり2つの木をより大きな番号の頂点を使って1つの木にすることが不可能ではないことに気づきました。

絶望しつつ、改めて考えなおします。番号の降順に見たときはループの発生を止められずダメでしたが、昇順に見たときどうかはまだ考察していませんでした。2つの木を1つの木にする場合、今見ている頂点をある木の葉に入れつつ、さらにその下に別の木を入れます。このとき「今葉を使った木」を入れてしまうとループになります。ところが、このようなケースは下に入れる木を「今葉を使った木」以外のものにすれば発生しません。そのような除外すべき木は常に1つだけ存在するので、ただ係数から1を引くだけで対処可能です。

結局、一番最初に考えていた $O(n^3)$ のdpで解けそうだとわかりました。制約の $n\le 300$ にもバッチリ根拠があったということで、ミスリードか何かだと思っていた自分を恥じるばかりです。ゆきのんさんに解法をうまく伝えることができず、実装を奪い取って書き始めました。遷移でミスを重ね、+3WAくらいしつつ何とか4時間21分時点で通りました。

さて、このように番号の昇順に見て解いたG問題ですが、本質はループを作るような遷移の際に「今見ている頂点を葉に入れる」→「今見ている頂点の葉に入れる」の順に考えることで、それさえ行っていれば番号の降順に見ても解けるようです。そのような考慮の順番の入れ替えを意図せず行っていただけなので、運よく解けたという認識です。

D問題（2回目）

残り40分もないですが、何とかD問題も通したいです。haさんに自分の先ほどの解法を説明している過程で、パスのうち最も標高が高い点で分割するのではなく、その点から2方向でそれぞれ作られたパスが互いに越えられない位置で分割するのがよいのではないかと感じました。つまり、上で導入した変数 $i,j,k,l$ で言えば、 $l$ で分割するということです。

この時、左側で作るパスは使う頂点のうち最も右側のものを、右側で作るパスは最も左側のものを保存しておきたいです。逆に保存しておきたい位置の頂点に対して値を持つと考えると、パスに新たに頂点を追加するときの更新は、区間加算と1点更新で書くことができます。左側で作るパスで言えば、使う頂点のうち最も右側のものが更新されないなら、その位置で持っておいたパスが同時に1つ伸びる、つまり対応する区間に1が加算されるということです。

これらは遅延セグメント木で書けます。半信半疑でサッと実装してみるとサンプルが合い、また以前に作っておいた、これまでの提出に対するハックケースも通ったので提出、ACしました。4時間34分時点でした。

1回目の挑戦の時は、パスを2本のパスに分解するという辺りになんとなく再帰っぽさを感じて、そのような考え方にすぐ飛びつきましたが、そもそも問題に一切再帰的な構造がないことをもっと重要視すべきでした。 $i$ を決めてから $l$ を決めるのは不可能な一方、 $i$ を決めずとも $l$ は全探索できてしまったのはそこから来ていると考えています。

残り時間

残り時間でI問題を読むことにしました。1本の辺で結ばれた2頂点を取り除くのが一番うれしいので、それが行いやすいように全域木を取って考えてみます。葉から少しずつ切り取ってみて、そうできないものはウニグラフを切り取って適切な処理を行えばよさそうと思い、時間もないので実装してみることにしました。結局これは間に合いませんでしたが、改めて考えてみればこの方針が上手くいかないケースも簡単に作れてしまいました。

コンテスト後

凍結前4完は、改めて考えてもあまりにもひどいです。一応その後2つ通したということで何とか面目を施した感じもありますが、国内予選で負けてからライバル視しているsuzukaze_Aobayamaは凍結前5完、さらに2問に提出があります。こちらはペナルティが大量にあるので、勝つためには完数で差をつける必要があります。まさか地区予選でも負けてしまうのかと気が気ではありませんでした。

休憩が1時間弱あるので、その間に解散して、それぞれ自宅からGather上の懇親会に参加することになりました。Gatherにログインしてから知り合いと少し話したりもしましたが、コンテストの出来だったりYesNoに気を取られてあまり盛んに交流はしませんでした。

YesNoの結果は6完8位。変わらず5完だったsuzukaze_Aobayamaに、何とか勝つことができました。

その後はGartic Phoneに混ぜてもらったり、社会人の方々の食事事情を聞いたり、開会式のPVの裏話を聞いたりして、Gatherが閉まる午後9時過ぎまでずっと交流していました。PVについて、東大だけやけに印象に残るなと思っていたら、小節数の関係で1大学だけ少し長く表示していたらしいです。4チームもいることですし、まあ順当に思えます。ラスボス感が癖になりました。

ICPC 2021 国際大学対抗プログラミングコンテストアジア地区横浜大会、の開幕映像を担当しました！チームの記念になれば嬉しいです

ぜひ高評価、コメントいいねマイリス登録お願いします！

PV・MVの制作依頼もお待ちしてます

YouTube https://t.co/GceibJ9hNc

ニコニコ https://t.co/cYBYr9dEFg pic.twitter.com/RrF2adYHnR
— 百千万億萬 (@TumoiYorozu) 2022年3月16日

結果

直前に書いたように、6完8位でした。順位表全体を見ても、最低限解けるべきだった問題は何とか解けているように見えなくもありません。ただここから+1完はどうあがいても無理だったので、上位争いには程遠く終わりました。一方suzukaze_AobayamaはCに加えてFもAC直前まで来ていたそうだったので、今回この結果で上回れたのもたまたまな気がしてきます。

今回のコンテストは何もかもが上手くいっていません。まず僕の頭が悪いです。さらに相変わらずチーム戦が下手くそで、結局CDGJは全部僕が実装を奪い取ったりして通してしまいました。G問題をゆきのんさんに割り振ったあたりは結構考えたムーブのつもりだったのですが、肝心の解法が大嘘ということで、やはり頭が悪いと言わざるを得ません。こうやって参加記を書きながら思い返してみて、他の2人が何をしていたかというのがほとんど分かっていないことに気づきました。自分のことしか考えていない・見えていないということです。

頭が悪いのは、国内予選からこちらさっぱり精進していないからです。チーム戦が下手くそなのもチーム練習をしていないからです。もうとにかく練習不足です。

ただ、自分のことだけを振り返ってみると、今日は最初から最後までずっと問題を考えていました。一切読んでいない問題もありましたが、それらを考えている時間で他の問題が間に合わなかった可能性もありますし、またそれらは結果的に解かれなかったので、良しとしましょう。嘘解法を何度も生やし続けたとは言え、まともに取り組んだものはちゃんと全部通せたというのは、すっきり終われる結果ではありました。

今年でゆきのんさんも引退ということで、来年のAobayama_dropoutはどうなるのでしょうか。正直、今更チーム戦が上手になるとは思えませんが、かと言って一人で戦った場合は黄色3人にも負けてしまうということが分かったので、どうしようもありません。精進せねば。

2022-03-14

週記（2022/03/07-2022/03/13）

03/07(月)

先週の週記を投稿したあとは比較的素早く布団に入ったはずが、寝っ転がったままなろうを読んでいたら寝るタイミングを逃してしまった。さらに今日の午後から来客が予定されていることに気づき、仕方なく起き上がってパソコンの前に座っていた。思いがけず届いた仕送りも受け取れてラッキー。中にとらやの羊羹が入っていてうれしい気持ちになった。

pic.twitter.com/MO5Z9Sgtdy
— こたつがめ (@kotatsugame_t) 2022年3月7日

どんどん眠くなっていって、かろうじて意識を保ちながらYouTubeをボーっと眺めているような状態が続いた。午後4時半からインターン先の定例会なので、何とか進捗報告スライドを生成。先週の進捗は、もしかしたらメッセージをいくつかやり取りしただけかもしれない。これは本格的にまずい。コードを書く以外のことはしばらくする必要がなさそうなので、どこかで気合を入れてガーッと書く必要がある。

定例会とそれに続く勉強会自体は何事もなく終了。今日の勉強会はかなり興味深い話題だったので、あまり眠気も気にならなかった。

シャワーを浴びてしばらくなろうを読み、午後9時半就寝。

03/08(火)

午前7時半起床。

ずっとなろうを読み続けて、午前10時に1作読了。「黄金の経験値」。02/25から実に12日間を吸い取られたようだ。

https://ncode.syosetu.com/n0806fu/

非常に面白かった。序盤はMMOで自分だけのキャラクタービルドを追求していく感じの話かなと思っていたが、そういう感じで真っ当なトッププレイヤームーブをしていたのは50話くらいまでで、あとは人類に敵対するボスとなるべく一直線だった。その他のプレイヤーとは格が違う、突出した強さが読んでいて気持ちいい。プレイヤーキャラクターなのにNPCのふりをするというのもかなり面白かった。主人公はちょっと迂闊なところがある設定だったので、何かボロを出すのではないかとハラハラしていた。そういう部分で頭の回転が速い人が味方に付いてからは多少安心できた。最強ボスとして君臨する主人公に挑む一般プレイヤーたちが真剣にゲームを進めている一方で、主人公陣営では気の抜けるようなやり取りが繰り返されたりして、その緩急もよかった。

ちょっとネタバレになる。600話もあるし、主人公がプレイヤーキャラクターであるという事実はいずれ大々的に明かされるのかなと思って読み進めていたが、本当に隠しきったまま完結してびっくりした。またリアルの話が全くと言っていいほど描かれない点も含めて、徹頭徹尾ブレなかった作品だと感じた。

読了後も布団に寝転がって、しばらくYouTubeを見ていた。先週の週記でも書いたflat-工房というYouTubeチャンネルの動画で、またテンポの良いものを見つけて何回もループしている。

www.youtube.com

ちょっとデュエマの話をする。預言者クルトという1コストパワー500能力なしのクリーチャーがあって、僕はこれをネタカードだと思っていた。普通能力なしなら2コストパワー2000なり3コストパワー3000なり、コストの1000倍がパワーになるべきところ、なんでこいつだけ500引かれているのかと。ただこれは逆で、こいつだけ500足されていたのが正解だったようだ。つまり、1コストのクリーチャーの適正パワーは1000ではなく0で想定されており、本来はそこからデメリット能力を付けて何とか正のパワーを得てカードとなるところを、クルトだけは「光文明→ちょっとパワーが高い」という世界観設定を利用して能力なしで正のパワーを達成したということ。

1コストだけ特別扱いされているのは納得もできる。そうポンポンクリーチャーを並べられても困るということだろう。 $N$ コスト支払える状態でどれだけ場に並ぶかを計算すると、単純に $\frac N 1$ が $\frac N 2$ より倍大きいという話。実際、1コストパワー1000能力なしのクリーチャーはいまだ存在しないらしい。またそれに関連して、凶戦士ブレイズ・クローという1コストパワー1000、能力で毎ターン攻撃しなければならないクリーチャーという、僕ですら見知った太古のカードが現役である（つまり完全上位互換が存在しない）ことはなかなか感慨深い。

二度寝ができなそうだったので布団から身を起こし、大学院の入学手続きをすることにした。まず期限が迫っている学生証用の写真を送信。次に書類を作成する。リストを確認しつつ必要な書類に記入を行っていると、2点、お金の振り込みが必要なものを見つけた。入学料と保険料。前者だけだと思っていたので、見落として郵便局まで往復することにならなくてよかった。外出し、いったん学食で食事し床屋に寄った後、郵便局で振り込んで、ついでに郵送用の封筒を購入してきた。

帰宅して書類を完成させ、再度郵便局に行って速達で出した。この時書留である必要があるかわからず大変に心配したが、後から確認したところ指定されていたのは速達だけだったので一安心。郵便局から直接バイク屋に行って原付を点検のために預け、そこから徒歩でゲーセンに行った。

今日は夕食を挟み午後5時半から午後10時まで。眠気が強く閉店までいてもしょうがなさそうだった。目立った成果もない。14の99AJがいくつか増えたのと、先週木曜日に詰め切れなかった14+を1譜面AJしただけ。ツイートの文面はふざけているが実際はTECHNOPOLIS 2085という曲である。先週、見るのとやるのとでは大違いと言ったものの、何回かやったら出た。

Battlefield 2042 AJ pic.twitter.com/2KnIjPhRZS
— こたつがめ (@kotatsugame_t) 2022年3月8日

帰宅してしばらくTwitterを眺めた後、午前0時就寝。

03/09(水)

いつから起きていたのか定かではない。Chromeの閲覧履歴は午前11時半から始まっているが、その前にどのくらいYouTubeを眺めていたのかがわからない。

正午ちょっと前に布団から出て、ICPCチーム紹介ドキュメントのメイキング記事を書き始めた。手元に届いたらすぐ公開するくらいの気持ちでいたのに、実際には一切書き始められていないまま今日届いてしまった。ただ自分は早いほうだったようなので、まだ少し時間をおいてもタイミングは逃さないだろう。

午後6時までICPC横浜大会のチーム紹介ドキュメントを作成していた。これについては別にメイキング記事を書いて公開する予定だ。
週記（2022/02/28-2022/03/06） - kotatsugameの日記

午後3時くらいまで書いていた。なかなか進まず詰まってしまったので、別のやるべきことを行うことにした。まず、昨日預けた原付の点検が終わっているので取りにいかなければならない。次に、そろそろ期限が切れるパスポートを更新しなければならない。今日はこの2つをこなす。まず県庁でパスポート更新の申請を行い、帰りにバイク屋に寄るのがよいだろう。

県庁のパスポートセンターに行って居所申請をしようとしたら、特別な理由がない限り受け付けていないと言われてしまった。「案内サイトのどこにそのような記述がありますか？」みたいにしばらくゴネてみたものの、普通に「必ず申請できるものではありません」と書いてあって絶望。すごすご引き下がって、今度は富山県のパスポートセンターに電話して代理申請について聞いてみた。こちらは僕が6か月以内に受け取りに行くことも含めて問題なく行えそうだったので、必要な書類を聞いておいて、再度パスポートセンターに行って申請書＋委任状をもらい、またその近くの写真屋でパスポート用写真を撮ってきた。これらとパスポートを合わせて、近々仙台に来る親に渡せば間に合いそう。

県庁を出て、食事する店を探す。仙台レジャーランド一番町店に通っていたころ足を延ばしていた本屋（が入っている三越）は県庁にかなり近いらしい。ということで、そのすぐ近くにあるミスドに入ってドーナツを5個ばかり食べた。フレンチクルーラーは形が特徴的なだけだと思っていたが、中にクリームが入っていてかなりおいしかった。

そこから本屋に寄って、さらにバイク屋まで歩くことにした。本屋からレジャランもレジャランから青葉通一番町駅も何回も歩いた道だし、そこから地下鉄一駅くらい歩いても大して変わらないだろうと思ったのだ。しかし続けざまに歩き通すとなるとなかなかつらかった。歩いている途中にいろいろな食事処を見て、下のツイートのようなことを考えた。30分ほどかけてバイク屋にたどり着き、原付を受け取ってそれに乗って帰宅。帰宅ラッシュかと思っていたけど今日は道が空いていて助かった。

今日あんまり通ったことない道練り歩いて帰ってきたんだけど、知らない呑み屋に突撃したと思しきサラリーマン見て、家で死んでるかゲーセンで板しばいてるかの2択じゃなくてそういうところで飲み食いする幸せもあるんだろうなと思った
— こたつがめ (@kotatsugame_t) 2022年3月9日

「黄金の経験値　番外短編集」を読んだ。

https://ncode.syosetu.com/n9587gk/

ハーメルンを漁ったりYouTubeを眺めたりしているうちにかなり時間が経ってしまった。今日はSRMがあるらしいが、眠いので不参加を決め込む。午後10時半くらいに布団に入り、寝転がったままノーパソを開いて朝の続きでメイキング記事を書いていた。さすがに無理があったので筆は全然進まず、午前0時就寝。

03/10(木)

午前6時半起床。しばらくハーメルンを読んでから、どうせ二度寝はできないと見切りをつけて起き上がった。

チーム紹介ドキュメントのメイキング記事を書いた。午前中いっぱい使って仕上げた。夜に投稿すれば人目に付きやすいかなど考えていたが、今日の午前中にICPCから荷物が届いた人が結構多いように見受けられたので、もう投稿してしまうことにした。

kotatsugame.hatenablog.com

サムネイルの設定が大変だった。何も設定しないと、記事中で最初に使われた画像が設定される。一度その状態で投稿してしまって、慌てて下書きに戻して（別に戻す必要はなかったらしい）再度投稿した。すると記事一覧においてはちゃんと設定されているものの、ツイートに表示されるカードでは先ほどの間違ったサムネイルのままになってしまっている。調べたところ対処法が見つかった。以下の「Card validator」を使うと、ちゃんと現在のサムネイルが見えるようになる。キャッシュされていた、みたいな話だろうか？

https://cards-dev.twitter.com/validator

午後からはずっと日記を書いていた。集中があまり続かず、頻繁にYouTubeを見てしまっていた。月曜日から溜めてしまっていたので、今日までの分を書き終えたころには夕方になっていた。

すでに眠気が強い。布団に入って眠い目をこすりつつラノベを読んでいたが、1冊読了とまではいかず午後9時半に就寝。

03/11(金)

午前7時半に起床。食事して昨日の続きのラノベを読み始めた。残り少なかったこともあり、1時間ちょっとで読了。

「神々の権能を操りし者」2巻。主人公が特殊対策部隊というチームに入ったところから始まる。1巻は確か学校内での出来事だけだったので、序盤のちょっとしたざまあ描写を除けば全く新しい場所のスタートとなり、前巻の内容をほぼ覚えていなくても何とかなった。1巻を読んだ時の日記を読み返すと下のような疑問が残されていたが、確か主人公が持っている全部の能力を見せてしまったように思えたのが引っ掛かっていたはず。2巻において、主人公の能力は全然そんなものじゃなくてもっとぶっ飛んでいることが分かったので一安心。文章的には、主人公視点である地の文のノリがあまり好きになれない。

1巻から実力を周囲に知らしめていて、手っ取り早い満足感があった。しかし2巻以降はどういう展開になるのだろうか。
週記（2021/09/20-2021/09/26） - kotatsugameの日記

別のラノベを開いてしばらく読み進めた後、訪れた眠気に逆らわず再度就寝。午前11時から午後4時まで寝ていた。

少しパソコンを触った後外出。ゲーセンに行く。油そば屋に寄って食事しつつ、午後6時から午後11時前まで遊んだ。今日の成果は理論値が3譜面と14+のSSS+が2譜面。

Bad Apple!! feat.nomico (REDALiCE Remix) 理論値 pic.twitter.com/4gylCZxP0i
— こたつがめ (@kotatsugame_t) 2022年3月11日

序盤の跳ねリズムの勝率が低く、結構な回数の捨てゲーをしてしまった。そのうち道中でもポロポロ赤を出すようになってきて明らかに止め時ではあったのだが、エアーだったりラストのスライドの終点だったりで一落ちを出していたのでどうしても諦められず、何とか捻り出した。

立ち食い蕎麦屋で食事して帰宅、午後11時半からCF #777 div.2。記念すべき第777回ということで、これに間に合うよう閉店前にゲーセンを離脱してきたのだ。

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

Aは $n\bmod 3$ で場合分けして1212...か2121...を出力する。Bは、「2x2マス内に1がちょうど3個存在する」ような箇所が存在することと答えがNOであることが同値であることに気づいてすぐ解けた。まず $(\Rightarrow)$ については、2x2マスの中で0を含まないように2種類長方形を作ったとき、それを適当に拡大して得られるniceな長方形が包含関係になく、また交差することからわかる。 $(\Leftarrow)$ については対偶を考える。0と1が隣接しているところを探し、そこから上のような2x2マスが存在しないように広げていくと、1の連結成分が必ず長方形になることからわかる。Cはギャグで、1x2か2x1を使って右下から塗っていけばよい。一番左上のマスは明らかにどうやっても黒くできないが、それ以外は今言った方法で対応できる。

Dは問題文がカス。先に本題以外の場合分けを説明する。 $x/d$ が $d$ で割り切れなければNOである。以降 $x=d^a\times y$ と分解する。ひとまず $\{d,\dots,d,dy\}$ という分解があるので、適当に組み替えてもう一種類を見つけられればYES、存在しなければNO。 $y$ が合成数ならそれをさらに分解すればよい。 $y=1$ なら $d$ を分解するしかなく、 $d$ が合成数であることに加えて $a\ge 3$ が必要である。

$y$ が素数の場合、こちらも $d$ が合成数であることと $a\ge 3$ が必要となる。ただ十分ではない。今度は逆に $d=y^b\times e$ と分解してみる。 $e\gt 1$ のとき、 $b\ge 1$ なら $\{d,d,dy\}\rightarrow\{de,dy^{b+1}\}$ と組み替えられ、 $b=0$ なら合成数 $e=d$ を適当に分割できるため、それぞれYESとなる。 $e=1$ のとき、 $d=y^b$ 、 $x=d^a\times y=y^{ab+1}$ とどちらも素数 $y$ のべき乗で表せる。 $b\ge 3$ ならば $\{y^b,y^b,y^{b+1}\}\rightarrow\{y^{b+\lfloor(b+1)/2\rfloor},y^{b+\lceil(b+1)/2\rceil}\}$ と組み替えることができる。 $d=y^b\ge 2$ と $d\ne y$ より $b\ne 0,1$ もわかるので、最後に $b=2$ の場合が残る。 $d=y^2$ 、 $x=y^{2a+1}$ である。

さて、ここで2つの分割が異なることを定義している文章「Two ways are different if the sets of numbers used are different.」が問題となる。「sets of numbers」とあるので、分割した後の数たちが「集合として」（＝重複を省いたとき）一致していれば同じ方法だとするんだな、と思った。このとき、すでに $\{y^2,\dots,y^2,y^3\}$ という分割があり $\{y^2,\dots,y^2\}$ という分割は不可能なので、 $\{y^3,\dots,y^3\}$ が可能かどうか、つまり $2a+1$ が $3$ で割り切れるかどうかで場合分けすることになる。しかしWA。40分くらい苦しんだ後、ふと「多重集合として」一致するかを見るようなコードを提出することを思いついた。この解釈の場合 $a\ge 4$ ならば $\{y^2,y^2,y^2\}\rightarrow\{y^3,y^3\}$ が許されてYESになる。これで出したら通った。

the sets of numbers used are differentって集合として一致しないことを言ってるんじゃないんか張り倒すぞ pic.twitter.com/2EtCq74U0P
— こたつがめ (@kotatsugame_t) 2022年3月11日

Dを通した後に上のツイートのようなclarを投げていたので、残り30分しかない。Eに進んだ。数列 $\{p_i\}$ が順列ではなくてびっくり。最初はループとそこに向かういくつかのパスに分解して、ループの中の数字はもともとループの中にあるとしてよいと思っていたが、最後のほうまで書いてから、パスから侵入してきた数字がループの中の数字を蹴り出す場合も普通にあることに気づいた。するとループの検出など面倒な操作を一切行わない解法が浮かび上がる。与えられた状態まで何ステップかかるかが一意に定まるので、それをもとにダブリングで各マスがどこに行くかを求めると、それぞれ入れてよい数の最小値が求まる。この条件に加えて、その最小値が同じマスたちのうちどれかには実際にその値が入っている、という状態であれば良いことがわかるので、先に後者の条件を満たした後前者の条件を満たすようsetなどで値を埋めていけばよい。これらはすべて先頭から貪欲に決められる。

ちょっと迷走し、Fに辿り着いた時点で残り5分。問題文を読んだぐらいで諦めた。システスは全部通って5完76位。D問題の問題文にはさすがに腹が立ったので、初めてコメントを書いた。しかし見返してみると、ただしょんぼりしているだけの人に見えるな。もうちょっとはっきりゴネておけばよかった。

https://codeforces.com/blog/entry/100739#comment-894976

布団に入ってラノベを1冊読了。「創成魔法の再現者」。初っ端から上下巻になっていて、1巻で話が一段落していない。基本的に主人公の能力で無双してはいるのだが、その下準備となる敵キャラに陥れられる描写がかなりえげつなくて辛かった。貴族階級の人間は生まれつき魔法を持っていて、爵位よりその強さだけで発言力などが決まってしまうという設定らしい。いろいろ考えさせられる話。今のところ敵の首魁となっている王子はこの魔法が強すぎてかなり無茶苦茶やっており、主人公たちが力で対抗する舞台を整えるだけでもかなり大変な目に遭っていた。

魔物の脅威があって、それを撃退する役目を負う代わりに様々に優遇されるのが貴族階級の人間であるということだから、魔法が強い人が偉いというのは理にかなっている。そのような常識を変えようとする主人公陣営にどのような正当性があるのか、というような話も出ていた。また魔法が強ければ偉いなら主人公も偉いはずだが、主人公は一度才能なしとして追放されていたもので、そこから戻ってきた前例がないため周囲の人間も強さを認めるに認められない状態になっていて、さらに苦しい。どうあがいても普通に手に入れた強さではないことが明らかなのだ。

さらに別のラノベを開いて読み進めた後、午前6時半就寝。

03/12(土)

午前10時半ごろ目を覚まし、うっかりスマホを触り始めてもう眠れないかと思ったのだが、何とか二度寝に成功した。次に午後0時半起床。食事してTUPC2021の観戦を始めた。

https://onlinejudge.u-aizu.ac.jp/beta/room.html#TUPC2021

TUPC2021を開催しました | puzzleknot 公式サイト

まず最初に言っておくと、僕は全体テスターとして参加しただけで1問も作っていない。全問にそれなりのACが出て、かつ全完が1チームもないという完璧なコンテスト設定だった。サークルのメンバーが強くなりすぎていて怖い。以下、コンテスト前に予想した難易度順に、各問題に対する感想を書いておこう。ACGIJKDEFBHである。実際のsolved数は、タイブレークを都合よく決めればACGIDJFKEBHの順だったので、編集距離的に考えれば外したのはDとFだけとかなりうまく評価できていたのではないか。

A - Unique Nickname。84AC。最初この問題は存在せず、C問題が一番簡単な問題として置かれていた。さすがにもうちょっと簡単な問題を置いてほしいと要望を付けたところ出てきた問題。急いで作ってもらった問題とは思えないほどTUPCらしいものになっていて感動した。

C - Extreme Balance。64AC。実はジェンガの進行を表現しているということで、そういう論文を探すと定数時間での判定法が見つかったそうだ。ただ、あまりに単純すぎて実験エスパーでも容易に同じものが得られる一方、その証明は論文になるほど難しいようで、仕方なくこの制約でこの位置に置かれたという経緯があるらしい。

G - Tree Happiness。57AC。特に言うことなし。ここまでが簡単枠だと見ていた。

I - Range Totient Query。52AC。想定解はなかなか頭のいいことをしているが、ABC238-Gのユーザ解説のようなMoでも解ける。つい最近見たのでこの位置と予想。

https://atcoder.jp/contests/abc238/editorial/3377

J - WISWIS。33AC。少し面倒な行列累乗。

K - Autumn Triangle。13AC。式変形すればやることはすぐわかる。凸包だけ見ればよくて尺取りできる、という事実は少し考える必要があるのでこの位置に。もともと $N\le 3000$ だったので $\log$ をつけて大丈夫か少し怪しかったが、制約を調整したのでいい感じになったのではないだろうか。ただ単純な全探索が爆速過ぎて $O(N^3)$ と $O(N^2\log N)$ を区別できずPythonお断りになった上、普通にC++の $O(N^3)$ が通ってしまった。ここまでがテスター作業時にすぐ解法が分かった問題である。

D - ABS Pairs。45AC。これはエスパー含めた難易度予想で、証明をつけるのはそこそこ難しい。僕もテスター作業時未証明で通してしまった。操作順も答えさせるという話が出ていたようだったが、スペシャルジャッジの設定がわからず見送られてしまったという悲しい裏話がある。結果的には、エスパー含めた難易度で予想したはずなのに大きく外してしまった。

E - LEQ and XOR。13AC。解説のように $A_{N+1}$ を定義するのが頭良すぎ。僕は思いつけなかったのでかなり苦労したが、数日頭の中で寝かせた結果何とかゴリ押せた。普通のdpを書くと、同じ値が結構連続するとわかる。それらを圧縮すると $O(\log M)$ 個くらいになるので、その状態で行列累乗できるかと思ったものの、どの位置の値が一致するのかがバラバラだったので失敗。そもそもなぜそんなに同じ値が連続するか考えると光明が見えた。

例えば $M=5$ のとき、 $[0,M+1)=[0,6)=[0,4)\cup[4,6)$ と分割する。 $[0,4)$ は下2bitが自由に定められる数、 $[4,6)$ は下1bitが自由に定められる数とみなせ、 $[0,4)$ から1つ、 $[4,6)$ から1つ選んでそのXORを計算すると $[4,7)$ が2つずつ得られる。これは下2bitが自由に定められる数が $2^1$ 個ずつという意味である。一般化すると、下 $n$ bitが自由に定められる数と下 $m$ bitが自由に定められる数のXORは下 $\max(n,m)$ bitが自由に定められる数 $2^{\min(n,m)}$ 個ずつである、と書ける。これを利用して頑張ると、最終的には解説のような式の再帰をループにしたようなものが得られる。

F - Gift Exchange。28AC。初見では二乗のところが一乗だったら無理だろと思って、二乗であることを用いる解法を探して迷走を始めてしまったが、NTTで解けることに気づいて戻ってこれた。それを元に二乗の式を展開すると、何もかもNTTで解ける形になって感動。ちょっと前まで $N\le 10^5$ でPythonお断りだったので、さすがにもうちょっと小さくしてもいいだろと思って制約を調整してもらった。多少筋力があれば通せる問題とはいえ思ったより解かれたなという印象。これも難易度予想を大きく外した問題。

B - Minimum Upper Sum。4AC。多分6時間くらいかかった。愚直dpを整理するといかにもCHTっぽい形になるが、そこからどう実装するのかが難しい。追加クエリも取得クエリも単調なので蟻本にあるdequeのCHTで通せるだろうとかなり試行錯誤して、なんとか通した。これについてはテスター解説を書いてある。LiChao Treeを書いたことがなくて、Undoが簡単にできるのを知らなかった。

B - Minimum Upper Sum.pdf のコピー - Google ドライブ

開始21分で解かれてひっくり返っていたら、既出だったらしい。まあシンプルな見た目だし仕方のないところはあるだろうか……。

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

H - Magical Shuffle。4AC。ボス問。5時間考えて想定解の方向に一歩も進めず、自力で解けなかった。そのくせコードは単純になるのでAGCっぽい最高の問題だと思っている。これも既出でないかだけが心配だった。

ラノベを1冊読了。「迷子になっていた幼女を助けたら、お隣に住む美少女留学生が家に遊びに来るようになった件について」。タイトルからわかる通りの半同棲ラブコメ。主人公もヒロインも怪しげな過去を抱えていそうではあるが、1巻の今は特に明かされず2人の馴れ初めを描くに留まっている。つまりそのうち否応なしに重い話が入るということで、ちょっとひるんでいる。またタイトルにもある「幼女」の行動が好きになれなかった。この子の強引な行動がなければ2人の関係が進展することもないとはいえ、強く咎められることもなくずっとわがまま放題なのにイライラしていた。もともと子供が好きではないというのもあるかもしれない。

しばらく日記を書いて、午後9時からABC243に出た。

AtCoder Beginner Contest 243 - AtCoder

Aは $V\lt A$ と $V\lt A+B$ を判定すればよいと思って書き始めつつ、サンプル3を見てひっくり返った。確かにどこにも $V\lt A+B+C$ のような制約はない。最短コードが自明な問題ではないので、いったんAWKで書いてお茶を濁した。BはRaku。どう書いたものかしばらく手元で試していたので問題なく通った。ここからC++。CはY座標でグループ分けした後X座標の昇順に見れば十分。Dはstackで操作を圧縮、ただしstackを使うと残った操作を前から順に行うのが難しいので慌ててdequeに書き換えた。

Eは難しい。とりあえずワーシャルフロイドを書いて、最短経路の候補にならないような辺は削除できる。問題は候補には挙がるものの別の辺複数本で再現できるような辺の検出である。適当に最小全域木を取ってみてもどうにもならないようだったので、改めて考えなおすことにした。すると、辺複数本で再現できるとしたとき、その中継点を全探索すればワーシャルフロイドで求めた距離行列から実際に再現可能かチェックできることに気づいた。

F問題はずっと包除原理を考えていたが、どうしても各 $1\le n\le N$ に対し、 $\binom{N}{n}$ 種類の「賞品 $n$ 個の $W$ の和を $K$ 乗したもの」の和が必要になる。これを計算するために、 $K$ 乗を展開した形でどの $W$ が何回出現するかで遷移していくdpを考えたところ、それを利用すれば直接的に問題が解けることに気づいた。30分くらいかかってしまった。

Gは簡単。 $X\le\sqrt[4]{9\times 10^{18}}$ までは愚直にdpができる。 $X\le\sqrt{9\times 10^{18}}$ までは、いま求めたdp配列の先頭 $\sqrt X$ 項の和になるので、事前に累積和を取っておけば定数時間で求まる。本題の $X\le 9\times 10^{18}$ の場合、 $1\le i\le\sqrt[4]{X}$ に対して $i=\left\lfloor\sqrt X'\right\rfloor$ となるような $1\le X'\le\sqrt X$ の個数分だけ「dp配列の先頭 $i$ 項の和」が答えに足されることになるので、 $i$ を全探索すれば $O\left(X^{1/4}\right)$ で解ける。

EFで時間を使いすぎて残り30分もなかったのに、Ex問題を見つつ順位表を確認するとまだ1ACも出ていなくて腰を抜かした。実際に問題文を読んでみると最小カットの数え上げみたいなとんでもないことが書かれていたので、早々に諦めてコードゴルフしていた。7完34位。

コードゴルフ。Aはdc。 $(V\bmod(A+B+C))-A$ と $(V\bmod(A+B+C))-A-B$ をそれぞれvコマンドに通して、出力に応じてスタックの深さを分ける方法。ただし今回、出力すべき文字の文字コードが70、77、84ということで、3連続の7の倍数になっている。実は先ほどの操作後のスタックサイズ（0、1、2のどれか）に10を足して7を掛けるとちょうど対応した文字コードになるので、この出力部の改善でかなり短くできた。Bはコンテスト中のRaku。さすがにもうちょっと何とかなるんじゃないの、という見た目をしているが、今のところどうしようもない。

CはRuby。Y座標でgroup_byした後チェックするというのんきなことをやっていたら、まとめてソートする方法で大幅に縮められた。そうでなくてもX座標は数値の大小だけが重要なので、to_iではなくhexが使えるという更新にも気づけず。DもRuby。LとRをそれぞれ0と1に置換しつつ読み込んで、文字列をスタックとして扱う。後ろから1文字切り離すのがchop!でできるということは他の人のコードを読んでいて気づいた。EはOctave。Fは手つかずで、GはRubyのメモ化再帰。2項ずつ進んでいくようにすると十分高速らしい。ただ平方根を計算する部分で普通に0.5乗すると精度の問題でWAになったため、bsearchを持ち出した。

布団に入ってしばらくハーメルンを読んでいたところ、僕とコードを共有した疑いでCodeChefからメールが来たという人をTLで観測した。慌てて自分の受信メールを調べると、プロモーションのところに入っていた。僕が関係するものでは5組くらいコード共有の疑いがかかっているらしい。一つ一つ確認してみると原因が分かった。 $O(1)$ 算数の問題でACLのmodintを貼ったのだが、このときコード全体のうちおよそ97%もの行がライブラリに由来するコードとなってしまい、結果同じくmodintを貼った人のコピペであると検出されてしまったようだ。異議を申し立てる……前に、メールに記載されているリンクから不正に関する取り決めだったりFAQだったりの文章を3つ読んだ。せっかく英語を読んだのでここに、特に今回のケースに関係する部分をまとめておこう。

CodeChef's Code of Conduct | CodeChef

よくある参加規約とほぼ同じに見える。今回関係するのは7番で、ライブラリの利用について。そもそもクレジット表記などがあることを期待されているらしいが、それがなかった場合にも一応救済は用意されていて、そのコードがコンテスト開始前に公開されていたことを自力で証明すればよいらしい。

Plagiarism FAQs - Google ドキュメント

一番上のものが関係する。MOSSというのがコピペコードを検出するシステムの名前で、それによって誤った検出がされてしまった場合の話が書いてある。対処法はCode of Conductにあるものと同じ。それより下のほうはそこそこ面白くて、今のケース以外でコードを共有していたらもう助かりませんよということが、複数の言い訳にそれぞれ対応して執拗に書いてある。

The Cheating Cases Saga | CodeChef

これはポエムなので読む必要なし。運営も大変だということだけが伝わってくる文章になっている。

ということで、結局僕のコードがACLに由来すること、またACLがコンテスト前に利用可能だったライブラリであることを証明すればよい。英作文してメールを送った。かなり疲れた。~~（仮にも世界ランク40位なんだから何か優遇措置はないだろうか……）~~

Hello CodeChef.
This is kotatsugame. I request you to do a manual check because of MOSS's false positive.Nearly 97% of my solution is come from ACL (AtCoder Library), which is a third party library with CC0 license. The link is here.https://t.co/ujGbwPspQy
— こたつがめ (@kotatsugame_t) 2022年3月12日

ハーメルンを読み続け、午前5時半就寝。

03/13(日)

午前11時起床。今日はコンテストがないので自由。

かなり眠かったはずなのにうっかりハーメルンを読み始め、二度寝しよう二度寝しようと思いながらもずるずる夜まで読み続けていた。午後8時半に1作読了。「強めのモブウマ娘になったのに、相手は全世代だった。」。

syosetu.org

面白かった。主人公はあくまでモブウマ娘ということで、まあ勝てない。勝てないといってもそこはお話の都合上かなりいい成績を残してはいるのだが、ほかのウマ娘ハーメルンの主人公に比べると、という話。ほかの強い主人公を据えた作品でも、レースに勝利することでほかのウマ娘の夢をへし折っているということはいくらか言及されてはいたものの、それを「へし折られる側」から読むと苦しいものがあった。普段主人公最強モノしか読まないので、余計に。幸い主人公は一回の敗北で落ち込んだりする様子がほぼなかったので、その点は安心して読めた。

作者の活動報告からあとがきを読んで、さらにこの人のお気に入り小説から1つ見繕って読み始めた。午後10時半に読了。「秒読みの契約　～あなたに三つの冠を～」。天才トレーナー主人公は良いもののちょっと不穏なところでエタっていて厳しい。

syosetu.org

結局二度寝できないまま夜になったので起き上がった。昨日のABC243-Eが縮められていたので縮め返した。辺の重みを $-\varepsilon$ しておくと判定が簡単になるというやつ。そのあとは未明まで日記を書いていた。未明と書いた部分は最初夜更けと表現しようとしていたが、調べたらもっと早い時間帯を指すことが分かって慌てて別の表現を探した。

2022-03-10

ICPC2021チーム紹介ドキュメントのメイキング

gist.github.com

https://ideone.com/d43uV5

参考：昨年の記事

kotatsugame.hatenablog.com

今回もアスキーアートQuineを作ってみました。

1. AAを用意する

昨年の経験を活かします。というのも、実行可能なAAかつQuineなんてすごいに決まってるだろという感覚があって、もっとドッカンドッカン話題になってくれるものと期待しながら作っていたのですが、昨年はエゴサしてもほぼほぼ反応がなかったのがちょっとショックだったのでした。そもそもすごくない可能性がありますが、それを置いておくにしてもまた別の理由が考えられます。つまり、昨年のAAは見にくかったのです。

理由は簡単で、チーム紹介ドキュメントの制約である1行75文字が結構厳しく、その結果AAを小さくせざるを得なくなったからです。AAの見にくさに加えて、そもそもコードをAAの形に収めることも難しくなったので、今年はとりあえずイラストをAAにするのは止めました。文字を使います。2行に「Aobayama_」と「dropout」を書くつもりでしたが、これも1行75文字の制約が厳しいので、ただ3文字「青葉山」と書くことにしました。

エクセル方眼紙を使ってAAを作成します。対称性を保つためには1文字の幅が偶数であると都合がいいので、1文字あたり24マス使うことにしました。また縦線を4マス幅、横線を2マス幅にすることにしました。適当なフォントを参考にしつつマス目を塗っていたのですが、このときフォントの縦横比が2対1であることをすっかり忘れて、1対1で作ったマス目を使ってしまったので、正しい縦横比に直すとちょっと縦長になってしまいました。もともと横長に作りすぎたかと思っていたこともあり、結果的にうまくいきました。

2. ランレングス圧縮する

この部分のアイディアは昨年と同じです。空白文字と非空白文字がそれぞれ何連続で出現するか数えて、空白文字から交互に配置した数列を作ると、それを元にAAが復元できるというやつです。数列を文字コードに埋め込んで、文字列として保持するという部分も一緒です。昨年は1行ごとに圧縮していましたが、別に全部まとめて圧縮しても問題ないので、今回はそのようにしています。

うっかり全部完成してから無駄な空白の存在に気付き、修正したところデータ部分の文字列が短くなりました。ただ一度完成したコードを弄るのはさすがに気力が尽きていたので、短くなった分適当な文字を入れてごまかすことにしました。下から5行くらいがそのコードです。文字コード65からいくら増えるかで数列を表現しているので、インデックスの偶奇さえそろっていれば間に文字コード65以下の文字をいくら入れても問題ないのです。

all=gets(nil).gsub(/\n/,"")
a=[]
t=" #"
c=0
all.each_char{|s|
  t[a.size%2]==s ? c+=1 : (a<<c;c=1)
}
a<<c
A=65
puts"WARNING"if a.include?(92-A)
ans=a.map{|e|(e+A).chr}.join
while ans.size<296
  i=rand(0..ans.size)
  ans[i,0]=[0,1].map{[33,35,36,38,43,47,*48..57,60,61,62,63,64,65].sample.chr}.join
end
puts ans

書いているときに気づきましたが、文字コード64を基準にしたほうが素直でした。

3. コードを書く

まず使用するプログラミング言語についてですが、C言語を使うことにしました。RubyによるアスキーアートQuineは昨年のやり方さえ知っていればめちゃくちゃ簡単で、しかもバラバラになった文字列を最後にjoinするという手法から、出来上がったコードにはあまりプログラムっぽさがありません。C言語を使えばもうちょっと難しく、またいかにもプログラムという見た目になることが期待できます。C言語によるQuineの作り方も「あなたの知らない超絶技巧プログラミングの世界」という本に載っています。具体的には3-3-3項（p.127）の、マクロを使う方法を参考にしました。

https://www.amazon.co.jp/o/ASIN/4774176435/gihyojp-22

コードの解説をする前に、いったん全体を見やすく整えたものを示します。ここからコードの意味をほぼ変えずに変形したものがQuineになっています。処理系定義や未定義動作がいろいろあるかもしれませんが、このあたり動けばいいだろという精神でやっているのであまり気にしないでください。本当は-Wallオプションをつけてコンパイルしても警告が出ないようなものを目指していたのですが、そもそも#include<stdio.h>を書くのが難しかったので諦めました。

char a[]="圧縮された文字列";
b=1,c,d,e,f;
#define Q(k)char*l=#k,m[202203];k
Q(
    main(){
        sprintf(m,"...",l);
        for(;d=a[c];c++)for(;--d>='A';b++%71!=0||puts("")){
            for(;m[e]==' ';)e++;
            putchar(...);
        }
    }
)

マクロQがQuineの重要なポイントで、本からコードを引き写してきた部分です。引数にそのままコードが書かれていますが、マクロの展開時、この引数はまず文字列化演算子#を用いて文字列にされ、次に直接コードとして解釈されるようになります。こうして作った文字列に適切な加工を施し、Quineとして出力すべきものを作り出すということです。同じコードを2回書かなくてよいという点で、今回のようなコード長に制限がある状態で有利だと考え採用しました。マクロ定義の上2行も引数に含めようと思えば含められますが、AAにした状態でdefineという6文字が連続している必要があり、その前も意味のあるコードで埋めるために外に出しました。

全体的な注意点として、空白文字の扱いに気を付ける必要があります。文字列化演算子は強力で、特殊な意味を持つ文字はエスケープしてくれますが、それとは別にマクロという性質上改行を含む連続した空白文字が1つのスペースに置き換えられます。そのため、そのまま出力するとAAの空白が中途半端に影響し、謎に穴が開いたボロボロのコードが出来上がってしまいます。このコードでいえば、char*l=#kの部分で穴あきの文字列が生成されます。sprintf(m,"...",l)で出力すべき文字列を構築した際にもその穴は引き継がれ、さらにフォーマット文字列に入り込んだ空白も混入します。

出力前にfor(;m[e]==' ';)e++;とすることでその穴を読み飛ばしていますが、代わりにsprintfで構築する文字列に意味を持つ空白文字が存在しないようにする必要が出てきました。そのような空白文字は、インデントを無視すれば、何か所かの改行とchar a[]=、#define Q(k)、m[e]==' 'の3つです。順に対処していきましょう。

まず改行については、使用しない変数の宣言を増やすことでAAに埋め込んだ時の位置を調整しました。配列長がm[202203]のように意味深な数字になっているのもその一環です。AA化したコードの12、13行目が該当します。次にchar a[]=は、たまたま最初からAAに埋め込んだ時に勝手に区切れてくれます。#define Q(k)はどうしようもないですが、/**/とコメントを書いておくとその部分がコンパイル時に空白文字とされる仕様を使い、#define/**/Q(k)とすることで回避できます。最後のm[e]==' 'は簡単で、文字リテラルの代わりに直接文字コードを書いておけばよいです。

それ以外の部分を順に見ていきましょう。まず1行目に、先ほどランレングス圧縮して出来上がった文字列を埋め込んでいます。間に何も書かず並べられた文字列リテラルは連結されるという仕様があるので、適切に"で囲むことでこの部分は好き放題分割することができます。2行目は使用する変数です。型がありませんが、この場合int型だと解釈されます。3行目は先ほど解説したマクロです。char*lがコードのデータになり、これに加工を施した後の文字列を保存する用途でchar m[]も宣言しています。

マクロの引数に入ります。6行目で出力すべき文字列を構築し、7行目で1文字ずつ出力するためのループを回します。AAを圧縮した文字列を先頭から見て、その文字コードから'A'を引いた回数だけ文字を出力します。さらに出力した文字数をカウントして、71文字に1回改行を出力します。8行目は先ほど説明した通り、空白文字を読み飛ばす部分です。

9行目で実際に文字を出力します。...で省略した部分に三項演算子を詰め込み、いろいろ場合分けを施しています。長いので下に抜き出しておきました。

c%2==1?f==2?f=1,'"':f==5&&b%71==0?'\\':f==1&&(d=='A'||b%71==0)?f=2,'"':(f=m[e]!='"'?f:f<1?1:f+2,m[e++]):' '

変数cの偶奇によって、出力する文字が空白文字か非空白文字か決まります。ここで非空白文字を出力すると分かったからと言って、すぐさまm[e++]を出力してはいけません。更なる場合分けがあります。まずコード冒頭の圧縮された文字列部分について、AAに変換する際好き放題分割できたのは適切に"で囲んでいたからなので、これを再現する必要があります。さらにsprintfのフォーマット文字列はどうしても2行以上にわたるため、改行の直前にエスケープ文字を入れる必要があります（~~よく考えればここも"で分割してよかったですね~~←そうすると分割に使った"が出力の変な位置に残ってしまいます）。

これらの場合分けを処理するために、今出力しようとしている文字が文字列リテラルの内部なのかそうでないのかを知る必要があります。これは変数fで管理していて、f=m[e]!='"'?f:f<1?1:f+2の部分で状態を更新しています。今見るとさすがにもうちょっと単純なやり方があったかと思いますが、場当たり的に書いていたのでこうなってしまいました。f==1の場合は圧縮された文字列内で、f==5の場合はフォーマット文字列内です。またちょっとした影響として、フォーマット文字列の文字列リテラル自体に直接"が出現すると嬉しくないので、この部分は%cにしてsprintfで埋め込むようにしました。

fを利用した場合分けを行います。改行の直前であることはb%71==0で、空白文字の直前であることはd=='A'でわかります。これらを適切に組み合わせて条件を作り、合致した場合は出力すべき文字を直接埋め込みます。文字列リテラルを分割する"を出力した際は、次の非空白文字も"にする必要があるので、これまたフラグ管理にfを使いf==2とf==1を行き来しています。

以上でひとまず完成です。sprintfのフォーマット文字列は、出来上がったコード全体を再現するように文字列aやlを埋め込むだけなので省略します。

4. AAにする

コードに細かい調整を施し、AAとして仕上げます。すでに動くコードが手に入っているので、それを実行したときの出力を見つつ調整していく感じでした。上から手を入れていきます。

まず無意味な変数を増やして、#defineが行頭に連続して現れるようにします。またこの時増やした変数のいくつかは適切な値で初期化しておいて、文字リテラルの代わりに使います。マクロ名がQQQに伸びているのは、この後との兼ね合いです。

          char                a[]=    "KE"                "QE"         

                                （中略）

    ">9";b=1,c,d,e,f      ,g=+                   34,h     =66,     i,j;
    #define/**/QQQ(k      )char*l=#k,m[202203]   ,n,o     ,p,*     q;k;

以降はマクロの引数です。この部分も後から直接コードとして評価されるので、sprintfなりputcharなりのキーワードが分割されないようにしなくてはなりません。幸い最初からかなりうまくいっていたので、数値リテラルに+を前置するとか、演算子&&を&に置き換えるとか、そういう小手先のテクニックだけでコードの形を大きく変えることなく実現することができました。

    QQQ(        main      (){for(sprintf(m,"ch   ara[     ]=%c     %s%\
    c;b=1,c,d,e,f,g=              +34,           h=66     ,i,j     ;#d\
    efine/**/QQQ(k)c     har*l=#k,m[%d],n,o,p,*  q;k;     QQQ(     %s)\
    ",g,        a,g,     11*91*202+1,l);d=a[c];  c++)     for(     ;d--

2つ目のfor文の途中までを切り出しました。mainをこの位置に置くためにマクロ名をQQQにしたということです。sprintfをfor文の第1項に入れましたが、ただの好みです。フォーマット文字列の内容は、確かに先ほど増やした変数まで再現するようなものになっています。配列長の202203という数値リテラルが2回も出現するのはあからさまな気がしたので、11*91*202+1として隠しています。

残りの部分はかなりバラバラになってしまいましたが、幸い三項演算子を連打する部分は連続しているべき文字が少なかったので何とかなりました。

    >=h;b++%71||puts          ("")){for(;+       32==     m[e]     ;)0>
    e++;putchar(c%2?         f==2 ?f=1 ,g:f      ==5&     b%71     <=+0
    ?+92        :f==        1&(d  <h|b  %71<     1)?f     =2,g     :(f=
    m[e]        -g?f       :f<1   ?1:f   +2,m    [e++     ]):+     32);

まだ2行ほど残っています。この部分を;なりで埋めてしまうことも可能ですが、それでは面白くありません。ここは昨年同様、Aobayama_dropoutやTohoku_Universityという文字列を埋め込むことにしましょう。

    }int    Aobayama      ;for    (;b<    -h;)   for(;f-->c+e*f;)d+++d;
    char    _dropout     ;q<&     p+d;     char  **Tohoku_University;})

かなりうまくいきました。特に「青」の跳ねの部分を8文字＋8文字でAAにしたのは我ながら天才的でした。右上のあたりをどう埋めようか迷って、実行されることのないかなり謎な式を書いてしまいましたが、それ以外特に思いつかなかった僕の精一杯です。

5. 完成！

見える！見えるぞ！

2022-03-07

週記（2022/02/28-2022/03/06）

02/28(月)

先週は土日分の日記を溜めていたくせに昼までずっとなろうを読んでいたため、週記の投稿が昼過ぎになってしまった。深夜にCodeChefがあるので徹夜は避けたい。今日はインターン先定例会の直前30分にも別のミーティングが予定されているので、さらに睡眠時間が圧迫されている。午後1時に布団に入り、正直ここまで来たら変わらんだろうと思ってしばらくなろうを読んで、午後1時半に就寝。このとき部屋の電気をつけっぱなしにしてみたが、効果のほどは謎。

午後3時に一旦目覚ましで意識を取り戻し、そこから二度寝で30分追加して午後3時半に起床できた。先ほども書いたように午後4時からミーティングを1つ、デプロイに関する作業手順の話を聞いた。次に定例会。先週の進捗はデプロイの話になる。勉強会まで含め、今週も平穏無事に終わった。毎週の進捗がほぼないので、何か想定外のことが起こりようがない、というのが正しいかもしれない。

ABC241-Gが縮んでいた。3項演算子の2項目と3項目の型を揃える（これはあまり正確な言い方ではないかもしれない）ため、数値型を得るためにわざわざ定数を置いていたところがあった。しかしそのようなことをしなくても、このコードでinsertメソッドの返り値はポインタなので、それの指す数値を参照してやればよかったらしい。setのinsertの返り値がポインタとinsertに成功したかどうかのフラグのpairである一方、multisetはポインタのみであるらしい。言われてみれば納得できる仕様である。

atcoder.jp

しばらくなろうを読んでから、CodeChefの前に仮眠を取ろうと思って午後8時半に寝た。

03/01(火)

02/28 午後11時に起きた記憶がある。もう少し寝ていてもいいだろうと思って15分後に目覚ましをかけ二度寝したところ、うっかり爆睡してしまって、次に起きたのは午前2時だった。CodeChefを逃したかと少しがっかり。しかしコンテストサイトを見に行くといつの間にか1日延期されていて、かなり儲けものという気持ちになった。

そこから、時たまYouTube shortsやPixiv小説に浮気しながらも午後1時までずっとなろうを読んでいた。二度寝に失敗し続けていた。昼になったので学食に行って食事し、予約していたラノベを受け取って帰ってきた。毎月25日くらいに出るラノベと1日に出るラノベは、僕が注目しているレーベルということもあっていつもそれなりの冊数を買う。02/25と03/01の間がいつもよりかなり短かったため間で受け取りに行くことができず、今日は11冊買うことになった。

会計を担当した店員さんがバーコードリーダーに本を近づける度、つり銭トレーに貼られているコーティングされたPOPに本の天の部分が突き刺さっていて、さすがに血の気が引いた。急いでトレーを引き離した。実は生協で買った本はそれなりの確率で帯が曲がっていたり、破れていたり、角が潰れていたりする。これらについては輸送時の問題ということも考えられるけど、そこからさらに店頭で傷を付けられるとげんなりしてしまう。細かいことを言えば、本をまとめている輪ゴムを外すときに帯のほうに引っ張るのは避けてほしいし、本を台の上を滑らせて移動させるのも止めてほしい。ただ向こうも本を専門に取り扱っているわけではないし、無意識でそういう扱いをする人間に細かく注文を付けても実行は難しいだろうという感覚があるので、一言カードでクレームを入れるまでには至っていない。

現在支払っているNHKの受信料は、学生ということで家族割引が適用されている。次の4月からそれが終了してしまうというハガキが来たので、続けて適用してもらうための手続きが必要となった。これは残念ながらネット上では行えないようで、コールセンターに電話を掛けた。平日昼間とはいえつながるまで10分程度の待ち時間があり、事情を説明すると書類を送ってもらえることになった。こういう作業をすると改めて受信料の無為さを意識することになる。何もかもスマホに使いもしないワンセグ機能がついているのが悪いので、次買うときはついていないものを選ぶようにしよう。受信料の支払い義務を回避するためにそういう機種が増えているという話は耳にしている。

2月が終わったので、2月分の読書記録をまとめてツイートした。先月はハーメルンとなろうに時間を吸い取られたタイプの月だった。

2月の集計
買った：18冊
読んだ：10冊
積読：+8冊
積読（累積）：-3冊
— こたつがめ (@kotatsugame_t) 2022年3月1日

4年後期に取った講義のうち、大学院の講義の先行履修については4月にならないと成績が出ないらしい。それ以外はすでに出そろっており、また先行履修も真に何もしなかったのでどうせDか履修放棄扱いだろうと考え、成績報告のツイートを行った。これで1つのリプライツリーに僕の4年間の軌跡を残すことができたことになる。なかなか感慨深い。いろいろ再履修してきたけれど、結局のところ講義にちゃんと取り組むのが単位取得の必要十分条件だったように思う。ちゃんと取り組むというのは、出席を求める講義なら出席する、課題提出を求める講義ならちゃんと提出する、ということ。

単位取得状況 14/16
単位取得率 88%
大学生活、初見クリアです pic.twitter.com/INjYTG0C64
— こたつがめ (@kotatsugame_t) 2022年3月1日

1年：23/57（40%）
2年：61/67（91%）
3年：40/42（95%）
4年：20/22（91%）
合計：144/188（77%）
— こたつがめ (@kotatsugame_t) 2022年3月1日

午後4時から1時間ほど1on1を行い、その前後30分程度でインターンのコーディングを行った。昨日のミーティングで聞いたデプロイのための作業をこなしていく報告のような感じ。正直よくわからない部分があったので少し介護してもらいながら進めていた。

しばらくなろうを読んで、午後6時半に就寝。CodeChefに向けた仮眠である。

03/02(水)

03/01 午後11時起床。午後11時半からFeburary Lunchtime 2022 div.1に出た。

https://www.codechef.com/LTIME105A

MAGNETSORTは極がすべて等しい場合を除けば2手で必ずソートできるので、1手でソートできるかチェックすることになる。動かさなければならない要素の両端を見つけて、その両側に極が異なる2要素が存在するかをチェックすればよい。MAGICMODは解けなかった。1時間半ほど粘って適当に候補を絞り試すコードを提出したが、TLEどころかWAも出てしまい絶望して次の問題に進んだ。

VISEMALLは0と1が前後半で完全に分かれていなければどこからでもループできて、完全に分かれている場合は後半の要素の先頭からスタートした場合のみ前半の要素の末尾まで一筆書きできる。隣接する要素が異なるインデックスをsetやBITで管理して実装した。COOKPERMは、まず $A$ 、 $B$ をそれぞれ置換と見てループのサイズを求める。 $A$ で長さ $a$ 、 $B$ で長さ $b$ のループに属する要素たち $ab$ 個は、実験すると $\gcd(a,b)$ 個のループに分解されるので、これらをソートするためには $ab-\gcd(a,b)$ 回の操作が必要である。この値をすべての組 $(a,b)$ に対して求める。 $a$ 、 $b$ の種類数がそれぞれ $O(\sqrt N)$ 個しかないので、頻度を数えておけば全探索できる。

PERMXORは謎。まず $\bigoplus_{i=1}^N i$ 、つまり $N$ または $N\oplus 1$ で立っているbitはそれぞれどこかのペアでも立っていなければならない。それ以外はできるだけ $(2a,2a+1)$ のようなペアを作りたい。そのようなペアをできるだけ残しつつ $N$ で立っているbitを1つずつ順番に消していこうと思い、 $N$ 以下の最大の2べきを $2^b$ として $(N-2^b,N)$ というペアを作り $N\leftarrow (N-2^b)\oplus 1$ と更新するような手順を繰り返したら通った。これで $N=2^b$ となった場合は $(1,N)$ というペアを作る必要があるが、それ以外は確かに1bitずつ消していけているし、 $1$ 、 $N$ 以外に使う要素は全部 $(2a,2a+1)$ のようなペアを解体した形になっている。

4完41位で2762→2634(-128)。人生終了。MAGICMODは $\sum_i A_i-\sum_i i$ を割り切るような $X$ しか候補にならないので、全探索できるらしい。天才すぎる。この問題は列を好き勝手に並び替えられるという点で非常に自由度が高い操作を行うので、その並び替えで弄れないもの、すなわち総和に着目するべきだった、と言える。別に初めて見るようなタイプでもないものの、ドハマりしてしまった。

3月ぶんの新刊ラノベを注文した。17冊。新刊チェックについては、2月の中旬にラノベを注文したときから更新がなかった。そのときは以下のような理由で3月発売のラノベを予約していなかったが、大学生協の3月の営業時間が公開されて昼間だけとは言え普通に営業してくれることが分かったので安心して注文できた。

ラノベの新刊チェックと予約をした。とりあえず03/01発売までの19冊。3月に入ってからは大学生協の営業時間がどのようになるのかわからないし、自分の帰省がいつになるかも決まっていないので、確実に受け取れそうな発売日のラノベだけ予約したということ。
週記（2022/02/07-2022/02/13） - kotatsugameの日記

なろうを読みつつテスター作業をした。ふと開いてみたvalidatorに間違いがあって冷や汗が出た。ところで、最近のテスター作業では問題文や解説の文章表現にもいろいろ口を出している。曖昧な表現を厳密なものにするだけにとどまらず、単に文章として読んだときに違和感を得るものも結構遠慮なく書き直している。一応、そういう文章は他の人の創作物であるという認識だから元の表現を尊重しようとは考えているものの、実際書いてみるとどうしても自分の好みが入る。そこまで行くとちょっと微妙な気がしてきているが、伊達にたくさん問題を解いているわけではないのだから、自分の感覚は正しいだろうと信じてそのような修正を行っている。独り善がりな行為に終わらないことを願う。

昼過ぎ布団に入り、さらに1時間ほどなろうを読んでから寝た。午後1時半だった。

03/03(木)

03/02 午後10時半起床。なろうを読んだりYouTubeを見たりしていた。

「ダンダス」というYouTuberがいる。ちょっと前に音割れASMRでバズっていた。他の動画も勢いがあって面白く、いくつか眺めていた。特に好きなものを貼っておく。

ASMR動画を撮ったけど
音量設定間違えてとんでもない動画になった。

フル動画→ https://t.co/m18Gx8o4jj pic.twitter.com/X0aDQ4s38i
— ダンダス (@Dandas315) 2022年1月17日

www.youtube.com

午前4時半に再度寝て、次に午前8時に目を覚ました。YouTubeを開くと「科学の力使いまくって隠居生活」シリーズに更新が来ていたので、視聴した。さらになろうを読んで午前11時半ごろに布団から出た。

www.youtube.com

午後6時までICPC横浜大会のチーム紹介ドキュメントを作成していた。これについては別にメイキング記事を書いて公開する予定だ。昨年のものよりパワーアップしたと自負しているので、ぜひ探して見てほしい。参考までに、昨年のもののメイキング記事はこれだ。

kotatsugame.hatenablog.com

2022/03/10追記：公開した。

kotatsugame.hatenablog.com

自転車を出して外出。まず夕食としてラーメンを食べた。最近TLで故・仙台レジャーランド一番町店の近くに新しいゲーセンができたような話を聞いたのでちょっと探してみたが、見つからず、結局いつものセガ仙台で閉店まで5時間ほどチュウニズムをプレイした。アプデの日だったため待ちがいて、最初1時間ほどは交代しつつのプレイだった。

今日はアプデで追加・通常開放された譜面を埋めるだけで終わり、とはいえ好みの曲だったりちょうどよい難易度だったりしてかなり楽しめた。成果としては追加された14を5つ（全部）AJ、14+を2つAJ、15を2つ（全部）SS。プラチナポゼッションは保たれた。14+について、妖々跋扈は定数14.5と旧基準では13なのでそれほど難しくなかった一方、Elemental Ethnicはさすが旧基準で13+といったところか、単純な譜面に見えたもののかなり苦労させられた。どんどん癖がついて絶望したが何とか捻り出せた。TECHNOPOLIS 2085は譜面動画を何度も見たので余裕だと思っていたはずが、見るのとやるのとでは大違いということで終盤の難しさを思い知った。

妖々跋扈AJ！！！Demetoriかっこよすぎ！！！！！ pic.twitter.com/o1tvGNYyGp
— こたつがめ (@kotatsugame_t) 2022年3月3日

Elemental Ethnic AJ pic.twitter.com/z8SD3QySba
— こたつがめ (@kotatsugame_t) 2022年3月3日

どこが難しい年と思っていたけど見るのとやるのとでは大違い pic.twitter.com/r9Y0Fuc9Ax
— こたつがめ (@kotatsugame_t) 2022年3月3日

立ち食い蕎麦を食べて帰宅。しばらく日記を書いて、午前4時半就寝。

03/04(金)

午前11時半くらいに一瞬起きていた形跡がある。その後またすぐ寝て、次に午後4時起床。東北大学から卒業判定についてのお知らせが来ていて、無事卒業が確定した。別紙学生とあるが、その別紙に自分の学籍番号があったということ。

【理学部】卒業判定について

４年次学生　各位

　　　　　卒業判定について

このことについて，別紙学生は，令和４年３月４日開催の教授会において卒業が承認されましたので，お知らせします。
— こたつがめ (@kotatsugame_t) 2022年3月4日

布団でずっとなろうを読んでいて、午後7時半ごろにまた寝た。次に午後11時に起床。30分後からのCF div.2は、なろうを読むのが止められず見送った。

生活リズムが乱れているので、週末のコンテスト予定を確認しておこうと思ってチェックしていたら、日曜日にOpenCupがあることに気づいた。先週以下のようなことを書いたが、この5月というのは3月の間違いだった。Mar（ch）とMayを取り違えたらしい。

今日は久しぶりのOpenCup……と思ったら、いつの間にか5月に延期されていた。
週記（2022/02/21-2022/02/27） - kotatsugameの日記

そのままずっとなろうを読み続け、午前4時就寝。

03/05(土)

午前7時半起床。なろうを読んだりYouTubeを見たりしていた。

今は「flat-工房」というデュエマを主に扱うYouTuberの動画にハマっている。ありえないくらいテンポがよくて、高速で繰り出される暴言もやたらリズムに乗っていて耳に残る。3分程度の動画をポコポコ出すスタイルのようだけど、ある一定のテーマで作られた動画をまとめたものも投稿されていて、そちらは20分以上あるにも関わらず気づいたら終わっているくらい引き込まれてしまった。もともとが3分だからほぼ無編集でつなぎ合わせるだけでも十分見られる動画になり、最初から最後まで延々高速トークが聞ける。特に好みだったものを貼っておこう。

www.youtube.com

「『バトルゾーンにある自分のクリーチャーを、自分のマナゾーンにあるかのようにタップしてもよい。』と書かれていますが、そんなこといいわけがありません」で説明が放棄されているが、それだけぶっ壊れたカードだったということだろう。どうぶっ壊れているのかについては、このカードに巻き込まれて殿堂入りした他のカードを解説する動画のほうで説明されていた。通常、クリーチャーのコストをいくら軽減しても、文明を支払うために1未満にはならないようカードの効果で定められている。ところがこのとき、出したカードが新たにマナとして扱えることで、1コストでマナ+1、つまり疑似的に0コストでクリーチャーを召喚できるのがヤバいらしい。これでクリーチャーを大量に展開する戦略が猛威を奮ったそうだ。

マナコストを支払うためタップしているので、1ターン待ってから殴るのかななど思っていたが、それですら悠長すぎるらしい。実際に使われた勝ち方としては、他のカードと組み合わせてループすることで何らかのクリーチャーを無限回召喚して、その効果で相手の山札を削ってライブラリーアウトで勝利するというものがあるようだ。

なろうを読み続けて、午後3時半くらいに再度就寝。午後7時に起床。またなろうを読んで、午後9時からABC242に出た。

AtCoder Beginner Contest 242 - AtCoder

AはAWKで書いた。フィールド番号を間違えてWA、しかもページの反応が遅くて提出ボタンを2連打してしまったらしく2ペナついた。BはRakuで書いたらTLEしてしまい、BashでAC。このあたりはジャッジが詰まっていたので、とりあえず両方投げておいてよかったという感じ。以降はC++。Cはdp。Dは非常に難しい。実験すると、 $t$ としては $\bmod 3$ が等しく60をギリギリ超える値まで減らして問題ないことが分かったので、そうした後に $t$ 回のループを回して答えを求めた。Eはどこで辞書順が確定するかを全探索。

Fが合わなくて1時間くらい苦しんでいた。占有する行と列の数を全探索するところまでは良いが、そのあとの包除原理が間違っていた。公式解説で言うところの $f(n,m,x)$ について、 $f(n,m,x)=\binom{nm}{x}-n\binom{(n-1)m}{x}-m\binom{n(m-1)}{x}+nm\binom{(n-1)(m-1)}{x}$ が成り立つと思って実装していた。今日記を書きながら試してみたところ重複の扱いが全くもってダメ。一体どこから出てきた式だっただろうか。しかもこのような計算が軽い嘘包除を考えていたため、黒白それぞれで占有する行と列の数を全探索する $O(N^2M^2)$ のループの中で $f$ の値を計算しようとしており、正しく計算するループがTLEに思えてなかなか思いつけなかった。最終的には解説の動的計画法による計算を4次元それぞれで行うことで解いた。定数倍軽めの $O(N^2M^2(N+M))$ で1200ms。

GはMo。瞬殺だったはずがRE。クエリのソート関数について、ブロックの番号block_numの偶奇によって $r$ 昇順・降順に切り替えようと思ってr[i]<r[j]^block_num%2のようなコードを書いたのが悪かった。これはblock_numが奇数のときr[i]>=r[j]と等しく、このような等号付き不等号を表す関数でソートすると壊れる。配列サイズばかり気にしていて、ランダムケースを試してようやく気づけた。Exは解けず、7完110位。

コードゴルフ。Aはdcで、頑張ってみたら結構うまく縮んだ。 $X$ の値によって $B-A$ 、 $C$ 、 $0$ のどれかを得て、それを $B-A$ で割ったものを答えとする方針。 $A\lt X$ のときは $B\lt X$ を見るのではなく $B-A\lt X-A$ を見ることで、答えとして用意した $B-A$ が流用できてお得。さらに、それらの比較の際引き算してvコマンドに与えることで負かどうかを見るという方法をとると、 $A\lt X$ の時に作った $A-X$ もまた流用できるのでさらにお得になった。BはVimの20Bが早さで負けてあ～と言っていたらPerlの18Bが出てひっくり返った。コンテスト中sort{$a cmp$b}など書きながらなかなか見ない形だなと思っていたが、見ないのは当たり前で、cmpでソートする際はそのようなコードブロックを書く必要がない。

CはRubyがVimで縮むやつで、負け。DもRuby。 $k-1$ の2進数で下 $t$ 桁のpopcountを知りたいとき、digits(2)で得られた配列の先頭 $t$ 要素を切り出すという書き方をすると $t$ が非常に大きくても動いてくれるらしい。その後入力読み込みの改善で取った。EもRuby。文字列の前半分だけ見てbytesでループを回すと、メソッド適用後の値もそのまま文字列になっているので、直接reverseして文字列の後ろ半分と比較することで答えをインクリメントするかどうかが容易にわかる。以降は手付かず。

午後11時半からMarch Cook-Off 2022 div.1に出た。

https://www.codechef.com/COOK139A

ALTERNATEDIVは $(i,2i)$ を $i=N$ から降順に並べた。NANDXORはいつだかのオンサイトのA問題で見たやつで、この制約下でpopcountは高々30種類しかないので、同じ要素を使ったペアが被りまくるとしても $30N$ 回くらい探索すれば見つかることが期待できる。ただし無思考で配列に出現したペアを保存していくだけでは、チェックに時間がかかってしまい解けない。ここで丁寧に考えると、ペアとしては出現した順番に先頭3個を保存しておけばよいことがわかる。同じpopcountのペアが3個出現したとして、まだ答えが見つかっていないなら、それらは $\{(A,B),(A,C),(B,C)\}$ または $\{(A,B),(A,C),(A,D)\}$ のような形をしている。前者の場合は次出現したペアが何であれ被りがない相方が見つかるので良い。後者の場合は、 $A$ を含むようなペアがこの後何個見つかっても無意味な一方、 $A$ を含まないペアはこれまた3つのうちどれかと被りがないことが言える。

A - Equal Weight

SECRETREEは面白かった。 $(1,i,j)$ を聞くと、 $1$ を根としたときに $j$ が $i$ の部分木内にあるかどうかがわかる。これを全部聞くと木の状態が復元できる。復元の方法は、頑張って直接の親を見つけるなどということを考えずとも、トポロジカルソートを行うと入次数が0になった瞬間の辺が木に含まれる辺であることが言える。

PO2は面倒。基本的に値が大きいほうから貪欲に取ってよい。ある要素を選ばないことによって新たに最大2つの要素を選べるようになる可能性があるが、その2つの要素がどちらも選ばないことにした要素より小さければ、問題設定から2つ合わせても選ばない要素に勝てないため。つまり、 $\max P$ だけ取り出して見たとき、奇数個連続しているような箇所の選び方が決まる。偶数個連続している箇所は左右にずらす自由度があって先ほどの性質が成り立たないが、よく考えてみるとこの場合はその連続している箇所を削除した状態で考えてもよいことがわかる。結局その箇所の両隣を2つとも選べることはないからだ。以上のことを $P$ の値の降順に行っていけばよい。ただ実装が面倒だった。削除した箇所はどこまで削除したかを双方向連結リストの要領で管理して、選び方が決まった場所はその両隣も使えないようチェックを入れた。サンプルを合わせて祈るように投げたら1発で通ってくれた。フルフィードバックじゃないと絶対にやりたくないタイプの実装だった。

PO2で苦しんでいる間にその次の2問のsolvedのほうが多くなっていた。まあたくさん解かれているので簡単。FLIPOINTSはflipしたい点を全探索して、ちゃんと選べるかチェックした。これは点の凸包2つが重ならないかで決まる。そうして選び出した遷移を使ってBFSを行う。どうせ遷移の種類は少ないだろうとエスパーして、特に工夫なく探索した。凸包2つが包含関係にある場合でミスして1WA。遷移の種類は高々 $N^2$ 個らしい。OH1DCAREは列をflipするかどうかで2-SATが作れて、辺数 $O(NM^2)$ のところをABC210-Fのようにすることで $O(NM)$ に減らす。

math.stackexchange.com

F - Coprime Solitaire

6完6位で2634→2744(+110)。水曜日の傷が深すぎてhighestに戻れていない。

ABC242-Cについて。この数列はOEISにある。FORMULAの部分を見ると母関数が書かれていて、分母を見ることで数列の漸化式が得られる。なぜか外に出ている負号を入れると $(1-x)(1-4x+x^2+6x^3+x^4)$ で、 $1-x$ で割るのは累積和を取ることだから、逆に差分の漸化式が $a_n=4a_{n-1}-a_{n-2}-6a_{n-3}-a_{n-4}$ だとわかる。ただし先頭の数項では成り立たないようで、しばらく首を捻っていた。 $1-x$ も掛けると今度は直接値が出る漸化式も得られるが、どちらにしてもdpで計算するよりコードは長くなった。dcでもTLEして通らないのでダメ。

A126363 - OEIS

朝方はなろうを読みつつ日記を書いていた。明日は午後1時から模擬地区予選ということで、午前8時くらいには布団に入ったはずが、うっかりなろうを読み続けてしまい午前10時就寝。

03/06(日)

正午の目覚ましで意識は取り戻したものの起きられるはずがなく、結局午後1時にハッと目覚めた。Slackで起床確認されており申し訳のなさがある。またこのとき、OpenCupがさらに延期されていたことに気づいた。

食事もせずにコンテスト開始。コンテスト中の様子は参加記を書いた。

kotatsugame.hatenablog.com

午後6時に終了。前述のとおり今日はOpenCupがないので、食事して午後7時ちょっと前からCF #775 div.1に参加した。

Dashboard - Codeforces Round #775 (Div. 1, based on Moscow Open Olympiad in Informatics) - Codeforces

Aはよい。Bは $\lfloor y/x\rfloor$ をいろいろ調べるとき、 $y$ でループを回すと商列挙で $O(N\sqrt N)$ かかるところを、 $x$ でループを回すと調和級数で $O(N\log N)$ になるというやつ。 $x\mid y$ なるペアを調べるときに同じ現象が発生するほうが典型的か。具体的に $x$ でどうループを回すのかが思いつかず、しばらく迷走していた。数列に存在する値 $x$ と存在しない値 $k$ によって作られた区間 $[kx,(k+1)x)$ に、数列に存在する値が含まれているとアウト。判定は出現したかどうかのbool値配列の累積和で行える。

Cは昨日のABC242-Eみたいに先頭から決めていくやつ。 $s$ のヒストグラム $cnt$ を作っておくと、まずすべての並び替えが $C=\frac{n!}{\prod cnt_i!}$ と書ける。先頭の要素として $1\le i\lt t_1$ を選ぶと、残りの並び替えは $cnt$ の差分を考えて $C\times\frac{cnt_i}{n}$ と書ける。 $cnt$ の累積和をBITで管理しておけば、この値をすべての $i$ に対して求めた和が得られる。先頭要素を $t_1$ に固定して次に進むときは、 $C\leftarrow C\times\frac{cnt_{t_1}}{n}$ 、 $cnt_{t_1}\leftarrow cnt_{t_1}-1$ 、 $n\leftarrow n-1$ と更新して次に進む。次に進んで $n=0$ だった場合は答えをインクリメントしてbreak、 $cnt_{t}=0$ だった場合はそのままbreakして出力。 $C\times\frac{cnt_i}{n}$ の式を勘違いして1WA。

Dは難しかった。眠気も強くフラフラしながら考察していたが何とか解けてよかった。 $a_1$ 、 $a_2$ 、 $a_3$ の累積和を取ったりして整理すると、移動経路のマスの総和が下に移動するときの列を $i,j$ （ただし $i\le j$ ）として $L_i+R_j$ という形で表せる。まず区間を一つだけ使う場合を考えると、 $(\max L,\max R,\max L_i+R_j)$ のようなデータをセグ木に乗せることで計算できる。次に区間を複数使う場合について、 $L$ の値のみ考えた場合はdpができる。区間を $r$ の昇順に並べて、 $dp_r\leftarrow \max(\max_{l-1\le i\le r-1}dp_i,\max_{l\le i\le r}L_i)-k$ という更新をすればよい。最終的に選ばれる区間は包含関係にはないので、このように $r$ の位置にdpの値をセットしておいても次の区間で必ずその値を参照できるからだ。この計算をした後、新たに $L_i\leftarrow\max(L_i,dp_{i-1})$ と定めると、先ほどの区間を一つだけ使う場合に帰着できる。