週記(2021/12/13-2021/12/19)

12/13(月)

先週は週記を投稿してから少し業務を進めようと思ったが、すぐわからないところにぶち当たったので布団に入り、なろうを読み始めた。しかしそのまま読み続けているうちに質問を投げてよい時間になったため、また起き出してしばらく作業を進めていた。一段落つくまでやっていたら昼前になったので、今度こそ布団に入って寝た。正午だった。

午後3時半、生協の弁当配達で起床。先週土曜日からずらしてもらったものだった。自分からこの時間帯を指定しておいて、寝過ごすようなことがなくて本当に良かった。

またすぐ寝るつもりだったし、実際物凄い眠気だったが、うっかりコードゴルフを始めて目が冴えてしまった。ABC231-Fに2時間ちょっとかけた。

atcoder.jp

座圧せずにBITに乗せるテクニックとして、mapを使うものがある。必要なところだけ作ればそう酷いことにはならないだろうという楽観に基づいていて、この問題はそれが通った。しかし詰めが甘く最短を取られてしまったので、別のところから攻めようとかなり試行錯誤していた。最終的には、負号をつけてソートすることで逆順ソートしていたところを、昇順ソートのままでも正しい値が求まるアルゴリズムに置き換えることで縮んだ。

もう一度問題を振り返ろう。この問題はA_i\ge A_jかつB_i\lt B_jなる(i,j)の組を数える問題だった。今、まずBの値で昇順ソートしている。このとき、B_i\lt B_jについてはBITを参照することで求まるが、B_i=B_jの場合が問題となる。Aで降順ソートしておけば、先のBITの参照でB_i=B_jかつA_i\gt A_jの場合がカウントできる。A_i=A_jの場合は相変わらず問題に見えて、l\le i\le j\le rA_i=A_jかつB_i=B_jとするならば、各l\le i\le rに対してまだBITに入っていない分、r-iを答えに加えたい。しかし実は、i-lを答えに加えることにしても値は変わらない。正方形領域に対角線を引いて、その上側を数えたいと思っているが、下側を数えても同じという寸法である。r-iは先を見てみないとわからなかったが、i-lは直前の要素と比較してカウンタを弄ることで容易に求まる。

Aを昇順ソートにすることを考えよう。実はこの場合も先ほどとほとんど同じ理屈が通用する。l\le i\le j\le rB_i=B_jとし、さらに(l\le)l'\le i\le j\le r'(\le r)A_i=A_jであるとする。各l'\le i\le r'について、BITを参照することで等号が成立する部分のi-l'+1個が答えに加えられる。残りは等号成立がr'-i個あって、さらにstrictに大きい要素もr-r'個ある。足し合わせてr-i個を新たに答えに加える必要があるが、これを先ほどの正方形領域の上下の話からi-lに読み替えることで、相変わらずカウンタを弄ることで求められる。

日付が変わってから、アドベントカレンダーの記事に着手した。とりあえず読書記録を手作業で集計してグラフを作成した。自分が読んだ本のレーベルごとの分布は個人的にかなり気になっていたが、題名からレーベルを思い出すことができない本がかなりあって、実際に本を読むときはあまり意識していないんだなあと感じた。各レーベルごとの本のリストも作成して、いよいよ記事の本題と目している、今年読んだ本から印象に残っているものを選ぶ作業に入った。とりあえずいくらか抜き出し少しだけコメントをつけ始めた段階で、思ったより大変なことに気づいたので、今日はここまでとした。

本のリストは長くなるので、折り畳みメニューをググってコピペしてきた。折りたたまれる文中に改行が効かなかったので焦ったが、HTMLを直書きしていると考えれば素直に<br>を使えばよかった。

布団に入ってなろうを読み始めたが、午前5時過ぎに寝落ちした。

12/14(火)

午前10時くらいに何かの検査で来客があって起床した。そのまましばらくなろうを読んでいて、午前11時半に再度入眠した。午後7時半起床。久しぶりに満足感のある睡眠だった。

チュウニズムで、代行により取得された皇帝の称号が剥奪されたという告知がなされた。代行を判別する方法としては、例えば離れた場所でのプレイ記録の間隔がどう頑張っても移動不可能なくらい短いと黒、というものが考えられる。もちろん何か一般プレイヤーに隠された情報が収集されているのかもしれないし、そうでなくてももっといろんな方法で検証しているのだろう。どういう判定をしているのか気にならないといえば嘘になるが、競技プログラミングにおける不正検出などと同様、広く公開してはいけない性質の技術になる。

日付が変わるまで一所懸命ととりにゃあアドベントカレンダーに向けた記事を書いていた。結局30分ほど間に合わなかったが、どうしようもない。買った本に関しても集計を行ったが、これに1時間強かかっている。しかしこれだけ時間をかけたとはいえ、249アイテムを分類してそれぞれの個数を数え、和を取ったときに、見事249に一致したときはちょっと感動した。ミスをしなかったということ。

kotatsugame.hatenablog.com

本に付けたコメントには、結構力が入っている。設定に少し触れた後、自分が何に惹かれたのか・どういうところが特徴的だと感じたかなど、とにかく自分の印象を言語化することを意識していた。これは僕のブログ記事であるから、ストーリーの通り一遍の説明などではなく、僕の気持ちを書くべきなのだ。またその中でも、同じ表現がそう連続することはないようにしているつもりだ。

今週のPythonの課題を熟した。今週は音声データを離散フーリエ変換してスペクトル分析を行うというもの。今週は結構難しく感じた。なんの断りもなく離散フーリエ変換後の配列の後ろ半分を無視しているが、実際に試してみるとその部分は前半部分を逆にしたような値になっていた。式を改めて確認すればそれはそうという感じで、三角関数\sin(-\theta)=-\sin(\theta)とか\cos(-\theta)=cos(\theta)とかの話。課題は、具体的にはスペクトル分析を行って音声の音階を調べよというもので、やってみると見事に倍音も検出してくれてかなり上手くいったという気分になった。

なろうを1作読了。「鷹は瑞穂の空を飛ぶ~プラスチックの専門家が華族の娘に転生したので日本は化学立国になります~」。

https://ncode.syosetu.com/n1453gs/

良かった。逆行転生し、日本の政治・経済・軍事に未来知識でテコ入れする系の話はいくつか読んでいて、これもその一つになった。タイトルにもあるように、この作品における未来知識は主にプラスチックに関するもので、化学的な説明もそこそこ挟まれる。そのあたりはシュッと読み飛ばしてしまったが、それ以外にも主人公が幼いころから積極的に表舞台に立てていること、またかなりのスピードで年齢を重ねていくことも特徴的に感じられた。他の作品では、幼い主人公は陰から操る(しかない)ことが多いように思うし、ずっと少女時代を描いているが、こちらは最新話までに出産をも済ませている。

ちょうど日付が変わってからTCB43が開催されていたようだったので、参加した。例によってこの日記が公開される頃には終了しているイベントなので、ここに結果と所感を書いておく。

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

5問目まではよい。6問目は答えがAB未満になるという事実だけ覚えていた。証明をつけるのに少しだけ手間取ったが、とにかく線形結合で表してから、AB以上の値ならABの係数をうまくずらすことで同時に非負整数にできるということが言える。7問目は文字列長が長いのを見落として1ペナ。8問目はNからどれだけ離れるかを考えると、だいたい\sum_{k=1}^N(N+k-N\bmod k)になる。kNの約数の場合はずれるが、それは個別に計算できる。あとはN\bmod k=N-\lfloor N/k\rfloor kの和だが、これも商でまとめるテクで計算できる。

9問目は非常に難しかった。2時間半ほどかかり、ペナこそ付かなかったもののタイムボーナスはびた一文も残らなかった。行列式の求め方はいろいろあるが、ここではすべての置換を渡る和で計算することにする。和を取る値は積の形をしているので、行に対して列を選ぶと考えるならば、置換\sigmaであって\sigma(i)=i+pまたは\sigma(i)=i+qなるものだけを考えればよい。\sigma(i)を選ぶと\sigma(i+q-p)も決まるので、結局g=\gcd(pq,q-p)個それぞれの行き先を考えればよくなった。あとは置換の符号を求める必要があって、とりあえず2^g通り生成した後転倒数をそれぞれ計算してみたが、各置換に対してO(g)からどうにもうまくまとめられない。各行の形が3種類に分かれるはずだが、それぞれの幅がgの倍数でないのだ。

かなり長い間悩んでいたが、行列をいくらかずらすことで解消された。左にp回シフトすることで、行列式(-1)^{p\times(pq-p)}倍しつつ対角成分をすべてpにできる。この状態で考えると、行の形は上からpq-(q-p)行とq-p行の2種類に分かれてかなり扱いやすい。丁寧に丁寧に計算すると、結局転倒数に関係あるのはg個のうち何個を+pにしたか(今はずらしたので+0にするか)だけだとわかって、二項定理で閉じた式になる。無事愚直解とも一致してAC。

10問目は解けなかった。本当に何もわからない。N=1のときの答えは\frac x{1-x-x^2}x=\frac 1 Mを代入すればよいとわかって、それだけ提出したが、M=0にやられた。再度出しなおして、あとからN=0の場合もわかることに気づいてもう一度出した。13点である。

朝になって業務上のやり取りが可能な時間になったので、2時間くらい進捗を産んでいた。タスクが片付いてスッキリしたが、生活リズムが崩壊している。学食に行って昼食を摂り、注文していた本を受け取って帰宅。午後3時過ぎまで日記を書いていた。

1週間くらい前に何とか終わらせたと思っていたタスクだが、僕が完了後の操作を間違えていたらしく、今までチェックに回されていなかったらしい。あまりにも申し訳なさすぎる。1週間なにも音沙汰がなかったので、もっと早く違和感を覚えるべきだった。連絡に対して謝っては見たものの、最早どうしようもない。次から確実に成功させていくしかない。

午後4時就寝。

12/15(水)

消えた。

12/16(木)

12/15の午後10時半くらいに目を覚ました。

「やばいクレーマーのSUSURU TV」がネット流行語にノミネートされていて、SUSURU本人がトロフィーをもらっていた。これに対して「本人は何もしてないのに」などのコメントが見られたが、個人的にはその批判は当たらないものと思う。もちろん本人ver.を歌った動画をアップロードしたというのもあるが、そもそも対外的にこのコピペを許容するような振る舞いをしてくれたことに、並々ならぬ価値があるものだと考えている。それに、もともとの流行語大賞についてもネタ元ではなくネタの対象となった人物に対して賞を与えるような性格があったと記憶している。

そのままずっとハーメルンを読んでいて、午前2時前に読了。「ハンターズギルドは今日もブラック【未完】」。主人公がG級に上がってからの話はかなり好みだった。

syosetu.org

しばらく別のハーメルンを漁って、午前3時に再度就寝。続いて午前8時半にまた目を覚ました。しばらくハーメルンを読んでいたら寝るタイミングを逃し、ゼミの友人から連絡がきたことをきっかけに起床することにした。午前10時半だった。

夜から宅飲みの予定なので、念入りに部屋を掃除していたら、正午を回ってしまった。急いで家を出て、ゼミ後そのまま市街地に出ることを見越して地下鉄で山に登る。学食で昼食を摂っていたらゼミに3分ほど遅刻してしまい、また寝坊かと心配をかけたらしい。3分程度の遅刻では先生からのお咎めはなしだったので助かった。今日のゼミは4限から集中講義があるらしく、1限ぶんで終了。来年一発目の発表者は僕らしいので、なんとか頑張りたい。

ゼミ後、予定通り市街地まで出てゲーセンに行き、新曲を埋めた。目立った成果はなし。午後5時になってディズニーストア前に行き、ホスフィンとたいぺーと待ち合わせして焼肉屋に行った。

僕は焼き鳥を食べたいと思っていたが、他の2人に夕食として焼き鳥屋を選択する発想がなかったらしく、こちらになったという経緯がある。店はリーズナブルでよかったもののサワーを頼んだのは失敗だった。味もアルコール分も薄くただただ腹を壊すだけ。実際家に帰ってからしばらくトイレにこもることになった。1年前に焼き肉を食べて腹痛に苦しめられた経験から、今日はかなりしっかり肉を焼いたし、生肉をつかむトングと焼いた肉を食べる箸を明確に使い分けていたので、腹を壊したのは単純に飲み物を多く飲んだからだろう。

日記(2020/11/06)あるいは僕が深夜に救急車を呼んだ話 - kotatsugameの日記

ドンキで酒とつまみを購入し、3人で僕の家に行って飲み始めた。そのようなことをするのは、今年の07/22以来だ。前回、途中でお酒が切れたという記憶が強く残っていて、今日は途中で絶対になくならない量を買ったのだが、さすがに多かった。

結局右から3本は手つかずに終わってしまった。右から4本目の日本酒は味に慣れないので敬遠していたが、ホスフィンにコーラと混ぜて飲むやり方を教えてもらい、これがかなり飲みやすくて驚いた。左から3本はどれも牛乳で割って飲むもので、金色のボトルのものが前回非常においしかったため今日も購入。しかし飲みやすさという点ではやはりというか、カルーアミルクが一番だった。正直これだけ飲んでいても満足なくらい。

最初はアニメを見ようとしたが、冷静になると1クール見るだけで今日が終わってしまうので、結構気合いがいる。適当なものを1、2話見て、これ止めようか……みたいなことを繰り返した後、結局前回と同じくそれぞれがおすすめの動画を紹介することになった。前回はノートパソコンを使ったが、今回はデスクトップパソコンを使った。机の高い位置にモニターを増やしたので、そこに映せば床に座りながら見られるだろうという考えだ。画面の文字が小さくて操作はしづらかったが、動画自体はいい感じに見ることができた。

お互いのネタも切れたところでナブラ演算子ゲームを始めてみたものの、3人でやると誰か1人を負かすのが躊躇われて、ダラダラ続くうちにたいぺーが寝てしまったので終わりになった。また動画を流すフェーズに戻る。何かボードゲームの1つでも用意しておいたほうがいいのかもしれない。買ってきた牛乳3Lがなくなって、コンビニに少し買いに行こうかという話をしていた記憶を最後に、僕も眠りに落ちた。最後のツイートは午前4時半だった。

12/17(金)

午前7時半ごろに目を覚ました。微妙な気分の悪さはあるが、頭痛や吐き気はない。昨晩ホスフィンがキレートレモンをくれたり、お茶を出したりとコントロールしてくれていたからだろう。部屋の後片付けをして、ホスフィンは早々に帰っていった。たいぺーはまだ帰らないようだったので、2人でベッドに並んでもう一度眠ることにした。

午後1時過ぎに起きて、たいぺーも帰っていった。僕はまだ眠るつもりだったが、インターンの業務で連絡が来ていることに気づき、通話などしていた。進め方にいろいろ間違いがあったらしく、チェックの方に迷惑をかけてしまい申し訳ない。ただ、一概に僕が無能というわけでもないと思っている。あまり細かいことをここに書くのはよくないのでぼかすが、知らされていないことは知らないのだ。午後4時頃に再度就寝。

午後9時半起床。元気が出ず、ずっとパソコンを触りながらボーッとしていた。日付が変わったあたりで気合を入れ、とりあえず酒瓶を捨てた。

僕の「おすすめのなろう小説まとめ」を見ている人がいるらしい。最近更新していないなと思ってざっと眺めているうちに、うっかり1作読み始めてしまった。「比企谷八幡 「・・・もう一度会いたかった」」の中盤から終盤にかけてを再読した。かなり面白い逆行モノ。巻き戻る前に身につけた能力を活かすタイプの話が好きである。なぜか逆行転生と言ってしまいそうになるが、転生するか転移するか憑依するかは様々であるため、「逆行」とのみ言うほうがよさそうだ。ネット小説を検索するときもそうするべきかもしれない。

syosetu.org

kotatsugame.hatenablog.com

その後朝方まで日記を書いて、午前6時過ぎに布団に入った。窓の外を見ると雪がうっすら積もっており驚いた。まだ原付のタイヤ交換をしていない。去年はそもそも原付に乗らなかったので交換しなくても問題なかったのだが、今年はゼミに行くのでちょっと考える必要がある。それとも、週に1度ならウン千円払うほどでもないだろうか。

布団でラノベを1作読了。「西野 ~学内カースト最下位にして異能世界最強の少年~」8巻。7巻を読んでから15ヶ月経っており、内容をあまり覚えていない。前に読んだとき、下のようなことを日記に書いていたが、直後に放り出してしまった。相変わらず設定は面白いが読むのがつらい。主人公の言動が見ていられないのと、登場人物の行動原理が全部性欲絡みなのが肌に合わない。しかし設定は本当に面白いのである。

4巻で止まってしまったのは、そのときは主人公の扱いのあまりのひどさに辟易してしまったからだった。今はまた面白いと思って読んでいる。9巻まで出ていて、ちゃんと全部買ってあるので、今度は一気に読み切りたい。なんだか自分の中で評価が定まっていないので、またいつ放り出すかわからない。

週記(2020/09/07-2020/09/13) - kotatsugameの日記

読み終わったらちょうど午前10時半だった。HTTF2022本選のオープンコンテストに出た。

HACK TO THE FUTURE 2022 Final (Open Contest) - AtCoder

rFまたはlFを連打した後、まだ行っていないマスであって最も少ない操作回数でたどり着けるものに向かう、ということを繰り返し、しばらく1位に立っていた時間帯もあった。最後に、ループに入ってからもしばらくrFやらを連打しておくことで後の移動回数を少なくするというものを提出し、11064913点。正午過ぎに出したこのスコアはそのとき3位だった。

午後0時半就寝。

12/18(土)

午後9時起床。マラソンが終わっていた。

寝る前の提出は40位まで落ちていて、一位は僕の5倍以上の点数を出しており、非常に驚いた。ちょっとTLを見た感じ右手法と左手法を繰り返すのがよかったらしい。それぞれRllFLrrFである。自分はRlFLrFを試して、全然よくならなかったのを見てやめていたが、それは右手法でもなんでもなかったのである。

午後10時5分からTROC #24に出た。前回#22に出てからおよそ3か月ぶりのようだ。

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

Aはよい。Bは全然わからなくて焦るが、符号の変化だけ見てみると高々2種類しかないことに気づけた。Cは左から貪欲に10に変えるか、右から貪欲に01に変えるのがよいとわかるので、左右それぞれ何回操作するかを全探索した。

Dは結構面白かった。ある範囲に存在する辺の本数は、使われている頂点数に、その範囲の境界を跨ぐ辺の本数の半分を足したものになる。このことは、境界を跨ぐ辺をペアにしてループをたくさん作るとわかる。N\times Nのマスを適当に2分割してそれぞれ聞くと、その答えの和から全体の辺数N^2-1を引くことで境界を跨ぐ辺の本数がわかり、この情報から2分割されたどちらに使われなかった頂点が存在するかわかる。あとは縦横それぞれ二分探索すればよい。

E1は、移動中の各マスに対して隣接しうるマスを列挙し、それぞれどの移動のタイミングで隣接しているかを求めた。これは区間になっていて、対応する頂点も区間になるため、imos法で足せる。E2はかなり悩んだが、先ほど求めた情報から各移動ごとにどの人にどれだけ寄与するかを差分更新で配列に持ち、実際にO(NQ)かけて足したら間に合った。実際、配列を別の配列に足すような形で書けるので、ベクトル化がかなり効くのだろう。

E2まで解いて9位、レートは2596→2651(+55)と最高値を更新した。E2の公式解説はbitset解だった。確かに、マスに対して何回目の移動で隣接するかを考えれば、shiftとcountで計算できる形になるようだ。一方、僕のような方法もベクトル化が効いて通るということが言及されており、なかなか攻めた出題だったと感じる。

TROC直後からECR119。コンテスト終了時点で全完2位である。

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

AはNが1つだけかどうかを判定する。Bはやるだけ。Cは連続する*を何個のbに変換できるかで置き換え、後ろが何通りあるか見つつ先頭からbを増やしていくというもの。実は後ろからxのあまりを取りつつ求めることもできたようで、そちらはかなり頭が良いと感じる。Dは最大値で場合分けで、最大値を3で割ったあまりが0か2なら簡単、1の場合は3+1を除けば2+22+1+1を判定する必要があって、それだけは実際に試してみた。Eはクエリを後ろから見ればUFすら必要なかった。

Fは、二部グラフに分解した後を考えると、同じ側に属する頂点たちの間に辺が張られていないという条件から、並べたときに単調増加になっているとわかる。つまり単調増加列2つに分解できればよくて、これは末尾の値の組として(-p,\ast)(+p,\ast)の2状態を考えたとき、それぞれ\astに適する最小値を持つdpで計算できる。Gは包除原理をゼータ変換で行うだけ。

Fで2^{23}\times 26要素のint型配列を宣言したのだが、これをvectorで行ってMLEしたという話を見聞きした。グローバル変数でないと持てないようだ。通常のローカル変数宣言だとスタック領域に取られて、それだと当然ダメなのだが、vectorは調べるとヒープ領域に取られるらしく、そちらでもダメであるというのはびっくり。グローバル変数は先の2つとも違う静的領域に取られるが、それぞれどのくらい違いがあるのだろうか。

朝までずっと日記を書いていた。布団に入って、金曜日の日記に書いたように「逆行」タグでハーメルンを検索し、見つけたものを読み始めた。これがかなり面白く、そのまま正午過ぎまで読みふけっていた。午後0時半就寝。

12/19(日)

午後8時半起床。かなり眠く、布団で10分ほどゴロゴロしていたが、この10分のせいでせっかく弁当を温めたのにABC前に食べきれそうにない。手を付けないまま放置して、午後9時からABC232。

M-SOLUTIONS Programming Contest 2021(AtCoder Beginner Contest 232) - AtCoder

Aはどう縮めたものかわからずとりあえずPerlで出したが、dcでただ?と読み込むだけでよいことに気づいて出しなおした。以降はC++。Bは先頭の差を見て、残りと一致するか確かめた。Cは順列を全探索。Dはやるだけで、400点である意味が分からずちょっと怯んだが何事もなく通った。Eは難しい。縦と横にそれぞれ何回動かすか全探索かと思って適当に書いたが合わず、細かく係数を考えているうちに4通りの状態を持つdpを思いついた。Fは順当にbitDP。

Gは難しかった。まずB_iの値でソートしておく。今ある頂点iにコストcでたどり着けたとすると、A_i+B_j\ge Mなる最小のjを取って、k\lt jに対してはc+A_i+B_kk\ge jに対してはc+A_i+B_k-Mで移動できる。dijkstraっぽく考えれば、とりあえず今興味があるのはk=1,jのみであるとわかるためそれを優先度付きキューに入れて、さらにk=i+1も入れるとよいだろう。コストを更新する必要があって、範囲chminに見えて面倒そうだが、逆転の発想で1点更新区間minによって取得できる。範囲k\dots Nに対してchminするのは、インデックスkに値を入れて範囲1\dots i区間minで取得するのと同じということ。実装上はまだ到達していない頂点をsetで管理して、k=1,j,i+1の代わりにそのlower_boundを使ったりしていた。

kanpurinさんのユーザ解説を読んで知ったが、これはそのままグラフを陽に作成してdijkstraできる。iからは1,j,i+1にそれぞれ辺を張り、コストは先ほど述べたものと、i\rightarrow i+1に対してはB_{i+1}-B_iを割り振るとよいようだ。正直自分のコードの計算量解析もよくわかっていなかったが、このことからそうひどいことにはならないと予想がつく。

Hを読んで、嫌そうに見えたのでしばらくBコードゴルフをして、戻ってきたら解けた。残り15分程度でそこそこ重い実装になりちょっと絶望していたが、書いてみると結構すんなりいって、しかも一発で通った。問題文中の「この問題の制約下において解は必ず存在することが証明できます」が肝で、ならば問題の制約を崩さないようにマスを狭めていけるのではないかと考えた。実際、縦と横がそれぞれ3マス以上存在するとき、左上からスタートして左下に行き1マス右に進むルートと、右上に行き1マス下に進むルートのどちらかは必ず通行可能である。そしてどちらも縦または横を1マス狭めつつ、適宜回転・反転することで左上からスタートする状態に直せるため、再帰的に解ける。あとは縦または横が2マスの場合のみで、これも適当にひっくり返すと縦が2マスと決め打ってよく、ここまで絞れば十分場合分け可能であった。

全完12位。学生6位に見えて絶望。Hを見ていったん絶望するフェーズが完全に要らなかった……。

コードゴルフ。Aは速度で負け、意気消沈。僕の1回目の提出から7秒後に最短コードが出ているので、無難にPerlを投げた時点で負けが確定していたようだ。どうせ迷った時点でFAは取れないのだから、落ち着いて考えてみるべきだった。BはRakuで書いたらVimに負けた。CはRubyで、負けたかと思ったがto_ihexに変えて縮め返した。1桁の整数ならhexで読んでも変わらないというのは久しぶりに見るテクな気がして、どこかに縮め忘れているものがあったような感覚があり、恐ろしい。DもEもRubyで、Eは縮められてしまったのでVimに移ってまた少しバトルし、今のところ最短を保持している。VimRubyコードを書くと縮むのはいいのだが、普段のコードゴルフと全く別のことをしている気がしてかなり疲れる。Fはすでに提出されていたRubyコードを眺めていたが縮まず、以降は手付かず。

午後11時半からCodeChef、December Cook-Off。いつの間にかSnackDownの最終予選の結果でレートが変わっていて、2463→2571(+108)と赤になっていた。たった3か月、6回のコンテストでたどり着けてホクホク。

https://www.codechef.com/COOK136A

BINSTRGAMEは、隣り合う文字が同じ位置を1か所か2か所選んで消すという操作に言い換えられるので、1手で1個か2個石を取れる1山のNimになる。考察自体は一瞬で終わったが、典型の積み重ね、それも思いがけないところからゲーム問題に飛ぶもので結構面白かった。RGBCONSTはしばらくいろいろ試していたらR+G\ge Bで構成できることに気づいた。Bと何かをペアにして、RBGBを1つつないだ後、残りのRBは先ほどつないだGBにつなぐ。逆もそうである。この条件の必要性は、ある頂点に直接つながるBが2つ以上存在できないことから言える。

BREAKBALは、どれか1文字だけを動かすのが最適ではないかとかいろいろ考えていたが、結局やりたいことはある区間に存在する')'をできるだけ前に持ってくることで(中途半端な位置で止めるくらいなら動かさないほうがマシ)、必要なだけの')'が用意できる区間は尺取り法で求められ、各区間での操作回数は01列の転倒数になるためセグメント木に乗る、ということで操作の最適性を考察する必要性はなかった。DESTRUCTは3山くらいまで手で試した感じ1の個数が重要そうで、その情報を持って実験を回そうとしたとき、そもそも山の個数が1000以下なのだから全部計算できるということに気づいた。ちなみに実験結果には規則性があるようだった。1の個数だけで決定できるかは示していないが、投げたら通った。残り時間はANGSPLITを考え続けて終了した。

4完42位。ANGSPLITが解けなかったのが痛い。前回SnackDownのときは40位で入赤したので平気だろうと思っていたが、今回は強い人が少なかったのか2571→2516(-55)となってしまった。レートの変動幅が大きすぎる。赤になるのが速かったのも、このvolatilityの高さが原因だろう。次回失敗したら赤から転げ落ちてしまうようだ。なかなか気が抜けないコンテストサイトである。

TCB43が終了していた。12位だった。賞金圏内から転げ落ちてしまった。1ペナさえなければと悔しい思い。それにしても10問目を解いた人が6人もいて驚きである。へのk氏から「高度知識ではない」という助言をもらったが、コンテスト中に考えているうちに自力では解けないと屈服してしまったので、解説が公開されたら読むようにしたい。

昨日布団で読み始めたハーメルンを読了。「クラップスタナーは2度鳴る。」。暗殺教室の二次創作で逆行モノである。非常に面白かった。原作前、本校舎での話は、原作で描かれた描写を深堀りしてそれっぽい設定がいくつも付け足されており、読んでいて感心した。また主人公のチートっぷりも好み。

syosetu.org

暗殺教室は漫画を全巻持っている。文章を読むと、その場面のコマが思い出せたりして、かなり懐かしい気持ちになった。しかし漫画の表現によるギャグを文章で再現するのは難しそう。ほぼ同じコマが2つ続けて描かれて、2番目のコマではキャラ達が殺せんせーの超スピードにより奇抜な格好をさせられるというギャグがたびたび登場するが、文章ではうまく切れ目を作れていないように感じられた。

しかしそれにしても、浅野学秀というキャラはこんなに印象が良かったのか。登場時は純粋な敵キャラだったが、原作でもたびたび描かれ、だんだん彼の人となりというものがわかってきて、卒業式における行動で決定的に味方になったという記憶がある。まあそれにしてもこの作品ではデレすぎに見えるが、二次創作なので全く問題ない。こういう浅野学秀も好きだ。

逆行モノを探していたはずが、暗殺教室の面白さを再発見してしまった。さらに1作、「『暗殺教室RPGRTA 殺せんせー札害チャート」を読了。RTA形式というのはハーメルンに特有の形態だと思っていて、文章になった淫夢語録がちょっとキツくて敬遠していたが、それはそれとしてかなり面白かった。もしかして、RTA走者の軽薄な描写と、それを原作キャラの視点から見るギャップを楽しむものだろうか?そういう第3者視点で主人公の凄さを語るシーンは僕の好みのものだ。勘違いモノとかもそういうシーンを楽しみに読んでいる向きがある。

syosetu.org

yukicoderのテスターを1件行った。

本当は12/20の夜まで起きているつもりだが、このあたりで日付を区切っておく。今週水曜日は遠慮なく消し飛ばしたのに来週月曜日は消し飛ばさないのか、という非対称性はあるが、週記という性質上仕方のないことである。

今年読んだ本のまとめ

はじめに

このブログ記事は、ととりにゃあ Advent Calendar 2021の14日目のために書かれました。嘘です。本当は自分が書きたかっただけです。

adventar.org

今年はまだ2週間ちょっと残っていますが、以下では「今年」を「2021年の01/01から12/14(記事公開予定日)まで」として取り扱います。また既刊等の情報もすべて12/14時点のものです。

統計情報

今年はちょうど150冊読みました。

月ごとの読書冊数

f:id:kotatsugame:20211214014524p:plain
月ごとの読書冊数

12月はともかく、4,6,10月にあまり本を読めなかったのが気になります。当時の日記を見返していたところ、ネット小説を読みふけっていたようでした。特に6月いっぱいを費やして1300万文字くらいあるネット小説を読んだのが効いています。またそれ以外の月も多かれ少なかれネット小説を読み続けてはいて、そちらに手を出す前の2019年と比べて1年の読書冊数は半分程度になりました。

レーベルごとの読書冊数

「一般書籍」とは「ラノベ以外」を指します。ここで言うラノベは、「そのレーベルから出版されるほとんどの本にイラストページが存在する」ことで定義します。また、「ラノベ単行本」とは、ラノベであって文庫本サイズでないものです。そういう判型のラノベを出版するレーベルは複数ありますが、まとめています。

以下、各レーベルのリストです。

f:id:kotatsugame:20211214232731p:plain
レーベルごとの読書冊数

ファンタジア文庫は常に強いです。僕自身追っているシリーズが大量にあると認識していますし、新シリーズも気になるものばかりです。他にはHJ文庫オーバーラップ文庫GA文庫も気になるものが増えてきたかなという印象です。一方、ファミ通文庫は一時期毎月のように新刊を購入して読んでいたのですが、最近はそもそも出版される本が少なくなってしまいました。

印象に残っている本たち

今年読んだ本(のシリーズ)の中で、自分にポジティブな印象を強く残したものを取り上げます。実質おすすめのラノベまとめです。

クラスの大嫌いな女子と結婚することになった。(既刊3巻)

主人公がなかなか超人的で、ヒロインはそれに対抗心を燃やしていがみ合っていたのですが、その2人が親の言いつけによって結婚させられたところから始まる話です。基本的に馬が合わない2人で、結婚生活も初めはギスギスしてうまくいかない中、シリーズを通して徐々に徐々に歩み寄っている様子が見られ、微笑ましいです。また、ヒロインは勢いで結構なことを口走ったりしますが、それに対する主人公のテンポの良いツッコミが印象的です。

継母の連れ子が元カノだった(既刊7巻)

中学生の時に1年間だけ付き合っていた主人公とヒロインが、高校生になって両親が再婚した時の連れ子として再開する話です。ヒロインが高校入学を機にイメチェンし、以前とはまるきり変わった環境ではありますが、そんな中で中学生の時のことを思い出したり後悔したりしつつお互いへの好意を再確認していく模様が微に入り細を穿って描かれ、その慎重さが甘ったるく感じられます。2人とも読書家という設定です、そのあたりのオタクっぽい描写に力が入っていて、会話の中で一般書籍の名前など挙げられているのに気を惹かれます。

暇人、魔王の姿で異世界へ(既刊12巻、完結済み)

オンラインゲームで育てたキャラクターに乗り移って、ゲームの世界で無双する話です。またゲーム時代に共に遊んでいた関わりの深いプレイヤーも数人ゲーム世界にいるようで、なぜか乗り移った時間が大きく異なるらしく、先にゲーム世界に入って高い地位に上り詰めた友人たちを探し、彼らの抱える問題を、いまだ無名であるという自由な立場から解決していくという流れでした。普段は温厚な主人公ですが、仲間が苦しめられている場合はその力を振るうことを厭わず、その快刀乱麻を断つような様が爽快でした。

魔王2099(既刊2巻)

魔法文明にて圧倒的な強さを誇った魔王が滅び、機械の発展に伴い荒廃した世界に復活するという話です。まずもって世界観の精密な描写に圧倒されます。魔法と機械が融合し、そこにサイバーパンク的な要素も加わった設定に忠実に、街の風景はもとより人々の活動、製品、食べ物に生き物などもそれらしく描かれ、実際にネオンサインあふれる大都市にいるかのような臨場感が味わえました。最初は常識の違いに苦労する魔王ですが、だんだん適応していって、しっかりファンタジー的な魔法でその強さを見せつけてもくれます。

りゅうおうのおしごと!(既刊15巻)

最年少で竜王位のタイトルを獲得した主人公と、弟子の2人や師匠の一門など周りの人との関係と成長を描く将棋ラノベです。各巻で対局のシーンはどれもお互いの想いがぶつかり合う熱い戦いが見られますが、個人的には5巻いっぱいを使って行われた竜王位防衛戦が大好きです。秒読みに突入し極限の状況にある主人公の思い、苦しみ、その中でも燃やし続ける闘志が文章から伝わってきて、泣きながら読んでいました。

最近、藤井聡太竜王の四冠記念で4巻まで期間限定で無料公開されていました。もし五冠を達成したら5巻まで無料公開されるのでしょうか。そこまででもぜひ読んでほしいシリーズです。

現代社会で乙女ゲームの悪役令嬢をするのはちょっと大変(既刊3巻)

現代人がバブル崩壊直後を舞台にした恋愛ゲームの悪役令嬢に乗り移り、そのままでは衰退していく実家やさらには日本経済を救うため、未来知識を使って奮闘する話です。幼い主人公の身に合わぬ活躍、それも政治・経済・エンターテインメントそれぞれの場での活躍が、読んでいて気持ちいいです。

お隣の天使様にいつの間にか駄目人間にされていた件(既刊5巻)

同じマンションの隣同士の部屋で一人暮らしをしていた主人公とヒロインが、ふとしたきっかけで関わりを持ち、互いに惹かれていく話です。もともとヒロインは学校でもあまり親しい人を作らず、周りの人と一線引いた立ち位置にいたのですが、主人公の誠実な態度に絆され、だんだん甘えるようになります。そのような可愛らしい姿に射抜かれつつ、何とか取り繕う主人公の内心にもニヤニヤできます。

ちなみに、「隣同士の部屋に住む主人公とヒロインの交流」を描くシリーズは他にもあって、僕はその設定が好みなのでどれも印象に残っています。以下に2シリーズ紹介します。

氷の令嬢の溶かし方(既刊2巻)

こちらは主に主人公が料理を作る側なのが特徴的です。ヒロインが甘えるというよりは主人公が甘やかすほうをメインに描かれていて、それに対してヒロインが喜んでいる姿を見てこちらも満足した気分になりました。

隣のクーデレラを甘やかしたら、ウチの合鍵を渡すことになった(既刊3巻)

これは結構早い段階でお互いがお互いへの好意を自覚し、その後徐々に距離を詰める様が微笑ましいです。また、そのような関係を周囲に隠してはいるのですが、それでも無意識に出てしまうような行動の描写が琴線に触れたのを覚えています。

時々ボソッとロシア語でデレる隣のアーリャさん(既刊3巻)

誰にもわからないと思ってロシア語で主人公にデレまくるヒロインと、ロシア語が通じるので全部聞こえつつ、バレないように表情を引き締めようと努力する主人公の話です。実はこの主人公、ロシア語が通じるほかにもなかなかハイスペックで、生徒会長を目指すヒロインをサポートするのですが、ほかの候補者との知略を尽くした選挙戦が手に汗握るもので面白いです。

D級冒険者の俺、なぜか勇者パーティーに勧誘されたあげく、王女につきまとわれてる(既刊2巻)

過去に勇者を目指して努力を積み十分な能力を手に入れつつも、想像との違いから勇者となるのを止めてしまった主人公が、その能力に目を付けたヒロインたちに追われつつ、問題を解決していく話です。主人公最強モノで、物語の展開としては今のところ特徴的なものはないと記憶していますが、軽い筆致のセリフが心地よく楽しめたので、良い印象が残っています。

VTuberなんだが配信切り忘れたら伝説になってた(既刊2巻)

清楚系キャラとして登場しつつも配信切り忘れによって破天荒な本性が露わになった主人公の、周りのVTuberともコラボしつつワイワイと進行する配信の様子をメインに描かれる話です。配信に付くコメントにはネットミームが多く含まれ、文章的に読む人を選ぶと感じていますが、主人公たちがとにかく楽しそうに配信をしていて、読後感がかなり良いです。

サベージファングお嬢様(既刊2巻)

魔法が使えないながらも対人戦闘の技量で傭兵として名を馳せた主人公が死に、時代を遡って悪女として名高かった令嬢に乗り移る話です。傭兵時代の技量と、乗り移った体が持つ膨大な魔力を元に、そのままでは国が崩壊してしまうという歴史を変えようと奮闘します。普段令嬢として完璧なふるまいを見せつつも、戦闘時には傭兵時代の性格が表に出るギャップが面白いです。

日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人(既刊1巻)

謂れのない悪評を流されて学校で孤立していた主人公が、日本語がまだ得意でないヒロインが転入してきたのを機に複数言語を操れるなどのハイスペックぶりを見せつけ周囲を見返す、いわゆるざまあ系の話です。主人公は本当にいろんなことができるという設定で、その多才さが読んでいて楽しかったです。もちろんざまあ系ですから周りのキャラの描写もこちらのヘイトを向けるようなもので、それを見返す描写には正直爽快感を感じました。

サイレント・ウィッチ(既刊2巻)

圧倒的な才能を持ち、国で最強格の魔女でありながらもひどい人見知りの主人公が、学園に生徒として潜入して国の王子を護衛する任務を何とかこなそうと頑張る話です。引っ込み思案で小動物のような描写をされる主人公の可愛らしさと、その才能を遺憾なく発揮して問題を解決するかっこよさの二面性が魅力です。文章のテンポもよく、作中世界に引き込まれて主人公を応援しているような気持ちになりました。

かくりよの宿飯(既刊11巻、完結済み)

祖父が残した借金の形として幽世の鬼神に嫁に取られそうになった主人公が、代わりに食事処を開いて稼ぎ返済しようとする、という導入の話です。度々問題に巻き込まれる主人公が、これまでに築いてきた信頼関係と幽世にはない現世風の新たな料理を武器に解決していく中で、鬼神との関係も徐々に深まるのですが、主人公は鬼神に絆される側であり、その視点から描かれる心情が楽しめました。

お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について(既刊2巻)

タイトルの通りにお見合いをした主人公とヒロインですが、ヒロインに隠された事情を見抜き、ひとまず交際を始めます。そのように戦略的に始まった交際でありながら、だんだん惹かれあう2人の姿が描かれます。この作品が特徴的だと感じているのは、2人の実家が家格という概念が存在するくらいの名家であることで、しかも家格は主人公のほうが高いので、周りから政略結婚のように見られているようです。もちろんお見合いをしたのですから家は結婚に納得していますが、周囲の人の印象が問題で、そのような恋の障害がありつつ2人がどのように進展していくのか気になっています。

転生ごときで逃げられるとでも、兄さん?(既刊2巻)

上で紹介した「継母の連れ子が元カノだった」の作者の別作品です。もともと主人公には病んでいる妹がいて、現実世界で歪んだ愛を受けていたのですが、これがファンタジー世界に転生しても続くという導入でした。妹は兄に逃げられたと感じ、転生してからは正体を隠して機会を伺っているのですが、主人公もそれを知っており、負けないように仲間を集めたり自分の能力を磨いたりして強さを追い求めます。単純なバトルシーンも効果的な見せ場が用意されていて読んでいて熱中するものですが、それ以外にもミステリ風味な頭脳戦が散りばめられていて、妹の正体を知らされていない自分も主人公と一緒になってドキドキできます。

天才最弱魔物使いは帰還したい(既刊2巻)

作中世界に数多ある種族の中でも最弱とされる種族の主人公が、他者を使役する魔物使いという職業を得て最強になる……なった後の話です。こう書くと使役する者の強さを借りているだけに思われて、もちろんそれがないとは言いませんが、主人公は肉体的にこそ最弱な一方、精神面を鍛えに鍛えてまさに最強の名にふさわしいものであったとわかります。実際、1巻では身一つで遠く離れた街に転移してしまった主人公が、その知略によってまた名を立てる様子が描かれます。肉体と精神のアンバランスさ、また極端に生き急ぐ性格が主人公の魅力で、特に2巻では人智を越えた洞察力を見せつけられ、終盤はハラハラしっぱなしでした。

灰原くんの強くて青春ニューゲーム(既刊1巻)

高校デビューに失敗し灰色の青春を過ごした主人公が、大学4年生も終わるぐらいで高校入学直前の自分に乗り移るところから始まる話です。前回の失敗を糧に自分を磨き、また他の人より7年分多い人生で培われた能力もあって見事無自覚ながらハイスペックになった主人公が、読んでいていい気分になれます。また人間関係を壊さないようにと慎重に行動する主人公の視点では、何気ない学校生活の中にも微妙に緊張感があり、ただ無双するだけではない面白さがありました。

今年買った本について

上で、今年読んだ本のレーベルごとの冊数を見て僕が注目しているレーベルについて話をしましたが、どちらかというと購入した本のほうがよく特徴を捉えているかもしれません。月ごとの購入冊数とレーベルごとの購入冊数もまとめてみました。今年購入した本は249冊でした。

f:id:kotatsugame:20211214232415p:plain
月ごとの購入冊数

3月は地元の古本屋で豪遊した月です。8月も豪遊というほどではありませんが、古本屋で「かくりよの宿飯」シリーズを大人買いしました。あとはその月に出た新刊を逐一購入しているくらいです。

f:id:kotatsugame:20211214235950p:plain
レーベルごとの購入冊数

よく買うレーベルとよく読むレーベルは、当たり前ですがおおむね同じになりました。それにしてもMF文庫Jは積みすぎですが、これは途中から読み損ねている人気シリーズがどんどん新刊を出し、前の巻を読んでいないのにただ買うという行為を続けているからです。

データ元

kotatsugame.hatenablog.com

kotatsugame.hatenablog.com

週記(2021/12/06-2021/12/12)

12/06(月)

先週は週記を投稿したあと比較的すぐに布団に入った、のだが、うっかりラノベを読み始めてしまった。結構終わり際で読み止しにしていたもので、そのまま読了。

「天才最弱魔物使いは帰還したい」2巻。今巻も非常に良かった。先週も書いたが、なろうでは読み落としていた伏線を探しつつ丹念に読んでいた。僕は槻影さんの書く文章やキャラクターが好きだし、中でもこの作品の前身となる「Tamer's Mythology」がハチャメチャに好きなので、他のラノベを差し置いてもこれはじっくり読みたかったのだ。と、まあいかにもわかっている風に書いたが、思い返してみればそれほどクリティカルな描写はなかったかもしれない。しかし、結末を知った状態で改めて主人公フィルの行動を眺め渡してみると、なるほどかなり初期から真相に気付いているらしき行動をしていたのだなとわかる。

あとは、登場する情報屋について。元の「Tamer's Mythology」でも《明けの戦鎚》の面々がフィルの正体を聞きに行ったのが初出だった。僕はこの部分がか!な!り!好きである。これはもともと1巻の範囲の出来事だったのだが、改稿後の1巻からはその描写が消えていて、ひどくがっかりしたのを覚えている。今、2巻にて改めて回想という形で語られ、非常に満足している。

『L等級のLは……Legend《伝説》のLなんだぜ』

https://ncode.syosetu.com/n4224gn/92/

読み終えて、さらにハーメルンを開いて読み進めようとした段階で寝落ちした。午前9時だった。

午後4時半前に起床。即座に進捗報告スライドを錬成し、定例会に臨む。結局、先週は見事に一文字もコードを書けていない。業務をやっていたつもりなのでそれで何とか「仕事してる感」を醸し出そうとしたが、冷静になると質問事項のやり取りに結構待ち時間が発生したので、その間に十分進められたのだと気づき、愕然。やる気がなさすぎるだろ。

今週も勉強会まで終えて、学食に向かう。今日はこれが一食目となる。このような場合、ミールカードの当日分をできるだけ使うためにも丼モノの小とカレーの中を頼んで腹をパンパンにして帰っているが、今日は丼が中サイズしか用意されていなかった。いけるだろうと思って購入したが……かなり辛かった。今日はまずカレーから攻めて、できるだけ噛まずに飲み込むことで満腹中枢の反応を少しでも遅らせようという戦略で戦った。多少効果があったようにも感じられる。

帰宅して業務を開始する。マニュアルや研修の模様を録画した動画を見つつ頑張っていた。それなりに頑張ると終わりそうな光明が見えてきたが、やはり初めてということがあって判断に迷うこと、通常どのように処理されるのか知らないことが多々あるので、完成はしなかった。どれもそれなりのところで留めて、また明日こそ質問を投げることにしよう。

ACL Practice ContestのSCCが、ACLを使うコードからRubyのトポロジカルソートライブラリtsortを使うものに縮められていた。メソッド名strongly_connected_componentsが長いので、TSort.methodsから配列アクセスで取り出してsendするという、Pythonのnetworkxゴルフテクみたいなことをやっていて面白い。それにしても、このライブラリの設計がよくわからなかった。頂点の子を取得するために「頂点を渡されると、その子を列挙する」というコールバック関数を作らせるのはわかるが、このライブラリはさらに1段階深く進んで「頂点を渡されると、その子を列挙して、これまた渡された関数の引数にして呼び出す」というものを要求している。つまりちょうど、コールバック関数が二段階になっているようなものだ。

と、書いていて気付いた。つまりこれは、Rubyで「列挙」を行おうとしているのではないか?ただ列挙して集めて返すだけだと、いちいち配列オブジェクトを生成することになって、パフォーマンス上の問題があるかもしれない。それで逐一生成させたいので、順当にいけばEnumeratorを返すべきかもしれないが、いちいちブロックを渡して実行するのはライブラリでは行ってくれないので自分でブロックを実行しなければならない、のような感じか?ブロックを我々が実行することになっているのも、これまたパフォーマンス上の問題かもしれない。詳しくはわからない。ちなみに頂点そのものもこのような形で列挙しなければならないので、都合2種類のラムダ式を書いている。

atcoder.jp

夜中からラノベを読み始めた。理由は定かではないが、なかなか読み進められずちょっと苦労した。

午前4時読了。「王立魔術学院の《魔王》教官I」。かなりハリー・ポッターを思い起こさせる学院の描写だったが、当然のことながら内容はそこそこ違う。中盤まではクラスの生徒たちのバックグラウンドが語られて、主人公である教官が問題を解決していく様が心地よかった。終盤にはバトルもあって、教官の強さが遺憾なく発揮されておりこれもまた良い。ラストで意味深に登場した敵キャラの正体が数ページ先で開示されており、びっくりした。それはそれで面白いのか、それとも正体不明の敵キャラが紛れ込む学院生活に耐えられない読者への配慮か。主人公が認めている上級生の一人と敵キャラの特徴が被っていたので、まさか裏切り……と冷や冷やしていた僕にとってはありがたかった。

冷蔵庫の中でぶよぶよになりかけていた梨を剥いて食べた。母が剥いてくれたものの形を思い起こして見比べてみるに、僕は芯の周りを深く切り落としすぎな気がする。どのくらいが不可食部分なのかわからず、とりあえず色が違うところを確実に除去するようにしていたが、実はそこまで神経質になる必要はないのかもしれない。

布団に入って別のラノベを開いたら、午前7時半になってしまった。就寝。

12/07(火)

午後1時起床。

とりあえず質問事項を投げておくか、としたら、そのままずるずると業務を始めてしまい、学食に行くタイミングを逃した。結局午後2時くらいから1時間休憩をとることにして、その間に購買に行って菓子パンを大量購入してきた。また戻ってきて頑張っていたが、単調なくせに細かい作業ばかりが続くフェーズで、かなりつらい。プログラマなんだから何かコード書いてサクッと効率化したい、と思うも、どこからどこまで機械に任せられるのか定かではなく、結局手でやったほうが確実で速いという話になってしまう。しばらくやって、自動チェック待ちの状態に進んだ。なかなか結果が返ってこないようだったので、ここで一息入れることにしてラノベを開いた。

そのまま2時間くらいかけて読み切った。「何と言われようとも、僕はただの宮廷司書です。」。こんなタイトルなのであらすじを読む前から無自覚チート系主人公だとわかり、実際そうだったので満足。自分のことを一般人だと言い張る丁寧語系主人公ということで、かなり「公女殿下の家庭教師」を想起させられるが、そちらより性格が幾分攻撃的になっている気がする。あとは、魔法が上手いとか、ヒロインが王女さまとかも似ている設定。まあこういう設定はいくらあってもいいので、良い。「公女殿下の家庭教師」とは違いこちらの主人公はより明確に強いので、読んでいて安心感はあった。ヒロインの挙動もより僕の好みに近い。

PCの画面を見るとまだ自動チェックの結果が返ってきていなかったが、リロードすると見れた。それを使ってさらに進めていたのだが、ほとんど終わり際になって、またわからないところが発生してしまった。実は今日が期限のタスクなので、どうしよう……という感じ。とりあえずできているところまで報告して、自分の誠実さをアピールすることにした。期限をぶっちぎっている時点で誠実さも何もないのだが。もう本当に自分がどうしようもない。見通しが甘すぎる。

KUPC2021でチームメイトに任せたっきりの問題から1問、C問題を解いた。かなりややこしい解き方をして合わせるのに苦労した。

C - Gacha

最適解は1\dots N区間に分かれ、各区間ではコインを全部拾ってからガチャを全部回すことになるだろうという予想を立て、「左からi枚のコインを拾って左からi個のガチャを回した」ときのコスト(をちょっと変えたもの)でdpをした。遷移はj\lt iからiまでのコインを一気に拾って、その後j+1のガチャに一直線に向かい、次に「コインiの位置に」帰ってくるまでの距離を足すことになる。ガチャiの位置に向かってしまうと、区間から外れるコインを拾ってしまう可能性があり、コスト計算の絶対値を外す関係上よくない。

さて、コストは行って・戻って・行っての絶対値3つで書けるが、このうち1つは絶対値記号を単純に外せる。残り2つ、|B_i-A_j|+|B_i-A_{j+1}|をどうするかが問題だが、A_jA_{j+1}B_iの大小を見るとうまくいった。A_{j+1}\le B_iのとき、A_{j+1}\le B_{i-1}\lt B_iからそのようなjの値は尺取りで求められる。よってこれに対しては、尺取りと同時に絶対値を外した後のA_jA_{j+1}寄与分を含めた累積最小値を持っておけばよい。A_j\le B_i\lt A_{j+1}のようなjは高々一つしかないので、毎回計算。B_i\lt A_jに対しては、これまた絶対値を外した後の寄与分を含めた最小値を、スライド最小値で管理すればよい。

夜は日記を書いていた。投稿して布団に入り、なろうの更新を確認すると、章の変わり目で投稿が途絶えていたシリーズに閑話っぽい感じの話が投稿されていた。それを読んで、ついでにシリーズ全体を読み返していたら、アッという間に朝になってしまった。午前9時になったので一旦今日の夜に出た質問事項を投げて、やり取りのためにまだ少し起きていようと思いつつ布団に戻ってなろうを読んでいたが、今度は寝落ちしてしまった。閲覧記録によれば午前9時半すぎのことだった。

12/08(水)

午後3時くらいに目を覚ます。Slackを見ると、僕が寝落ちしたちょっと後に質問に対する回答がついていた。やることは分かったつもりだが具体的にどうするのかわからなかったので、その旨返信すると、なんと通話で説明してくださるらしい。相手方の空き時間を提示されたので、1時間後を指定して、恐れ知らずにもまたちょうど1時間寝た。

午後4時、執念の起床。通話開始が少し遅れるらしく、その間パソコンの前に座っていていろいろ確認していたら、少し眠気も取れてきた。30分ほど指南を受けつつ操作を行い、その後も少し取り組んで、ようやくマニュアルにある工程をすべて終わらせた。タスクのステータスを最終チェック待ちにして、これでひとまず終了だろう。結局期日は1日オーバーしてしまった。社会人にあるまじき醜態。猛省。

学食に行った。今日もフードファイトで、ヒレカツカレーの中を2皿。ほぼ咀嚼せず10分で流し込んだので、辛さ(からさではなくつらさ)は月曜日ほどではなかった。しかし食べ終わってみると、まさに腹に一物(物理)があるような感じがしてちょっとまずい。無理はするものではない。

夜、いよいよゼミ準備を始める……前に、火曜日のPythonの講義で出ていた課題を終わらせた。これは今週も、講義スライドに出てきたコード片をサンプルコードと組み合わせたビジュアライズを追加するくらいで終了。

とりあえずほかの人の発表資料を読み返そうとしたが、前回の発表者が残している部分はアップロードされていなかったし、教科書を見ると分量的にもかなりあるようだったので、その部分はばっさり放置してすぐ自分の担当箇所を読み始めることにした。幸い章の変わり目にあたり、内容的にもパッと見前章の内容は関わってきていないため、何とかなりそう。途中集中を切らしつつも、とりあえず30分くらいは喋れるかなという分量の準備ができた。今日はこのくらいにしておこう。

Twitterでnullさん(競プロer的にはstoqさん)のブログが流れてきたので読んでいた。大変に面白かったのでスターをつけまくって、Twitterに戻ってみると、すでに投稿ツイートのRT数が20を超えており、他の人も面白いと思っていることが分かってうれしくなった。

null-mn.hatenablog.com

午前3時からラノベを読み始める。面白すぎて途中で切り上げることができず、しかも結構丁寧に読んでいたので、読了したのは午前8時半だった。

「時々ボソッとロシア語でデレる隣のアーリャさん」3巻。非常に良かった。1巻も2巻も良くて、このシリーズがすっかり好きになっていたので、丁寧に読んでいたというわけ。カバー折り返しにある著者コメントでは自信のない様子を見せている筆者だが、毎巻毎巻間違いなく面白いストーリーを作ってくる。そう、そもそもストーリーが面白いのである。ロシア語要素やデレ要素は僕の認識ではスパイスでしかない。

この巻は主人公政近の妹に焦点を当てた巻。2巻で登場した妹の従者も絡めて和気あいあいとしていたが、そこはやはり生徒会長を目指すうえで戦う敵ということもあり、終盤はバチバチバトルしていた。2巻のバトルとは違い、中学時代に仲間同士だったこともあってお互いの手は知れていて、搦め手もあってドキドキした。このシリーズでは主人公がロシア語を扱えることや、妹が妹であることを周囲に伏せて進んできている。ネタバレにはなるが、終盤でそのうちのほんの少しが明かされ、思わず震えが来た。

毎巻ラストの見開きイラストには訳なしのロシア語が書かれている。1巻は適当にググったのが正解で、2巻はスルーしたが、3巻ではロシア語で使われる文字の一覧からコピペして翻訳に掛けてみることにした。「с удовольствием」であった。なるほどなあ、という感じ。またネットで検索すればこれまでの巻のロシア語の訳も出てきたので、思い返してニヤニヤしていた。

午前9時前に攻めの就寝。3時間くらいで起きればゼミに間に合う。

12/09(木)

午後1時、ゼミの友人からのモーニングコールで起きて血の気が引いた。遅刻である。かなり急いで山に登ったが、30分程度遅刻した。教室に入って一息ついた段階で、途中で購買で買ったパンを食べようと思ったら、先生に止められた。僕はその時、本当にそのタイミングでパンを食べてよいと考えていたが、後から思い返してみれば普通の講義中でも食事をしてはいけなかったような気がする。長いオンライン授業生活で何もかもを忘れてしまった。

耐え切れずリプライツリーに書いたが、改めて言語化しておこう。最初は久しぶりに叱られて凹んでいただけで、あまり真剣には考えていなかった。教室の空気みたいなものも感じ取れていなかったが、どうやらそれなりに重い空気になってしまっていたらしい。そのことに全然気づけていなかった、ということにまず愕然とした。これは自分が空気を読めなかったと取れて、人間関係に関する能力の低さを暗示している。さらにそのような真剣味のなさから、ゼミ後に改めて注意された時も先生の意図をわかっていない反論を繰り出してしまった。これもまずかったらしくて追加ダメージ。

発表については、今週も前の発表者が終わらなかったのでまた来週。数週間前、筆が乗って大量に準備してしまったらしい。思う存分やってほしい。ゼミ後は今週も部屋を移動してボドゲ。今日はディクシットとスカルをプレイした。ディクシットは僕自身はいいとこナシだったが、友人の一人がありえないくらい正解してポイントをガンガン稼いでいてびっくりした。自分ひとりだけ正解して残りの人は自分の出したカードに騙される、という最も1ターンの点数が高くなる状態を何度も達成して本当にすごかった。スカルは良くもなく悪くもなく。今日はみんなイケイケでチャレンジをしていたので、ブラフはそれなりに成功していた。これまで何週間かやってきた結果、場にあるすべてのカードをめくるのが勲章みたいになっていて、みんな積極的に狙っていた。

さて、僕が叱られているのに真剣味がなかったという話を上で書いたが、これはスカルの途中で僕が言及して、周りから得られた反応から分かったことだった。特に発表中だった友人には申し訳ない。重くなった教室の空気にやりにくさを感じたことだろう。自分の空気の読めなさが原因で友人を失うことは避けたいが、人付き合いを今から鍛えるというのも難しい。とにかく慎重な行動を心掛けたいものだ。特に遅刻癖は何とかする必要がある。今日もたくさん目覚ましをかけていたが、起床の決め手になったのはモーニングコールだった気がするので、とりあえず来週もそれをお願いすることにした。そのくらいの仲の良さは、あるはず。

学食で食事して帰宅。年末にその年1年で読んだ本を振り返るような記事は、去年も書きたいと思っていたが、なんとなく怯んでいるうちに実現には至らなかった。今年ととりにゃあアドベントカレンダーを見ていて、それに便乗すれば筆も乗りそうだと感じ、勢いで参加登録をした。ととりにゃあ氏に全く関係がないことは許してほしい。Amazonのほしいものリストを貼るよりは、マシだろうか?

ととりにゃあ Advent Calendar 2021 - Adventar

少しコードゴルフをしてからラノベを手に取ったがあまり集中できず、ネットサーフィンをしているうちに眠気が強くなってきたので、日付が変わったあたりで布団に入った。

すぐにでも眠れるはずだったが、うっかりなろうの読み返しを始めてしまう。そうこうしているうちに眠気が消え、ラノベの続きを読み始めて、そのまま読了。

「ひきこもりの俺がかわいいギルドマスターに世話を焼かれまくったって別にいいだろう?」。キャラクターの設定はよかったし、最後の見せ場もかなり劇的だったが、それ以外は印象が薄い。主人公は最強という設定で、実際あまりにも強すぎてただでさえ少ないバトルシーンがどれもあっさり終わってしまっていた。ヒロインとの絡みがメインだったのだろうかテンポはよかったが、僕が求めていた描写は少なかった。

さらに1冊読了。「灰原くんの強くて青春ニューゲーム」。めちゃくちゃ面白かった。逆行転生モノで、空気が読めず手ひどい失敗をした高校生活をやり直す話。ハイスペック主人公も良いし、それに無自覚なのはさらに良い。そんな主人公が慎重に態度を取り繕ってやり直す高校生活が全部思い通りにいくかというとそうでもないようで、シリーズ全体を通して微妙な緊張感があるのは刺激的だった。ネタバレになるが、その緊張感が膨らんで弾け、ラストに繋がっていく。解決の過程で主人公の慎重さにも変化が出たようで、もし続刊すれば2巻からはまた違った一面が見られるのではないかとかなり楽しみになった。

とにかくかなり良かった。続刊することを願っている、とツイートすると、ふぁぼん氏にすでに決定していることを教えてもらった。感謝。この作者の作品は、先月も「英雄と魔女の転生ラブコメ」を読んだことを覚えている。帯を見て「灰原くんの~」を知り購入を決めた、という経緯があった。そちらも続刊が決定しているらしい。

また別のラノベを開こうとしたが、今読んだものが面白すぎて別のものに手が出ない状態にある。逆行転生モノが読みたい気がしたので、なろうで調べて1作読み始めてみた。半分くらい読み進めて、午前9時半に就寝。

12/10(金)

午後7時半起床。サークルを毎週欠席しており、申し訳なさがある。

実は昨日DMが来て、土曜日の午後に遊ぶ予定を入れたのだが、生協の弁当配達を完全に忘れていた。メールで連絡すれば配達日をずらしてもらえるようなので、月曜日の同じ時間帯をお願いしておいた。

夜はずっと日記を書いていた。本の感想をどう書いたものかわからず、そこでタイプする手が止まりがち。ちょっと読み返してみたり、集中を切らしてTLを眺めてみたりしてただただ時間ばかりが過ぎていった。多分、書評というジャンルの文章をほとんど読んだことがないのが原因ではないだろうか。

読んだ後に自分の中でその本を読んだことによる気分の変化があって、これが正の方向に大きいものを面白いと評価している。また、途中で下に振れたりしていた場合なども、終わりとのギャップがあって印象に残りやすい気がする。それを何とか書き残そうとして、気分の変化の原因を探っているつもりだが、どうしてもキャラ設定や世界観、文章力などの表面的なことにしか目がいかない。ラノベで「著者が読者に伝えたいこと」などの信念が表現されているとは思っていなかったが、そうでもないようで、しかし自分で読み取れているとは思えない。書評ブログをちょっと覗くと、1冊の本で1つの記事を作るくらい感想を書いているので、そこまでではなくとも参考にしたいが……。

今年、これまで5回開催されたCGRによるポイントの集計がCFに投稿されていた。自分は今28位にいるらしい。思ったより高くて震えている。20位以内だとパーカーがもらえるらしいが、さすがに遠いか。

Codeforces Global Rounds 2021: Current Results (GR13-GR17) - Codeforces

なろうを1作読了。「転生リベンジ芸能人ライフ~不遇だったアイドルオタクな青年、謎の死を遂げた推しアイドル少女の命を救うため、二度目の人生で芸能界へ飛び込む~」。昨日読み始めた逆行転生もので、完結済みという設定だったが、実際は章の変わり目で投稿が途切れているだけだった。

https://ncode.syosetu.com/n5160gu/

同じ作者の作品は他にも読んだことがある。そちらも逆行転生モノで、結構面白かった記憶があるのでこちらも楽しみにしていたが、あまり面白くなかった。題材の違いを除けば、どちらも逆行転生して幼少期に訓練を積んだ結果チートスペックを手にし、無双する話であるとまとめられる。よってこの読後感の違いは題材の違いによるものであると考えられる。アイドル活動はもうちょっと真面目にやってほしい、と自分が無意識的に考えていたのだろうか。サッカーものはほとんど読んだことがないが、アイドルものは結構読むので、その違いかもしれない。また、文章中にありえないくらいの誤字・脱字があるのはどちらも変わりないが、ストーリーにあまり集中できなかった結果そちらが目に付いて、さらに悪印象を強める結果となった。

素人おっさん、転生サッカーライフを満喫する 逆行転生にハマってた時に見つけた作品。 https://ncode.syosetu.com/n5399el/

おすすめのなろう小説まとめ - kotatsugameの日記

FHC Tシャツの連絡メールがまた迷惑メールに振り分けられていた。文面の「this link」にリンクが貼られていないように見えてどうしたものかと思ったが、迷惑メール扱いを解除するとリンクが見えるようになった。確かに、迷惑メールにあるリンクは問答無用で無効化するのは対処として正しい。以前Mサイズで注文したTシャツは裾が長すぎた記憶があるので、今年はSサイズで注文した。

キッチンの換気扇をつけると、エアコンからポコポコと水音がし出した。以前にも同様の現象が発生して、その時調べた限りでは、部屋の気圧が外に比べて下がった結果エアコンの排水ダクトから空気が逆流してきているという話だった。実際部屋の窓を開けて気圧を同じにすると水音が止むので、原因として正しいだろう。また、換気扇をつけて部屋の気圧が下がるということは、部屋への空気の引き込みがうまくいっていないとも推測できる。そこで、目につく換気扇のフィルターとエアコンのフィルターを掃除した。ありえない量の埃が溜まっていてほぼ完全に詰まっていたのを頑張って掃除すると、なんと部屋からの「排気」が正常化されたらしく、今度はキッチンの換気扇を止めた状態でもひどい水音が鳴るようになってしまった。仕方がないので部屋の窓を開けて眠ることにした。

外気温と等しい室温の中、布団にくるまってしばらく本を読んでいた。明日は遊ぶ予定があるので、午前7時半就寝。

12/11(土曜日)

正午、起床。あまりにも眠い。

昨日洗って干しておいたエアコンフィルターを戻しておく(換気扇のフィルターはティッシュで拭いて昨日すぐ戻した)。相変わらず窓を閉めるとポコポコ音がうるさいが、水が部屋に逆流してくるとまではさすがにならないだろうと信じ、その状態で放置して出かけることにした。

お互い待ち合わせに遅刻しているようだったので、のんきに神社に参拝などしていたら、先に集合場所にたどり着かれてしまった。今日遊ぶもう1人の家に行って家主と合流し、昼食を摂ってから家に戻って、夜までボドゲ三昧だった。今日プレイしたのはドミニオンとスプレンダー。僕がゼミ後にドミニオンなどのボドゲをやっているという話を聞いて今日誘ってくれたらしいが、実際のところはまだ1戦しかしたことがなかった。

まずドミニオン。何回やったか覚えていないが、ほぼずっと最下位だった。前回プレイ時に以下のような感想を抱いたので、今日はどのタイミングから勝利点を集めようか考えていたが、全然間に合っていなかった。慣れている人たちとプレイすると展開が速い。デッキを作るというよりデッキを削るのが上手くて、例えば序盤から「礼拝堂」という手札を4枚まで廃棄可能な(つまりデッキを削る)カードを何回も打っているなあと思っていたら、終盤になっても山札が薄くて強力なカードを何度も使っていたということがあった。

デッキを作るのに夢中になっていた結果勝利点をほとんど確保できず、最下位となってしまった。

週記(2021/10/25-2021/10/31) - kotatsugameの日記

また、そのようなデッキを削るカードがない場合には山札を回すことが必要になるが、これに関してもいろいろ参考になることがあった。前回のプレイでは「市場」なる+1ドロー+1アクション+1購入+1金という能力が多いカードが強いと思っていたのだが、これはどちらかというと中途半端になってしまいがちなもの。+1ドロー+1アクションはすなわち「手札を減らさず権利も消費しない」というだけの意味で、結局のところノーコストで+1購入+1金という意味だったとわかる。このカードを使った回で一緒に使われた「研究所」、+2ドロー+1アクションのほうがよほど自由度が高そうに見えたし、それで金貨など引き当てれば市場に勝る効果となる。+1購入を使いたいような機会は、少なくとも今日はなかった。手札の枚数といえば、「地下貯蔵庫」というカードで残りの手札を引き直しつつ+1アクションができるので、デッキを回すのに大変良いカードだと思っていたが、これも思ったより強くない。なぜなら、使った「地下貯蔵庫」の分だけ手札が減ってしまうからだ。

スプレンダー。毎ターンチップを集めてカードを購入し、そのカードとチップを合わせてさらに上のグレードのカードを購入していき、点数を集めるというゲーム。集めたカードの枚数によって貴族タイルというまた別の点数が取得できる。1戦だけプレイして、ビギナーズラックか僕が勝利した。序盤だけチップを集め、残りのターンはずっとレベルが低いカードをカードで購入するというのを繰り返していたら、最終的にレベル1が14枚、レベル2が4枚集まって、貴族タイルをすべて取得できて勝利した。聞くところによると、普通はもっと早く決着がつくゲームらしいので、この戦略とも呼べないような貪欲法は使い物にならなそう。

午後8時を過ぎ、みんなで夕食を食べに行くかという話になったが、午後9時からのABCに間に合うか不安だったし、食欲もないので、自分だけ先に帰ることにした。寝不足からかかなり頭が痛く、フラフラしつつ帰宅。

家に帰ってみると、今朝はあんなにうるさかった水音が静かになっていた。昨日掃除しなかった換気口を見つけ、フィルターを取り外してみると、こちらも目詰まりしていたので洗った。乾かすのは間に合わなかったので、換気口が開いてまた外気温と一致してしまった室温の中、寒さと眠気に耐えながらABCに出た。全完21位。

Panasonic Programming Contest 2021(AtCoder Beginner Contest 231) - AtCoder

Aはdcで6B。BはRuby。CもRubyで書こうとしたらWAで、「以上」という文言を見落としていたので、C++に切り替えて二分探索で解いた。Dは同じ情報が2度以上与えられないという条件を読み飛ばし、その辺りもケアしようと思って丁寧に書いている途中で気づいた。その名残で、ループ判定はdfsで行った。Eは桁dpをしたが1WA。このあたりが眠気のピークで、全然頭が働かず修正に10分くらいかかった。よくわからないまま式をちょっと書き直したら上手くいった。FはBIT。Gは積をcombinationの場合の数と読み替えるテクで、Cookie Distributionの解説を見ながら解いた。

atcoder.jp

Hが解けず、しばらくコードゴルフをしていた。一段落ついて戻ってくると何となくわかった。フローだという予想はついていたが、その辺の張り方について。すでに使ったことのある頂点を通るのにペナルティを与え、流量を変化させてみれば、最小値が求まりそう。ペナルティについては、最初は流量1・コスト0の辺で頂点とsource・sinkを結ぶが、以降は流量無限・コストINFの辺で結んでおけばよい。流す流量をkとしたとき、k\ge H,Wが必要で、理想的にはコストINFの辺を通るのは2k-H-W回となる。つまりその分を総コストから引いてみて、まだINFが残るようなら、ちゃんとすべての頂点を使えていないので、流量が足りないということ。またそれを気にせずとも、INFより大きな値が答えとなることはない。流量を変化させるのにはACLのslopeを使った。

コンテスト後に換気口から外していたフィルターを戻し、エアコンを付けたところ、一気に部屋が温まった。どうやら昨日エアコンのフィルターも掃除したのがかなり効いたらしい。最近エアコンをつけても部屋が温まらなくて、寒さに耐えられず設定温度を23度に上げていたが、今はあまりに暑いのでいくらか下げることにした。これまでどれだけ無駄な電気を使ってきたのだろうと後悔。

コードゴルフ。Aはbcに4Bがあった。bcを使うという発想を自分から出せたためしがなく、コンテスト直後に最短コードを確認して口から魂が抜けるような思いをした。Bは同様の問題が既出なのでそこから最短コードをコピペしたが、そちらごと更新された。この問題はAWKの解が28Bであったことだけ覚えていたので、手元にあるAWKの最短コードリストから28Bのもの18件を抜き出し、コードを読んでどの問題か探していた。

atcoder.jp

CはOctaveのlookup関数が超強力である。DはUFで、PerlのUFには最近手も足も出ない。大敗。Eは解説を読んでRuby再帰関数を書き、Vimに直していたが、直接N\times 2次元のdpをするコードに負けた。Fはコードゴルフの途中経過では全然勝てなかったが、最後の最後に隙をついた自明な更新で掠め取った。GはRubyで書いていたら式変形で縮められたので、Vimに直して縮め返した。HはPythonとnetworkx。公式解説でもslopeで流量を全探索していたが、僕の解法の強化版が最短コードになっていて、そちらはsourceとsinkをコスト2×INFで結ぶことで、その辺を使うのが実質流量を1減らしていることになり、流量maxの場合が即座に解となるようにされていた。

朝方までコードゴルフをしていて、眠気も微妙な具合になってきた。布団に入るちょっと前にFHC finalのYesNoが行われていて、見ているとへのk氏が4位になっていた。すごすぎる。

布団に入って読書。1冊読了。「江戸の花魁と入れ替わったので、花街の頂点を目指してみる」2巻。そこそこ面白かった。1巻を読んだときにも書いたが、現代の医療知識のまま江戸時代に転移した(憑依ではない!僕ももはや覚えていなかったが、1巻で体ごと持ってきたという描写があったようだ)ので、有り合わせのもので医療行為を行う描写がある。1巻では種痘を行っていたが、2巻では梅毒を治していた。真似しないでください、の注意書きが1巻よりも強い表現になっていた。とまあ、知識は現代のものだが、登場人物のセリフはすべて時代がかった口調になっている。物の名前や慣用句等も合わせられていて、注釈が結構多い。そのあたりしっかりしているなあと読んでいたのだが、一方江戸時代に西洋の料理や現代の髪型を持ち込んで高く評価されるという描写があって、そんなに容易く受け入れられるものか?と疑問に思った。

午前8時就寝。

12/12(日)

目覚ましを何度もスヌーズしつつ、午後4時ちょっと前に起床。すぐさまAHC007。登録時の質問で、インターン生が役職員に含まれるのかよくわからなかったが、TLでの助言を受けて含まれることにしておいた。今日は手も足も出なかったので、ちょうど1時間で切り上げてOpenCupに移動した。

THIRD PROGRAMMING CONTEST 2021 (AtCoder Heuristic Contest 007) - AtCoder

まず通常のMSTを求め、その辺のみを使うので12599577888点。入力の1行目にN Mがあると思い込んで、その部分を読み飛ばす実装をしていたため、なぜかずっと答えが合わずに苦労していた。もう何も思いつかなかったのでシャワーを浴びていると、毎回明らかになった辺の情報と残りの辺の長さの期待値(距離の2倍)でMSTを再計算し、そのMSTに採用されていたら採用という手法を思いついた。これで13885749353点となり、最終結果は245位だった。パフォーマンス1630でレートは2026→2034(+8)。

OpenCup後にいくつか解法を探してみた感じ、長さの期待値を正確な値である距離の2倍ではなくもう少し小さくしてみるとか、そもそも実際にランダムに長さを生成して何回か試してみるとか、そういう方法があったらしい。ランダムに生成するときも、ピッタリ1倍から3倍にするのではなく、もう少し区間を縮めたほうがスコアが良くなったようだ。また、「MSTを作って採用されたら採用」ではなく、「採用したMSTのほうが採用しなかったMSTより安い場合採用」とすると、ほんの少しだけスコアが伸びたようでびっくり。実際に書いてみると再現し、13917323561点になった。同値だと思っていたが、おそらく辺のソート順で前者のほうが採用されやすく、このような違いが生じたのだろう。

コードゴルフ的には、1を1995個以上出力してもよいことには気づいていたが、AWKsedでもインタラクティブが動くというのが想定外で大敗。

OpenCup。今日は5時間フルで参加できた。チームメイトの1人はAHCに参加していたため、最初は2人だった。チームとしてはAMCDJHIGEをこの順に解いて9完13位と、過去最高の順位を記録した。ほぼすべての問題に原神?というゲームが絡められていて、Paimonなるキャラクター等が登場するのはいいのだが、問題ページに特に関係ない画像(しかも一部は公式ではなくPixivから)が貼り付けられており、それのせいで問題文の読み込みが遅くてイライラした。

Aは地域のコンテストで出た問題の変形らしく、注意して読んでいたが、実際はほとんど関りがなくてただ問題文が長いだけだった。正方形を4つに区切り、どの領域に目的の点があるかで寄せる角を変えればよいとすぐにわかり、4通りのコードをコピペを駆使して生成しAC。いくつか問題を読んでいるとMが通されだしたので、読む。整理すると符号を割り振るだけになる、よく見る問題。n=1のコーナーケースにハマって1WA。次にCが通されていて、読んでもよくわからなかったのでチームメイトに投げるとシュッと通してくれた。

D問題を読んでみると、つい最近見たことのあるソート関数が取り上げられていた。ビジュアライズ結果も見た記憶があるので、しばらくTwitter検索でツイートを掘り出していた。

改めてアルゴリズムを把握すると、i=1の場合の交換とそれ以降の交換に分ければ求められそう。前者はシミュレートで、後者はほぼ転倒数になるため、インクリメンタルに更新できる。勢い勇んで書くもサンプルが合わない。もう少し考えると、値が重複する場合に困っていることが分かった。重複を部分的に取り除く必要があるが、これは後々削除される要素の寄与分を持って一緒に更新していけば後から無理して求めなくてもよい。チョイチョイ直してサンプルが合った。怖いのでランダムケース生成してチェッカーに掛けると、ボロボロ落ちるケースが見つかったが、幸い修正は容易で、値の分布を変えたランダムケースでも落ちなくなったので、満を持して提出しAC。これが全体で2番目のACで、かなり興奮した。

Dが通るのとほぼ同じくらいにJが解けたらしいので、実装に入ってもらって次に通されているHを考えていた。これは木dpをするだけに見える。しっかり遷移を詰めて、Jが通ったのを確認して実装に入る。1度WAするもtypoが見つかったので修正し、もう一度投げると通った。アルゴリズムの間違いではなくて一安心。その後Iもできたらしくて、通っていた。

Eを考えてわかった気になり、実装に突入。しかし2次元セグメント木が必要になって暗雲が漂う。このあたりでAHCからチームメイトが帰ってきて、1点加算矩形取得のデータ構造を持っていないか聞くと、シュッと投げてくれる。それをコピペしていざ具体的な値を求める段になり、ようやく解法の破綻に気づいた。しばらく考えても修正不可能で、そうしているうちにGが解けたらしいので、いったんパソコンを空ける。頭を抱えていると、先ほどデータ構造を恵んでくれたチームメイトがまったく別の解法を生やしてくれた。Gが通るのを待って実装してもらい、提出するもTLE。行列積が重いところ、三角行列であることや成分のいくつかが常に1であることを利用して展開すると、演算回数がかなり減ったらしく、それで通った。後から公式解説をチラ見したところ、行列の形に注目して行列積を軽量化するところまで含めて想定解だったらしい。

OpenCupから戻ってくると、今日の昼間に行われていたJOIの二次予選の問題がAtCoderに上がっていたので、急いで解いた。

JOI 2021/2022 二次予選 過去問 - AtCoder

Aは簡単。AWKの25Bを投げると、時間差ですでに投げられていた。その後Vimsedで頑張ってみたが、どれもTLEしてしまった。特にsedのホールドスペースをスタックのように使うやり方は、かなり上手いと思ったのに、小さいケースでも思いっきりTLEしてしまった。以降はコードゴルフなし。BはBFS。Cは難しかったが、縦の和・横の和が一致するというだけでもパターンは相当絞られるので、約数全列挙などした後全探索する。Dは直前に食べた飴の位置を覚えておいて、2個連続で食べたようなら遷移先を十分遠くに飛ばしておけばよい。EはTLで少し言及を見てしまって、Undo可能UFで殴り倒した。1250msくらいかかった。

CF #759 div.2があるようだったので出た。5分こどふぉるのが2連続で行われた。

Dashboard - Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3) - Codeforces

Aは丁寧にやる。Bはちょっと考えると、後ろからの累積maxが更新される回数だとわかる。Cは正負に分けて考えてよい。Dはしばらく1,2,4,3をソートできると思って手で実験していたが、ふと転倒数のパリティが変わらないことに気づいた。かなり見覚えがある考察だ。同じ値が2つ以上存在するなら、そこを入れ替えることでパリティを変化させられるため、必ず達成可能。Eはdfsして親へのパスに含まれる値の頻度テーブルを作り、その上で二分探索して、値の取得はsetで行った。頻度テーブルは数値のインクリメントとデクリメントで行えたが、最初の提出ではここにもsetを用いていたので、1TLE。Fはdpを考えると区間ごとに値が一定で、座圧した後遅延セグメント木に一次関数の作用をさせた。

システスも通って全完10位。上位10人中8人が日本人だった。Eは106にlogを付けたので心配していたが、TL 4000msのところを3200msくらいで通った。結局、削除のためにsetを使っていたので、そこをうまくやると線形時間の解法が作れるらしい。解法の一部に見覚えがあるなと思って日記を検索したところ、半年ほど前に見たことがあったらしいと発覚。

vectorの途中の要素が、一番後ろの要素とswapしてからpop_backすることで削除できるという話を聞いた。言われてみれば当たり前だが、かなり盲点。

週記(2021/05/03-2021/05/09) - kotatsugameの日記

FはARCで既出だったらしい。当時の自分はちゃんとstackを使って線形時間で解いていた。

atcoder.jp

終わってからずっと日記を書いていた。火曜日にはととりにゃあアドベントカレンダーの記事を錬成しなければならない。実は、今年読んだ本ではなく去年読んだ本を書こうかと迷っている。去年同様の記事を書けなかった理由を思い出したからだ。12月にそのような記事を書くと、当然12月に読んだ本が記憶に新しすぎるため、正しく判定できないのではないかという恐れがある。しかし読んだ本の統計を取ろうとも考えていて、その場合今年の本を対象にするのが望ましい。どちらにするのか、書き始めてみなければなんとも言えないだろう。

週記(2021/11/29-2021/12/05)

11/29(月)

先週の週記を投稿してから1時間くらい、インターンのコーディングをした。このようにやる気を出したら1時間で終わるようなものを作るのに、自分はどれだけ放置していたんだろう。猛省。

布団に入って少しだけハーメルンを読み、午前10時半に就寝。

午後4時半起床。今日も定例会があるが、寝る前に進捗を産んでおいたので、ギリギリまで寝ていることができる。ということで追加で15分くらい横になって、ギリギリに着席して進捗報告のスライドをサッと書いた。今週からいよいよ業務の体験が始まるので、しばらくは生活リズムを正して連絡に備えておく必要がありそうだ。

定例会は特に何事もなく終了、勉強会まで終えて、しばらくTLを眺めていたら学食が閉店してしまった。冷凍の弁当を食べてコードゴルフを始めた。

PerlのUnionFindに新手が出ていた。ルートノードを!defined$p[$v]で特徴づけると、$p[$v=pop]&&=find($p[$v])でpath halvingが行える。ここで$vはローカル変数ではないため、find関数の最後に$vを返しておけばちゃんとルートノードが得られるというわけらしい。そこから問題に合わせてさらに縮む余地があって、$vの代わりに$_を使ったり、popするのではなくfind関数の呼び出し時に書き換えるようにしたり、配列@pではなく変数${-$v}を使えたりするようだ。最初に見たときABC228-Dを思い出したが、確認してみるとあまり似ていなかった。

atcoder.jp

これを使って縮む問題が他に7問ほどあった。ルートノードの@pの値を迂闊に書き換えてはいけないのがつらいところで、ちゃんとルートノードが異なることを確認してからuniteする必要があるため、コードこそ少し長くなりがちなものの、find関数がこれまでに比べてあまりにも短いため、猛威を振るった。最も単純には、「グラフを連結にするのに新たに必要な辺の本数は?」という問題がAtCoder上に少なくとも2問存在し、これは何もなくてもルートノードが異なることの確認をしなければならないため、かなり効いた。逆に、適当にuniteした後同じ集合にあるかどうかを判定するような問題にはほぼ効かなかった。

昨日投稿した週記の一部に誤りがあって、修正した。

2021/11/29追記:⇒は嘘だった。

週記(2021/11/22-2021/11/28) - kotatsugameの日記

午後11時半になってCodeChefで謎のコンテストがあったので、試しに参加してみた。公式コンテストではないが、一応div.2以下でRatedではあるようだ。

https://www.codechef.com/FOUR21A

全完1位。問題名が長く、問題コードは公式コンテストとは異なり無機質な文字列に設定されているので、以下では順位表の左からABCDEと付けておく。solved数はこの順ではないようだった。

Aは、とりあえず全体の最小値だけ回してから引いて、非ゼロ要素が最も長く連続する箇所を探せばよいか、と思って提出したらWAだった。改めて問題文を読み直すも、特に読み飛ばした要素はない。ここでサンプルの説明文を見ると、なぜか人が並ぶ順番を自由に入れ替えている。慌てて数列をソートしたら通った。後から問題文を確認したところ、「Among all possible ways in which the N neighbours start the game」が順番を入れ替えてよいという意味に取れなくもない。しかし、「Any person can hold the bowl initially」とあるのだから、このpossible waysとは誰が最初にbowlを持っているかについて言っているととらえるのが素直な読み方ではないだろうか。

Bは自明。Cは残す文字を決め打って、取り除かなければいけない区間を数える。それがK個よりも多ければ、残したい区間も短い順に使っていくしかない。これもWAが出てびっくりしたが、負になりうる整数とsize_tを比較していたのを見つけて、試しにintにキャストしてみたら通った。このバグをすぐに見つけられたのはかなり冴えていたのではないか。DはSTのどこに対応するかを全探索して左から貪欲に決める。文字を追加した後、その文字を巻き込んでflipする可能性があるので、一応端には気を使っておく必要がある。そのことは最初から分かっていたのに、コスト計算を間違えて1WA。ところで入力のテストケース数Tと文字列Tが被っているのは誰も何も思わなかったのだろうか。

Eはそこそこ面白かったが、modを取る要素は要らないかな……。まず観察として、購入する座席の長方形は左上に寄せてよい。なぜなら、左上に寄せていくと総和が小さくなる一方、数値同士の間隔が狭くなるからである。さらに、縦よりも横が長い長方形だけ考えることにしてもよい。これも長方形を倒すことで総和が小さくなることと、間隔が狭くなることからわかる。コンテスト中は総和にだけ注目して、数値の間隔は考えていなかったが、フルフィードバックなのでヨシ。さて、ここで数値の間隔などに着目すると、S_{i,j}=(i^2-i+j^2-3j+2ij+2)/2であることがわかる。[1,H]\times[1,W]で和を取ると閉じた式ができるが、その値のオーダーはO(HW(H^2+W^2))となって、この問題の制約下では64bit整数に収まる。よって普通に最小値を計算して、出力の時だけmodを取ればよい。

あとはH\le WかつHW\le max_N=4\times 10^5の範囲で全探索できる。まずHH\le \sqrt{max_N}の範囲で全探索し、W:=Hとしてどんどん増やしていく。このとき、「中央値(ただし要素が偶数個の場合は小さいほう)」、「中央値が存在するマスの座標」、「中央値以下の値の総和」を管理しておくことで、S_{i,j}の総和の式と合わせて常に最小コストが計算できる。まず最初に、H=Wのときは1から十分多くの整数が連続で含まれているため、中央値\left\lceil H^2/2\right\rceilとなり、それ以下の値の総和もすぐ出るし、座標もちょっと実験するとわかる。そこからWをインクリメントするときには、中央値が何個ずれるかを求めて、その回数ぶん座標をずらし、座標から値を取得することでうまくいく。各Hに対して、中央値をずらす操作が全体でO(max_N)なので十分間に合って、今の前計算をもとにクエリに答えればよい。

div.3の問題も残り3問解いておいた。こちらは特に言うことはない。

布団に入って少しハーメルンを読んだ。「帝征のヒーローアカデミア」を読了。

syosetu.org

面白かった。普段のほほんとしている主人公の、見せ場における圧倒的な威風が読んでいて気持ちいい。やはり古龍を題材にするとあまりに強力な個性を持つことになってしまい、先日読んだ主人公が悪役となってしまったハーメルンに似たものを感じて勝手に不穏な空気を感じていたが、今のところ真っ当にヒーローをしていてよかった。

さらにしばらくハーメルンを漁り、午前5時就寝。

11/30(火)

午前10時起床。TLに検索してはいけない言葉をまとめたwikiが流れてきて、見入ってしまい二度寝どころの話ではなくなった。

正午から1on1。今日はちょっとした進捗報告で、この後の動きももう結構前から話してはあったから、再度確認するだけですぐ終わった。

昨日ゴルフしたPerlコードがいくつも縮められていた。値が異なることの判定は引き算して非ゼロであることを使っていたが、XORを取って非ゼロであるか判定すると、例えばF-FというコードがF(-F())と解釈されるのに対してF^FF()^F()となるため、括弧がいくつか省ける。何とか取り返そうとコードをガチャガチャしていたが及ばなかった。

学食に行って昼食を摂り、注文していた本を受け取って帰宅。午後2時過ぎからインターン先業務に関する追加の説明をしていただいた。先週、研修をしてもらったが、今日はその周りの細々としたことについてで、ツールのアカウント発行をしてもらったり、他の人とのやり取り方法(Slackの各チャンネルの目的と投稿テンプレート)を聞いたりした。早速始められる状態になったが、いざ自分でやろうとしてみると腰が引けて、思ったより手が出ない。

一旦1時間ほどラノベを読んでから再度取り組んでみた。内容によって個別に判断しなければならないことが多く、質問したいことがたくさん出てきてしまった。工程の最初のほうにダブルチェックがあるので、とりあえず仮にそこまで進めて聞いてみることにした。と、そういう内容でSlackに投稿を行ったが、その後マニュアルをよく読むと午後4時までに投稿しなければならないとされていて、時間が過ぎていたので申し訳なくなってしまった。

今日の業務はこれで終わり。火曜日のPythonの講義がClassroomに投稿されていたので、課題を終わらせた。今日はパラメータ2つとそれの戻り値で3次元プロットを使ってみた。jupyter notebookではグラフをマウスでぐりぐり動かせた覚えがあったのだが、Google Colab上ではある一定方向からの画像しか表示されないようで、ちょっと残念だった。%matplotlib notebookと書くと、そもそもグラフが表示されなくなってびっくりしたが、調べた感じ、そもそもこれがjupyter notebookでグラフを動かすときのおまじないだったらしい。

ラノベを1冊読了。「ログアウトしたのはVRMMOじゃなく本物の異世界でした」。導入部分はほぼソードアート・オンラインで大丈夫かと思ったが、現実とゲーム設定が入り混じった世界に飛ばされてからは、ゲーム知識とゲーム内で育てたステータスで正当に(?)無双していてよかった。主人公のスキルで新しく「呪紋」を作るのも、いろいろ設定があってなるほどと納得できる。ただ、ステータスの魅力値を参照してヒロインたちが主人公に惹かれていくような描写だったのは気に入らなかった。そこだけは本当に正当にやってほしい、というのが僕の好みだ。

別のラノベを開いて少し読み進め、午前0時半就寝。

12/01(水)

午後1時起床。すぐ学食に向かい昼食を摂って、今日もまた注文していた本の受け取りをした。

先月は思ったより読んだなあという感想だが、相変わらず買った本のほうが多くてどうしようもない。本棚にももう入りきらないので、そろそろ買い足すべきではないだろうか。普通に本棚を買うと付属する棚板が少ないため各棚をラノベの高さに合わせることができず、1段はラノベの上に直接ラノベを並べるアクロバティックな配列にならざるを得ない。なので、本棚を買うときは忘れず棚板も追加で買うようにしよう。

しばらくパソコンの前でボーっとして、午後3時半からインターンの作業を始めようとした。結構時間に余裕があると思っていたが、冷静になるとやり取りの締め切りである午後4時までは残り30分しかない。慌てて昨日の続きを少しだけ進めたが、今日もまともな進捗は産めずに終了。

ゲーセンに行くことにした。今日は夜から雨が降るらしいので、地下鉄で向かう。まず仙台駅のほうまで足を延ばして、予約できなかった本を1冊買った。

「時々ボソッとロシア語でデレる隣のアーリャさん」3巻が12月の頭に発売されるが、それだけ予約受付が終了していた。

週記(2021/11/22-2021/11/28) - kotatsugameの日記

今日も結構いい感じ。新曲の14+を99AJし、既存の14+でSSS+とAJをそれぞれ1つ出した。また理論値も5譜面出た。これまで出した理論値は、何回もプレイして1落ちを踏んでようやく出たというものだったが、今日は適当に選択したら1発で出たものがあって、かなり上手くいったなあという感想。内部精度はかなりボロボロだったので、運がよかっただけにも思える。

帰宅。AtCoderに「Rated/Unrated登録機能」が追加された。今週末のコンテストから適用される予定らしい。僕は(自分が覚えている限り)いわゆるNoSubをしたことがないので、完全に歓迎する側の立場である。ああでも、AtCoderを始めてしばらくは青でもARCに出ずにABCに出ていたことがあったので、そういう意味でRatedから逃げた経験はある。今でもCFのdiv.1はサボり気味。

Rated/Unrated登録機能追加のお知らせ - AtCoder

少しインターンの作業を進めてから布団に入り、しばらくラノベを読んで午前6時就寝。

12/02(木)

午前11時半に起床。

昨日進めておいた分のチェックのためにやり取りをしていた。大きな修正は後からにすると決めていたが、すぐ終わるような修正がポロポロ見つかって、それを直して再度チェックをお願いするということを繰り返していたら午後1時前になってしまった。毎週木曜日は4年ゼミだが、特に今週からは山の教室で、対面で行われる予定。完全に遅刻である。

急いで身支度をするも、出発がそもそも午後1時だった。どうしようもないので開き直って学食で悠々と食事をし、今日もまた注文していたラノベを受け取って、教室に到着したのは開始から30分以上過ぎたころだった。今日は僕の発表の番ではないので、聞くだけ。しかし換気のため扉が開け放たれた教室は寒すぎる。防寒着を羽織ってパーカーのフードを被り、震えながら発表を聞いていた。暖房が強められ、部屋が暖まってきたくらいで終了してしまった。

その後は部屋を移動し、前回の対面ゼミのときと同様に5人でスカルをプレイした。前回の経験から、部屋の使用は6時をオーバーしても大丈夫そうだったので、みっちり2時間ほどプレイしていた。今日はあまり振るわず。攻め時がわからず、初手でドクロを置いてめくられず終了、みたいなことが多い。ドクロを置いているのでチャレンジにも参加できない。ところが、逆にドクロを置いているのにチャレンジに参加し、ブラフを使うのが非常に得意な人がいた。一度など、場に10枚しかないのに7枚を宣言するから、僕も強気でやってやろうと思って8枚を宣言し、いざその人のタイルをめくってみると一番上にドクロがあったということがあり、心底びっくりした。

解散して、閉店ギリギリの学食で食事。テレビがついていて、バラエティ中の小ドラマに片桐仁さんが出演していた。ちょっと前にTLで片桐仁さんの個展の話も流れてきたことだし、そうやって活躍されている様子を見れるのは嬉しい。

午後8時前に帰宅。今朝受け取ったラノベを読み始めた。

あまりに眠く、布団に倒れこんで午後11時から午前1時半まで昼寝していた。また起きて読み進める。1年ほど前に1巻を読んだ時も書いた気がするが、この作品は、リメイク前のなろう→リメイク後のなろう→書籍版と辿ってきて、これで読むのは3回目になる。特にリメイク後のなろうと書籍版にはほとんど違いがなく、同じ文章を2回読むことになって、気づいていなかった伏線をいくつか見つけることができた。僕は普段本を読み返すことがないので、こうやって見落としてきた伏線が数えきれないくらいあるんだろうなあと思った。まあ、1つの作品を深く読み込むより大量の作品をとにかく摂取することを求めて読書しているので、仕方のないことではある。

朝になって、さらにちょっとだけインターンの作業を進めた。布団に戻って寝ようとしたが、今度はハーメルンを読み始めて、午前9時になってしまった。作業に関するやり取りを投稿してよい時間になったので、改めて起き上がり、いくらかやり取りを進めて、午前10時半に就寝。

12/03(金)

午後6時半起床。少しハーメルンを読んで布団から脱出。

ABC227の学生奨励賞4位ということで、アマギフが物理的に届いた。再配達をお願いしていたもの。実は昨日、再配達の時間設定を2回も変更していた。最初は特に何も考えず18時~20時を指定したが、サークルと被ることに気づき、また床屋にも行きたくなったので、一気に午前中にずらした。ちゃんと夜眠れればそれでよかったのに、うっかり朝方まで起きてしまったので、今度はサークルのあとになるように19時~21時を指定した。今日は結局午後6時半起床ということで、サークルにも床屋にも行けていない。無力。

しばらく日記を書き進めて、午後9時からABC230。今日は金曜日開催。

AtCoder Beginner Contest 230 - AtCoder

Aから難しい。適当に提出していたら2WAも重ねてしまった。とりあえずAWKでACした。Bは"oxx"を9個結合して、入力された文字列が含まれるかをチェックするコードをPerlで書いた。普通にやると改行のせいで常にマッチングに失敗するので、どうやって取り除くのがよいかしばらく試行錯誤して、結局chopするコードを出した。CからC++。Cは、今見ているマスがもし黒で塗られるなら、それのもとになったkの値が確定するので、それを元にB+kB-kをチェックした。Dは区間スケジューリング。Eは商の値でまとめる典型で、うっかりミスで1WA。Fは難しかったが、累積和を取って考えると、元の列の累積和から適当に選んだ場合の数を数えているとわかったので、同じ値は一番右の位置における場合の数だけ保存するようにdpを書いたら通った。

Gも難しい。ちょっと前にCFで似たような問題を見た気がするが、覚えている問題内容から判断してコードをコピペしに行く必要はないと思い、コンテスト中は探さなかった。ちなみにこの問題だ。

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

ただ、方針は似ているだろう。各d\ge 2に対して、i\le jかつd\mid iかつd\mid jかつ\gcd(P_i,P_j)\gt 1なる(i,j)を数えられれば、あとは包除原理で求まる。これは後から調べるとGCD畳み込みを再発明していただけらしい。まず、d\gt\sqrt Nのとき、関係するインデックスが高々\sqrt N個しかないため、2乗かけて愚直に調べても間に合いそう。この部分はO(N\sqrt N\log N)となる。d\le\sqrt Nのとき、今度は関係するP_iたちを全部集めて、そこでGCD畳み込みをすれば求まる。この部分もO(N\sqrt N\log N)になる。組み合わせても5secには間に合いそう。一度WAが出たが、修正すると4700msで通った。

実は定数倍が少し良い。最初、誤読してi\lt jなる(i,j)を数えようとしていたが、この時d\le \frac N 2としてよい。また、P_iたちを集めて行ったGCD畳み込みにおいても、\frac N 2以下の範囲だけ考えてよいことになる。この定数倍をなくして提出してみるとTLEしてしまったので、コンテスト中は運のよい誤読をしていたということ。

残り1時間弱でHに進んだ。とりあえず愚直にdpするコードを書こうとして、それすら挫折してしまい、あとはコードゴルフしていた。

A問題はdcが短くなった。10で割った商とあまりを続けて出力すれば、2桁のゼロ埋めと同じことができる。AGC0はそのまま出力しておけばよい。BはVimで書いていたが、普通にsedで判定できたらしい。xxxoooxoを含めばNo、それ以外はYes。確かにそうである。テストケースも多いので、これ以上少なくすることはできないだろう。CはRubyVimで書いたものが今の最短。dcで無理やりコーディングしてみたら、一応短くはなったもののTLEしてしまった。またOctaveは64bit整数が読めず、精度が落ちてしまって通らなかった。DはPerlだと思っていたが、AWKで判定してwc -lするbashコードが短くなった。さらにそれをVimから行うコードで-1Bされるも、Vimの場合はwc -lのオプションを外して、手作業で余計な出力を取り除くほうが短くなるので、さらに-1Bできた。

Eは2\sum_{i\le\sqrt N}\left\lfloor\frac N i\right\rfloor-\lfloor\sqrt N\rfloor^2が答えになるようで、商でまとめる方法だとTLEしてしまうdcでも、こちらの式なら余裕をもって通る。以前から何度か目にした覚えのある式だが、この度4年ゼミで読んでいる教科書の定理からこの式が導けることを発見した。式変形を追うよりも、その定理の下に書いてあった図から一発だろう。ここで曲線はq=\frac 1 dを表している。

FはAWK。答えが合わなくて、累積和が大きくなりすぎて精度が落ちたかと思ったが、普通に負の数のあまりが負になっていただけだった。累積和自体は最大2\times 10^{14}と、倍精度浮動小数点数の有効数字でちゃんと表現できる。Gは今のところ、コンテスト中のC++コードが最短になっている。

午前2時からSRM819に出た。

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

Easyはカス。難読テーブルマジック。どんな顔して出題したんだろう。AtCoderのRated/Unrated登録機能を僕が歓迎しているのには、AtCoderはこのようなゴミみたいな問題を出さないと信頼しているからというのもある。解法はまあまともで、およそ前半分を見て文字コードが一番小さい文字が1枚目に選ばれたカードになって、この情報からtopの山の枚数がわかるので2枚目に選ばれたカードも取得できるというもの。後者の事実に気づくのに結構時間がかかった。

Medも難読気味。オートマトンで二分木をdfsしろという問題で面白くはあるが、ratedで解きたいかというと……解きたくない。問題文にリンクが張られていたオンラインでオートマトンを試せるページにdfsのコードが載っていたので、基本はそれを元に考えた。問題内容は「二分木の最大独立集合を1つ構成せよ」というもので、これは葉から貪欲に詰めればよい。dfsして、親に移動する前に子を2つチェックして、どちらもマークされていなかったら今見ている頂点をマークする、というのをオートマトンの状態で管理しつつ行った。

Hardに10分しか残せなかった。焦ってdpを書くも、全然合わず終了。コンテスト後にしばらく頑張ったら通った。1ターンで何人消えるかを各2\le n\le Nに対して求めたい。人を順番に見て行って、次のターン何人消えるかをdpのキーに持てばいけるかと思ったが、「今見ている人が次のターンに残っているか」がわからなければ正しい確率を求めることができない。そこで、0\le i\lt nを見ているとき、[0,i)で何人消えるかと[i,n)で何人消えるかの2つに分けて持ってみると上手くいった。ここを分割したせいで各nに対してO(n^3)のdpを行うことになったが、定数倍がかなり小さいので余裕を持って間に合った。

結局EM2完で14位、2536→2552(+16)。じわじわhighestに近づいている。

布団に入ってハーメルンを1作読了。「デート・ア・ライブ 士道リバーション」。原作完結前に書かれた二次創作で、作品執筆時に登場していた七罪までの精霊たちの攻略順序を逆にするというもの。非常に面白かった。確かに、原作でも精霊たちが士道に惹かれるのはその人柄からであって、別にラタトスクの補助がなくても精霊と出会いさえすれば攻略可能だったのかもしれない。原作では1年で一気に全員を攻略していたところを、1年1人くらいのペースで描かれていて、最初に攻略されたため最も付き合いが長くなって正統派ヒロインと化した七罪が非常に健康に良かった。

syosetu.org

ほかにデート・ア・ライブの二次創作を漁るもあまりピンとくるものが見つけられず、午前7時就寝。

12/04(土)

途中弁当を受け取りつつしっかり眠り、午後6時半起床。食事して日記を書き、午後9時からAGC056に出た。

AtCoder Grand Contest 056 - AtCoder

AC2完で64位(ratedでは63位)、パフォーマンス2871でレートは2850→2852(+2)。一応highest。耐えた。

Aは難しい。問題を読んで、手でN=6の場合の解を構築し、次にN=8を同じ手法で構築しようとして失敗した。ここで初めてサンプルを見ると、なんとN=6の解が書いてあるではないか。しかも自分の作ったものと全然違うタイプで、なんとなく拡張性がありそうな気がする。実際紙で試してみると、N=7N=8が作れてしまった。このあたりで実際のコーディング画面に移り、そこでさらに9\le N\le 11を手作業で作るという方針に走った。コンテスト開始から30分弱で6つ全部完成し、チェッカーを書いてみるとちゃんと条件を満たしていることが確認できたので、あとはN=6で穴埋めするコードを書いて提出、AC。すでに300人以上がACしていて血の気が引いた。

順位表を見るとC問題が多く通されていたので、それを考え始める。まずS_i[0,i)における0の個数引く1の個数(ただし文字列は0-indexed)として、必要な条件をリストアップしてみた。入力のLの値から1引くことで半開区間にしておくと、(L_i,R_i)S_{L_i}=S_{R_i}を表す。他に必要な条件はあるだろうか。例えば、L_x\lt L_y\lt R_x\lt R_yという入力があったとき、S_x=S_{L_x}=S_{R_x}S_y=S_{L_y}=S_{R_y}とおくと、|S_x-S_y|\le\min(L_y-L_x,R_x-L_y,R_y-R_x)も必要である。同様の不等式を区間が重なる条件たちについて求めれば、それで必要十分な条件が集まっているように思われる。しかし条件の数がO(N^2)になって困る。

例えば、\min(L_y-L_x,R_x-L_y,R_y-R_x)=R_y-R_xの場合を考えてみよう。この場合、特に|S_x-S_y|=|S_{R_x}-S_{R_y}|と書けば、暗黙的な条件であった|S_{i+1}-S_i|=1より|S_{R_x}-S_{R_y}|\le R_y-R_xが満たされる。つまり、|S_{i+1}-S_i|=1さえ満たせば、ほかの条件は一切考えなくてよいのだ。このことに気づくと、あとはS_iを条件を満たしつつ辞書順最大化すればよくなって、牛ゲーになる。正確には、牛ゲーのためには|S_{i+1}-S_i|=1|S_{i+1}-S_i|\le 1に緩める必要があったが、実装してサンプルを試すと一致したので深く考えずに提出した。AC。コンテスト中はS_iの定義の符号が逆だったので、辞書順最小化とか最長経路問題とかに帰着しそうになったが、ちゃんと牛ゲーを見抜けてよかった。

残り100分はBを考えていたが、驚くほどわからなかった。そのままコンテスト終了。

Aの解説を見てひっくり返った。そのままでも十分短くなるが、TLで見た「\left\lfloor\frac{N}{3}\right\rfloor\left\lfloor\frac{2N}{3}\right\rfloorを入れ替えれば通る」というのを使うと場合分けがなくなってさらに縮む。美しすぎる。

朝方までずっと日記を書いていた。modint配列を{}で初期化しようとして、コンパイルタイムアウトしてしまったコードがTLに流れてきた。コードゴルフをしていたときに似たような経験をしたことがある。めちゃくちゃ長いint配列の先頭数要素だけ非ゼロに初期化するのに{}を使うと、コンパイル時間が非常に長くなるのだ。なぜ長くなるのかよくわかっていなかったが、今試しに実行ファイルのサイズを見てみると一目瞭然だった。普通にコンパイルするより何倍も大きな実行ファイルが生成されている。ファイル書き込みが長くて、結果コンパイル時間も長くなっていたのだろう。

そのことを伝えると、stackoverflowの似たような言及を調べて下さった。僕の予想はおおむね合っていそう。ちょっと変な初期化をしようとすると、配列の全要素をunrollして実行ファイルに書き込んでしまうらしい。int配列では{}はセーフで、例えば{1}で初期化すると発生したが、modint配列では{}ですら起こるらしい。

午前8時半就寝。

12/05(日)

午後4時起床。食事してOpenCup。今日はチームとして8完、HLCDJFKIの順だった。

Aから順番に読んでいるとH問題が通され始めたので、読んで通す。この問題は自明枠。その後Lもシュッと通っていった。Cもsolvedが増え始めたので考えてみると、左から見ていったときに、各列の行先としてはマッチする列かつまだ他の列の行き先になっていない列のうち、最も左の列に決め打ってよいことが分かった。そうでないなら行き先を適当に入れ替えることができて、その入れ替えで転倒数が減る。これを提出するとMLEしてしまった。どうやらqueueがまずいらしくて、何もしなくても最初に512要素確保するのでオーバーしてしまっているのでは、ということ。vectorに変えてWAを出しつつ3ペナで通った。

DとJがポンポンと通って、Kが書かれている間にFも解けた。bを考えているとき、b以上の要素は\frac{10^6}b個しかないため、それ未満の要素を事前にまとめておけば全体でみる要素数が調和級数で押さえられるというもの。まとめるのも、vectorを舐めて次のb+1に対応するvectorを作りつつ、その直前の要素とマージできるかチェックすればよい。他の問題はよくわからないので考察を進めず、代わりに紙コーディングして完璧に準備しており、Kがバグった隙をついて5分で書いて通すことができた。

その後しばらく苦しい時間が続く。Kが定数倍高速化でかなりペナを吐きつつ通るも、その直前で考察が完了したと思ったIはWA。Aもユークリッド最小全域木を使うコードが投げられ、WA。Iは本当に間違いが見つからないので、チームメイトに愚直を書いて試してもらい、無事WAのケースが見つかる。手で試してみると見事に考察が崩壊して絶望。その後はAに適当に口出ししてペナを量産し、何も進まずARCに逃亡した。

その後、Iがチームメイトの天才的な発想によりACされたらしい。これについてはコードを読んでもよくわかっていなかったが、夜になって別の人のツイートを読んで納得した。下のほうに書いておく。さらにGもセグメント木に乗せるモノイドが分かったらしいが、時間切れで終了したようだ。

午後9時からARC131。5完9位。かなりうまくいったらしい。600点3問をポンポン通せて全能感があったが、Fの前に敗れ去った。ARC全完は遠い。

AtCoder Regular Contest 131 - AtCoder

Aは冷静になると上位桁で\frac B 2を、下位桁でAを作ればよい。\frac B 2は整数でない可能性があるので、代わりに\frac{10B}2を考えればよい。上位桁と下位桁をつなげるのは、桁数を求めて10のべき乗を掛けて……とすると面倒なので、文字列として連結してしまえばよい。これをRubyで書いて、通るのを確認してすぐさまdcで書き直した。こちらは、文字列連結の代わりに2数を続けて出力する方法をすぐ思いつけて、6Bのコードが完成した。Bは小難しいことを言っているが適当にやればよい。

Cを読んで、しばらく考えてもわからなかったのでDに移った。Dはすぐわかった。矢の間隔は常にDであるとしてよい。非負の座標であって最も中心から近い位置に当たった矢の座標0\le x\lt Dを全探索することを考える。当たった座標が負の矢については、全部反転して非負の場合の計算に帰着できるので、以降座標は非負のところのみを考える。さて、まずx=0の場合における矢の点数を尺取り法で求め、BITに乗せて矢の本数から得点をすぐ得られるようにしておく。今からxをインクリメントしていくが、このとき境界を跨いだ矢を逐一検出して対応する点数を更新したい。実は、xを動かす過程でそのような更新は高々M回しか行われない。なぜなら、ある境界を2本以上の矢が跨ぐとすると、その矢の間隔がD未満となってしまうからだ。なので、更新されるタイミングのxを最初に計算して優先度付きキューに入れ、毎回それを見て更新していけばよい。

Cに戻った。自分の手番であるクッキーを食べると、次に相手のターンで勝利できてしまう場合を考える。クッキーが3枚以上残っていれば、まったく関係ないクッキーを代わりに食べることで、相手のターンで勝利させないようにできるのではないかと考えた。これは当然大嘘で、まったく関係ないクッキーを食べたら今度は相手も食べるクッキーを変えてくるので、もうちょっと考える必要がある。ともかくこれで実装すると、初手で勝てるかクッキーの枚数が奇数なら勝ち、そうでないなら負けである。証明は全く正しくなかったが、通った。しばらくコードゴルフもした。

Eに進んだ。手でN=6を試してみた感じ、それぞれの頂点から出ている辺がだいたい同じ色になっていればよさそう。i=1\dots N-1を順に見て、使える辺の本数がN-i以上残っている色を貪欲に選びi\lt jなる辺(i,j)に使うというコードを書き、プログラムでチェックしてみたところ、そもそも辺の本数が3の倍数でない場合とN\le 4である場合を除いて全部正しく構築できているらしい。初手で正解方針を引き当てたようでびっくりしつつ提出すると、WA。よくわからないのでとりあえず再度チェッカーを回してみるか、としたが、コード中の定数をよく見ると、色としてRBWではなくRGBを使っている。慌ててこれを書き直し、提出してみると通った。

1時間以上残してFに進んだ。Fはdpだろうと思って、現在見ている区間にどのようなスタンプが押されているかを状態で持ってみるも、サンプル2が合わない。デバッグ出力をにらみつけてみると、これまでスタンプを押してこなかったのに、急にCをスタンプで押したくなったので、文字列を遡ってそのようなスタンプの押し方が可能か探すのができていないらしい。正確には、そのような遡りが2文字くらいならば対応できていたのだが、実際はもっと前まで見なければならない可能性があって、対応できていなかったようだ。これに気付いたのが残り10分くらいで、急いで書き上げてサンプルも試さず2回ほど投げたが、どちらもサンプルすら通っていなかった。

ARCの直後、午後11時からCodeChefでSnackDown 2021 - Online Elimination。

https://www.codechef.com/SNCKEL21

SORTSEGSは腰を据えて考えると分かった。後ろ、前、後ろと3回ソートすると、ちゃんとすべての値が正しい位置に来ることが直感的にわかる。つまり答えは最大3回なので、2回以下かどうかを判定する。まず数列の前と後ろから触らなくてよい部分を切り落として、何も残らなければソート済みと分かって0回、長さがK以下なら1回。2回で可能かの判定はちょっと考えたが、結局両端を触らなければならないので、後ろ→前か前→後ろの2通りの手順しかない。両方試すことにした。

TSPはたまに見るdp。経路のループを頂点1Nで分割し、両方1からNに向きづけてみる。すると、途中で頂点番号が小さいほうに移動しなくてよいことがわかる。c_{ij}\lt Dの制約が効いていて、そのような移動があった場合、順番をswapすることで必ず距離を縮められるからだ。よって頂点1N以外で重ならない2本の経路の、長さの和の最小値を求めることになり、これは頂点1から延ばした経路の現在の端点を2つ持つ2次元dpで解ける。頂点番号の差の絶対値によるコストは定数として後から足した。

RNDCHULLはかなり嫌な感じだが、丁寧に実装するとすんなり通って気持ちよかった。とりあえずi\lt ji'\lt j'を用意して、(x_i,y_{i'})(x_j,y_{j'})を結ぶ辺がどれだけ寄与するかを考える。これはXY平面において右上がりの線分で、それより上または線分上にしか点が存在しなければx_iy_{j'}-y_{i'}x_jの寄与、下または線分上にしか点が存在しなければ-(x_iy_{j'}-y_{i'}x_j)の寄与をすると考えられる。後者はiji'j'を入れ替えたものも考えればそちらでカウントすることにして無視できるが、後々のためこの状態で数えることにしておく。

さて、とりあえず線分より上または線分上にしか点が存在しない場合を考える。これは、X座標が小さくなるにしたがって使えるY座標が大きいほうから広義単調に増加していくため、どのY座標を使えるかは尺取り法で求められ、また場合の数も「今使える個数」引く「もう使った個数」を掛け合わせることで出せる。逆も、X座標が大きくなる方向に計算すれば同様のことができる。これを図に書いてイメージするため、先にi\lt ji'\lt j'のように固定しておいたのだ。実はj'\lt i'の場合も考えなければならないが、これもほとんど同じコードの繰り返しになる。

ONECHANGEは解けなかった。各文字は高々2つの部分列にしか現れず、abの後半を組に、bの前半とcを組にすると必要な部分列が1減らせる、のように計算していくものだと思った。しかしそのように使える組の列をまともな計算時間で列挙する方法がわからず、適当に貪欲してWAを出した時点で集中が切れてしまった。残り30分くらいは別のことをしていた。

結果は3完ほぼ最速で40位。思ったよりFinalが近かったようだ。

ARCのコードゴルフ。A問題はコンテスト中の6Bが最短。Bを飛ばして、CはPerlでコンテスト中に書いたのが49B、そこから$%==$_/$%/にすると、1回TLEしつつも通ってくれて47B。この書き換えは同値ではなく、例えば$%==1かつ$_==11などでTrueと判定されてしまう。それ以外にも、ループのためにgrepを使っている箇所も微妙に嘘である。Dも飛ばして、Eはコンテスト中の方針をRubyで書いて101B。

昨日のAGC056-Aが今日の昼頃縮められていたので、取り返しておいた。斜めに大きな連結成分を作り、周りに1x1の連結成分を大量に作るという方針らしい。文字列を作りながら行ごとに出力するのは昨日と同じで、行番号のswapの必要がなくなって縮んでいた。文字の判定で-1B、Rubyのゴルフテクでさらに-1Bした。

OpenCup-Iについて。この定義がどこから降ってきているのか全然わからない。遷移を読むと確かに定義通りの値を計算しているんだなあとなるが……。次見たときに思い出せるようになりたい。

今日も9時間ほどコンテストに出ていた。CodeChefで思うように問題が解けず、集中が切れてしまったと思っている。腰を据えて考えるのが苦手である。まあ今のところどうしようもない。精進しなければ成長せず、逆に精進していないので成長しないのは当たり前なのだ。

ところで、インターンの業務の進捗が悪すぎて、とりあえず今あるタスクの期限である火曜日まではそれに全力投球することになりそう。しかも今週木曜日の4年ゼミは僕の発表の番だ。非常にまずい。4年ゼミは前回の発表者がまだ結構残っているようなので、最悪は今週分として30分ほど話す内容だけ用意しておけばいいかな……という気持ちがある。

週記(2021/11/22-2021/11/28)

11/22(月)

先週は週記を投稿した後しばらくほかの人の日記を読み漁り、布団に入ってから少しなろうを読んで寝た。午前8時半だった。

午後3時起床。ARC129-Aが縮め返されていたのを見つけて一気に目が覚めた。布団の中で唸っていると大幅(-3B)に縮む改善を思いついたので、提出して取り返した。

しばらくラノベを読んでから、今週の定例会に向けた進捗報告スライドを作り始める、前に進捗を作り始めた。先週は本当に何もやっていなくて非常にまずい。思ったよりコードの設計が難しかったので、諦めて正直に何もやっていないと書くことにした。定例会自体は無難に終了。Kaggleのサンタコンペが始まったのでまたチームを組むかという話になったが、前回何も手が動かなかったのがトラウマ気味で腰が引けている。まず自分ひとりで手を動かせたら、チームに入れてもらいに行くつもりだ。

今週はかなり早めに勉強会まで終了したので、午後6時半というとんでもない早朝からあるECRに出ることにした。その前に学食に行こうと思って、自転車ならまあ間に合うかなと思って外に出たら、思いっきり雨が降っていた。学食に行くこと自体諦めそうになったものの、何とか気力を奮い立たせて歩きで向かった。結局3分ほど遅刻して帰宅、即レジって問題を解き始めた。

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

Hackフェーズ前は全完。Aは、マンハッタン距離を上に移動してから右に移動する道のりの長さだと思えば、その経路の中間地点を答えればよいことがわかる。Bは、左右でそれぞれ使える要素の個数をカウントしてみると、a\gt bの場合n,n-1,\dots,1しかありえず、そうでない場合はb\gt \frac n 2\ge aが成り立つ必要がある。構築はn,n-1,\dots,1からa,bの位置をswapすればよい。Cは二分探索。Dは結構難しかった。a\ge bとしてみると、値が小さな方に操作するのは(a,b)\leftrightarrow (a,a-b)を行き来するだけで、そこからの派生(値が大きな方に操作する)はどちらも(a-b,b)になってしまうため、無意味。つまり値が大きな方に操作することだけ考えればよくて、この場合ユークリッドの互除法であまりを取る操作を引き算だけで行ったような変化をしていく。逆に、引き算を行う途中で求める値が出現するかは、あまりを見れば判別できる。

Eは貼る枚数を20枚以下で決め打つと、各メッセージに対して貼りだしたとき期待値の分子にどれくらい貢献するかが求まる。これを使って貪欲に取ればよい。21枚以上貼る場合は分子だけ20枚の場合の値を用いれば計算できたので、そちらも求めたが、実は20枚以上貼る場合は\sum_{m=m_i} k_iの平均を取っているのと同じという理由から、21枚以上貼る場合がそもそも存在しないらしかった。答えを構築するときの境界ミスで2WA。Fのsolvedが少なく、しばらく考えてわからなかったのでGに移った。こちらはインデックスに対する係数列を考えれば瞬殺で、どの係数がどれくらい出現するかはimos法で求まる。自由度は係数の重複度の階乗を掛け合わせたものになる。

Fに戻る。最後の状態からさかのぼるのはいい性質が見つからなかった一方、最初の状態から進めるのは、常に最強の装備を組み合わせて最強のものを手に入れるのが最適だと分かった。フィボナッチ数列を考えるとあまり操作回数は大きくならなそうだったのでBFSをしたがTLE。操作回数が同じもののうち、手に入れた最強装備2種類の和が大きなものの上位1万種くらいに絞ってステップを進めるという謎の枝刈りを行ってもTLEだった。ここで、NMの値に大きな差があると操作回数が多くなることに気づいた。しかしこの場合は小さいほうがすぐに上限に達するので、どちらかが上限に達した場合の残り回数を前計算しておくことでそのようなケースに対しても高速に処理できるようにした。ずっとWAが出ていて困っていたが、前計算の際にシナジーを考慮するのを忘れていただけだった。8ペナの末何とかACしたが、謎の枝刈りの正当性が全く存在しないのでちょっと怪しい。

ラノベを1冊読了。「信長転生」。まったく肌に合わなかった。なぜなのかがうまく言語化できない。主人公が性欲を積極的に表に出すキャラなのが合わないのかとも考えたが、そこまで問題ではない気もする。テンプレすぎるというのも、受け入れられたラノベがあった覚えがある。そういえば、同じ作者の「貴族転生」もなろうで読もうとして挫折した覚えがあった。そちらの思い出した内容と合わせて考えると、話が軽すぎるのが問題なのではないだろうかという結論に至った。主人公が何かして周囲の人に褒められる、というサイクルを回すのが異常に速い気がする。当然、そこに鬱展開が挟まる余地はない。確かにストレスフリーではあるだろうが、自分には合わなかったということ。特別そういう展開が印象に残っているだけかもしれないが、それはそれで、自分の肌に合わなかった理由としては適当だろう。

7000フォロワーになった。

日曜日のCodeChefの結果が反映され、レートが変動していた。2146→2309(+163)で橙になった。これまで順調に色変してきたが、次回赤というのは不可能だろう。

またラノベを1冊読んだ。「ブラックな騎士団の奴隷がホワイトな冒険者ギルドに引き抜かれてSランクになりました」5巻。先ほどの反動か知らないが、かなり面白く感じられた。表面的には変わらず無双ハーレムものではあるのだけれど、突っかかってくるキャラにも背景があって、最終的にはいい奴だったとわかるなど、ちゃんと厚みのある物語になっている。また注意深く読んでみれば、登場するいろんな国家における物事の考え方の違いを丁寧に表現していて、主人公はそれを受け入れつつも自分の軸はブレさせずに動いている、ということがわかる。

TCB41の商品でアマギフが送られてきた。先週、返信期限を過ぎたメールを発掘してしまったコンテストのものだ。向こうでよしなにしてくれたらしい。感謝。

TCB41のメールが迷惑メールに入っているのを見つけてびっくりした。こちらは返信期限が11/12だったので、もう手遅れ。

週記(2021/11/15-2021/11/21) - kotatsugameの日記

朝方日記を書いて布団に入り、Pixiv小説を読んでいる間に寝落ちした。午前7時くらいだった。

11/23(火)

午後2時くらいに目を覚ます。購買に行こうと思ったが、今日は祝日で閉まっているということに気づいてやめる。ぼんやりとスマホを弄っているうちに時間が経過し、インターンの予定が近づいてきたので、午後4時くらいに布団から出た。昨日のECRはHackフェーズが終了し、全完が保たれていた。

食事してからミーティング。先週火曜日の日記で言及したように、ヒアリング先の業務を自分でもやってみるということになったので、その研修だった。一応他の研修の録画だったり資料が共有されてはいたのだが、わざわざ時間を割いて説明していただけることになって感謝。実際聞いているとかなり複雑な作業だったので、画面共有で作業の流れを見つつ質問などできたのは助かった。2時間半ほどかけて一通りの説明が行われ、あとは実際にやってみてのお楽しみというところらしい。この業務は、僕が普段やっているコーディングとは違って明確に納期が決まっている作業なので、ちゃんと稼働できる時間を把握して作業が割り振られることになる。週に最低限保証できるだろう稼働時間を見繕って向こうに伝えた。自分の時間はかなり有り余っているはずだが、自分が毎日何時間も作業できる体質ではないということが分かってきたので、伝えた稼働時間はかなり少なくなってしまった。

ハーメルンを1作読んだ。「これ以上龍気活性してしまうと、あたしはバルファルクになってしまう」。僕のヒーローアカデミア世界にモンスターハンターの(今のところ)天彗龍バルファルクの能力だけが持ち込まれたクロスオーバー。途中でエタっている。実はヒロアカにはほぼ初めて触れた。一応個性という能力があることや、やたら強いオールマイトというヒーローがいることくらいは知っていたが、ストーリーを全く知らないので、目新しく読めた。あとがきで作者が進学校イキりをしていて面白い。

syosetu.org

別のハーメルンを読み始めたが、途中でCGR17に出た。

Dashboard - Codeforces Global Round 17 - Codeforces

Aはよ……くない。N=M=1のとき、理論的には全く質問をせず特定することができる。k=0が許容されるのかが問題文からは読み取れなかったので、どうするか非常に迷ったが、statusを見るとめちゃくちゃWAが出ていたので、おそらくk=0がコーナーケースとなっているのだろうと思って出したら通った。これをCGRのA問題に置いた人は垢BANされても文句は言えない。Bはちょっと悩んだ。回文の条件を確認していって、最初に条件が満たされなくなった値のペアは、そのどちらかを削除しなければならない。つまり削除する値の候補が2通りに絞られて、あとはそれぞれ試して、チェックはその値を全部削除したときのことを考えればよい。Cもけっこう悩んだが、選ぶ人数を決め打つとそれぞれの(a_i,b_i)が満たす必要のある条件がわかり、その条件を満たすものを先頭から貪欲に取ってよいため、二分探索できる。1secでn\log nを出すのは少し躊躇したが、問題なく通った。

Dは難しい。まず奇数を1つ以上選べば必ず構築可能である。では偶数のみの場合は、と考えると、4で割ったあまりで分類することでサンプル1が合う。しかしサンプル2は合わない。さらによくよく考えてみると、どうやら値を割り切れる最大の2べきの値で分類しなければならないようだった。これに気付くのに非常に時間がかかり、ACしたときにはコンテスト開始から1時間が経過していた。Eは、任意の3要素a\le b\le ca+c\ge 2bを満たす必要があるらしい。このもとで貪欲にとっていいようだったので、a=a_ib=a_{i+1}を選んで、あとはa_j\ge 2b-aを満たすような最小のjを選んでb\leftarrow a_jとしていけばよさそう。a=bのとき以外は値が2べきオーダーで大きくなっていくようだったので、先頭要素の重複だけは別でカウントしておけば全探索できないこともなさそう。jを選ぶ部分でlogがつくので、O(n(\log n)^2)になってしまうが、どうしようもなかったのでそのまま提出したら通った。相変わらず1secとTL設定が攻めている。priority_queueのlogにしたのだが、lower_boundとどちらが速かったのだろうか。

この時点で-100近いレート変動が予測されていて絶望気味。Fに崖ができていたので、何とか解きたいと思って気合を入れた。結論から先に書けば、残り30分で解法が完全に分かったものの、実装ができずに通せなかった。重み2のパスを重み1のパス2本に変換してから戻す、という考察に執着していたようにも感じられる。

まず自明な上界として、重さ1の辺が奇数本出ている頂点しかOddyseyになれない。逆にそのような頂点は全部Oddyseyになれる、ということを、実際に構築することで示す。まず重み1の辺を、「サイクル」と「奇数次の頂点同士のパス」に分解する。サイクルはぐるっと一周向き付けたら放置で良い。パスのほうは、とりあえず適当に向き付けておく。次に重み2の辺を考える。その辺が結ぶ頂点のうち少なくとも片方がOddyseyにならない場合、最後に適当に向きづけてよい。両方がOddyseyの場合が問題だが、これもうまくできるということを以下で述べる。

そのような辺だけを抜き出して、また「サイクル」と「奇数次の頂点同士のパス」に分解する。サイクルは先ほどと同様無視。今作ったパスは、重み1の辺からなるパスたちの先頭か末尾に属する頂点と、同じく先頭か末尾に属する頂点を結ぶパスとなる。実は、重み1の辺からなるパスを適当にひっくり返すことによって、これを重み1の辺からなるパスたちの先頭に属する頂点と末尾に属する頂点を結ぶパスにできる。といっても簡単で、奇数次の頂点は偶数個しかないので、適当にひっくり返していても最終的には矛盾せず収まるのである。

そのようにすると、重み2の辺からなるパスは、末尾から先頭に向けて向きづけることでOddyseyという状態を崩さずすべて向きづけることができるようになる。あとは最後に残った辺を向きづけて終わり。実装はかなり面倒。サイクルとパスに分解するのがまずとんでもなく面倒で、そのあとひっくり返すのも、影響が伝播していくのが微妙に面倒。コンテスト終了後もコーディングを続け、3ペナを出して40分後に通った。5000B近くのコードになった。WAを突破するためにテストケースを見てしまったので、本番ではEまでがうまくいき、考察がすんなり済んだとしても通せなかっただろう。ちなみに考察に間違いはなく、向きの取り扱いミスとか条件の書き間違いだった。

自分はまずdfsでパスに属する辺を検出し、それらだけからなるグラフを適当に突き進んでパスに分解した後、残りのグラフでこれまた適当に突き進むことでサイクルに分解した。これは手数が多くて絶妙に面倒。heno239氏は以下の方法で、まずサイクルを取り除いた後パスに分解したらしい。こちらのほうが手数が少ないかと思ったが、あんまり変わらない気がしてきた。そういえば僕の解法は完全に線形時間を達成している。辺削除を辺番号とフラグで行うのは苦痛の極みだったが、その甲斐あって実行時間は結構短かった。

結局5完遅解き、130位でレートは-89する予測。伝説は遠い。

夜はまたハーメルンを読んでいたが、いい加減切り上げ、日記を書いて布団に入った。さらに少し読み進めて就寝。午前7時半だった。

11/24(水)

午後3時半起床。

昨日から読んでいたハーメルンの最新話まで読了。「蛇王龍、海賊になる。」。

syosetu.org

ワンピースとのクロスオーバーで古龍が海賊をするのは非常に良い設定だった。よく知らない古龍が大量に仲間として出てきてパワーバランスがガタガタに崩れているのも許容できる。ただ、原作介入の結果ルフィ一味が崩壊気味になったのが受け入れられず、辛かった。タグの「アンチ・ヘイト」というのは、こういうことなのだ。これまであまり気にしていなかった(念のためという理由でつけている人が多い?)が、受け入れられるものとそうでないものがある。

家を出て閉店間際の購買に駆け込み、注文していたラノベを2冊受け取った。そのまま学食の夜の部の開店を待ち、入店。一昨日学食に行った際、「納豆はカウンターで注文してください」という張り紙があったのを覚えていて、夜も納豆が食えるのか!とわくわくしながらレジに進んだ。ここで重大な勘違い、レジとカウンターは別の場所を表す言葉であった。また焦っていて、今日も張り紙があったかどうかを現時点で覚えていない。同じ位置に何かが貼ってあったのは確認したはずだが、あまり自信がない。

レジに進んで意気揚々と「納豆をください」と発言。レジ担当の方もよくわからないまま、とりあえず納豆を含めて会計を済ませた。ここで僕が納豆を持っていないことに気づいたらしい。僕もよくわかっていなかったので、「言えば納豆がもらえるはずでは……?」などモゴモゴ言っていた。それでレジ担当の方がカウンターに確認したところ、今日は納豆がないらしい。返金処理になったのだが、ミールカードから払ったのにプリペイドカードに返金ぶんがチャージされ、よかったのかちょっと謎。

さて、以上のことは開店直後のレジで行われた。そのときレジは1台しか稼働しておらず、ふと後ろを振り返ると学食の入り口までレジ待ちの列ができていた。非常に申し訳ない思いをした。納豆がないので白ご飯を噛みしめながら振り返ってみるに、やはりレジとカウンターを混同していたのが混乱の原因だったのだろう。深く反省。帰り際に一言謝ろうと思ったのだが、新人さんにレジ打ちの研修をされていたようだったので声をかけるタイミングをつかめず、すごすご帰ってしまった。人の顔を見ないように過ごしているので、服装や位置で認識するしかなく、日が変わってしまえばもう誰だったかも定かではない。二度と謝ることができないままになってしまった。

昨日のCGRのレート更新が来ていて、予定通り2990→2901(-89)。

受け取ってきたラノベを読んでいたら、いつの間にかJOI一次予選(第3回)の過去問が公開されていた。提出記録を見るに、公開から11分ほど遅れて見つけたらしい。今回も例のごとく、パソコンやスマホでURLを開いておいて、定期的に公開されていないか確認していたのだった。しかし結局今回見つけたきっかけはatgolferの更新だった。

URL自体は推測できるので、先週日曜日からずっとスマホとパソコンの両方で以下のページを開いており、起きている間は数時間に一度リロードしていたのだった。

週記(2021/10/18-2021/10/24) - kotatsugameの日記

JOI 2021/2022 一次予選 (第3回) 過去問 - AtCoder

急いでコードゴルフした。A問題はdcの自明な5Bで、負け。ただBCDは今のところ最短を取れている。Bは負の数の取り扱いと切り上げ除算がそこそこ面倒で、非自明に感じられる20Bのdcコードが最短。CはPerlかと思ったがVimが予想外に短くなった。Sの末尾に"WR"をつけ、先頭からK個目の'R'の上にカーソルを移動させる。これはfRを適切に繰り返せばよい。この状態で1文字右に移動すると、元のS'R'K個存在したならカーソルは'W'の上に移動し、K-1個しか存在しなかったならそのまま'R'の上に留まることになる。あとはカーソル下の文字のみを出力すればよい。Dはかなり自明なPerlコードから縮まなかった。

CodeChefのドメイン名の有効期限が切れていた。今日の夜からコンテストがあるようだが、大丈夫だろうか。正直面白がる気持ちしかない。

ホスフィンに誘われて、CoRe Challenge 2022というコンテストにチームを組んで出ることになった。マラソンも得意ではないし、そもそもドメイン知識がないとマラソンにすらできない可能性がある。何とか頑張りたいが、どうなるだろうか。

今週金曜提出のレポートがあるので、講義動画の視聴を始めた。Python数値計算をする講義で、どうせしばらくPythonの初歩的な内容だろうと思っていたら、いつの間にかそれっぽいことが始まっていた。しばらく見ていて、先生が「\frac{n(n-1)}2回の掛け算をする」と言いながらi=1..nに対して0.9**iをしていたのが気になった。べき乗は単なるループで計算されるのだろうか?

Pythonの内部実装を調べることにした。どうやら最も一般的なものがCPythonであり、GitHubでコードを見ることができるようだ。単純にpowerで検索して出てくるコードから辿ると、謎の構造体のメンバ変数tp_as_numberが関数の配列になっているようで、そこからべき乗を実装している関数を取り出して呼び出しているらしい。しばらく構造体のほうから攻めていたが、検索をかけると大量に引っかかって心が折れそうになった。tp_as_numberで検索してみるとそこそこうまくいって、何とかそれらしき実装にたどり着けた。整数型と浮動小数点数型の2種類の実装があった。

cpython/longobject.c at 345ba3f080c140dee3102f472bc166c2db191bcc · python/cpython · GitHub

整数型は絶妙な高速化が絡み合っていて読み解きづらいが、おそらく二分累乗法をしているだろうというコードが上のリンク先で読み取れる。

cpython/floatobject.c at 345ba3f080c140dee3102f472bc166c2db191bcc · python/cpython · GitHub

一方、浮動小数点数型は簡単で、いくつかの場合分けを取り除いた後はpow関数に投げている。これは別の行で定義されているということもなさそうだから、C言語由来の関数と見て間違いないだろう。C言語のpowの実装を調べるまではさすがにやらなかったが、順当に考えればexplogを使うはずで、これはどちらもテイラー展開で実装されていることが期待できる。0.9**iの計算にはこちらが使われるだろう。つまり、実際には先生はO(n)回の掛け算しか行っていなかったのだ。

このことを指摘しようかと思ったが、そもそも数回前の講義に今更何を難癖付けるんだ、と自省して、取りやめた。

午後11時半からCodeChefの野良コンテスト。しかし開始したはずなのに問題がない。しばらくTLで騒いでいるうちに1時間延期された。ラノベを読みながら待って午前0時半からまた参加しようとしたところ、明日に延期というメッセージが表示されていた。明日はCFのコンテストがあるので、もう出ないかな……。メッセージを読むと、どうやら夜にドメイン名の有効期限が切れた影響がまだ残っているから、ということらしい。

「公女殿下の家庭教師」10巻を読了。この巻は休憩の巻という感じで、ストーリー的にはあんまり進んだ感じがしない。主人公アレンとヒロインリディヤの二人がずっと一緒に行動していて、それ以外のキャラとの絡みもほぼない感じだった。あとがきにもリディヤがアレンを独り占めする巻と書いてあって納得。量こそ少なかったがバトルシーンもあり、アレンとリディヤのタッグが非常にいい感じだった。

CGR17-Fの公式解説を読んだ。重みが等しい2辺(u,v)(v,w)を、1本の辺(u,w)に組み替えるということを繰り返すと、最終的に各連結成分が重みが交互に現れるパスまたはサイクルになって、それらを適当に向き付けると関係する頂点が全部Oddyseyになる。あとは組み替えた辺を戻せばOK、ということらしい。かなり頭が良い。

「サベージファングお嬢様」2巻を読了。面白かった。1巻の途中から学園生活がスタートして、この巻では初めからずっと学園が舞台になった。新たに登場したキャラクターとの交流がメインで、ストーリー上の敵組織も今回は終盤に攻めてくるだけだったが、一方バトルシーンでは主人公の新たな能力が発揮されて少し成長した感じがある。と、表面的な内容はそんな感じで言葉にしてみての印象は薄いが、読後感が非常に良かった。バトルの決着の爽快感はあるものの、それ以外で一体何がそんなに心地よかったのか自分でもよくわからない。とにかく面白いと感じたことだけは確かだ。

12月発売のラノベをメインに23冊予約した。「時々ボソッとロシア語でデレる隣のアーリャさん」3巻が12月の頭に発売されるが、それだけ予約受付が終了していた。残念。かなり快調に売れているのだろう。月が変わったどこかのタイミングでリアル書店に買いに行くことにしたい。

布団に入って少しなろうの更新を確認し、午前7時就寝。

11/25(木)

午後1時ちょっと前に起床。今日は少し余裕をもって4年ゼミのZoomに接続できた。今日のゼミは特に発表もなく、のんびりと聞きながらラノベを読んでいた。

ネトゲの嫁が人気アイドルだった」2巻を読了。1巻の印象があまりよくなく身構えて読んでいた。最も受け入れられなかったヤンデレ気味のヒロインについては、慣れたのかあまり気にならなかった。これまた1巻の感想を受けての見方だが、2巻も主人公とヒロインの関係を深めることをメインに、ネトゲやアイドル要素はほぼなかったように感じられた。まあそれは分かりきっていたこと。この巻では主に主人公の内面を掘り下げていて、案外こちらも闇が深くてびっくりした。

人気アイドルだとかネトゲの要素を目的としていたのに、実際にはヒロインの性質やヒロインと主人公の関わり(のみ)を掘り下げるような内容だったからだろう。あとはヒロインがヤンデレなのもあまり受け入れられない。

週記(2021/06/21-2021/06/27) - kotatsugameの日記

次に「神様の罠」を読了。しばらく前に半分くらい読んで放置していた短編集だった。どれも非常に面白かった。以下短編ごとに感想を書くため、ネタバレ注意。

「夫の余命」:呑気に読んでいたら叙述トリックでびっくりした。これでこの本に対する緊張感のようなものが生まれた。帯に「二度読み必至」と書かれていて、実際この短編は本当に二度読みすることになった。

「崖の下」:米澤穂信氏の手になる短編。これを目的に購入した。ずっとつららだろうと思いながら読んでいたので、そこを外されてまんまと引っかかったなという感じ。

「投了図」:序盤からかなり不穏で、実際その予想は当たったのだが、それでも救いのある結末でよかった。

「孤独な容疑者」:普通のミステリだなあと思いつつ、アリバイ崩しの伏線が全然ないように思えたのでどうするのか見守っていたら、意表を突かれた。

「推理研VSパズル研」:題材となっている論理パズルは、以前レポートで出題された以下のものに似ている。「しばらくして」という曖昧な記述が、ちゃんと1日単位になっていて、より厳密になっていたように感じられた。それだけなら有名問題を紹介しているだけの短編だが、そこから論理パズルの状況としてあり得るストーリーを考えるという試みはかなり興味深かった。ちゃんとそれっぽいものが完成していて感動。

「3人の死刑囚がいる。3つの青い帽子と2つの赤い帽子が用意され、看守が3人にランダムにかぶせた。自分以外の死刑囚がかぶる帽子は見えている。自分の帽子が青いと確信したならば逃げてよいが、このとき実際にかぶっている帽子が赤かったら射殺される。しばらくして、3人の死刑囚は一斉に逃げ出した。なぜ3人は自分の帽子が青いと確信できたか?」

週記(2021/08/02-2021/08/08) - kotatsugameの日記

「2020年のロマンス詐欺」:途中主人公が騙されて犯罪の片棒を担がされそうになり、非常につらい思いをした。最終的にはハッピーエンドになったが、ギリギリ助かったという感じで読後もちょっとモヤモヤしていた。

学食に行こうと部屋を出たら上のほうから音が聞こえ、なんだと見上げたら花火が見えた。帰りにATMで通帳に記帳したら、インターン先から9月分の給料が振り込まれていたのが確認できて嬉しくなった。残高が思ったより多かったのを目にして感づいてはいたが、やはり通帳の一行として自分の稼いだ金銭が記録されていると別格の味わいがある。

眠気に耐えられず午後8時から午後11時まで昼寝した。起きてからCF #756 div.3に出た。

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

Aはよい。Bは自明な上限が\min(a,b,(a+b)/4)で、どうせ達成可能だろうと思って出したら通った。後から考えてみれば、その上限についての帰納法で示せる。Cは操作の最後に消す値が必ずnで、冷静になるとnと比較し続けることで残りの順序はどうとでもできる。Dは距離を0\dots n-1としてよい。E1は多始点BFSでx_iからの距離の最小値を求める。頂点1からの距離がそれより小さい頂点だけを通ってしか移動できない。E2はすぐにはわからなかったので、順位表でより解かれていたFに進んだ。Fはセグ木上のにぶたん。

E2に戻る。根を頂点1として、ある頂点uの親にはたどり着けるけれどuにはたどり着けない、というような頂点を考えれば、uにたどり着けなくするために必要な頂点xはそのほかの頂点に対しては無意味ということがわかる。なのでxの代わりにそのようなuを数えればよくて、再度多始点BFSをしておけばよい。Gはなかなか難しい。盤面を45度時計回りに回転させると、ロボットの移動は下か左に1マス動くことになる。こうすると貪欲ができて、できるだけロボットが盤面の右にいるように移動させればよい。コンテスト後に知ったが、これはLongest Decreasing Subsequenceに等しい。実際LDSに含まれる飴は1回の操作で1個しか取れず、逆にLDS回ロボットを操作しても取れないなら、それらの経路からうまく飴を選びだしてより長いLDSを構築できてしまうようだ。

Gにかなり手間取ったがそこまでが結構速かったので5位。Hackに耐えることを願う。

その後、金曜提出のレポートにようやく着手した。全然集中できなくて結構頻繁にラノベを読んでいたが、ちまちま書き進めて何とか午前6時半に完成した。今回の課題は、常微分方程式を一つPythonによる数値計算で解いて、結果に対して何らかの考察を加えよというもの。常微分方程式なぞほとんど知らないし……ということで、オリジナリティ重視で勝手に差分方程式を考察することにした。イロレーティングというのは実質差分方程式ではないだろうか。

イロレーティングを扱うというネタは決まったが、中身をよく考えないまま適当にコードを書いてビジュアライズして、と繰り返していたら、何が言いたいのかよくわからないレポートが出来上がってしまった。いうほど差分方程式っぽさも感じられないコードになっている。提出した後、ふと変数名の英語が間違っていることに気づいた。historyの複数形はhistoriesであって、historysではない。そもそもhistoryを複数形にする理由もなかったので、そこを修正して再提出したりもした。

少し日記を書いて布団に入り、ハーメルンを読んでいたら寝落ちした。午前11時だった。

11/26(金)

午後6時半起床。サークルに行けなかった。

しばらくラノベを読んで、午後8時過ぎからCF #757 div.2。10分こどふぉったのでyukicoderと被ったかと思っていたが、どうやらまだ5分余裕があったらしい。5完47位だった。

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

ABはよい。Cはとりあえず1例作ればよさそう。各インデックスに対してそれを含む区間のbitwise OR値すべてのbitwise ANDを計算すれば条件に矛盾しない中で最も多くのbitを立てることができて、しかも少なくとも1例存在するという条件からそれらは入力に適する。遅延セグメント木で区間更新したが、最後に答えを計算するとき、式変形の過程で「あるbitが立っている要素数」という情報が消えることに気づいた。コンテスト中はそのまま書き上げたが、bayashikoさんは今の発見を用いて解いたそうだ。つまり、適する数列であるbitが立っている要素が存在するかどうかさえ分かればよく、これは入力のbitwise OR値すべてのbitwise ORを見れば判別できたらしい。かなり頭が良い。

D1はdp。各1\le g\le 5\times 10^6に対して、gで割り切れるa_iの個数cnt_gを数えておく。数列の先頭にcnt_g個並べておいて、そのうちいくつかを選べばさらに\gcdが大きくなるだろうが、それをdpで計算する。具体的にはdp_g=\max_{g\mid h}dp_h+g\times(cnt_g-cnt_h)となる。D2はかなり悩んだが実はD1と同様のdpでよい。cnt_gの計算には、素数をふるっておいて素因数分解→dfsで約数全列挙、とすると速くなりそう。dpの遷移は、実は素数pに対してh=gpとなる場合しか考えなくてよいため、それだけ遷移すると全体で108回未満となり、十分高速になるようだった。コンテスト後に試したところ、cnt_gの計算のために\sqrt{a_i}かけて約数全列挙しても実行時間は大して変わらなかった。

Eは解けなかった。グラフが傾き1と0をつなげた形になるため、これをどうにか管理するものと思っていた。クエリ平方分割をすることにして、B回に一回グラフの傾き0の地点とその値を再計算し、実際に値を取得するときは二分探索でグラフのどこの地点にいるかを探し、残りB回に満たない分は愚直に計算、とした。14ケース目のTLEが取れず、コンテスト後にmapだった部分をvectorに変えるとそこは突破したが、26ケース目でやはり詰まってしまった。バケットサイズガチャも効果なし。

yukicoder 325に出た。全完、writerとtesterを除いて3位。

yukicoder contest 325 - yukicoder

Aはよい。Bは端を通り過ぎてしまい1WA。Cは面倒なdp。DはA_iA_{i+1}の間ごとに、左右どちらにどれだけ寄せるかを全探索。Eは適当にパターンマッチングした結果失敗しまくった。B_iが小さい順に貪欲に揃えることを考えてよくて、A_j\le B_i\le B_jが満たされるようなjのみの区間から取ってくることができる。区間の管理はインデックスをsetで管理し、値の存在判定はrangefreqというライブラリを使った。セグメント木のノードにソート済み列を乗せるやつだ。

Fはよくわからないがうまくいった。全方位木dp。まず最初に、データ構造をマージする一般的なテクで、各XOR値に対して根からの経路途中にその値が出現するような頂点数を数えておく。これは子らに対して再帰的に計算し、mapをマージした後、最後に根から自分までのXORに対応する値XOR[u]と部分木のサイズch[u]を使い、map[XOR[u]]=ch[u]と書き換えれば求まる。あとは求めたデータを全方位木dpで子に渡すときにきちんと更新する方法を考えればよい。結構苦労してガチャガチャやっていた。まず最初に、先ほどch[u]に書き換えてしまった値を元に戻す。これは元の値との差分をメモして、逆に引けばよい。さらに子vに渡すときの値はmap[XOR[u]]だけ正しい値に変更すればよく、vでも元に戻す作業が発生することを考えれば、今のところはvにおけるN-ch[v]v以下に対して計算した時のmap[XOR[u]]を足し合わせたものにするのがよい。後者は1回目のdfsのときにメモしておけばよい。

「僕らのセカイはフィクションで」を読了。非常に面白かった。珍しく単巻完結っぽい感じがする。帯に「作者のチート知識で無双する」など書いてあるが、これはあまり本筋を捉えているとは言えない。ネタバレになるが、このラノベは作中作の作中作とかいう複雑な概念を扱っていて、読んでいるうちにその階層が逆転したりするのでかなり振り回された。総じてあらすじなどから事前に想像していた内容とは全然違っていた。ヒロインの小さな行動が最終的に壮大な話につながって、なるほどこれがセカイ系、という印象。また作者の夏海公司さんは「なれる!SE」が有名で、本人も前職がシステムエンジニアだったらしく、ところどころIT用語が出てくるのも面白かった。

朝方はずっと日記を書いていた。午前7時くらいに布団に入り、ハーメルンを2時間くらい読んで午前9時就寝。

11/27(土)

途中弁当を受け取りに一瞬だけ起きたが、そのままずるずるとスマホを触り続けるようなこともなく、すぐに二度寝に成功した。午後8時起床。食事して午後9時からABC229。

NEC Programming Contest 2021(AtCoder Beginner Contest 229) - AtCoder

Aから難しい。よくよく制約を読むと、縦または横に2マスつながっているとき、またそのときのみYesになるらしい。これをsedで書いて、1回目の提出の後すぐ/#\n.#\|#.\n#//#..#/とまとめられることに気づいて再度提出した。Bはよくわからないので適当にC++。CはRubyで出したが、サンプル1だけ試して出したらサンプル2で落ちてしまった。落ち着いてみると一体何を考えているのかわからないコードになっていて、赤面しながら修正してAC。またC++に戻って、Dは尺取り、Eは逆順に見てUF、Fは一周して最後に閉じるdp。

GはどのYに寄せるかを全探索しようとした。それを一つ固定したとき、残りのYを寄せるためにかかる手数を1文字ずつ求めて、何手かかるYまで寄せられるかを二分探索するとうまくいきそう。a手かかるYまで寄せられるなら、残った操作回数をa+1で割ることで、a+1手かかるYをどれだけ寄せられるかが求まるというもの。しかし詳細を詰めずに実装に移った結果、かなり迷走して非常に時間を食ってしまった。残りのYを寄せるためにかかる手数はいちいち更新していられないので、頻度分布と総和をBITで持って、適切なオフセットを引き算することになる。最初うっかり手数ではなくインデックスを管理してしまい、それでサンプルは合うものだからデバッグ出力を睨みつけて手計算と照合する羽目になった。解説はかなり頭がよい。

それでもHには40分以上残せたが、何もわからず。とりあえず行ごとに分解して、非不偏ゲームなのがつらいが、1手ごとに黒と白をswapすれば不偏ゲームじゃないか?とか考えていた。これでgrundy数を計算して、全然サンプルが合わないことを確かめて絶望。7完遅解きで箸にも棒にも掛からない順位になった。

コンテスト後に急いでC問題までコードゴルフして、午後11時からCodeChef。今日はNovember Lunchtime 2021。

https://www.codechef.com/LTIME102A

SUBJUMPは、図を描いてみると、iからjまで飛んだ時A_{i+1\dots j}=\mbox{元の}A_iとし、最終的な\sum A_iがコストとなるような式だとわかる。よって累積最小値を管理して埋めていけばよい。PERPAIRはまず適当に式を立ててWolframAlphaに投げた。全然帰ってこないので改めて考え、よさげな式をひねり出すことに成功した。ji\lt j-Kを固定する。まず先頭j要素の最大値がj番目に来る確率は\frac 1 jであり、さらにその上2番目に大きな値がi番目に来る確率は\frac 1{j(j-1)}である。今iには自由度j-K-1があるため、結局N!\times\sum_{j=K+2}^N \frac{j-K-1}{j(j-1)}が答えになる。シグマの中身を部分分数分解すると分母が定数になって、これもシグマの外に出せば残りは単なる逆数の和になり、累積和を前計算すれば求まる。逆数を107回求める必要があったので、全体で線形時間で求められる式を使った。

MNMXROTはちょっと難しかった。コンテスト中の考察を整理していたら、詰め切れていなかったところを見つけたが、文字列の周期に関する性質を考えると行間を埋めることができた。maxbminwを決め打つことを考えると、iBに、jWに割り振れる条件が気になる。d=|i-j|として、文字列のk,k+d,k+2d,\dots,k+(N-1)d番目が全部同じ文字だった場合のみ割り振れなさそう。結局d\leftarrow\gcd(N,d)で考えているのと同じで、これで調べる必要のあるdNの約数の個数通りになった。毎回O(N)かけても間に合うようだ。ただ、まだi,jを探索する必要が残っている。割り振れないd\mid Nが存在してi\equiv j\pmod dとなるとまずい。コンテスト中はここで、その割り振れないdに着目した。あるNの約数dであって、dでは割り振れず、h\mid dなるすべてのhで割り振れるようなものを考える。d=Nの場合割り振れず、d=1の場合割り振れるので、そのようなdは必ず一つ以上存在する。i,jとしてi\not\equiv j\pmod dなるものを選べば、実は必ず適している。

ここで、なぜ適していると言えるかに文字列の周期が関係してくる。実は割り振れないdというのは文字列の周期の一つになっている。しかも、そのような周期のうち最小のものは、そのほかの周期の約数になっているから、先ほどdの条件として書いた「h\mid dなるすべてのhで割り振れる」を満たすようなdは実はただ一つしか存在しない。そのdによってi\not\equiv j\pmod dとなれば、そのほかの割り振れないh\mid Nはすべてd\mid hも満たすので、i\not\equiv j\pmod hが従うというわけだった。

MINFUNDは結構すぐに見えた。グラフ全体は最終的に連結になるので、新たに張る辺の本数は一定である。まず二辺連結成分分解して、二つのcityを繋ぐ唯一の辺としてすでに存在する橋を使ったか使ってないかを持ちつつ、片方のcityの大きさに関する部分和dpをbitsetで行う。分解してできた木ごとに含まれる頂点数を数えて、橋を使わないならその頂点全部を含めるか含めないかの遷移があり、橋を使うならそれで木を二つに分けて、どちらか一方を含める遷移がある。最終的に、橋を使ったか使ってないかに関わらず、\frac N 2に最も近づいた部分和が片方のcityの大きさになる。コンテスト後にbitsetの話からCodeChefのメモリ制限の話になって、問題ページに書いてないのでさすがインドと言っていたところ、LayCurseさんに1.5GB制限らしいというのを教えてもらった。思ったより大きかった。

CHASEはかなり難しかった。部分点1は直線グラフで、2点から両端にそれぞれ\left\lfloor\frac{K-1}{2}\right\rfloorだけ進めそう。部分点2は2点の距離+1が答え。部分点3から考察する必要がある。自分は結構後まで気づかなかったが、まずK\le 2の場合は2点の距離+1が答えになるらしい。K\ge 3の場合を考えると、次数3以上の頂点には必ずたどり着けることがわかる。またクエリで与えられる2点も次数3以上と見なしてよい。その他は、次数3以上の頂点を繋ぐ頂点と、次数3の頂点から距離\left\lfloor\frac{K-1}{2}\right\rfloor以下にある点も到達可能。ここまで考察すると、毎回dfsするO(NQ)が書ける。

最後に満点解法。とりあえず直線グラフの場合を取り除き、またK\ge 3とする。次数3の頂点には必ずたどり着けるので、そのような頂点のうち一つ(直線グラフではないので必ず存在する)を根として、他の次数3の頂点とその間の頂点たちに到達可能のマークをつけておく。すると、残ったグラフは次数3の頂点から生えるパスの集合になる。それぞれ親となる次数3の頂点からの距離をメモしておく。このもとで、Kの昇順にクエリを処理する。まずメモした距離がk:=\left\lfloor\frac{K-1}{2}\right\rfloor以下の頂点は新たに到達可能となる。クエリで与えられた点に距離がマークされていた場合、それが含まれるパスの長さをL、クエリの点にメモされた距離をxとすると、そのパスでは新たに距離\min(x+k,L)以下の頂点がすべて到達可能になる。今そのうちkまでの頂点がすでに到達可能とマークされているので、増分は\max(\min(x+k,L)-k,0)である。これをクエリの2点それぞれで計算するが、2点が同じパスに乗っている場合があるので、その時はxとして大きな方のみを計算することにする。増分の計算が壊れていたが、何とか修正できてギリギリで通せた。

全完9位でレートは2309→2463(+154)。いい感じ。

ABC229のコードゴルフに戻る。Aはコンテスト中の二度目の提出が最短になっている。Bはdcで、一度取られたが取り返せた。なかなかシンプルなコードになって気持ちがいい。Cはコンテスト中に出したPerlコードの、変数の値の書き換えを防いでいるところで更新があって1B縮められた。DはPerlで尺取り。尺取りの幅の最大値を求めるとき、右端でループして左端はインクリメントするかしないかだけでよい、というテクがかなり好き。左端のループが消えるので相当短くなる。もちろん途中で持っている区間が条件を満たさなくなってしまうが、最大値を更新するためには左端をインクリメントしない必要があって、このときちゃんと持っている区間は条件を満たしている。EもPerl。残りは手付かず。

日記を書いて午前7時半ごろに布団に入り、満を持してハーメルンを読み始めてしまった。

1作読了。「僕のヒーローアカデミア それは古龍の王たらん」。特定の古龍の能力というよりは、いろんな古龍の能力が登場していたらしい。よく知らないので気づくのが遅れてしまった。途中から一気に不穏になって、今は主人公がなんだか似非サイコパスっぽくなって作中で暴れまわっている。あまり面白くなかった。

僕のヒーローアカデミア それは古龍の王たらん - ハーメルン

もう1作、ヒロアカ世界で古龍の個性を持った主人公という似たような設定のハーメルンを読んでみたら、こちらはかなり面白くて、うっかり午前11時半くらいまで読んでいた。明日はコンテストが目白押しだが、もう睡眠時間が確保できない。急いで寝た。

11/28(日)

午後4時半に無理やり起きる。食事して午後5時からOpenCup。今日はANFCJKEGHの9完。

Aから順に読み始めた。さっそくAがそれっぽい貪欲で解けそうで、証明を考えつつ順位表をチラチラ見ているとどんどん通され始めたので、ようやく解法に自信をもって書き始めた。実は証明もほとんど完成していた。解を適当に組み替えることで貪欲に選んだ場合と一致させられることを示す、という方針だった。最近似たような問題を見たのを覚えていた。次にNが他の2人によって通された。ソートする比較関数でガチャを回すやつで、チームメイトによって証明がつけられていてなるほどなあとなった。順位表を見るとFが通されていたので読む。これはすぐ解けた。戦法が2種類あって、どちらにどれだけ操作回数を割り振るかを全探索すると、あとは貪欲でいいので差分更新ができる。

その後Cを考え、2以上の要素の個数がかなり少ないことを考察してからちょっとパソコンを借りて実験を回した。要素がすべて2以上の整数であるような配列であって、総積引く総和が2\times 10^5以下になるようなものを探索。5e8個くらいあるようで普通に配列を全探索すると間に合わないが、出現する値の頻度分布なら全探索できそうだった。改めて実験はしなかったので、書き上げて実行するとめちゃくちゃ時間がかかったのを見て血の気が引いたが、1か所オーバーフローでループのbreakがうまくいっていなかったのを直したら爆速になり、通った。Cを書き始めるちょっと前からJが挑戦されていて、数回のWAの末に通っていた。

Kは最初に消すことになる最小の頂点番号を持つ葉の親を仮の根とするのがうまい手で、その親が葉になるまで部分木を貪欲に消した後は、残った部分木も消すか、グラフ全体を再度再帰的に解くかの2通りになる。最初WAが出て、dfsが正しく回っていないバグを直したら、直線グラフのケースでO(n)回グラフ全体のdfsをすることになって困っていた。しかしdfsの根は1つずつしかずれないので、再計算する必要がないことに気づいて難を逃れた。最悪ケースは直線グラフで、手元では1.3secくらいかかっていたが、ジャッジは0.6secくらいで爆速だった。次にEが燃やす埋めるっぽいという話になって、自分ではどう弄っても条件がうまく表現できなかったが、頭の良いライブラリを見つけてきてそれに投げてみればいいんじゃないか?と言い残し、しばらくHを考えているうちにいつの間にか通っていた。実際にどのくらいライブラリに頼ったのかは不明。

koyumeishi.hatenablog.com

Gは、Hの考察を交代して行ったチームメイトが瞬殺していた。Hは全然わからないので、考察メモに残されていたO(n^{2.5})を通りそうだと強固に主張して書き始めてもらった。このあたりで4時間が経過し、ARCに移動した。

僕がARCに逃亡した後の話。結局Hは先ほどの計算量の元になったコードで通ったらしい。ジャッジが爆速だったのではなく、計算量の評価が違っていたようだ。2乗の木dpで配列をK番目までで打ち切ると、計算量がO(NK)になるという話を聞いた。全然納得できなかったので調べてみたら、すぐに見覚えのあるブログ記事が見つかった。やはりこういうものを読むだけ読んでも問題を解かないと本番で役に立たないようだ。

木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

午後9時からARC130。4完29位。崖が大きい。

AtCoder Regular Contest 130 - AtCoder

Aは削除した文字が等しくなる場合の数と誤読してサンプルも試さず提出し、WA。冷静になると連続する同じ文字たちから2文字選ぶ場合の数になる。コードゴルフしやすそうな見た目をしていたので5分くらい粘着していたが、思ったより短くならなかった。Bは操作を逆順に見る典型で、それどころか問題設定からかなり見覚えがある。Cは繰り上がりの回数を最大化すればよいらしい。繰り上がりする桁は下に詰めることができて、そうすると考えることが単純になる。まず1桁目で繰り上がりを起こして、以降桁同士の和が9を超えられる限りそれを並べていけばよい。並べるのは小さい値から貪欲に行えばよいが、1桁目はどうするのが最適か全然わからない。しかしこれだけは全探索できる。かなり考察がスムーズに行って、ここでいったん順位表を見るとかなり上のほうにいてびっくり。

Dを解く。頂点の大小関係で辺を張ると、二部グラフであって片方からもう片方にしか辺が張られないようなDAGになる。これのトポロジカルソート順を数え上げられないか考えていたが、うまくいかない。もう一度問題に立ち戻ってみると、グラフが木であるという条件を使えていないことに気づいた。これを生かそうとすると木dpが思い浮かんで、自然な流れで2乗の木dpを考えてみようという気になった。つまり、サイズc_lc_rの部分木があって、それらに値を割り振って部分木の根の値が小さいほうからl番目とr番目になった場合の数から、マージして部分木の根のうち大きな方がk番目に来る場合の数を求めたい。もともとサイズc_rの部分木の根だったもののほうが値が大きくなった場合を考える。このとき、l+i\le c_lなるiに対してk=l+r+iの場合の係数が\binom{l+r+i-1}{r-1}\times\binom{(c_l-l-i)+(c_r-r)}{c_r-r}と求まる。これはl'=l+iと置けば、1\le l\le l'を満たすようなlすべてに対して係数が等しくなるため、累積和を求めておけば各l',rに対して定数時間で求められる。部分木を入れ替えたものも同様に計算できて、これで2乗の木dpのマージ部分が書けた。実装は、辺が\lt\gtのどちらに対応するかでコードを変えるのが面倒だったため、毎回列をreverseして片方のタイプの辺だけ考えつつ、最後に答えを2倍することにした。かなり単純になってくれて気持ちがよかった。また順位表を見ると、相変わらず上のほうにいた。

Eに1時間ちょっと残せたが、実装が終わったのすらギリギリで、しかも全然合わなかった。これについては今日の日記の最後に書く。コードゴルフはA問題のみ、コンテスト中に書いたものが最短になっている。

午後11時半からCF combined。疲れているのか頭がふわふわしていた。

Dashboard - Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

Aはi\lt jを幻視してdpを書き、サンプルが合わなくて誤読に気づいた。誤読しなければ簡単。Bは"abc"が重ならないので、長さ3の部分文字列を全部見ればよい。更新するときは関係する高々3つの部分文字列をチェックする。"abc""ABC"と大文字にしていて、サンプルが合わずしばらく困っていた。Cは後ろから見て、2以上の要素の出現を直近2回分、インデックスiについてi\bmod eごとに保存しておけばよい。素数判定も必要になる。DはUFをマージしていくと目的の達成に使わない辺の本数がわかるので、毎回それを使ってできるだけ大きな集合を作ればよい。ここまで考察すれば、制約が小さいので、集合のサイズを毎回全部取得してソートして足すのが間に合う。

Eは難しかった。まずクエリなしの場合を考えると、一番左の'a'と一番右の'c'の間に'b'が存在しないようにするとわかる。先頭からどこまでは'a'を消して、末尾からどこまでは'c'を消して、と考えると、結局あるi\le jが存在して[0,i)'a'が存在せず、[i,j)'b'が存在せず、[j,n)'c'が存在しないようにできればよい。実はより一般に、ある文字列Sが文字列Tを(連続するとは限らない)部分列に持たないためには、文字列S|T|個の(連続する)部分文字列への分割であって、i番目の部分文字列がT_iを含まないようなものが存在すればよいらしい。\Leftarrowは、区間を固定して先頭から当てはめようとしてみれば、不可能なことがわかるので示せる。\Rightarrowは、T_1を含まない区間を先頭から貪欲に取ると、残りの文字列がT[1:]を部分文字列に持ってはいけないので、帰納法が回る。

2021/11/29追記:\Rightarrowは嘘だった。反例としてS=01T=00がある。実は文字列Tの隣り合う文字が異なれば正しいらしい。これは、打消し線の下の事実が正しく成り立つことからもわかるし、区間への分割を貪欲法で行うのが最適という観察から、それで分割できなかった場合のことを考えると、対偶を示すこともできる。

今、A_iを、[0,i)'a'の個数引く'b'の個数とし、B_i[0,i)'b'の個数引く'c'の個数とし、文字列中の'c'の個数をcnt_cとすると、最小コストは\min_{i\le j}A_i+B_j+cnt_cになる。C_i=A_i+\min_{i\le j}B_jとおくと、\{B_i\}\{C_i\}がそれぞれ区間ADD区間MINの遅延セグメント木で取り扱える。i番目の変更を考える。\{A_i\}への影響は常に数列の右端までの区間ADDになり、直接\{C_i\}に書き込めばよい。\{B_i\}への影響は\pm 1ごとに分解して考える必要がある。まず更新前の値でx=\min_{i\le j}B_jを計算して、+1の場合はx\lt\min_{l\le j\lt i}B_jなる最小のlに対しC[l:]に1加算、-1の場合は先ほどのxx-1になってC[l:]から1減算、とする。その後B[i:]に変更分を足して、分解した\pm 1がまだ残っていればそれを処理する、という流れになる。lの探索はセグメント木上の二分探索で行った。

Fは解けなかった。右端を固定して左端を動かしたとき、stackを使って最大値・最小値それぞれについてどの値がどのくらいの区間で出現するかを計算できる。これを60種類のpopcntそれぞれについて遅延セグメント木の区間加算で表現して、最小値と最大値両方が同じpopcnt数の場所の数、つまり遅延セグメント木で2が入っている場所の個数を求めたい。これはその遅延セグメント木によって全体の総和と奇数(つまり1)の個数を取得し、引き算して2で割ることで求まる。計算量はO(n(\log n+\log \max a_i))だが、全然通らなかった。まず遅延セグメント木を60本持つとMLEして、1本持って60回のループ中で使いまわす形にするとTLEした。区間をsetで管理してみたが、これはそもそも被っている区間を求めるときの計算量の保証ができない。しかしコンテスト終了ギリギリだったので、書き上げてええいままよと出してみたら、一応これまでより2ケースだけ進んだところでTLEしていた。

129位で2901→2837(-64)。あっという間に見覚えのあるレートに落ちてきてしまった。つらい。また大当たりを引くまでは雌伏の時、というよりは、大当たりを引きたかったら精進をしなければならない。漫然とコンテストに出ているだけでは強くなれないが、今はコンテストに出るのが楽しすぎてupsolveを放り出している。

ARC-E問題を解いた。頑張って何も見ず96/99まで通ったが、最後はTLでテストケースを見てしまった。

i_1Iを分割する。分割された区間のうち今見ているものを[l,r)とする。直前のi_{l-1}=i_1に対する操作で値がxになっていた場合、[l,r)で操作された値はxに確定するか、\{x,x+1\}のどちらか未確定になるか、x+1に確定する。これらはこの順番で区間に並ぶことになる。それぞれどれに確定したかを持って次の区間に進むとする。

まず簡単なものから、i_{[l,r)}に同じ値が3回以上出現してはいけない。i_ai_bで2回出現した場合、i_{[l,a]}による操作ではxになることが確定し、i_{[b,r)}による操作ではx+1になることが確定する。また、直前の区間x-1xに確定した値を操作する場合も確定する。さらに、直前の区間で未確定だった値も、今確定した影響で確定する可能性がある。この「未確定だった値が確定する」のがややこしくて、例えば\{x-1,x\}からx-1に確定した場合、区間でそれより前に並んでいたものも一斉にx-1に確定する。xに確定した場合は、それより後ろが確定する。これで確定した値たちについても先ほどのチェックをもう一回しなければならない。書いていて気付いたが、このループは2回以上繰り返される可能性がある。自分のACコードでは1回しかチェックしていない。

また、前の区間で操作された値が今見ている区間で操作されない場合もカバーする必要がある。これは、以降さらにi_1に操作するか、つまりr\lt Nであるかどうかによっても処理が変わる。どちらにせよxに確定した値はそのままでよく、x-1に確定した値はr\lt Nなら即座に-1を出力、そうでなくとも最後にx+1に確定した値が存在すればこれまた-1を出力することになる。\{x-1,x\}で未確定の値については基本的にxに揃えることになるが、先ほど述べた判定を回避してx-1のまま生き永らえることが可能ならば、x-1に揃えることになる。

このようなチェックが分割された区間について順に行われる。次の区間に移るときは、\{x,x+1\}で未確定のものはいったんxとしておいた。最後に、残りの要素を最後に操作した値-1で埋めて、操作回数をそれぞれから引くと、最初の数列として最も値が小さいものが得られる。

日記を書いていたら午前8時になってしまった。この1週間、インターンの進捗を何一つ産めていない。明日起きてからやりたいが、起きられるかどうか……。やはり自分には1on1駆動開発しかないようだ。

ここまで書いて今週の週記は28000文字を超えた。1日当たり4000文字という大台を達成し、過去最長な気がする。今週はコンテストが多かった。数えてみると1週間で10個のコンテストに参加していた。これらの問題に対する解法などを逐一書いていたらこのような長さになってしまったというわけらしい。

週記(2021/11/15-2021/11/21)

11/15(月)

先週の週記を投稿してからはすぐに布団に入った。30分ほどなろうを読んでから、午前4時就寝。

午前10時起床。微妙な眠さで二度寝ができそうだが、勉強会の準備にどれくらいかかるかわからないので、起きておきたい。しばらく布団でモゾモゾしてから起き上がり、学食に行った。

帰りに購買で予約していたラノベを5冊受け取った。これも先月末にまとめて予約したものの一部だ。正直もうどれを予約して、どれを受け取って、どれが未発売なのか自分でも把握していない。予約すると受付メールがバラバラに届いてしまうのでちょっと不便である一方、特に気にしなくても予約商品の入荷メールで新刊発売を知れるのは便利だった。そろそろ以前予約した分は打ち止めだろうから、また11月下旬~12月発売のラノベを予約しておこう。

以前から生協では一気に10冊以上購入したりと特徴的な行動をしていたが、冊数よりは頻度が重要だったのか、今日ついに声をかけられた。「何日くらいで読まれるんですか?」……実はほとんど読んでいないのだ。ただまあ、そういうことを事細かに説明するとオタク早口になってしまいがちなので、ただあいまいに「すべて読み切ることは考えていない」というような返事をした。今日買ったラノベは転生ものとハーレムものばかりだったので、微妙な恥ずかしさがあった。

帰宅して勉強会のスライド作成を開始。題材は「競プロでシェルスクリプトを使う」というものだ。この題材の発想自体は一か月ほど前からあったが、決め手になったのは、最近行われたマラソンコンテストで複数のケースを手元実行するのが難しかったという話をTLで見聞きしたからだった。というわけで、シェルの操作をほぼ知らず、サンプルをコピペして貼り付ける方法しか使えないくらいの競プロerを想定してスライドを作成することにした(というかそれ以上の人間に対して発表できるほどの自信がない)が、よく考えると勉強会の聴衆は普通に職業プログラマなので、釈迦に説法。

リダイレクト回りの話を念入りに書いて一段落ついたと思ったが、やはり内容として初歩的なものが多い。あまりに丁寧に書きすぎて内容が希釈されてしまっている感じもする。残りの部分は競プロで使えるシェルスクリプトの実例を取り上げて解説を加えるつもりだったが、もうちょっとテンポよく進められるよう、細かいことまでは書かないことにした。罠にも触れない。厳密でない表現を自分だけが気にしていても、知っている人は勝手に補完してくれるだろうし、知らない人には混乱させなくてむしろ良いだろう。シェルスクリプトの実例については、自分の引き出しがないので、online-judge-toolsのサブコマンドのhelpで表示されるものをいくつか拾ってきた。

定例会直前に勉強会のスライドが完成した。進捗報告のスライドを超特急で生やして臨む。進捗報告では、もうちょっと現実に即したことを、というような意味合いの指摘をされた。行っている学習は結果をビジュアライズしてもあまり出来が良くないため、Lossの値だけ出して比較することをずっと続けていたが、進捗報告としてはあまり良くなかったらしい。何かビジュアライズの結果を見せるか、見せられないような絵にしかならないなら、いっそ進捗なしと言い切ったほうがわかりやすいのかもしれない。

その後、勉強会。ただでさえ定例会で話す内容が多かったため普段より遅めのスタートだったが、さらに自分の話す分量も多く、おそらく終始オタク早口だったろうに1時間以上かかってしまった。逐一丁寧に説明するような時間はなかったのでかなり飛ばし気味だったが、それで希釈された内容も少し元に戻ったかもしれない。ともかく、お付き合いいただいた皆さんには感謝しかない。内容に関するコメントで、知っていることばかりだろうと思っていたが思いがけず新しい知識を得られた、というものがあり、かなりありがたかった。

上でも述べたが、スライドは競プロer向けに作成したものだった。競プロで使うだろう入出力回りを丹念に説明している。というわけで、使用したスライドはその後、いろんな競プロerに見てもらえるようTwitterで公開した。ここにもリンクを貼っておこう。

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

スライドの題名は題材そのまま「競プロでシェルスクリプトを使う」となったが、これを見て、シェルスクリプトで競プロの問題を解くのだと思った人が何名かいた。それでもよかったかもしれない。しかし結構泥臭い作業が必要だった気がするな、と思って、例えば文字列の末尾1文字取得をbashの変数展開でやるのは大変というツイートをしたら、よりシンプルなやり方を教えてもらえた。変数$aを使うとして、これまでは「文字列長を取得してそれ-1以降のsubstringを取る」という意味で${a:${#a}-1}を使っていた。二重に変数展開をしているのでシンタックスハイライトがかなり醜くなった記憶がある。ところがこれは${a: -1}でできる。自分で試してダメだったような、と思ってよく見ると、途中に空白がある。実はこの空白がない場合、別の変数展開の機能である代入なしデフォルト値と解釈されてしまっていたようだ。

少しインターンを進める。引き継いだコードをそのまま使っている箇所があるが、その部分の理解が浅いことを自覚したので、ライブラリについていろいろググっていた。期待していた機能がちゃんと存在したので、やりたいことは問題なくできそうでよかった。

その途中で気づいた事実をコードに反映してみて、ちょっと学習を回しつつ午前0時過ぎ就寝。

11/16(火)

午前7時半に目を覚まし、しばらくなろうを読んでいたようだ。午前10時過ぎにまたて、次に午後2時半に起床。昨日回していた学習の結果は、Lossの値こそよくないものの値の分布的にはかなり求めている状態に近いように見える。昨日の改善を採るか採らないか、ちょっと迷ってしまう。

午後3時からミーティング。これはヒアリング準備ということで、普段の定例会とも1on1とも違ったものだったから、ちょっとばかり緊張していた。自分が準備不足であるような気もしていたが、そもそも何を準備したものかわからないので、ほぼ無手で挑んだ。結果はまあよかったのではないだろうか。メンターさんともう一人が話しているのを聞く時間が多かったが、大まかな方向性は掴めたと思う。そもそも今日はその「大まかな」部分を決めるミーティングだったので、前提としての説明だったりあいまいな話だったりが多く、準備がなくとも何とかなったという面がある。別部署へのヒアリングを始める前に、しばらく相手方の業務を自分でもやってみるのがよいのではないかという話になって、実は結構楽しみ。

このミーティングは1時間で終了し、直後にいつもの1on1。先ほどの話を踏まえての、今後の動きのようなものを確認した。あとは関係ない話として、先ほどのミーティングではカメラをオンにしていたが、背景ぼかし機能がすごいですねということを言った。これも機械学習の結果だろうが、動画を処理できるほどのスピードというのは凄まじい。

午後6時前に家を出て、途中油そばを食べ、ゲーセンに行った。まず先週土曜日の続きとしてLv.13+をちゃんとAJ埋めした後、Lv.14に進んだ。こちらもできる限りAJ埋めするつもりだったが、曲数が多いのもあってこの日は中途半端なところで終わった。

閉店までプレイした後マックに寄ってポテトとコーラを注文。午前0時閉店とのことなのでちょっと焦っていたが、食べ終わってみるとまだ結構時間があった。帰宅してシャワーを浴び、しばらくチュウニズムネットを眺めてから布団に入る。なろうを読もうとしたが即座に寝落ちした。午前1時半だった。

11/17(水)

午前8時起床。少しなろうを読んでから起きる。今日は午前中からゲーセンに行くつもりだ。

と、その前にTCB42が開始していたので、解いた。ここ最近1時間ちょっとで全完できているので舐めてかかったら、ひどい目に遭い、合計で5時間くらいかかってしまった。午前中からゲーセンに行くどころか学食の昼の部にすら間に合わなかった。例のごとくこの日記が公開される頃には終了しているコンテストなので、各問題の感想を書いておこう。

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

1問目はともかく2問目からもう面倒だが、5問目までは問題なかった。まず6問目で1ペナ出した。誰も0を宣言していない状況下で0が出て全員0点、というケースはカバーしていたが、それ以外のところで0の処理を間違えていた箇所があった。この問題で0が登場するのは、単純に問題を面倒にしたかったんだろうとしか思えない。くだらん。7問目もよい。8問目は変数をミスって1ペナ。これは僕が悪いが、サンプルで落ちてくれなかったのが悲しいミスだった。9問目はよくある迷路探索、と思ったがMLEに悩まされた。MLE?と疑いながら高速化を繰り返していたが、ある時BFSでキューに入れる条件を間違えていることに気づいた。距離が同じになる場合もキューに入れてしまっていたのだ。結局この問題では3ペナも重ねてしまった。

10問目。面白いことは面白かったが、できれば解きたくなかった。問題文が難解だが、結局区間ごとにそこにある確率を求めて、あとは選んだ地点から離れるよう区間の端に寄せたときを考えればよい。制約から区間を処理するのはグラフを作ってBFSなり行えばできて、選ぶ地点としては、差の絶対値の和を考えれば区間の中央だけが候補になる。あとは累積和など使えば解ける!と思って提出すると、1ケースだけWAだった。考察ミスや実装ミスを探して、コードを単純化したり処理を変えたりしてみるも、このケースのWAは取れない。

1時間くらい考えていると、区間の幅がちょうど1のとき、期待値の計算を間違えていることに気づいた。通常\int_x^{x+1}|y-t|dy=\left|x+\frac 1 2-t\right|であるが、x\lt y\lt x+1のとき壊れる。そこで、ちゃんと期待値を計算するようにして投げなおすも、やはりWA。さらに30分かけてよくよく計算すると、この場合区間の中央が最適になるとは限らないことが分かった。立式すると二次関数になって、平方完成して最小値を求めるコードを出すもまだWA。立式に間違いがあって、二次関数の二次の係数にその区間に対応する確率(の分子)が出現するようだった。これまで出力する答えの分母は常に2だったので、なぜ\bmod{10^9+7}で答えさせるのか理解していなかったが、ここにきてP\lt 10^9+7の制約とともに理解した。この限られた場合だけ分母が一般の整数になってしまうのだ。コードを修正しているとオーバーフローが避けられなさそうだったので、有理数を使いたいことでもあるし、Rubyで書き直すことにした。さらに30分くらいでコーディングし、dfsの再帰が深くなりすぎて1ペナ出しつつ、ついにAC。3時間と10ペナかかってしまい、得られたスコアは最初に9/10通った時のものと全く同じだった。

午後3時からゲーセン。昨日イベントマップを(最後のスタチュウを残して)走り切ったので、今はNEW ep.Iを進めている。それで解禁した新曲を埋めつつ、Lv.14の残りを触っていた。Lv.13+で苦労させられた「XL TECHNO -More Dance Remix-」の紫譜面がLv.14にあって、それは譜面があまりに嫌らしいのでSSを出して放置したが、それ以外は鳥で埋めて、さらにAJを出せそうなものも軒並み出したと思う。

夜になったので夕食を探して歩き回った。何か定食が食べたい気持ちだったので記憶を頼りに定食屋を探したが、なく、そうこうしているうちにラーメンが食べたくなってきたので、結局つけ麺屋に入った。食後の腹ごなしに本屋に行って本を3冊買い、またゲーセンに戻る。いよいよLv.14+を触り始める。

とりあえず全部触ったので、銀ポゼが復活した。また、試しに「XL TECHNO -More Dance Remix-」を選曲してみたら、急に覚醒してAJが出てしまった。4回しかプレイしていないはず。多分もう二度と出ない。それにしても、縦連が何連打なのか数えたりしていないのだが、ずっと交互で叩いているだけで本当に全部通せるのだな。事実としては面白いが、譜面になると非常に嫌らしい。

今日も閉店までいて、日付が変わるしばらく前に帰宅。OPを確認すると98%台後半まで伸びていて安心した。

OVER POWERもプロフィールから確認できるようだ。思ったより低くてびっくりしたが、まだ新曲を埋めきっていないので、当然といえば当然だった。……よく考えたら、そもそもMASTERを解禁していないので、OPにも含まれていないのだろうか?そうだとしたら、自分のOPがもともと低かったということで、かなりショックだが。

週記(2021/11/08-2021/11/14) - kotatsugameの日記

しばらく椅子に座ってぼんやりしていたが、火曜日の講義にコメントをつけるという課題が水曜日で締め切りだったので、焦って出した。数分間に合っていないが、正直コメントだけなのでどうでもいいとは思っている。

ABC227の学生4位だったらしく、キーエンスからアマギフ1万円に関するメールが来ていた。5位か6位だろうと思っていたが、よくわからない。賞金メールといえば、ゲーセンにいる間にTCB41のメールが迷惑メールに入っているのを見つけてびっくりした。こちらは返信期限が11/12だったので、もう手遅れ。まあ1000円だし、いいかな……。

午後9時からABC227。 KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) - AtCoder 全完10位。学生順位は5位か、6位か。よくわからない人が一人いて怪しい。

週記(2021/11/08-2021/11/14) - kotatsugameの日記

yukicoderで1問問題が公開されていたので解いた。手を付けるのが遅く、考え始めた時にはすでに「ZobristHash」というタグが見えていたので、解法は一瞬。このハッシュ方法の存在自体は知っていたが、使ったのは初めてだった。

No.1746 Sqrt Integer Segments - yukicoder

午前2時半就寝。

11/18(木)

午前10時前起床。うっかりハーメルンを読み返し始めてしまった。

午前11時半くらいに切り上げて学食に向かい、帰ってきてゼミに備える。今日は夕方から別のセミナーがあるとかで、ゼミが普段より30分前倒しになっていた。しかし午後0時半になっても始まらない。LINEでの会話を見るに、先生にメールを送っても返事がないようだ。午後0時45分になって、普段の定期ミーティングのZoomに入ることができた。しかしこれは普段通りの設定で、先生はいまだ音沙汰なし。しばらく4年生の進路についての話をしていたら、午後1時ちょっと前にようやく先生がZoomに入ってこられた。前倒しにしたことをすっかり忘れておられたらしい。ほぼ通常通りの時間から始まった。

発表を聞きつつメールを確認していたら、pixivのほうでメッセージが来ているのを見つけた。以前書いたpixiv小説がイベントの抽選に当たり、アマギフ1000円がもらえるらしい。そのような商品があることを知ってはいたのだが、まさか当選するとは。イベントの情報を見るに、本当に抽選しているだけなので、ただただ運がよかった。

またこのツイートが最後の一押しとなって、小説のPVが1000を突破した。しばらくPV数を確認していなかったが、じわじわ伸びてはいたようだ。

ゼミは何事もなく終了。僕も先週の残りの分を発表したが、スライドを作成した時の記憶が薄れていて、流れを把握できずちょっと大変だった。事前に見直しくらいしておくべきだった。今週の発表者の時間を圧迫してしまった結果、その人もまた週をまたいで次回発表することになった。

先週の対面ゼミがかなり良かったということで、今先生が教室を確保しようとしていて、成功すれば今後ずっと対面でゼミが行われるようになるらしい。移動が面倒なことだけが辛い。最後に、先週対面で集まって撮影したゼミの集合写真が共有された。写真屋に送って、卒業アルバムにも載せてもらうことになる。

ゼミが終わった後は布団に倒れこみ、朝の続きでハーメルンの読み返しを続けていた。「アイドルの世界に転生したようです。」の外伝の部分。おすすめのなろう小説まとめでも触れた。ここはオリ主たちがライブをやる完全オリジナルの章で、逆にそれ以外の章は、ちゃんと二次創作らしく元となった公式ストーリーがあるらしい(が、自分はアイマス関連に無知なのでよくわからない)。それが理由か、普段ライブのシーンはあまり描かれないのだが、そのぶんここで念入りに描かれていて満足感があった。何度読んでも面白い。

これ本当に好き。外伝『Days of Glory!!』はまるまるライブをやるんですけど、マジで面白い。それまでの数百話を振り返り、泣きながら読んだ。

おすすめのなろう小説まとめ - kotatsugameの日記

syosetu.org

「天才最弱魔物使いは帰還したい」の更新が来ていた。作者ツイッターを見ると、どうやら2巻の発売が決定していたらしい。しかも12月のはじめとかなり近い。多分この巻で前作「Tamer's Mythology」の終わりまでが描かれるだろう。そちらをちょっと読み返していたが、やはり唐突に終わったように感じられて消化不良という思いがあるので、ぜひぜひ3巻も出てほしい。いくらでも待つ。

先週日曜日のyukicoderのコンテストのupsolveをした。有向辺を張って強連結成分分解するというアイディアだけを知ったまま臨み、2問とも解けたが、方法は少しDM分解と異なった。一つ固定した最大マッチングに含まれる辺は、両方向に張るのではなく、含まれない辺と逆方向に張ることにする。解説にある一番上の資料に従えば、含まれる辺は任務からスパイに、含まれない辺はスパイから任務に張る。このもとである辺を含む閉路、あるいはマッチングに含まれない頂点からの到達可能性を知りたい。

特に後者も、適切に辺を追加すると強連結成分分解で解ける。具体的には、任務側ではマッチングに含まれる頂点から含まれない頂点へ、スパイ側ではその逆に、すべての組に辺を張ればよかった。これで「任務側でマッチングに含まれない頂点から含まれる頂点へ」「スパイ側でマッチングに含まれる頂点から含まれない頂点へ」の到達可能性がどちらも、今追加した辺を使った閉路の存在判定で解ける。辺を張るのは超頂点を追加すればよい。解いた後に解説を参考に調べて、DM分解も何となくの理解はしたつもりである。

Y.Y. さんの単発問題コンテスト 2 - yukicoder

AHC007の開催が発表された。株式会社THIRDがスポンサーにつく。これまで具体的な名前は出さなかったが、これを機会に明言しておこう。ここが僕が今インターンをしている会社だ。そういえば、火曜日のミーティングの時に自分でも業務を体験することになって楽しみということを書いたが、これには理由がある。以下のページに「お客様の現場に突入し、お客様と同じ仕事を経験し、現場に落ちている改善の変数を見つけ、管理ロイドに組み込む事を得意とする」という文言があって、そういうのが一番「開発」っぽいなと感じ、初めて目にした時から気に入っていたのだ。

チームメンバー – 株式会社THIRD

日付が変わったあたりからは溜めていた日記を書いていたが、眠くなったので途中で切り上げて布団に入った。試しになろうを開いてもほぼ読み進められず、午前3時就寝。

11/19(金)

午前11時前に目を覚ましたら、昼過ぎから予定されていたミーティングが来週火曜日に変更になっていた。CLISTを見てコンテストの予定がないことを確認し、メッセージに了解の返事をしておく。その後予定表を確認していたら祝日だということを知り、びっくりした。まあ問題ない。

その後二度寝しようとしたが失敗。昼過ぎになって起きだし、学食で昼食を摂ってからゲーセンに行くことにした。すでに全曲触ったのでやることもないかと思えたが、旧Lv.13の上位勢が軒並みLv.14+となったので、残っているLv.14を埋めればAJフィルまで付けられるのではないだろうかと考え、今日はAJが出せそうなものを出し、同時に未SSS+も減らしていた。

成果としてはLv.14の新規AJが新曲含め+9。未SSS+も残り4つになり、さらにLv.14+もいくつか伸びて、かなり満足のいく日になった。またFREEDOM DiVE↓が無理せず押せたり、Blackmagik Blazingの最後の高速トリルがガチ押しで追いついたりと、成長を感じる場面も多かった。最近上手い人の横からの手元動画を見たので、それっぽい脱力を意識してみたが、効果があったのだろうか。

途中食事のためガストに行ったが、ラーメン屋に慣らされた自分の金銭感覚ではやたら高く思えた。不用意に入るのは憚られる。これもあって閉店前に手持ちの現金が底を尽き、帰宅した。そういえば今日は部分月食だったらしい。ガストに行った前後に見る機会もあっただろうに、完全に失念していた。

今日のyukicoderのコンテストを少しだけupsolveした。ACDは自明、Bは実験。Eで詰まったので切り上げた。

yukicoder contest 323 - yukicoder

昨日の日記を書き進め、少しコードゴルフをして就寝。午前2時半だった。

11/20(土)

午後0時半起床。学食に行こうと思ったが、午後1時からyukicoderでコンテストがあるので止めにして、パックご飯を温めつつインスタント味噌汁を用意した。しかし食べる前にコンテストが始まってしまった。

yukicoder contest 324 - yukicoder

すさまじい難しさで、ABを何とか通した後CとDを読んで心を折られた。5時間コンテストだったが、実質1時間半くらいしか参加しなかった。実はCまでは客寄せ用問題のつもりだったらしく、完全についていけない。AはbitDPに見えるが、2行持つ必要があって実装が爆発。書いているうちに実はパターンは少ないのでは?となり、試しに最初少し決め打った後埋めてみると、4x4をいくつか横に並べたもののみ、それぞれに2通りの敷き詰め方があることに気づいた。これをもとにdpを書いてAC。

Bは最初頑張って立式しようとしたが合わず、文字の種類数を絞っての実験に切り替えた。立式の段階でNの偶奇が関係することはわかっていたので、それで分けて眺める。Nが奇数の場合はすぐ法則性がつかめたが、偶数の場合は全然わからなかった。文字の種類数2の場合はOEISにあったが、そこから演繹できない。種類数3は、そのままでは見つからないのだが、全体をN=2の場合の答えで割ったものが見つかった。一般項に3が何か所か表れていたのでそれっぽく書き換え式を整理すると、種類数2の場合の式と一致したので、これが正解であることを確信。出すとACだった。

上のツイートの最後の一文は結構過激な言葉を使っているが、コピペのパロディという文脈があって言いやすくなっている、という解釈を見た。確かに、文脈を知っている側からすれば強い言葉というよりはネタに走っているような印象を受け、一方これまでその言葉を使ってこなかったことから一線を越えた怒りが表現されているとも捉えられる。

ハーメルンを1作読んだ。設定がかなり良かったのだが、9話でエタっている。

syosetu.org

夕方は日記を書き進めていた。午後9時からABC228。

TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) - AtCoder

なんとか全完して19位。学生順位なら10位に入っていたりしないだろうか。

Aから面倒。AWKで場合分けを連ねた。Bは適当にやる。Cは境界の周辺が微妙に怖い気がしたが、別に怖くなかった。Dは-1の区間を管理することも考えたが、-1のindexを全部setに入れても間に合う制約なのでそちらで解いた。

Eは答えがM^{K^N}であることがあまりに明らかすぎて、何を問うているのかしばらくわからなかった。これを\bmod{p=998244353}で答えればよいことを確認して、慌ててdcで出すと、WA。dcが微妙に信用できなくなったのでとりあえずC++で書き直すも、さすがにこれで答えは変わらないよな……となってもうちょっと考えた。フェルマーの小定理を使おうとしているが、a^{p-1}\equiv 1\bmod{p}a\equiv 0\bmod{p}のとき成り立たなかったことに気づく。今制約はM\ge 1に見えるが、上限をよく見るとM=pなどがありうるようだ。さらにK^N\equiv 0\bmod{p-1}となったとき、M^0を計算してしまって困るらしい。K^N\gt 0であることが分かっているので、このような場合は答えを0としてしまってよさそう。これで出すとACして、さらにdcでも、計算した指数にp-1を足すことで正しく計算できることに気づき、通しておいた。

Fは二次元累積和をしたあと二次元区間minがしたい。二次元セグ木を貼ることも考えたが、定数倍がちょっと怖いので、スライド最小値2回で書くことにした。参照する配列を間違えていてしばらくサンプルが合わなかったりとコーディングはちょっと苦労したが、通る。

Gは非常に難しく、また面白かった。パッと見普通のdpかと思ったが、重複をどう省くかが問題のようだ。同じ数字を生成する移動たちが今いるマスの集合を管理して、これをどんどん分割することを考えたが、冷静になると管理する集合の個数が答えの通り数になるため容易に爆発する。埒が明かないので、移動の特徴を観察することにした。すると、2回の移動をまとめると、駒が今いる行だけで状態を表せることに気づいた。この考察を経てさっきの集合の話に戻ると、等しい集合を何個管理しているかを持つbitDPが可能なことに気づく。これで本当に重複が省けているのか半信半疑で書くとサンプルが合う。計算量もちょっと多めだが、手元でサンプル3がほぼ一瞬なのでまあ通りそう、と思って出すとAC。

Hはあっけなかった。とりあえずA_iをソートして重複を省いておき、どの区間の値をそろえるかをdpする。オンライン・オフライン変換など考えていたが、C_iの累積和など用いて冷静に立式するとCHTだった。この時点で残り20分弱だったので、イチから書くと間に合うか自信がない。ということでうしさんのライブラリから、直線の傾きが単調なときのCHTを窃盗してきた。いろいろなケースに対応していてかなり便利だった。ドキュメントを読んで適当に使ってみると見事にサンプルが合い、そのままACした。

Convex-Hull-Trick-Add-Monotone | Luzhiled’s Library

コードゴルフ。A問題は、stxの間隔を、差を24で割ったあまりを取ることで求め、大小比較するRubyコードを見つけた。強そうなのでこれをdcで書いておいた。BはRubyPerlも試してみたが、AWKが大幅に短くなった。Cは隙のないシンプルなRubyコードが提出されていて負けかと思ったが、Perlで縮めることに成功した。普通にsortすると辞書順なので比較関数を書かねばならなかったところ、bit反転しておけば264から引いたような値になるので桁数が揃い、辞書順比較と数値での比較が一致する。その状態でも数値の差は保たれるので、判定も正しく行えるという寸法。Dは負け。Eはコンテスト中のコードから、998244353-1=119\times 2^{23}+1-1を利用して定数の記述を縮めたコードが提出されていた。パースの関係で空白が入っていたため、それを頑張って取り除いたようなコードを書いたら、13秒差で勝った。残りはGがC++で最短になっているくらいで、手付かず。

火曜日に出ていたPythonの課題をこなした。講義スライドの内容はいよいよデータ分析が本格化してきたなあという感じで、気合を入れて課題提出用のノートブックを開いてみたら、今週もまたサンプルコードとしてほぼ答えそのままのコードが書いてあって拍子抜けした。弄るところもほとんどないので、ちょっとビジュアライズなど追加して終わり。

しばらくラノベを読んでから、午前4時半就寝。

11/21(日)

正午あたりしばらく起きていたが、1時間くらいでまた寝た。午後5時半起床。食事してから、昨日のABCがいくつか縮められていたので、コードゴルフしていた。

A問題は負け。t-xs-xを比較してもよかったらしい。言われてみれば確かにそうで、sを先頭に持ってくる手間がなくなり-2B。C問題は、Perlで行の和をとるとき、空白を+に置換してevalするのがシンプルで短かったらしい。別のところで縮めて取り返した。Dは昨日からさらに更新されていて、そちらのコードからさらに-2Bできたが、ARCに出ている間にさらに縮めて取り返されていた。

昨日から読んでいたラノベを読了。「恋人全員を幸せにする話」。この作者の著作では「クラスの大嫌いな女子と結婚することになった。」を読んでいて、そちらの文章のテンポが結構面白かったため、こちらも購入した。ヒロインが極端なことを言って主人公が冷静に突っ込むという掛け合いはこちらでも健在で、やはり面白かった。しかしこの作者が描く登場人物が誰もかれも極端な思考・行動なのはちょっと気になる。

午後9時からARC129。ギリギリの4完で自尊心が粉々になった。

AtCoder Regular Contest 129 - AtCoder

Aは最上位bitだけが問題なので、それを全探索。Bはよく見ると累積max/minを計算すればよかった。ここまではシュッと通ってかなりいい感じだったのに、C問題で迷走してしまった。三角数で分割するのだろうなと思い、しかし7ばかり並べるとちょっとまずそうだと思ってしまい、142356をずっと繰り返してみていた。判定関数を書いていろいろ試したが全然合わない。長い間適当に試していたが、ふと自分の書いた判定関数そのものに注目すると一瞬で分かった。「文字列のある位置から後ろを数値としてみたものを7で割ったあまり」を全部計算し、それぞれの重複度を見てカウントしていたが、その7で割ったあまりは7種類全部任意に作り出すことができる。つまり三角数7個以下で分割できればよくて、これは実際にやってみたらできた(多角数定理で、3個以下で分割できるらしい)。あまりをずらすための数の計算に手間取ったが何とか実装してAC。

Dも全然わからずかなり辛かった。適当に差を取ってみたりしてもいい性質がなさそうだったので、操作回数をa_iとしてA_i+2a_i-a_{i-1}-a_{i+1}=0の式を考えることにした。隣接する2項を決めると全部決まりそうだが、そうやって決めていった結果が合わない場合もあるらしい。たとえばa_0a_1(0-indexedにした)を決め打ったとすれば、頑張って展開するとa_0=a_N=A_{N-1}+2A_{N-2}+\dots(N-1)A_1+Na_1-(N-1)a_0が得られる。ここで、すべてのa_iから同時に1引いても結果は変わらないので、a_0=0としてみる。するとA_{N-1}+2A_{N-2}+\dots(N-1)A_1は非正かつNで割り切れる必要があって、しかも次にa_1=0と決め打つときの更新も定数時間で行える。とりあえずこれらの条件を満たした場所を全探索してみるコードを投げ、当然のようにTLE。

次に、a_{N-1}の値をa_Nと同様に計算して、ちゃんと決めていった結果が合うことを確かめてから改めてa_i\ge 0をチェックするコードを投げた。TLEするケースは減った。最初に\sum A_i=0をチェックしてみても変わらず。やはりa_i\ge 0のチェックをしているのがまずいらしい。何か区間加算のセグメント木などで扱えないかと考えていたが、無理そう。残り時間がなくなってきたので、試しにa_iの最小値を全体に足しこんでみると、なんと通ってしまった。どうやらa_i\ge 0の条件を外しても解は定数の差を除いて一意らしい。

Dの解説は、操作回数の差を取っていてなるほどなあという感じ。そちらの差を見る問題は初めて見る気がする。言われてみればA_i+2a_i-a_{i-1}-a_{i+1}=A_i+(a_i-a_{i-1})-(a_{i+1}-a_i)で、よく見る係数列なのだから気づいてもよかったはずだ。

コンテスト後にしばらくAとBのコードゴルフをしていたが、どちらも負けていいところなし。失意のうちにCodeChef SnackDown 2021 Pre-Eliminationに出た。

https://www.codechef.com/SNCKPE21

PRDTPAINは、列の先頭・末尾と、そのできるだけ中間のものを選べばよい。尺取り法で書いた。DECSUBKは先頭から貪欲ができる。判定は、実際に選んだ際にLISのdp配列がどうなるかを計算し、残りの列は降順に並べておけばよい。初期化ミスで1WA。GOODRANKINGは面白かった。各人の勝利数を数えると、列の前半に来るか後半に来るかで完全に分かれる。分かれたそれぞれでは、誰が誰に勝つという関係が完全DAGにならなければならないので、順番は存在するなら一意に定まって、最後にくっつけて残りの部分をチェックすればよい。

コンテスト開始時は上の3問がその順に並んでいたのだが、いつの間にかSLIPPERSが大量に解かれて前のほうの問題になっていた。実際後ろから累積minをキーにするdpをすればよいだけ、だったが、境界条件を間違えて1WA。MEGAMU1はなかなか特徴的な問題文をしているが、結局包除原理ができればよさそう。タプルがspecialであるかどうかは、先頭から見ていって0を取り除いたときの最後の要素を持っておけばよいため、これをキーにしてdpした。キーの値が大きい代わりに非ゼロの部分が少ないため、vectorvalueと一緒に持つことにした。一方valueはどれくらい大きくなるかわからないのだが、結局最後にゼロかどうかさえわかればよいため、3つくらいmodintを用意してHashを取ることにした。

GUESSROWが全然わからないため、MEGAMU2に移った。先ほど述べた遷移をより詳細に観察すると、結局vectorとしてありうるのは\{\}\{(x,1)\}\{(x,1),(x-1,-1)\}とその符号反転のみであることが分かった(実は先ほどのHashは必要なかったらしい)。特に\{\}の場合は以降何をしても変わらないため無視することにして、符号反転も無視して2M-1状態のdpを書いた。もともと結構複雑な遷移をしていたので、dpに直す際にかなり手間取ったが、何とか通った。結果は6完21位。

TCB42が終了して結果が出ていた。6位。全完は少ないようだったが、僕が10問目で得たスコアがカスすぎて9完に負けてしまっている。まあ賞金が得られたのでOK、次は賞金のメールが迷惑メールに振り分けられないことを願う。

ARC129-Aのdcコードが提出されていたので、粗探しをして-2Bした。そのあとは朝方まで日記を書いていた。

週記(2021/11/08-2021/11/14)

11/8(月)

先週は週記を投稿してからすぐ布団に入り、しばらく本を読んで寝た。午前10時半だった。

午後3時半すぎ起床。眠気がかなり強かったためしばらく布団でクネクネして、30分くらいかけて布団から這い出た。

毎週恒例のインターン先の定例会がある。先週は進捗をほとんど産めていない。ICPCがあることを言い訳にしていたが、そのICPCに対しても特別努力していたわけではないので、もうどうしようもない。今週も4年ゼミの発表があるのでほとんど動けない予定だ。とりあえずパッとコーディングできることを一つ見繕い、ひとまずの形にすることにした。コーディングした後に進捗報告のスライドを作っていたら、1分ちょっと遅れてしまった。定例会は特に何もなし、のはずだったが、いよいよヒアリングに向けて動き出すということで、手始めに来週火曜日にミーティングが追加された。頑張っていきたいという気持ちはある。

毎週、定例会の後に勉強会が開かれる。来週は僕が担当なので、何かひねり出しておく必要がある。これまで2か月見てきた感じ、題材は本当に幅広いので、まあ何を発表してもそれなりに受け入れられるのではないかという楽観的な期待がある。その前に木曜日のゼミ発表の準備もしなければならないが。

定例会が終わってからは、しばらくICPC参加記を漁っていた。C問題はいろんなチームで一人が割り当てられ、そのまま帰ってこなかったところといつの間にか通っていたところに分かれるようだ。やはりコンテスト中の時系列、特に自分が担当していないところのものを復元するのは難しい。僕の参加記も結構曖昧になっている。また、イベントの順序という意味での時系列ではなく、何時何分という意味の絶対的な時系列はさらに難しい。これについては、時間の感覚がないのは参加記を書く以外でも問題かもしれない。個人的にC問題はスムーズに通せた印象だったが、実際には問題を見てからでさえ確実に20分以上かかっているのだった。

学食に行って、帰りにコンビニでパリパリバーを買ってきた。確か、最近何かのツイートで目にして思い出したはずだ。実家では一時期よく食べていたが、いつの間にか見なくなっていた。アイスは主に母が購入するもので、母の好みか何か知らないが、一定期間は同じ種類のものがずっと買われ続ける。パリパリバーもそうして僕の前に現れ、消えていった。

AGC055-D「ABC Ultimatum」を自力ACした。

atcoder.jp

本番では手も足も出なかった問題。今日ふと思い出してちょっと考えた方針が思った以上に良く、そのままゴールまで突き進むことができた。本番ではまず判定問題を考えようとして、それにすら失敗していたので、逆転の発想で判定問題を解かないのでは?と考えた。

分解した後の文字列が、ABCa個、CABb個、BCAc=N-a-b個となったとする。このとき、文字Aは先頭a個がABCに、その次のb個がCABに、残りのc個がBCAに含まれるよう組み替えることができる。さらに組み換えを続けて、同時に文字B、文字Cについても先頭から順番に割り振ったようにできることがわかる。よって、abを全探索し、現在それぞれの文字が何個あるかを持つ3次元dpをすればよい。……というのはまだ足りなくて、最後のサンプルが合わない。同じ文字列が複数の(a,b,c)による分解に対応してしまう可能性がある。ここでいったん諦めてしまったが、実は重複を省くのは簡単。ありうる(a,b,c)のうち辞書順最大なもののみ考えるようにしたい。これは、先ほどのdpで文字列を構築しつつ、同時に(a+1,b-1,c),(a+1,b,c-1),(a,b+1,c-1)のそれぞれでも条件を満たし得るかを3bit使って持っておけばよい。この3種類のどれも条件を満たさないような文字列の分解は、(a,b,c)が辞書順最大となってくれる。祈るように実装したら最後のサンプルが合い、AC。

日付が変わったあたりからゼミ準備を始めた。手始めに、前回・前々回の発表資料を読む。毎週ギリギリに起きているので頭が回っていないし、それでなくても集中が保てなくてまともに聞けていない。いつの間にか教科書でかなり進んでおり、焦った。前回の僕の発表はmodに関する話が登場し始めたところだったので、なかなか競プロチックだなあとワクワクしていたのに、それから2週間でその章が終わってしまったようだ。

何とか読み終わったが、疲労困憊。実際に自分の発表分の教科書を読むのは明日以降にしよう。少しコードゴルフをして、布団に入ってしばらく本を読み、午前7時半就寝。

11/09(火)

午後4時から午後5時まで起きていた形跡がある。ネット小説の更新を確認して、いくつか読んでいたようだ。またすぐ寝て、実際に起きたのは午後9時半だった。

食事してからゼミ準備をする。今週のゼミは写真撮影のため対面で行われるらしいので、発表も黒板を使うことになるだろうが、準備としてはこれまでと変わらずBeamerでスライドを書くことにした。しかし教科書を1ページ進めたくらいで集中が切れてしまったので、読み止しのラノベを開いた。そのまま3時間ちょっとかけて読了。

「迷探偵の条件」。「薬屋のひとりごと」の著者の新作であるが、買ったときはそのことを知らなかった。それだけ魅力的な表紙・タイトル・あらすじだった。内容もかなり良かったと思う。ミステリかどうかはともかく、ラノベとして十分面白い。それだけに、文章が微妙なのが気になった。ロープトリックの読解が難しかったので、図が欲しいところ。また、事件の関係者をアルファベットで置いたからなのか、それを間違えているところもあった。

ゼミ準備に戻り、さらにしばらく進めるとまた集中が切れたので、今度は火曜5限のPythonの講義の課題に取り組んだ。もうPythonの基本的な使い方については一通り済ませたのか、今日はライブラリを使って多項式回帰分析をしていた。やっていることがどんどんそれっぽくなっていく。向こうも脱落者を出さないように念を入れているのか、課題提出用に用意されているPythonノートブックには元から完動するプログラムが書かれるようになった。こうなると、自分なりに追加で何かするのは難しいし、何より適当に弄って出せば終わりでいいのだからそれ以上のことをするのが面倒になる。今日はそれなりに図表など描画してみたが、実際にやっていることはほぼ、無。

またまたゼミ準備に戻ったが、今度は購買が開店する時間になったので、それと学食に行った。野菜サラダを2皿選んで健康になった気でいたが、1日のそれ以外の食事に一切野菜が含まれていないため、全体としてみれば全然足りていないことに気づいてしまい、悲しい。毎日野菜を十分な量摂取するのはなんと難しいことか。僕の食事の写真を見た親にいつも、野菜が足りていないと言われるわけだ。

帰ってきて、ゼミ準備のラストスパート。午後2時半くらいに今回の担当分の教科書を読み終わり、スライドも作り終わった。もう眠いし、一晩寝かせるという意味も込めて、手直しだったり実際の発表の流れを確認するのは明日に回すことにする。とりあえずスライドをホスフィンに投げておいた。毎回確認してアドバイスをくれてありがたすぎる。

日記を書いて寝ようと思ったが、もう少しだけ起きていることにした。今日遅く寝れば寝るだけ、木曜日変な時間に起きてしまう確率を低くできる。CF #753 div.3を埋めることにした。

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

Aはよい。Bは実験すると4回ごとに元に戻るようだ。Cは操作によって要素の大小関係が変わらないので、操作する回数を順に試していける。Dは青色の要素が順列の小さい値に対応するとしてよい。Eは(0,0)からスタートしたと考えたとき、ロボットが最大どれだけ上下左右に動いたかを持っておく。Fはdpっぽいことをするが、ループを検出した場合はそのループ内の値をすべて同じにする必要がある。ループ内かどうかを頑張って検出しつつdfsした、と思ったらMLEしてしまった。どうやら最大1e6回の再帰はマズいらしい。stackを使って自分で再帰を書いたら通った。

Gはちょっと考えてわからなかった。椅子の上で一瞬意識を飛ばしてしまったので、布団に移動して寝てしまうことにした。午後6時半就寝。

11/10(水)

消えた。

11/11(木)

午前2時くらいに起きてしまった。夢を見た。

頑張って眠ろうとして、目を瞑ってdiv.3-Gを考えていたら、解けてしまった。仕方ないのでHを読んでもう一度目を瞑ったら、これまた解けてしまった。

仕方がないので一旦起きて、ラノベを読むことにした。午前6時くらいまで読んだあと、今度こそ眠ろうとしたが、どうにも眠れず、午前8時くらいに諦めて身を起こした。

広義昨日に作ったスライドをチェックする。一読して推敲しつつ、教科書と照らし合わせて抜けている情報がないかを確認し、印刷してさらにチェック。今度は、口頭で発表する際の助けとなるような情報を書き加えておく。章の変わり目に線を引いたり、細かい式変形をちゃんと式にしておいたり、参照している定理のステートメントを確認したり。それも終わったので、これで準備完了と考えてよいだろう。

シャワーを浴びようとして、うっかり今朝読んでいたラノベの続きを手に取ってしまい、そのまま最後まで読み切った。「護衛のメソッド」。特に意識せず買ったが、著者が小林湖底さんなのに気づいてびっくりした。僕の認識では、この方は今「ひきこまり吸血姫の悶々」が売れている。内容は、面白かったと思う。どんでん返しが何重かになっているのは良かったが、仲間だった人が実は敵、を1巻からやるとは、以降シリーズ化するとなったときどうなるのだろうか。確かに、1巻が売れないとどうしようもないのだが……。

死装束を着たキャラがいるシーンに挿絵がついていたが、ちゃんと左前になっていて感心した。昔道着を着るとき無意識に右手から折りたたんでいることに気づき、左側が前になっている……!と愕然としたものだが、左前とは対面から見た時の左側が前である、ということを知って安心した覚えがある。

ラノベに挟まっていたチラシで1冊気になるものを見つけたので、hontoでほしい本リストに入れておいた。

その後シャワーを浴びたので、対面ゼミに向けて出発したのは正午だった。学食に行ったらホスフィンの姿が見えたので、呼び止めてホスフィンの連れと3人で昼食を摂った。

ゼミ。発表した側の感想としては、結構うまくやれたのではないかと思っている。何も見ずに再現できるというレベルではなかったが、定理のステートメントだけ準備したスライドから書き写して、その時ついでに述べておく情報も確認して、あとは証明を黒板でやりつつ話をしていった。本の内容自体が簡単めなので、証明の再現には特に手間取ることもなし。付け加える情報については、どういう流れで話すか整理不足だったので少しとっ散らかった場面もあった。書きながら話していたので、黒板のほうを向いて喋っている時間が長かったかとも思ったが、大きな声を出すように意識していたので、聞こえてはいたようだ。

対面でゼミをするのは、やる前は面倒に思っていたが、いざ発表してみるとかなり楽しかった。普段はスライドで丁寧に(あるいはねっとりと)式変形をしてしまい、発表時はそれを読み上げるだけになっていたが、今回はほぼ手の運動な証明を口でちょっと説明するだけで終わらせられたりと、爽快感があった。実はこれには急いでいたということもあって、自分ではかなり飛ばしたつもりでも結局用意していた分が全然終わらなかったので、次回またオンラインのゼミでスライド読み上げマシーンになってしまう予定。今週と来週分のスライドは、例のごとく以下にリンクを張っておく。

Apostol_Chapter6_6.5-6.10.pdf - Google ドライブ

ゼミが終わってから、以前院試ゼミの友人と遊んだ部屋に行って、今度は5人でスカルをプレイした。ハチャメチャに楽しかった。2回戦って、1回目は僕が勝利した。どちらの回も、全部オープンするチャレンジが成功して勝負がついていたので、かなり劇的だった。今日は、ドクロを伏せておいてブラフでチャレンジしたのに、そのまま自分がチャレンジすることになって自滅するのが多かった。どうやら雰囲気がやってやろうという感じだったらしい。気を付けたい。

午後6時まで4人でボードゲームをして、山の学食で夕食を摂って帰宅。

週記(2021/10/25-2021/10/31) - kotatsugameの日記

山の上の学食で夕食を摂り、帰宅。

朝頭の中で解いたdiv.3のGHを実際に書いた。Gは、aから必ず引かなければならない分を最初に考慮した後は、差の絶対値が最小値をとるまでaからさらに引いていけばよい。Hは、まずa+b-mでグループ分けした後は、各グループでaの値をできるだけそろえればよい。これは可能なaの値が区間になって、区間スケジューリング問題を解けばよい。

眠くなる前にと思い、掛布団を秋用のものから冬用のものに交換した。シーツについている紐を蝶結びするとき、以前から自分の蝶結びのやり方を動画に撮りたいと思っていたのを思い出して、チャレンジしてみることにした。右膝の上に左足を乗せて左足の指でスマホを保持すると、何とか動画の撮影に成功した。この蝶結びのやり方は、片方を折り曲げてもう片方を周りに巻くやり方よりかなり簡単だと思っていて、中学生の頃どこかで知って以来ずっと使っている。しかしツイートしても一切反応がなかったので、もしかしたら常識なのかもしれない。

シャワーを浴びてしばらくパソコンを触っていたら、案の定すぐに眠くなったので、就寝。就寝報告のツイートをする間もなく寝たらしい。午後9時半くらいだった。

11/12(金)

午前7時起床。もうちょっと寝ようかどうしようか迷いつつ布団でスマホを弄り始めたので、当然のように二度寝ができなくなった。午前8時半くらいに身を起こす。夢を見た。

AOJ-ICPCの600点から1問解いた。

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

問題文がちょっと曖昧だが、サンプルの3番目を確認するに、電話がかかってきてからちょうどL単位時間後まで電話を取れるらしい。適当に二分探索してみると、親切にもサンプル3で落としてもらえた。これ間に合うんじゃないかと思って二分探索の範囲を全探索するコードを書くと、通ってしまった。解説スライドを読むと、全探索が想定解らしい。向こうはlogを付けたりしているが、こちらはそれどころか1ケースあたりO(N^2 T)に定数倍が64分の1ついているので、圧倒的に速い。

さらにもう1問開いたが解けなかった。悩んでいるうちに午前10時になったので、切り上げてゲーセンに行くことにした。途中学食で昼食を摂り、先週木曜日のチュウニズム新作稼働以来初めてのゲーセンへ。

カードを通すとレートが16.82になった。実は旧筐体では、2019/12/30にレート15.83を記録してからほぼ2年highestを更新していなかった。まさかこのような形での更新になるとは……。

理論値済みの譜面を選んで試しにプレイしてみると、FASTがすごいことになった。判定Bという新しく増えた項目の値を-1.0くらいにするといい感じにFASTとLATEのバランスが取れたので、しばらくこれでやってみることにする。他に、判定時にFASTとLATEを表示したり、JCの表示をなくしたりしてみた。

今日はずっと新曲を埋めていた。MASTERチケットを使ってあらかた解禁した後、ポプアニの譜面についてはAJ埋めまで済ませておいた。やはり新筐体になって精度が出しやすくなっているのか、今日AJを出した譜面は全部99AJだった。そのうち初見AJは20譜面。最初はAIRの新しく増えたノーツにびっくりしたり、譜面が見えずミスを出したりしたが、AIR-SLIDEは手の誘導になっているということを意識すると何となくわかってきた。ただしAIR-CRUSHは譜面が見えなくなるだけなので、害悪。

通っているゲーセンはチュウニズムの後ろにmaimaiが並んでいるのだが、今日そこからSweets Timeが聞こえてきてびっくりした。どうやらちょうど今日追加されたらしい。

午後5時から1on1があるので、そこそこで切り上げて午後4時半には家に着いていた。1on1まで新しくなったチュウニズムネットを眺めていた。課金しなくても直近50回のプレイ記録が見られる(内訳は見られない)のと、ランキングのところで自分のハイスコアが確認できるようになったのが変わったところだろうか。あとはOVER POWERもプロフィールから確認できるようだ。思ったより低くてびっくりしたが、まだ新曲を埋めきっていないので、当然といえば当然だった。……よく考えたら、そもそもMASTERを解禁していないので、OPにも含まれていないのだろうか?そうだとしたら、自分のOPがもともと低かったということで、かなりショックだが。

CHUNITHM ■ CHUNITHM-NET

1on1。ここ2週間くらいICPCだのゼミ発表だのでほとんど稼働していないが、そもそもヒアリングをすると決まってからは、実際にヒアリングを始めるまであんまりすることがなかったのだ。まだしばらく時間が空くので、その間何をしていましょうか、ということを話し合った。するといろいろアイディアが出てきて、やってみたいことがたくさん積みあがった。

これでコードが縮むかと思って試してみたが、WAが出て通らなかった。なぜ通らないのか全然わからなかったので、適当に試していたら、8頂点の直線グラフで落ちることに気づいた。驚くべきことに、AtCoder上のOctaveでは以下のツイートのような行列積を正しく計算できないらしい。手元のcygwin+Octave 5.2.0やUbuntu+Octave 5.2.0では正しく計算できている。かなり謎。

yukicoder 322に出た。30分足らずで全完。

yukicoder contest 322 - yukicoder

Aはよい。Bはちょっと難しかったが、冷静になると魔法Aを優先的に使い切ったあとの残り体力の総和を魔法Bで削り切れるか見ればよい。Bの強化版らしいEに飛んで、これはBのコードをそのまま二分探索の判定関数にすればよい。Cは素因数の和。Dは適当に式を立てる。ボールが1個も入っていないケースでREを出してキレてしまった。Fは桁dp。Gは寄与が二項係数の偶奇でわかるので、Lucasの定理で求める。Hはセグメント木を想像して、浅いところに上がるのは立っている一番下のbitに1足す、深いところに潜るのは差を取ってpopcount、とした。

結構眠い。少しネットサーフィンして、午後11時過ぎ就寝。

11/13(土)

午前5時半くらいに起きてしまった。AOJ-ICPCの600点の問題をいくつか頭に入れて考えていたら、また眠れたようだ。午前10時半起床。

すぐ準備をして午前11時からゲーセン。昨日は平日なのに昼間からチュウニズムが埋まっていたので、休日である今日はもっと待ちが多いんだろうな、と思っていたら案外空いていた。今日はLv.12からどんどんAJ埋めを取り戻していくことにする。Lv.12+以上は、旧筐体のときからLv.12以上だった譜面ばかりなのでちゃんとAJで埋まっているが、Lv.12はLv.11+から上がってきた赤譜面が結構あった。ところどころ難しいものもあったが、どの譜面も2回以下でけりをつけてLv.12のAJフィルを取り戻し、そのままLv.12+、Lv.13とAJで埋めることができた。

Lv.13+まで埋めて今日は終わりにしようか、と考えていたら、「XL TECHNO -More Dance Remix-」の赤譜面が異常に難しくて、残り時間はずっとこれをプレイする羽目になった。結局難しくないところに癖がついてしまったので、今日は終わり。ちょうど待ちも出てきたようなので、連動イベントのためにmaimaiとオンゲキをそれぞれ1クレプレイし、帰ることにした。午後3時以降生協から弁当が届くので、それに間に合う必要がある。

メールでアマギフが届いていた。ABC225の飛び賞が当たったらしい。アカウントに反映するのを忘れていたTCB40の1位の賞金と合わせて、一気に1万円が転がり込んできた。定期購入しているお茶の代金に使われるだろう。それにしても、これまで飛び賞なんて設定せず上に詰めてくれよと思っていたが、実際に当たったのでそんなことは言えなくなってしまった。

ラノベ新刊チェックをした。11月下旬に発売する本は、チェックから漏れていたのか、それとも先月末に予約したからチェックを外したのか、どちらかわからなくてちょっと不便だった。

弁当は結局午後4時半に届いた。すでにかなり眠く、ちょっと昼寝でもしようかとも思ったが、せっかくいい感じの生活リズムなのを崩したくないと思い、シャワーを浴びた後は頑張って日記を書いていた。午後9時からABC227。

KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) - AtCoder

全完10位。学生順位は5位か、6位か。よくわからない人が一人いて怪しい。

Aはよい……はずが、なぜか頭が回らなくて1分もかかってしまった。初手でdc 9Bを出せて最短なので、それはよかった。Bは適当に全探索。うっかりRubyで書き始めてしまい、挙動がよくわからないので書き直すことを何度か行っていたらこれもまたかなり時間がかかってしまった。具体的には、配列の引き算が集合としての引き算であることは覚えていたが、重複する要素が消されるかどうかを覚えていなかったのだ。実はこれは消されないので、ただ引き算をすれば答えが得られる。このことがわからなかったので、本番ではわざわざ要素ごとに.include?メソッドを使っている。Cは適当に全探索したら爆速だったので出した。Dは、降順にソートすると大きなほうからいくつかは全部使えないな、など考えていたら、決め打ち二分探索を思いついた。Rubyで実装しようとして、実行時間を気にしてC++に変え、提出するとWA。二分探索の上限設定ミスと、それを修正したことにより顕在化したオーバーフローで2WAだった。どちらもRubyで提出していれば避けられたミスだけにもったいなく感じるが、そもそもC++でミスるほうが悪いのだ。ちなみに、このアルゴリズムRubyでの実行時間は問題なかった。

Eはパッと見操作回数をmapのキーに持ってdpかと思ったが、操作回数にどれくらいの種類があるのかわからず怖い。冷静になってみると、操作回数は最大でも転倒数程度にしかならないので、普通にdpを書いた。FはなんとなくAlienDPっぽさを感じた。なぜそう感じたかはよくわからない。二分探索できると嬉しいのがAlienDPの特徴だが、これくらいの制約なら二分探索じゃなくて全探索してもいいんじゃないか、と思い、答えとなる移動における大きいほうからK番目の値を固定してみたら解けた。同じ値の要素があるとつらいので、インデックスを含めて比較するコードを書いた。コンテスト後のTLで知った方法だが、大きいとしても小さいとしても良い、と取り扱うのが一番楽そうだ。Gは区間篩して残った要素は全部素数区間篩の幅をKにしてしまい1WA。修正のとき、残った素数たちに重複があるかと思ってそれに対応したコードを書いたが、残った素数は全部10^6以上なので、N-K+1\dots Nの素因数として2回以上出現することはない。

Hは難しかったが、何とか時間内に解けた。移動は、方向も含めて24種類しかない。それぞれの移動回数が分かれば経路は復元できるだろう。ここで、各マスの入次数と出次数がそれぞれ入力からわかるので、18個の等式を立てることができる。この連立方程式が非負整数の解をもつか確かめ、持てば復元、という風に解くことにした。連立方程式の解を求めるのには、今回はフローを流せばよかったようだが、わからなかったので、Octaveのglpkという関数を使った。これで解いて経路を復元すればよい。書きなれない言語で必死に頑張り、数十分かけて書き上げた。サンプル2を試すと、連立方程式の解は見つかるようだが、答えはNOになる。実際に経路を復元してみたところ、移動回数が使い切れていない。どうやら経路が2つ以上の連結成分に分かれてしまっているらしい。経路復元で移動回数を使いきれなかった場合NOという場合分けを入れるとサンプルが合ったので投げたが、WA。恐らく、連結成分に分かれるような移動回数の割り当てとそうでない移動回数の割り当てがあって、glpkで求めた解が前者の場合に落ちているのだろう。glpkでは最小化する目的関数を設定することができて、今は適当に重みをすべて1にしていたので、そこをランダム値とすることにした。これで何回か挑戦していれば、そのうちうまく連結になる移動経路を引き当てることができるだろう。というか、残り10分しかないので、これでダメだったらおしまいである。TLの様子も見て5回くらい調べるコードを書くと、爆速で通ってくれた。この乱択っぽい部分はフローで再現しようとするとかなり難しく、実際1ケースWAを出した人が、何とかランダムにしようと辺の順番を弄ったりしたという話をTwitterで見聞きした。

Submission #27234914 - KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227)

コードゴルフ。Aはコンテスト中のものでよい。Bは各Sに対してaを全探索し、\frac{S-3a}{4a+3}が正整数になるかを確認する。aの上限を適切に決めることで正であることの確認が必要なくなり、整数性だけ確認することになる。つまりこの分数が割り切れればよいという話で、それを調べるときのS-3a\equiv S+a+3\pmod{4a+3}という式変形はかなり頭がよくてびっくりした。Rakuで実装して最短。Cは典型90問-085がかなり近いので、最短コードをコピペしてちょっと変えたものを提出しておいた。DはRubyのbsearchを使うコードをVimで書くとさらに短くなるいつものやつ。以降は手付かずである。

085 - Multiplication 085(★4)

朝方まで日記を書いて、布団に入って少しYouTubeを見てから午前5時就寝。

11/14(日)

午前10時半くらいに起きてしまった。YouTubeを見たりしていたら眠れるわけもなく、しかし起きる気にもなれず布団でゴロゴロしていた。

Twitterで興味深い問題を見つけた。4つの数が与えられるので、適切に並び替えた後四則演算と括弧を使って所定の数値になるような式を作る、という問題。何パターンか取り上げられていたうち、8/(1-1/5)=10はかなり有名な問題で、それの類推から(1-1/9)*9=10(3-7/4)*8=1012/(3-13/5)=30は解けたが、3,7,7,11->2という問題の解き方が全然思いつかずに苦しんでいた。あまりに苦しいのでTwitterで助けを求めたところ、引用ツイートで教えてもらえた。

衝撃的過ぎてしばらく呆然としていた。

昼から夕方まで、来週月曜日の勉強会の準備をしようとしていたが、考えが全然まとまらず、結局Twitterを見たりして時間を無為に過ごしてしまった。午後4時からAHC006に1時間だけ参加した。このために今日の午後3時からあったCF div.1は見送っていた。

Kyocera Programming Contest(AtCoder Heuristic Contest 006) - AtCoder

とりあえずコードゴルフのつもりでRakuやVimのコードを提出したあと、C++でコードを書く。どうせ1時間後にはOpenCupなので、とにかくシンプルな解を作ることにした。まずレストランを50軒回って、次に配達先を50か所回るのが一番面倒がなくて確実だろう。このとき、レストラン同士・配達先同士が近ければ良さそう。ここで、領域を4分割すると、レストランが位置する領域と配達先が位置する領域のペアは16通りなので、どこか1つのペアには注文が50個以上属することになる。そのようなペアを固定することで使う注文を決定することにした。

レストランと配達先は適当に巡回セールスマン問題を2-optで解くことにしたが、ここで区間reverseのとき右端をbegin+rではなくend+rにするというバグを埋め込んで大変なことになった。どこで落ちているか確認するために出力を挟むと、落ちる場所が変わってしまう。気づくのに10分くらいかけてしまい、結局OpenCupには間に合わなかった。

チームメイトに遅刻すると断りを入れて、もう少しだけ続けることにする。最初の提出は1303679点だった。次に、2-optを山登り法で行っていたので焼きなましに変えると、1303679点になった。最後に、実行時間にかなり余裕があったので、使う注文50個をリストをシャッフルして何回も選ぶことにしたら、1310835点になった。これが午後5時15分のことで、このアイディアではこれ以上先はなさそうなので、今度こそOpenCupに向かう。

OpenCupはチームで9完だった。AIGEDJBFKの順。最終的な結果を見るに、この9問とそれ以外の3問の間にはかなり大きな崖があったようだ。崖の手前までちゃんと通せたのはよかった。

僕が問題を読み始めた時には、すでにAとIが通っていた。次にGが解かれていたので読み、面倒だけど書けるなと思って書き始め、ちょっと苦しみつつ投げたらWAだった。どうやら誤読をして、直線状に並ぶ街を円環だと思い込んでいたらしい。それがわかってしまえば実装で苦しむ必要もなし、と投げるとまたWA。今度はコーナーケースで、チームメイトが示唆したケースで落ちたので、それを修正して投げるとようやくACできた。次にE問題を読み始めたが、僕が有向グラフであることを読み落としているうちにチームメイトが解いてしまったので、書くのは任せてさらに別の問題を読みに行った。

D問題を読む。順当に最大の要素をどう動かすか考えて、良さそうな移動方法を思いついたが、順位表を見るにかなり落ちていたので、不安になっていた。考えているうちにどんどん正しそうに思えてきて、チームメイトが実際に書き始めたあたりで何となくの証明が完成した。具体的には、「良さそうな」移動方法によって、実際行われるべきだった移動を行えなくなることがないことが言えた。

いつの間にかJのコーディングが始まっているのを横目にKを考え始めたが、全然わからない。唸っていると急にチームメイトがFとBの解法を出してきた。それぞれ幾何と、ランレングス圧縮をmapで管理してごにょごにょするやつで、かなりやりたくなさがあったが、僕はFのほうがやりたくないと思っていて、チームメイトはBのほうがやりたくないと思っていたようだったので、二人とももう片方を担当することになった。JがWAになったあたりでまず僕がBを書き始め、途中一瞬の割り込みでJがACされつつ、30分くらいかけて丁寧にコーディング。投げると一発で通ってかなり気分がよかった。定数倍高速化のため、mapへの挿入時に挿入すべき場所のイテレータを一緒に渡すやつを多用した。しかしこれは、コンテスト後に全部外して投げてみたところ、普通に間に合ってしまった。

Fが書き始められたので、再度Kを読む。最短路という文言を見落としていて、この元では僕が適当に投げたヤバそうな解法が実はヤバくないのでは?という話になった。Fが落ちてしまったのでチームメイトがKを書いたものの、TLE。Kが何度かTLE出ている間にFのコードを読んであれこれ言っていたら、Presentation errorが出たりしつつも30分くらいで何とか通ってくれた。

残りはKの定数倍高速化だけ。1時間くらい全然光明が見えずかなり辛かったが、uniqueを取っていたところは実は最悪ケースではほとんど重複しないだろうことに気づき、チームメイトがそれならBFSではなくDFSで良いということを残り15分で指摘して、残り3分の時点で通った。細かい話を書いてもしょうがないのでこうあっさり言っているが、通ったのを見た瞬間は思わず声が出るくらい感動した。最終的に単純なDFSで解けてしまい、おもしれー問題。ヤバいケースが思いつかないからと言って投げていたが、計算量解析などはどうなっているのだろうか。

AHC006は、僕は入力された頂点のうち先頭100個のみを回っていたが、全頂点を回るコードでもよく、それが最短になっていた。Vimで書き直すとさらに縮んだ。

日付が変わったあたりから勉強会の準備を再開した。題材は決まっていて、それに関して触れたいこともリストアップしておいたので、流れを考えてスライドに埋め込んでいく。しかしもうかなり眠い。2時間弱頑張ったあたりで、もう寝て明日起きて完成させたほうが良いと考えるようになった。

寝る前に日記を書き上げて投稿しようと思ったら、昨日のABC-Hの分から書いていなかったので、+1時間くらい踏ん張る羽目になった。日曜日の部分はかなり頭が回っていない状態で書いており、書き残したいことの集合を日本語の文章にまとめる方法が全然思いつかず、苦労した。