日記 2021/05/27
8時ごろ、雨音に叩き起こされた。4時間くらいしか寝ていないので眠い。先日傘をどこかに置き忘れたあと、代替を用意してなかったことを思い出して絶望する。しかたなく近くのコンビニへ濡れながら向かった。傘を買うついでにやよい軒で朝食。350円で健康的な朝ごはんが食べられるのはありがたい。 家に戻ると眠気が鎌首をもたげてきたので、二度寝した。12時ごろに目が覚める。眠かったので布団のなかで競プロの考察をして、解けたので布団から這い出て実装をした。 atcoder.jp
13時ごろに家を出て、秋葉原へ向かう。目的はクールタイムが明けた献血と、1ヶ月前に修理に出したノートパソコンの受け取りだ。献血ルームは平日の昼間にもかかわらず混んでいて、成分献血なのもありかなり時間がかかる。待ち時間に、このルームに来るごとにちびちびと読み進めていた『HELLSING』を読了した。この作品は、自分の「厨二病」と、自分が物語に求めているものにクリティカルに刺さったので、とても気に入った。後者についてはいつか記事にしたい。
献血が終わり、PCを受け取ろうとしたが、受領に必要な控えを家に置いてきてしまった。何をやっているんだろう……。結局、土曜日にもう一度伺うことになった。
その後、昨日に続いて丸ノ内の丸善を訪れた。昨日はギフトカードを持ち合わせていなかったので、1冊を購入するにとどめたが、今日は追加で『三体 死神永生』の下巻、『石取りゲームの数学』、『究極の英単語プレミアム Vol. 1』を買った。『石取りゲームの数学』は、競プロでも登場する不偏ゲームにかんする理論を記述した本である。Grundy数を学ぶついでに読んでおきたい。『究極の英単語プレミアム Vol. 1』はいわゆる英単語帳だが、ほかの単語帳で見られない、面白い語彙が多く載っていたので買ってみた。以下にいくつか例を挙げる。 解法と感想（クリックで展開）
一見不可能に見えたので制約を見直すと、 がともに小さいことに気がついた。あとはbool値でDPをしてやればよい。余裕で間に合うと思っていたが、実際は959msもかかっていた。
- 800 pound gorilla 「無視できないもの」
- arrow in the quiver 「手段の一つ」
- pizzazz 「活気」
- take-no-prisoners attitude 「強硬な態度」
- deep-six 「放棄する」
- dragoon 「無理やりなにかをさせる」
どれも響きや語源が面白く、頭に残りやすい。自分は地道に単語帳を覚えるという作業が苦手なので、楽しく語彙を増やすことができるこういう本はありがたい。 家に帰り、食事をとる。人参やもやしが余っていたので、昨日にひきつづき野菜炒めを作った。話はそれるが、一人暮らしを始めた当初、その辺のスーパーで適当に購入する食材や日常品の質の悪さに驚くことが多かった。ぱっと思いつくところでは、スーパーの安いハムや、日用品でいうとラップや歯磨き粉など、実家で何気なく使っていたそれらと比べて大きく質が劣る。実家にいたころは気がつかなかった親の気配りをいまさらになって感じる。 21時ごろから、高校同期とAmong Usをした。前半は調子がよかったが、後半インポスターで2敗してしまった。自分がインポスターで負けるときの要因として、序盤に慎重になりすぎて、中盤から終盤で雑なキルをせざるを得なくなって吊られる、というのが多い。もう少しキルに積極的になってもいいかもしれない。 0:30ごろにお開きとなり、そのあと2時間くらい駄弁っていた。最近、友人との話題も就職や院試、研究に関することが多くなってきて、時の経過を感じる。喋りながら青diffの問題を眺めて、解けそうなものを2問解いた。
解法と感想（クリックで展開）
ベルマンフォードを初めて書いた。頂点から到達できない、または頂点
に到達できない負閉路は考慮に入れないようにする必要がある。自分は前処理としてBFSを各頂点から回し、到達可能性を調べておく方法を取った。正解したあとにGoogleで検索すると、どうやら嘘解法が大量に通ってしまった問題らしい。以下のページの記述が参考になった。
ABC137-E:Coins Respawn ~負閉路検出について~ - 思考の墓場
atcoder.jp
青diffのsolvedはこれで221問中70問となった。 解法と感想（クリックで展開）
木の直径を求めるだけ。試験管青diffはこういった問題が多く、典型の復習になる。
明日は昼から実験があるので、12時には起きたい。
日記 2021/05/26
こたつがめに倣って日記をつけることにしてみた。いつまで続くかはわからない。
深夜1時にこの日記を書き始めた。 数理演習の課題が今日までなので、徹夜覚悟で終わらせにかかる。最近ようやく「早めに課題を終わらせる」ことが自分には不可能であるという諦めの境地に至ることができた。 演習の課題はロバスト最適化に関するものだった。いわゆる連続最適化という分野の一分枝である。自分は圧倒的に離散のほうが好みなので、この課題はあまりやる気が起きない。案の定というべきか、今回もとりとめもなくYoutubeを見たりタイムラインを眺めたりと、非効率的な時間の使い方をしてしまった。
眠気に耐えられなくなり、5時ごろに就寝。
12時ごろに起床した。演習の授業を聞きながら、課題の残りを解いてTeX打ちして提出。17時からバイトに出勤し、20時退勤。帰り道に丸ノ内の丸善に寄って、『三体』の第三部を買った。このシリーズは、筆者が「理系」の人間であることが筆致からありありと伝わってきて、親近感と安心感を覚える。家に帰ると、昨日注文した『マツリカ・マジョルカ』が届いていた。この筆者の『medium』がとてもよかったので、期待大。
夕食を作る。最近はなんのせいやら、20時以降に外食ができない。バイト終わりに気軽に食事ができなくて本当に困っている。ここ数週間ろくに緑黄色野菜を摂っていなかったので、ニンジンとピーマン、豚肉、もやしを買って野菜炒めにした。味付けは適当だったが、かなりうまくできた。
青diff埋めの続きをする。バイト中に考察した数問を実装した。
解法と感想（クリックで展開）
見た瞬間に解法が分かった。これは自分の得意分野なので当然だが、自分がコンテスト中に解けなかったABC-Eも、強い人たちから見ると同様に自明なのだろう。実際、ABC-Eは既出の問題ばかりで、精進の最中にも類似の問題によく出会う。早く十分な知識を身につけて、考察勝負のステージに上がりたい。
解法と感想（クリックで展開）
部分列の和が になるような添字の集合
それぞれについて、その解への寄与は
と表される。ナップサック問題のDPをベースに、「初めて要素を取ったタイミング」と「和が
になったタイミング」だけ別に処理し、後者のイベントが起こるたびに解に上のスコアを加算する。自然な発想だけで解けてよかった。
解いたあとにmaspyさんのブログを読んだ。FPSは考察が固まってないころに検討したが、今回は単なる集合ではなく区間なので、よくわからず投げ捨ててしまった。全区間について適当な多項式の積を求めて、足し上げればよい、という発想はなかった。
解法と感想（クリックで展開）
少し考えるとただの整数計画問題であることがわかる。頑張ればでも解けそうだが、制約が小さいので全探索をした。例外処理を忘れて2WA。この問題に限らず、ここ2回のARCの敗因が、さほど難しくない問題をバグらせたうえ、雑な提出をして大量のペナをくらったことなので、気をつけたいが……。
解法と感想（クリックで展開）
普通にシミュレーションすればいい。一回縦/横に反転されたら、その列/行よりも右/下は干渉を受けなくなる。
早く解いている人のコードを見たら、遅延セグ木でぶん殴ってる人が多かった。
青diffのsolvedはこれで221問中67問となった。
オイラーツアーの勉強をすこしした。概念じたいはさほど難しいものではなかったが、できることがかなり多そうで、使いこなすのは慣れが必要だろう。明日はLCAの実装をするつもり。
今日買った『三体』を読む。明日はいろいろとやることがあるので、3時までには寝たい。
