04/10(月)

午後2時半ごろ頭の痒みに飛び起きシャワーを浴びた。先週も同じことをやっている。基本的に寝る前にシャワーを浴びるのだが、寝るタイミングが自分が眠くなった時なので、あまりに眠気が強い日はスキップしてしまうことがある。一日ならいいが二日続くとこうなる。

次に起きたら午後9時半だった。インターン先定例会を寝過ごして欠席してしまった。1年半働いてきて初めてである。取るものも取りあえず、Slackで謝罪のメッセージを送った。

睡眠時間3時間でも起きられるだろうというのは自分を過信しすぎで、これまで成功していたのは単に運が良かっただけに過ぎない。長く働いていることによる気の緩みも正直あったし、遅かれ早かれこういうことにはなっていただろう。反省して、これからは寝てから起きるまでの間隔をちゃんと空けるようにしたい。

日付が変わるまで先週の週記を書いて投稿。日曜日のコンテストを終えてからも日記を書く時間は十分にあったのにうっかりハーメルンに全てを捧げてしまい、さらに今日は遅い時間まで眠りこけていたので、今週も書き終えることができず、Universal Cup・ABC・CFとコンテスト三つが穴あきで残ってしまった。その後ABCの分を加筆した。

あとはずっとハーメルンを読んでいた。午前11時前に就寝。

04/11(火)

午後5時半ごろ目覚ましで起床。今日は何としてもゲーセンに行きたかった。シャワーを浴びて外出。

夕食として以前見かけて気になっていた天ぷら屋に入った。ここは実は飲み屋で、天丼に加え天ぷら単品で二品注文したところ席料を含めて2000円を超えてしまった。量的にも質的にもまったく満足できなかったが、これは自分の目的に沿わない店選びをしてしまったのが悪かった。

この件から得られる教訓は二つ。一つ、酒を飲まない場合飲み屋で食事するのは損である。二つ、どんな店でも満腹になれるわけではない。

食事 pic.twitter.com/iK78OONS7T
— こたつがめ (@kotatsugame_t) 2023年4月11日

午後8時から閉店までゲーセンで遊んだ。今日の目的はチュウニズムデュエルを終わらせること。今進行しているものは明日で期間が終了してしまう。まだ単純計算で25クレ分くらい残っていたが、幸い今日はクリティカル発生率アップの日なので必要クレ数はもう少し減るだろうとの見込み。だから目覚ましをかけてまでゲーセンに来たのだ。

中盤までは全くクリティカルが出ず明日もゲーセンに来ることを覚悟したが、最後7連続くらいで出て閉店ギリギリで何とか終わらせることができた。スコアとしての成果は、新曲をあらかた埋めて14+からSSSが四つ。14+全SSSの再達成はReverberateがどうにもならないせいで現状不可能。この譜面はまだSS+にすら到達できていない。

今日 pic.twitter.com/vPU4UTvuNT
— こたつがめ (@kotatsugame_t) 2023年4月11日

油そばを食べて帰宅。TLを眺めるのに時間を溶かしつつ、シャワーを浴びたり先週の週記にCFの分を加筆したりした。午前6時くらいからハーメルンを読み始め、正午を回ってから寝落ち。

04/12(水)

消えた。

04/13(木)

04/12 午後11時半ごろ起床。ハーメルンを読み続けて午前4時頃読了。「【完結】閃光と隼と風神の駆ける夢」。

syosetu.org

非常に面白かった。レースのシーンはとことんシリアスで何度も泣かされた。泣かされたというのは比喩表現ではなく実際に涙を流していたということ。逆に、ネタバレにはなってしまうが、主人公チームが苦しむ展開というのはほぼなかった。「ほぼ」というのがポイントで、どんなにチートな主人公たちでも楽勝というわけにはいかないレース展開がウマ娘二次創作一般に通底する面白さだと思う。主人公の設定もとても好みだった。微妙に違う3年間をループし続ける主人公というのは、実は逆行を繰り返し続けているのと同じである。その逆行による知識チートが最高。

その後午前8時まで二度寝していた。シャワーを浴びてセミナー準備開始。普段はセミナーが午前10時開始なのでとても間に合わない時間だが、今日は正午からだったので何とかなるはずと考えていた。

午前11時過ぎに切り上げた。6章のはじめの部分なので内容は簡単だろうと思っていたら、簡単すぎて書くことがなく、分量が少し足りない。それでも時間的にこれが限界。準備を整え出発し、学食で食事しラノベを受け取ってからセミナーの教室に向かった。

まず2時間は同級生の発表だった。教科書でClearlyと書かれている部分が自分にとっては明らかでなく、また発表での説明も不十分だと感じたため指摘したら、そこで詰まって先に進まなかった。

3人だけでずっとセミナーしていると気が抜けてしまうからと、先生に聴衆として呼べる人がいないか聞かれた。この日記を読んでいる方は興味があれば連絡してほしい、と書いてみる。日程や時間は調整可能のはず、オンライン参加も歓迎。

次の2時間は自分の発表。特に問題はなかったはずだが内容も薄かった。定義ばっかりが続いて終了。一応次回に示す定理を紹介して定義がどう現れるかだけは言及したつもり。

最後の2時間はこちらに留学することを考えている海外の学生の発表だった。先週の同級生の発表内容に関わる論文について。ところが発表者はそもそもグラフ理論の用語からあやふやだし、我々も別に論文を読み込んでいたわけではないので、誰も理解していない論文について議論するというギャグみたいな時間を過ごす羽目になった。

https://www.sciencedirect.com/science/article/pii/S0095895603000297

学食で食事して帰宅。

「音楽チートで世に絶望していたTS少女がSIDEROSの強火追っかけになる話」が完結していた。ラストはちょっと駆け足気味で不完全燃焼だが、非常に好みの主人公最強ものだった。正体不明のネット上の有名人という設定も良い。

syosetu.org

履修登録をした。卒業のためには必修単位の他にあと4単位取る必要がある。今セメスターの集中講義に一つ面白そうなものがあった以外どれにも興味が持てなかったので、来セメスターの集中講義でもう一つ取ることにした。そのような余裕があることを願う。

ゴミを出したりシャワーを浴びたりした後インターンの作業をしたが、眠すぎてお話にならなかったので1時間で切り上げた。少し日記を書き、午前1時半就寝。

04/14(金)

午前11時前に起床。外出し、原付への給油を済ませた後、学食で食事したり購買で買い物したりして帰ってきた。

ブラックサンダーを箱で購入したら、これまで640円だったのが720円になっていた。1本あたり4円の値上げ。その場では値上げを理解して支払ったが、後から売り場に戻って確認してみたら値札は値上げ前のままだった。真面目に営業してほしい。

しばらくインターンの進捗を産んで、午後2時から1on1。今週のタスクは機械学習の精度評価を今動かしている学習コードで使えるようにするというものだったが終わらなかった。1on1の最中に必要なデータをAmazon S3上に上げるところまではできたので、来週はこれを読み込んだりする部分を書く。1時間ほどで終了した。

ラノベを読んでいた。午後6時半ごろ「悪役御曹司の勘違い聖者生活」を読了。タイトル通りの勘違いものだが、その勘違いの背景が主人公以外のキャラ視点を読んでも十分に理解できなかったという印象が残る。真面目に読んでいたわけでもないので自分の読解力不足かもしれない。ただそういう点や、主人公が内心でよく慌てていたという描写から、状況に振り回されすぎだと感じた。そのような主人公はあまり好みではない。

午後7時くらいに寝落ちして次に起きたのが午前0時だった。yukicoderは寝過ごしたが、これはほぼ意図的なものである。なぜならwriterからして今日の問題文が読みにくいことは明らかだから。

yukicoder contest 384 - yukicoder

「厳密さを重視して「 $\dots$ 」は使わないようにする」、なるほど言っている内容は理解できるが、しかし競プロの問題文でやるべきことではないと考えている。これに関しては昨年一度指摘し、その上で自分もwriterの方も翻意する気はなさそうだった。よってもう議論する気もなく、コンテストに不参加を決め込んだ挙句日記という場で愚痴っているわけだ。一方的な批判になっていることに申し訳なさはあるものの気持ちのやり場がなかった。

「… … 」で省略することについては、厳密性が失われるためどうしても避けたいそうだ。自分は、少なくともこの問題文のような使い方において「… … 」が厳密性を損なうとは一切思っていないが、その根拠は競プロerとしての前提知識に依存してしまっているので主張するには弱い。ある程度競プロに慣れた人間が読みやすい問題文を目指している自分に対し、writerの方は数学好きなら競プロに不慣れでも把握できるような問題文を目指しておられたので、それは意見が合わないわけだ。
週記（2022/10/31-2022/11/06） - kotatsugameの日記

朝までラノベを読んでいた。2冊読了。

1冊目、「未練タラタラの元カノが集まったら」。集まって何をするかはあらすじでも隠されていたが、本編ではすぐ明らかになった。グループで動画の配信活動を行うようだ。これに関する描写が中途半端で、配信者モノとして読むには活動があっさりしすぎだし、かといってラブコメとして読もうにも配信関係のシーンばかりだし、いったいこの設定で何がしたいのかよくわからなかった。

2冊目、「許嫁が出来たと思ったら、その許嫁が学校で有名な『悪役令嬢』だったんだけど、どうすればいい？」2巻。面白かった。幼馴染二人との関係性を問う巻。後半ではだいぶ厳しい現実も描かれていたが、ちょくちょく挟まる許嫁とのシーンがいい気分転換になった。主人公に対して幼馴染二人と許嫁が好意を向けるハーレム状態はそのうち終えなければならない、というのは確かだが、この設定が読んでいて楽しいので、いくらご都合主義的であっても丸く収まってくれて安心した。

シャワーを浴びて昼間で日記を書いていた。正午就寝。

04/15(土)

午後5時半起床。今週のUniversal Cup 12回目は大岡山セットでTTPC由来だったため不参加。

The 1st Universal Cup. Stage 12: Ōokayama - Dashboard - Contest - QOJ.ac

食事して午後6時からCF #866 div.1に出た。

Dashboard - Codeforces Round 866 (Div. 1) - Codeforces

Aは元のMEXが $m$ だったとすると $m+1$ にするのが目標で、達成すべきは $a$ に $0\dots m$ があり $m+1$ がないようにすること。まず、元々 $m+1$ がない場合、すでに $0\dots m-1$ はあるからあとは $m$ を作れればよい。書き換える余裕があるか判定することになり、シンプルに $m+1\le n$ で行える。

$m+1$ がある場合はすべて書き換える必要がある。この時操作では $m+1$ をすべて含むようなギリギリの区間を選ぶのが最適である。また書き換え先はまだない $m$ 一択。これで操作が具体的に決まるため、それを行った後再度MEXを計算し判定すればよい。

Bは最初に切り出した長方形を考えると $h=\max a$ または $w=\max b$ が成り立つ。これを両方試し、 $hw=\sum ab$ より $h$ と $w$ のもう一方も求めて判定した。判定は $a$ 最大または $b$ 最大の長方形を貪欲に切り出していくのが正当で、要素の削除のためmultisetを持ち出した。

Cは適当に根付き木にして実験した結果、「ある頂点に入ってきて部分木を全部通り子の一つから出ていく」またはその逆というパターンが再帰的に連続していることが分かった。再帰的というのは、具体的には葉でない子に対してこのパターンを繰り返す必要があり、特に葉でない子が二つ以上あると破綻する。ただし根の場合は二つまでなら許容できる。

判定と構築は頑張れば同時にできるだろうが、頂点を辿る順番のreverse操作が必要になって面倒だったので、判定してから構築することにした。しかし1WA。適当に作ったテストケースに対し根を全探索したら、葉を根としてしまった場合に壊れることが分かった。見落としている構築方法があったわけではなさそうなので次数が2以上の頂点を選ぶようにしたら通った。 $n=2$ の場合そのようには選べないので注意。

Dはバックパックの中を空にできるタイミングを全探索する。例えば店 $l$ の直前に空になり、その次に店 $r$ の直後に空になったとしよう。これが可能であるのは、店 $l$ から $r-1$ までに重複するリンゴがなく、店 $r$ で売っていたリンゴがそのどれかと被った場合である。

重複するリンゴがない範囲については尺取り法で求めることができるから、 $l$ の下限がわかる。後者の条件は $l$ の上限に対応していて、店 $r$ の売り物を忘れている場合 $r-1$ 、そうでない場合は底と重複するリンゴを売っている店または売り物を忘れた店で最も近いものの番号となる。この範囲に、直前でバックパックを空にできる店があるか判定すればよい。

CとDでそこそこ手間取りEは考える時間もあまりなかった。4完。

Cは全頂点が直径パスから距離1以下にあることが条件で、そのパス上の点を行きと帰りで交互に取れば構成できるようだ。美しい。

Dは $m$ の総和に制約がついていないので、ちゃんと配列を使いまわしたり必要なところだけ初期化したりしないとTLEになる。pretestに入っていなかったらしく、システスで結構な人数が落ちていた。

Dのおかげで順位が結構上がり23位、2755→2823(+68)。前回の傷が半分弱癒えた。撮った動画のアップロードだけ済ませ、午後9時からABC298に出た。

TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder

Aはoがありxがないことを判定。sedで書いた。最初は条件を逆転させて/x\|^[^o]*$/と一つの正規表現で表したが、これくらい長くなるなら2段階の判定を重ねたほうが短いのではと思い再提出。目論見通り-2Bに成功した。

Bは4回回して愚直に判定。条件が単に $A=B$ でないことに注意。回転方法については、自分で考えず問題文に書いてあるものをそのまま持ってきた。

Cは箱に対するカードをmultisetで、カードに対する箱をsetで管理した。出力の個数に関する制約があるので、毎回ソートしたり重複を取り除いたほうが定数倍的には良いが、ABC-Cで気にしてもしょうがない。

Dはクエリ3で出力すべき値を常に一緒に管理する。クエリ1は簡単で、クエリ2も10のべき乗を掛けて取り除けばよい。このべき乗は前計算した。 $Q$ が大きいので毎回計算するのは少し怖かったが、TL 3secなので余裕だったか。

Eはdpの計算順序を考えるのが面倒だと思ってメモ化再帰で書いたが、別に順序は難しくなかった。

Fは $R$ も $C$ も入力のどれかのマスと一致させるのが良い。 $R$ を全探索することにして、 $C$ の寄与はセグ木で求めた。 $c$ を座圧して、対応するインデックスに $x$ を加算しておく。 $R$ を決めたら $r=R$ なるマスの $x$ を一旦取り除いて全体の最大値を求める。取り除く操作と戻す操作は全体で合計 $2N$ 回しか行われないので、十分高速。

Gは区画と切った回数を状態にしたdp。 $m$ と $M$ を両方持って遷移するのは、単に $M-m$ が最小のものだけ採用すればいいわけではないからおそらく不可能。そこで $m$ を決め打ち、 $M$ の最小値を求めた。

$m$ の候補は区画の数と同じ $O(H^2W^2)$ 個、dpの状態数は切った回数も掛けて $O(H^2W^2\times HW)$ 、一つの状態に対する遷移はどこで切るかと片方の切った回数で $O((H+W)HW)$ 。これだけ見ればおよそ6¹³となって到底間に合わないが、実際には定数倍が非常に軽く十分高速に動作する。

コンテスト中にこういう見積もりを真面目に行ったわけではない。とりあえず書いて $H=W=6$ のケースを試したら爆速だっただけ。ちょうどこの時間帯AtCoderがDDos攻撃を受けていて繋がらなかったため、提出に少し手間取った。録画を確認すると書き上がってから提出まで3分ほど空いていた。

Exは問題を分解したら解ける形になった。 $L$ と $R$ を結ぶパスの真ん中で切ってできる二つの木について、それぞれ $L$ からの距離の総和と $R$ からの距離の総和を求められればよい。全体の木を根付き木にしておくと、考えるべき木はある頂点以下の部分木、あるいはそれを全体から取り除いたものとして表せる。

つまり「 $v$ を根とする部分木の頂点への、頂点 $u$ からの距離の総和」を求めるクエリを $O(Q)$ 個の $(u,v)$ に対して計算できればよい。頂点をオイラーツアー順に並べると、 $u$ を木上で動かしながら区間ADDで各頂点への距離が更新でき、クエリには区間和で答えられる。

パスを上手く真ん中で切る部分で少し手間取った。 $L$ と $R$ のLCAを求め、そこから $L$ 、 $R$ への距離を比較するのだが、一致する場合に $v$ の設定を間違え、片方の部分木に $L$ と $R$ が両方含まれてしまっていた。

66分で全完し6位。5位とは1分、4位とは2分しか離れていないので、Aのコードゴルフで試行錯誤していた時間が順位にかなり影響したようだ。賞品についてはコンテストがDDoS攻撃の影響でunratedになったからどうなるかはわからない。

振り返りまでして動画をアップロードし、午後11時からGCJ Farewell RoundsのRound Dに出た。

https://codingcompetitions.withgoogle.com/codejam/round/0000000000c95b95

Aは木の頂点それぞれに対しそこから全頂点への距離の総和が求まればよい。先ほどのABC-Exと同じ方法で、今回は単に総和を管理するだけで求まる。

Bは $A+B$ のSuffix ArrayとLCP Arrayを計算しておくとクエリごとに答えを二分探索できる。判定は、LCPに関する条件がSuffix Arrayの区間になり、 $P$ に関する条件がSuffixの開始地点として使える最大値になる。LCP Arrayを乗せたセグ木上の二分探索で区間を求め、Suffix Array上の区間MINで後者の条件をチェックすればよい。 $\log$ が二つ付くがまあ間に合うだろうと出した。

より多く解かれていたDに進んだが全然わからずかなり時間を使った。最終的に計算量がよくわからない解法で通した。

金がある位置で分割統治dpする。位置 $l$ に金があり、次に位置 $m$ をまたいで位置 $r$ にも金があるとする。このとき $m-l\ge r-m$ なら、 $l$ から $r-m$ 文字はo<...<<というようになっていて、 $m$ から $r$ も>>...>oとなっている。残りの真ん中部分は右端が $m$ であり、長さの偶奇に応じて<...<<>>...>または<...<<=>>...>となっている。 $m-l\le r-m$ でも真ん中部分の左端が $m$ である以外は同様。

この真ん中部分をまず全列挙する。 $l$ と真ん中部分を決め打つと対応する $r$ が求まるし、逆に $r$ と真ん中部分を決め打ってもよい。いずれにしても明らかに間に合わないが、ここで可能な真ん中部分の長さがいくつかの連続した区間で表現できるのではないかと考えた。すると、 $l$ とその区間を決め打った時に $r$ の区間が求まり、累積和なりimos法なりで先ほどと同様の遷移が行える。

コンテスト後に知ったことだが、真ん中部分として使えないものが見つかった場合、合わなかった文字を飲み込んで次に使えるようになる時には長さが倍くらいになっていることから、区間の個数が $\log$ 個しかないとわかるようだ。

Eはギリギリでテスト1のみ通した。 $C\le 9$ の場合は順列を全探索、 $C\ge 10$ の場合はループの上に次数2の頂点を一つおきに残し、それ以外の頂点間に好き放題辺を張った。 $C\ge 10$ ならこれで10本は必ず消費できる。次数2の頂点から出ている辺だけ全部残せばそれがループを構成する辺になっているので、復元は容易。

C問題は目を通しすらしなかった。ABDeの61点で22位。かなり疲れた。本来ならこの後5時間Universal Cupに出なければならなかったんだなと思うと身震いがする。

CFとABCの動画を公開した。

www.youtube.com

少しだけABCのコードゴルフをした。Aはコンテスト中に出した20Bが最短になっている。BはOctaveでrot90を使った。以降は手付かず。

atgolferのTwitter APIが一時停止されたとのメールを見て、重い腰を上げてTwitter API v2に対応させた。といってもTwitterのDeveloper Portalで少し設定した後使用するライブラリを変えただけ。動作確認を慎重に行っていたら朝までかかってしまった。

github.com

ラノベを読んで正午くらいに就寝。

04/16(日)

午後11時半ごろ起床。布団でダラダラYouTubeを見ていたら1時間半経過していた。その後朝までかけてラノベを2冊読んだ。

1冊目、「転生したら皇帝でした」3巻。2月下旬に半分ほど読み進めた後今まで放置していたら、人名・地名・勢力関係など重要な設定が結構頭から抜けていて苦労した。内容は、前半は2巻の後始末、後半は外交をしつつ次巻の戦争に向けた準備。内政シーンは好きだと思っていたし実際に楽しく読めたが、記憶には残らなかった。それほど権力を回復できておらず思い切りのよい行動がとれないのも辛い。

2冊目、「転生したら皇帝でした」4巻。いよいよ戦争ということで派手なシーンが多く、かなり面白かった。戦争準備や中盤までの趨勢の描写など派手でないシーンも、策を立てたり実行したりでわくわくしながら読めた。誤字が多かったのだけはちょっと気になる。

それからは日記を書いていた。午前11時くらいに学食で食事、午後1時に就寝。先週同じ時間に寝て月曜日の定例会を寝過ごしたのに、一切学習していない……。ただ今週はコンテストがほとんどなかったため睡眠負債が溜まっておらず、状況は少し違うはず。