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

03/14(月)

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

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

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

コードを書く以外のことはしばらくする必要がなさそうなので、どこかで気合を入れてガーッと書く必要がある。

週記（2022/03/07-2022/03/13） - kotatsugameの日記

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

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

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

第73章 mmap の使い方

knqyf263.hatenablog.com

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

atcoder.jp

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

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

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

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

03/15(火)

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

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

kotatsugame.hatenablog.com

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

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

atcoder.jp

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

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

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

03/16(水)

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

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

kotatsugame.hatenablog.com

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

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

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

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

週記（2021/02/08-2021/02/14） - kotatsugameの日記

前回の地震の際、本棚に取り付けてある突っ張り棒のゆるみに気づいて直していたおかげか、今回は特に本が落ちてきそうになることはなかった。

週記（2021/03/15-2021/03/21） - kotatsugameの日記

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

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

03/17(木)

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

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

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

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

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

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

03/18(金)

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

syosetu.org

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

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

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

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

syosetu.org

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

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

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

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

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

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

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

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

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

03/19(土)

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

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

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

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

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

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

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

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

AtCoder Regular Contest 137 - AtCoder

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

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

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

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

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

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

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

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

03/20(日)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 244 - AtCoder

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

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

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

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

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

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

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