08/02(月)

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

午後5時半くらいにすこし目を覚まし、起きようか悩んだが、もうちょっと眠れそうだったのでそのまま横になっていた。再度起きたのは午後9時になってからだった。

起きて食事をする。今日はTCO21 Regionalの開会式で、聞くところによれば参加しないとTシャツがもらえないらしい？とりあえず入ってだけおくが、人の話を聞く気もあまりない。午後9時半からのはずだったのに、直前に15分前倒しされており、早速ワクワクという感じがする。

先週の週記で、HIKAKIN TVに投稿された「ウ”ィ”エ” ヒカキンVer.」について触れた。そのメイキング動画が公開されていた。すごい熱量だ……。ほとんど同じ動きをしている8人の映像はコピーして重ね合わせたのではなく、8人それぞれで撮影していたというのを知り、ヒカキンの本気を感じた。動画1本（+メイキング）を作るために撮影チームを動員するのもすごい。どういう伝手で人を集めたのだろう、ただ金に飽かせただけではない、まさにYouTuber界の王の面目躍如といった様相だ。

youtu.be

ラノベを1冊読んだ。「グッバイ現実世界」。作者がVTuberということが帯に書かれているが、購入の決め手は普段と変わらずあらすじや表紙イラストによるものだった。実際に読んでみた感想だが、あまり面白くなかった……。

プログラムを書くことで様々な現象を起こせるVR空間が舞台で、主人公はプログラミングにおける発想だったり単純な技術力が優れていることから強いとされていた。主人公が強い話は好みだったが、こういう設定でさらに実際のプログラムも文章中に現れると、プログラマの端くれとしてはそちらに気を取られてしまう。一方、作中のプログラミング言語は文法こそ既存のものと似ているが、予約語や変数名に英語以外の言語が使われており、読んでも意味が分からない。文法だけ見ればループ処理すらない普通のコードを書いていそうなのに、何をやっているかちっともわからないというのは結構ストレスだった。

と、まあここまで作中のプログラミング言語についてしか書いていないわけだが、ストーリーとしても特に印象に残る部分はなかった感じ。

数学基礎論特選のレポートを書く。これまで3回レポートを提出してきて、これが最後になる。前回TeXでレポートを作成した。今回もそのつもりだが、さらにOverleafというサイトを利用することにした。リアルタイムでコンパイル後の文書を見つつ書けるらしく、それは当然便利だろうという感じ。まずjsarticleを使うために少し設定する必要があって、あとは普段と全く同じ感じで書ける。TeX用エディタなのでオートインデントだったり、\beginに対応する\endが自動で挿入されたりとかなり便利。

5時間くらいかけて3回分の講義資料を確認し、いつものように途中の問題を5問選んで解いた。与えられた論理パズルについて「共有知識」の定義を参考にしつつ論じよという問題があった。何か適当なモデルを用意するのかと思ったがどういう感じになるかちっともわからないので、飛ばそうとしたものの、講義資料をよく見ると他に解ける問題があまりなさそうだったので、渋々これを選び、適当に日本語で書いておいた。

出題された論理パズルはこれだ：「3人の死刑囚がいる。3つの青い帽子と2つの赤い帽子が用意され、看守が3人にランダムにかぶせた。自分以外の死刑囚がかぶる帽子は見えている。自分の帽子が青いと確信したならば逃げてよいが、このとき実際にかぶっている帽子が赤かったら射殺される。しばらくして、3人の死刑囚は一斉に逃げ出した。なぜ3人は自分の帽子が青いと確信できたか？」……めちゃくちゃ見覚えがある。レポートを書いた後に調べたら普通に有名問題だった。ここに書いても著作権などの問題は発生しないだろう。

水曜日の院試ゼミのために問題を解く。今回はこれまでの共通科目とは違い、8問から3問選んで解く選択科目の過去問を取り扱う予定。相変わらず大問の最後の1つが難しいが、何とか解けた……と思う。無限集合 $A$ について、可算無限集合 $\mathcal{B}\in\mathfrak{P}(A)$ であって集合ブール演算（補集合、2つの合併・共通部分）で閉じているようなものが存在することを示せという問題だった。特に $A=\mathbb{N}=\mathbb{Z}_{>0}$ の場合に示せばよい。 $[2^i,2^{i+1})$ （ $i\ge 0$ ）の合併で表せる集合たちを考えると、その濃度は一見 $\mathfrak{P}(\mathbb{N})$ と同じように見えるが、実は $\mathbb{N}$ への全単射が構成できる。イメージとしては $2^{\log_2 \#\mathbb{N}}$ という感じか。

と考えたまではよかったのだが、実際に解答を作ってみると1時間以上かかってしまった。どのくらい記述を省いていいのだろうか。まあアイディアさえ見て取れればそうひどい扱いはされないだろうから、粗く書き上げてから余った時間で補題として証明を付け加えるのも一つの手だろう。

布団に行ってしばらくラノベを読み、午前9時半就寝。

08/03(火)

午後4時半起床。目覚ましによるもの。もう2日後にチュウニズムのアップデートが近づいてきているが、まだ削除されてしまうマップを走り切れていないので、今日は何が何でもゲーセンに行く。

ちょっとパソコンを触っていたら学食の夜の部が始まったので、夜ご飯をそちらで食べてから市街地に出る。適当に自転車を停めた後、すぐゲーセンに行くのではなく、まずラノベを購入することにした。メロンブックスでチェックしてあったラノベの新刊をあらかた購入。7月発売のラノベをまだ1冊手に入れられていないので、さらに2件ほど本屋を巡ったが、どこにも置いていなかった。「剣と魔法の税金対策」3巻。ガガガ文庫で、同じ月に発売されたラノベは置いてあるのにこれだけないとは、かなり謎である。それだけ売れているということだろうか。重版を待たねばならないかと思ったが、ネット書店では注文できそうだ。

いよいよゲーセンに入ってチュウニズムをプレイした。今日は13のAJが2つ増えたくらいで、目立った成果はない。狙っていた譜面のAJが出せなかったのが悔しい。

閉店までプレイして、立ち食い蕎麦屋でざるそばを食べて帰宅。ざるそばのつゆを蕎麦湯で割ろうとしたが、つゆが思ったより多くて全然薄まらなかった。でも結局全部飲むなら塩分量は一緒、例えばインスタント味噌汁にお湯を注ぐときも、そのまま食べたほうが効率的だよな……ということを考えている。

今日もHikakinTV（HIKAKIN TVじゃなかった！）に本気動画の1本が投稿されていた。今回はHIKAKINがVTuberになるらしい。いや～……すごい。前回の「ウ”ィ”エ” ヒカキンVer.」とは全く違った切り口の「本気」であることに驚き。普通の新人VTuberとは違い、生身のYouTuberとしての膨大なバックグラウンドがあるわけで、配信のスタイルにも編集にも慣れからくる貫禄があるのだろう。また、動画の序盤でHIKAKINの声の収録風景がちょっと挟まるのは、普通はできない表現なので、非常に面白かった。

youtu.be

ところで、この3Dモデルは今後どれくらい使われるんだろう？何回か使って忘れ去るというのは、もちろん3Dモデルを作ってもらうのにも金銭と契約があるだろうしその上では問題はないが、心象的にはよくないだろう。HikakinGamesのゲーム実況で常用されることを期待したい。

ECR112-Fのupsolveをした。07/30の解き残し。

Submission #124796890 - Codeforces

ループを作らないような辺だけ先に処理して、後から出来上がった森を使って頑張るということは知っていた。森になったらあとはどうとでもなると思ったが、その部分も結構難しい・あるいは面倒くさくて大変だった。ループを作るのに使った辺にマークしたいが、これは遅延セグメント木の区間更新ではできないようだ。仕方なく、各辺が高々1回しかマークされないことを利用して、毎回1本ずつマークしていく形になった。公式解説もそうしていたので、もはやどうしようもなさそう。

布団に移動し、ラノベを一冊読んだ。「大罪ダンジョン教習所の反面教師」。面白かった。主人公が実力を隠している設定はやはり良い。さらに教官物も最近の自分の嗜好に合っているようだ。総じて好みの設定だった。ダンジョンで手に入るアイテムにはデメリットが設定されているが、それがどれも絶妙に嫌らしかった。使ってバフをかけたらその後の人生のどこかで同じだけのデバフがかかるだとか、使用回数に制限があるのはわかっているのにいつ使えなくなるかわからないとか。

別のラノベを開いたが、少し読んですぐに寝ることにした。午前8時半就寝。

08/04(水)

午後1時半くらいに目覚ましをかけていたが、止めた後も起き上がれず、1時間程度布団でクネクネしていた。今日は院試ゼミで、1人の家に集まって対面で行う予定なので、起きなければならない。

何とか身を起こしたものの、午後3時の集合時間にはかなり頑張らないと間に合わなそうだったので、遅刻すると連絡を入れて大学生協に寄り、昼ご飯のパンを買って食べていた。のうのうとしていたら事前に伝えていた時間よりさらに遅れてしまい、かなり申し訳ない気持ちになった。

院試ゼミ。今日もかなり勉強になった。選択科目の話で、これまたすっかり忘れてしまったことを問われている。適宜ググったりしながら話を聞き、自分も作ってきた答案を発表した。自分の担当した問題は基礎論の範囲で、特別な知識は特に必要ない答案になったが、これを試験時間中に書けるかと言われると……かなりつらい。

午後7時過ぎ、僕がTCOのRegionalに出るという話をしたら解散する感じの流れになったが、なあなあのうちにコンテスト直前になってしまったため、そのままノーパソで参加した。

TopCoder Statistics - Match Overview

EM2完86位。Appretも拡張も何も入れていないため、Web Arenaで問題を見て自分でクラスと関数を定義することになった。それはそれでよいのだが、EasyもMedも解くのにかなり時間をかけてしまった挙句、Medでリサブしてしまい、このような順位になった。レートは2535→2451(-84)。何とか次のRoundへ進めるようだが、通行料としても高すぎるだろう。

Easyは微妙に難読。競技結果によるタイブレークのアルゴリズムが延々書かれているが、そもそも結果のスコアが異なったらそれで順位が決まるということをよく理解していなかった。サンプルを合わせるのに非常に手間取った。Medはいかにも普通の問題で、解法も簡単だったはずだが、指数ではなく実際にべき乗した値を持ちながら計算しようとして大小関係が崩れることに気づいていなかったりと大変なことに。さらに、提出後しばらくして、高さ2以上の部分木を2つ以上持つような頂点で壊れていることに気づき、リサブ。かなり絶望した。

Medは結局2の各頂点の深さ乗を足し合わせる感じになるらしい。頭が良すぎる。またEasyでSTLのsortと指定された関数名sortが被るため、前者をstd::sortとしなければならないことも話題になっていた。僕も1度CEを食らったが、運よくすぐにこの対処法を思いつくことができた。

コンテストが終わって、みんなで近場の定食屋に行ったが、僕がコンテストに出ている間に閉まってしまったらしく、非常に申し訳ない気持ちになった。終電があるということで1人帰宅し、3人で何を食べるか悩んだ。これからどこか別の店に行くのも面倒だということで出前のピザを注文した。久しぶりに食べるとかなりおいしい。

その後、結局朝方まで3人でずっと院試の問題を解いていた。昔の共通問題はやってみるとかなりスラスラ解けるものもあり、そうやって瞬殺できると非常に楽しい。また初手から発想を必要とする問題が紛れていて、それをシュッと解けたのは本当に快感だった。このときチャレンジした問題はすべて解けたが、1人でやっていてはかなり詰まった問題も多かっただろう。まさに3人寄れば文殊の知恵といったところか。

昼過ぎに集まって朝方までみんなで院試の問題解き続けていた。こういうの、いいよね……
— こたつがめ (@kotatsugame_t) 2021年8月4日

院試ゼミが始まった当初は何にも覚えていなくてみんなについていくのに必死だったが、ある程度物事を思い出せて、今ではとりあえず手を動かすことが可能になった。成長を感じる
— こたつがめ (@kotatsugame_t) 2021年8月4日

午前7時前に解散。コンビニで少し朝食を買って食べ、帰宅した。結局朝までやっているのだったら、途中で帰ってしまった人も引き止めればよかったなあと後悔している。

帰宅してシャワーを浴び、TCのレート変動を確認して絶望したり以下の動画を見てエモくなったりした後、午前10時半に就寝。

www.youtube.com

08/05(木)

午後6時半くらいに起床。TLでチュウニズムのアップデート情報が流れてくる。チケットが大量に廃止されるらしく、今貯めこんでいる分はアップデートまでに使ってしまわなければならないらしい。レベルが5の倍数になるたびに1枚もらえる「もう1曲遊べるチケット」は、なんとなくもったいない気がして上限ギリギリまで貯めているので、非常にまずい。

ヤバい pic.twitter.com/kbBP757DIk
— こたつがめ (@kotatsugame_t) 2021年8月5日

論理学の最終課題に取り組む。これが今セメスター最後の課題になるはずだ。まず溜めていた5回分の講義動画を視聴。といっても、大胆に飛ばしつつ黒板に書かれている内容を読むだけ。あとは講義資料も適当に読んで、いよいよ課題に取り掛かる。

中間課題では、対話形式で証明を進めてくれるプログラムを作ったのだった。これは、それまでの講義で扱っていた命題論理にしか対応していないので、それを述語論理にも対応させ、最終課題とすることにした。

テーマはこれまでの講義に関係していればなんでもよいという自由度の高さなので、対話形式で証明を進めてくれるプログラムを作ろうと思い立った。
週記（2021/06/21-2021/06/27） - kotatsugameの日記

しかしどのように実装したものか。そもそも、今さっき講義動画を見たばっかりで、述語論理の証明については何もわかっていない。実装方針を迷ったり、そもそも別のことを最終課題にしようか迷っているうちに、TCO RegionalのRound 2が始まったので、出た。

TopCoder Statistics - Match Overview

またEMの2完。Hardを通した人も大量にいたが、一方でMedを落とした人も大量にいたので、結局21位になった。レートは2451→2480(+29)。日曜日のトーナメントに進出したらしい。

Easyは自明。あまりに自明すぎて怖くなり、かなり慎重にチェックした。Medは全然わからなかったが、「最後の要素が小さければ小さいほど良い」という性質をエスパーして解いた。証明はできなかった。エスパーした後もしばらく、最後の要素としてどこまで和を取るか二分探索することを考えていたが、普通に前からdpできることに気づいた。Hardは4次元dpを書いたが、最後のサンプルだけ合わずにコンテスト終了。

touristと同じルームだったが、チャレンジフェーズに入ってすぐtouristがどんどんMedを落としていて、非常に怖い思いをした。TCでエスパーするのは度胸試しという感じがある。しかし結果としては落とされることなく終われてハッピー。落ちた提出を見ても何が違うのかあまりよくわかっていない。後ろから貪欲に取っているのかとも思ったが、案外そうでもなさそうだ。

課題に戻る。実装したりラノベを読んだりを繰り返し、午前8時くらいに一応の完成を見た。正直まだまだという感じではあるが、講義資料に載っていた証明のいくつかを再現できたので、もういいだろうという感じ。 $\lnot\forall x.\lnot Fx\vdash\exists x.Fx$ が紹介された導出規則で示せず悩み、 $\forall$ の定義だと思うことにして左から右へ変換してくれる命令も用意したが、結局それを使わずにできた証明しかチェックしていない。以前までの命題論理のみの挙動を保つように実装したので、述語論理に対しても中間課題の時に実装した機能がそのまま動いてちょっと感動した。

github.com

あとはちょっと文章を書いて提出するだけ。ミニットペーパーも最後の分だけは提出しなければならない。ミニットペーパーの文章を作成して提出しようとしたところ、ログインセッション切れで書いた文章が吹き飛び、思わず声を出した。今度は手元のテキストエディタで書くことにする。頑張って再現して、いざ提出しようと思ったら、入力欄に吹き飛んでしまったはずの文章が復活しており、また非常な徒労感を得た。

次いで、作ったプログラムに関する文章を書き、最終課題として提出した。しかし、これで終わったと解放感に包まれながら最終課題をもう一度チェックすると、「小論文」を作成せよと書いてあるではないか。かなり困ったが、ここまで作ってしまったものはどうしようもないため、このままにしておくことにした。これで落ちるならそれでもいいやという開き直り。

布団に入ってラノベを読み、午前11時半就寝。

08/06(金)

午後6時半起床。前日は何となく寒い気がしてエアコンを切ってから寝たのだが、起きたら部屋が暑くて参ってしまった。ちょっと間違えば命の危険性があるのでは？もはやエアコンは生命維持装置の1つであるようにも感じられる。

サークル解説会の準備をする。今日はG問題とH問題にすでに解説役が立候補してくれており、非常にうれしい。僕もF問題の解説スライドを生やしておくことにする。午後8時から1時間くらい解説会を行った。今日はかなり濃い3問で、普段より大幅に長くなった。来週から9月末までは夏休みの予定だが、9月に入ったらICPC関連の連絡をするかもしれないので、Slackはチェックしておいてほしい、ということも話しておいた。相変わらず次代のサークル代表が見つからない。

2021/08/06 定例会 | puzzleknot 公式サイト

ICPC練習で部室を使いたいという話が合ったので、活動計画書を教務課に提出する必要がある。去年のものを参考に書くことにしたが、まずはyukicoder 308から。

yukicoder contest 308 - yukicoder

全完。タイムはそこそこ速いものの、前から順番に解いているため点数は低い。結果、後から全完した人にかなり抜かされてしまい、悲しい。

ABはよい。Cはdijkstra。Dはちょっとびっくりするが、赤字の制約を読むと、読み込んだ順に辺を張っていけばよいとわかる。Eは判定問題を解くのは一瞬だが、構築をどうするか悩んだ。結局、連結成分ごとに全域木とそれに含まれない辺を1本用意し、木上でdfsした後根に向かって辺を追加することにした。Fはオイラーツアーやるだけ。

Eにevilケースが入っており、自分の提出ではREを出してしまっていた。表示上はACだが、提出欄にACではないケースが紛れているのは目立つ。しかしREとは何だろう。適当にTLEを出したりして、問題文に記載されている制約を違反していることを確信し、clarを投げた。しかし回答は「evilケースなので制約違反していてもよい」とのこと。これは納得できないが、ほかの問題のevilケースがどんな感じだったかをよく覚えておらず、制約違反しているケースがあったような気がしないでもないので、結局「evilケース用の制約を表示してはどうか」と言うにとどめた。そのような変更はされなかったようだが。

入力される値がどんなものかわからないままだが、適当にvectorで確保することにすればACはできた。ほかの問題では200msを超えていないのにevilケースでは700msくらいかかっているので、相当大きいケースだったらしい。実際後から確認したら $N=3\times 10^5$ だった。

明日の院試ゼミの準備をする。今回も選択科目の問題を解く予定で、僕は多様体の問題を担当している。講義も演習もかなり頑張った（課題が多かったので頑張らざるを得なかった）科目なので、何とかなるんじゃないか？という感じ。

今回は射影空間の問題だった。射影空間の計算は演習で何度も何度もやっていたはずが、すっかり忘れてしまった。提出したレポートを見返しても問題がないので何をやっているのかわからず、問題も見つからなかった（後から調べたらちゃんとClassroomにあった）ので、当時の講義資料をClassroomから掘り返して記憶を補いつつ、定義と計算方法だけ何とか飲み込み、解いた。やることさえわかってしまえばあとは愚直に計算するだけだった。

溜めていた日記を書き、午前7時就寝。明日のゼミは、生活リズムを整えようとのことで午前10時から予定されている。

08/07(土)

午前10時の目覚ましで起きる。信じられないくらい眠いが、人を待たせるのはまずいのでパソコンの前に向かってZoomに接続。すると他に1人しかいなかった。どうやら2人がまだ来ていないらしい。ゼミが始まらないのをよいことに、自分もうつらうつらとして少しでも眠気を取っておく。

1人は時間の勘違い、もう1人は徹夜に失敗していたらしく、午前11時を過ぎてからゼミが開始した。が、大変まずい。1度など人の発表を聞きながら意識を飛ばしてしまったらしく、気づいたら自分の番になっていた。申し訳なくなりながら自分の解答を発表。ついでに自分の理解していることを確認したりして、今回もかなり有意義だった。最後に、過去問を見つつその場で少し議論したりしながら、次回の日程と問題の担当を決めて終了。

午後2時だった。AHC005まで2時間あるので、少し寝ることにした。……午後4時の目覚ましに起こされるまで、その30分前の目覚ましにも気づかず爆睡。しかもこういう日に限って生協の弁当配達が午後3時台に来ていたらしく、もう1年以上注文し続けているのに初めて受け取り損ねてしまった。土曜日であることを完全に忘れていたのも悪かった。電話が来ていたので、折り返して再配達をお願いする。

AHCの問題を確認する。スコア的に、全マスを視界に入れるのは前提らしい。ただ、全マスをちゃんと回るような解を書くのがまず難しそう……。眠気も相変わらずひどいので、しばらくボーっとしていた。

シャワーを浴びたりして考えをまとめ、実装に移る。まず愚直に全マス周回する解を出して様子を見ようと思っていたが、そのあと使わなそうなコードを書く気力はないので、初めから思いつく限りの改善を実装する。まず考慮するマスを絞る。例えば行き止まりにわざわざ入っていく必要はないし、縦または横に通るだけの道の上のマスを特別扱いする必要はない。条件を詰めると、周囲に3マス以上の空きマスがあるか、2マスの空きマスがあって、それが縦横に分かれているようなマスだけを抜き出してもよさそう。サンプルが270個くらいなので、だいたい300個で抑えられそうな気がする。このマスたちの間の距離は全部前計算できる。

あとは適当にTSPを解けばよいだろう。TSPは普通どう解くのか知らないが、適当に2点swapして山登りしてみた。最初、抜き出したマスの個数を300個で抑えていて困ったことになった。手元で試してみると、普通に300個を超えるケースがあった。ところで、手元で試すときにinというサンプル入力のファイルを作っていたら、ジェネレータを動かす際inディレクトリが存在すると判定されてしまい、結果入力を書き込むパスが有効にならずエラーを出してしまっていた。

結局、500個で抑えなおしたら通った。しかしスコアはあまりよくない様子、6601725。次に、山登りを区間reverseにしてみた。11699590で、かなりの改善になった。最初の巡回順はマスを上から順に見ていった時のものだったが、このとき大体同じ行のマスが連続しているので、行の間のつなぎ方を変えるのがスコアに良い影響を与えるのだろう。

次に、初期解を実際に動かしながら作ることにした。貪欲に未訪問の頂点に向かい、隣接する頂点を全部訪れたら一番近い未訪問の頂点を目指す。11810404、これも多少の改善。続いて山登りを焼きなましに変えた。 12320530と先ほどよりは大きな改善。焼きなましの温度はコピペ元と全く同じにしていたので、手元で適当にずらしてみたところ、最初の温度をもっと高くするとスコアが上がるようだった。スコアの増減の度合いをよく確認していなかったのかもしれない。この改善で13213242と大きく上がった。

あとは、実際に解を文字列に直す前に、順番に見ていて明らかに余計な頂点（4方向の先にあるマスをすでに訪れているようなマス）を通らないことにしたら13282173、順番に見るのではなくランダムに消していくようにしたら13969535。ここでコンテスト終了、結果は170位でパフォーマンス1790、レートは1941→1969(+28)だった。

出っ張っている部分が消えないんですよね～～～ pic.twitter.com/i37ejUknHg
— こたつがめ (@kotatsugame_t) 2021年8月7日

日記を書いていて気付いたが、余計な頂点として「4方向の先にあるマスをすでに訪れているようなマス」を考えるとき、壁マスのことを完全に忘れていた。その方向を考慮する必要はない。この改善を入れたら14720756になってしょんぼり。でも10位も上がらないらしいので、まあいいか。

TLを見た感じ、どうやら通るべきマスをさらに絞り込み（ここでも焼きなます）、何度もTSPを解くのが強いらしい。僕の解法に適用するなら、後半部分だろう。焼きなましを何度も行うべきだった。確かに、焼きなましの時間を延ばすことによるスコアの改善は小さかった覚えがある。それでも微妙に増加したので、結局2.9sec焼きなましてしまったのだが、それより通るマスをもうちょっと考えたほうがよかった。また、通るマスを計算するために二部グラフの辺カバーを計算するという解法もあるらしくて、アルゴリズムの力に震えた。

しばらくTLを眺めてから布団に倒れこむ。本でも読もうかと思っていたが、耐え難い眠気が訪れ、午後9時から午前0時まで寝ていた。

起きたら窓ガラスからゴンゴンと音が鳴っていてびっくりした。注意深く聞いていると、羽を持つ虫がぶつかってきているようだ。閉め切ってあるので害はないとはいえ、時折音が響くのは非常に恐ろしい。

GCJの順位表を見ながらラノベを読んでいた。GCJはtouristの連覇が止まってびっくり。YesNoを見ながら心臓が消し飛びそうになっていた。

「最強魔法師の隠遁計画」13巻を読んだ。Web版の記憶と書籍版の記憶がまぜこぜになって、前の話をあまり覚えていない。元首シセルニアは好きなキャラなので、今巻はアルスとの絡みが結構描かれていて良かった。しかしWeb版から加筆されまくっていて、全然話が進んでいる気がしない……。

別のラノベを手に取り、少し読んだ後今度こそ就寝。午前8時だった。

08/08(日)

午後6時半起床。食事し、午後7時15分からTCO21 Regionalのトーナメント1回戦に出た。

TopCoder Statistics - Match Overview

両方提出したが、両方落としてしまった。対戦相手も落としていたが、Round 2の順位差で負け。どちらも面倒くさくてコーナーケースが大変そうな問題だった。2問目は適当に出したので何とも言えないが、1問目については述べておこう。

文字列が2つ入力されるので、辞書順比較でその間にある文字列を1つ構築せよという問題。ただし文字列の長さは $L$ 文字以下と制限されている。最初に $A\lt B$ であることを確認した後、後ろに'a'を付け足せるなら1個だけ付け足し、付け足せないなら末尾の文字をインクリメントすることで候補を作り、実際に $B$ 未満であるかをチェックすればよかった。

僕は後ろに'a'を目いっぱいつけるという謎の操作をしていた。そこがあっていても、末尾の文字をインクリメントするときは'z'を'a'に直すのではなく削除しなければならないというのもできていなかったので、全然ダメ。

しばらく院試ゼミの準備をして、午後9時からABC213に出た。6完。完全にヤバい。

AtCoder Beginner Contest 213 - AtCoder

ABはよい。Cは縦横それぞれ座圧。Dはdfs。Eは01BFS。FはSA+LCPで累積minの総和みたいな操作に言い換えられ、これを遅延セグメント木で殴りつけたら2000msちょっとで通った。

ここまでは順調だったが、GもHも解けずに終了。しばらくGを考えて、何の成果も出なかったのでHに移動。ワーシャルフロイドみたいな感じで経路数をカウントしてみて、最後に1から1へのループをたくさん重ねてサンプルを合わせたが、他の頂点で何回もループする場合が全然カバーできていない。Gに戻って、連結成分を決め打つことを思いついたが、慌てて実装を初めて詰め切れず終了。

Fはstackでマージしつつシミュレーションすることで全体で線形時間が達成できる。priority_queueで同様のことを行うのは考えていたが、データをマージするのを考慮に入れ忘れており、計算量が抑えられないと思って捨てたのだった。

コードゴルフ。Aは最初にRakuで提出したものが最短だが、AWKでも同じコード長が達成できるようだ。gawkにxorという関数が存在することをかなり忘れがち。BはVimで書いたが、さらに縮められた。factorコマンドで空白区切りの数値を1行に1つに直すテクが使われており、同じことをして縮むコードを一通り縮めたりもした。Cは座圧なのでOctave。DはPerlで書いたが、負けた。EFはコンテスト後にC++で書き直したものが最短になっている。

Gに取り組む。1を含む連結成分を決め打つと、1を含むそれより小さい連結成分がある場合に適当に係数をかけて引くことでちゃんと求められる。この係数のせいで○○変換みたいな形にするのは難しいらしい。3¹⁷なので惑わされていた。落ち着いて考えたらすぐサンプルが合ってそのまま通ってしまい、なぜHに行ってしまったのかと後悔。

Hは全然わからないので、kyopro_friendsさんのツイートにリンクがあったオフライン・オンライン変換を読む。それでもよくわからなかったのでいよいよ解説を開いたら、自分の間違った思い込みに気づいた。いくつかまとめて遷移しようとしているように見えていて、それなら今ある辺たちもいくつか繋げておく必要があると思ったが、そんな必要はないのだ。

qiita.com

実装したらサンプルが合って感動、勝ちを確信しつつ投げたらTLE。しばらく悩んでいたが、ループ中に $T$ 要素のvectorをコピーしていたのが重かったらしい。コピーもちゃんと必要な分だけにすると通った。GHともに、これまた僕のC++コードが現状の最短になっている。

院試ゼミの準備の続きをする。今回の問題は群に関するもので、見た目のシンプルさに違わずちょっとがんばったらすぐ解けた。特に忘れていた語彙などもないはずで、あとは自分が勘違いしていないかだけが心配だが、とにかく解答は完成した。さらにもう1問くらい解いておこうかと思ったものの、途中で詰まってしまい、ラノベを読み始めた。

「継母の連れ子が元カノだった」7巻を読んだ。非常に良い。最近こういう両片思いのラノベをよく読んでいるが、良いものは非常に良い。しかしこのシリーズ、7巻も両片思いしているのか。1巻からちょっとずつ近づいてきた感があり、かなり丁寧。この巻もラストシーンが非常に健康に良く、大変ありがたかった。あとがきで1巻の表紙に関する話が出て、改めて確認して変な声を出したりもした。

日記を書きながら月曜日に提出したレポートがどうなったか見に行くと、採点がすでに終了しており、なんと解いた5問すべてが満点の評価だった。有終の美。勝ったな、ガハハ！