06/13(月)

先週は週記を投稿してすぐ布団に入った。午後0時半就寝。

午後4時過ぎ起床。あまりの眠気に体が動かず、5分おきにセットしていた目覚ましに助けられ何とかインターン先定例会の前に布団から這い出た。先週もほとんど何もしていない。昨日の夕方から回していた学習は未だにlossが下がり続けていたので、ログ出力から途中経過を見てそれっぽいことを言ったりしてお茶を濁した。

勉強会はリファクタリングの話。こういうのは宗教的な要素を多分に含んでいて、自分の感覚と合わないものも多い。競プロをやっていて書き捨てのコードばかり触れているからと思っていたが、実は統合開発環境を使わずほぼ素のVimだけでコーディングしているのも問題な気がしてきた。例えば変数・関数の型を自分で覚えておく必要がないというのはかなり便利だろう。そういう機能を駆使することで、プログラムの泥臭い実装からある程度離れて全体的な構造を把握するのもやりやすくなりそう。まあそんな規模のコード群に触れたことがない身でいろいろ言っても仕方ないか。

今週も月曜日は課題に追われる日。一つ目はゲーム理論。今回の教科書の範囲には発展的と注記された内容がたくさん含まれていて、これは課題も大変そうだと身構えていたら、さすがに大変すぎたらしく教科書の演習問題ではなくスライドで定義されたゲームに関する証明が一つだけ課題になっていた。簡単。

二つ目はハードウエア基礎。小さな論理回路が与えられるので、FPGA上に設計せよという問題だった。ルックアップテーブルで $n$ 変数関数をシミュレートするのは便利だが、これまで基本的なゲートを組み合わせて頑張っていたのを振り返ると、何というか仰々しすぎる気もする。問題も論理回路を設計するというよりは論理回路の入出力の様子を見て同じ挙動をするように設定するだけで、何が面白いねんという感想に。

三つ目は離散数学。もういい加減分かってきたが、数学科の学生がこの講義を受講して得られるものは単位だけである。学部一年の専門科目でやったことを延々繰り返している。さすが文理問わず受講できる講義なだけはあるぜ……。ただ僕も単位しか求めていないので、実はWin-Winになっている。今日も無難に課題を解いて提出しておいた。来週は休講になるらしい。

四つ目はまたハードウエア基礎。教員3人が持ち回りで担当していて、今週の講義から教員が変わると同時に、課題の提出期限も次週月曜日の23時59分から10時30分に変えられていた。気づけて本当に良かった。念のため今出ている課題をもう終わらせておくことにする。今回は様々な要素から回路の抵抗や容量を求めて云々する問題。レポート提出という形式になったので、答えが正しいか即座にはわからない。変な値になったのが気になる。

終えて午前1時半。日記を書いて午前3時過ぎに布団に入った。

校正と校閲の言葉の違いを知った。これまで日記を読み返して文章を手直しするのを校正と言ってきたが、校閲のほうが正しそう。まあ本当は推敲のほうが良いのだろうが。検索すると「校正」という単語が出現した記事が五つしかなかったので、全部別の表現に直しておいた。

午前4時就寝。

06/14(火)

午前10時前に目を覚ました。まだ寝足りないので二度寝をしようと思いつつ、ついつい布団でスマホを触ってしまう。ABC249で8位を取った時の賞金10000円が届いていた。

先週日曜日（から日付が変わって月曜日）、寝る前に生協に出向いた際に一言カードを確認したら、回答で電話による相談窓口が紹介されていた。せっかく営業時間内に起きているので、ここに電話してみることにする。昼前なのでまだそこまで忙しくもないだろう。納豆の購入制限をなくしてほしいと何度も言ってきたが、自分の考えをもう一度整理すると、結局納豆を一度に2パック購入する方法さえあればよいということが分かったので、これについて聞いてみることにした。

開口一番「レジに2回並べば2パック買えるので正しいのか」と言ったところ、想定しない行動であるが可能との回答を頂いた。なんだ可能なのか。先週僕をレジで止めた担当者の方がルールを勘違いされていたという話も出てきたので、おそらく次からは止められないのだろう。また、ご飯の量が多いなどの理由があればその場で申し出ることで対応してもらえもするらしい。席に食事を置いて離れるのは正直抵抗があるので、こちらを採用したい。

ハーメルンを読んでいた。まず4話でエタっているものをサッと読了。内容の感想はない。そういえば、チャンネル登録者数が1000人なのに普段から同接が500人というのはさすがに無理があると思ったな。しかしどのあたりならリアリティがあるのだろう。知名度は低いけど一部にカルト的なファンを抱える、という状況なら案外近い値を叩き出すのかもしれない。

syosetu.org

比企谷八幡がVtuberになるハーメルンは他にもある。1年以上前に読んで、そのときすでにエタっていたのだが、以来何話か更新があったので改めて読み直していた。やはり面白いし、面白くなりそうという感じもする。

やはり俺がVtuberになるのはまちがっている。 - ハーメルン

昼過ぎからは「輝きたくて」を読み返していた。何度目かわからない。とにかく面白い。

輝きたくて - ハーメルン

午後3時くらいに二度寝に成功。次に起きると午後10時半だった。ICPC模擬国内予選の参加登録が始まっていたので、チームメイトのメールアドレスを聞いてフォームを送信しておいた。

ICPC OB/OG の会による模擬国内予選を 6/25 (土) に実施します。
参加を希望するチームは以下のページより申し込みをしてください。申し込みの締め切りは 6/19 (日) となっております。申込期間が非常に短くなっていますのでお気を付けください。https://t.co/hUSQ5gbwLn
— ICPC OB/OG の会 (@icpcjag) 2022年6月14日

午後11時半からCF #799 div.4。

Dashboard - Codeforces Round #799 (Div. 4) - Codeforces

Aは問題文を読むのに手間取った。 $a$ より大か小である個数を答えればよさそうだったので、あとはサンプルを見て合わせ提出。Bは消すべき個数を求めて切り上げ。必ず1個以上残せるので、切り上げたとき $n$ を超えることはない。Cは実際にビショップを配置して一致するかチェック。端にないという制約の意味が分からず首を傾げていたが、後からこの制約なら8近傍がXのように埋まっているかチェックするだけでよいのだと気づいた。Dは最初の状態に戻るまで $x$ 分経過させるのを繰り返し、それぞれ回文かチェックする。

Eは尺取り。Fは $\bmod 10$ で要素をカウントし、 $a_i\bmod 10$ と $a_j\bmod 10$ を固定して対応する $a_k$ が存在するかチェックする。Gは $a_i\ge 2a_{i+1}$ なる要素を含まない区間を数える。隣り合う各ペアに関する条件なので添え字の $\pm 1$ がちょっと難しかった。一度 $b_i=[a_i\ge 2a_{i+1}]$ と置いて、この数列の連続する $k$ 項を考えるほうがやりやすかったか。Hは $a$ を決め打って、それが出現するインデックスを先頭から $I_1,I_2,\dots$ としたときに $i\le j$ のもと $2(j-i+1)-(I_j-I_i+1)$ を最大化すればよい。 $(2j-I_j)-(2i-I_i)+1$ と変形すれば $2i-I_i$ の累積 $\min$ を管理する典型。

24分全完で10位。

今日もマイク音声付きで録画していた。相変わらずボソボソ喋ってしまった部分もあるが、問題文の読解フェーズはあまり黙らないように頑張った。全完まで24分しかないのでほぼ無編集で投稿してしまおう。コンテスト終了までに前後を少しカットしてエンコード・YouTubeへのアップまで済ませておき、コンテスト終了後に公開した。サムネはopen hacking phaseが終わってから。

www.youtube.com

今日の夜にしぐれういさんがゲリラ配信をされていたらしい。アーカイブを視聴した。

www.youtube.com

29分21秒時点。気になっていた期間限定商品の販売がすでに終了しているとコメントに嘘をつかれ、すごい顔をするシーン。Live2Dの表情が豊かで可愛らしいですね。

https://www.youtube.com/watch?v=piVNAMMi0_k&t=1761s

日付が変わって06/15からTCB48が始まっていたので参加した。例のごとく日曜日終了なのでここに感想を。

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

6問目はとりあえず根から最も遠い頂点が $2^N-1$ であることがわかるが、もう片方はすぐには決定できない。しかしLCAを全探索すれば十分で、そこからコストを求めるのも毎回 $O(N)$ かけてよい。7問目は二分探索して判定はUF。判定に $O(N^2\alpha(N))$ かけてちょっと怖かったが普通に通った。8問目は親の顔より見た拡張dijkstra。

9問目は難しい。トポロジカルソートを計算するときについでに何かすることで求まるのかと思って考えるもよくわからない。入次数が $0$ の頂点からの最長距離でグループ分けしたものを提出して思いっきりWAを出した。反例だらけ。30分ほど考えてどうにもならなかったので、各点についてそこに到達可能な点とそこから到達可能な点が合計で $N+1$ 個になることを確認する方針に。DAGの到達可能性判定は各頂点でそれぞれ愚直に計算する $O(N(N+M))$ をビット並列にするやつ。事前にトポロジカルソートすることで見るべき頂点を減らし、定数倍にさらに $1/2$ を付けて提出すると4.6secくらいで通った。C++最高！

10問目も難しい。その頂点にたどり着いた時の操作回数 $\bmod 2$ を考えて頂点を倍化すると、辺 $(a,b,c)$ が $(a,c)\rightarrow(b,1-c)$ と $(b,c)\rightarrow(a,1-c)$ になり、 $2N$ 頂点 $2M$ 辺の有向グラフが得られる。このグラフのすべての辺を通るような道を見つける……わけではない。辺も倍になっているので、そのうち片方ずつさえ通っていればよいというのが問題。まず強連結成分分解して、始点を含む強連結成分からどのように辺を辿っていけばよいか考える。今見ている強連結成分から出る未使用の辺が二本以上あったとき、どれを使うべきか。

実はどれでもよい。そのような辺が2本 $e_1,e_2$ とあったとして、それぞれペアになっている辺を $e_1',e_2'$ とおく。例えば $e_1$ を使ったとする。このとき二度と $e_2$ は使えないので、そこから先のどこかで代わりに $e_2'$ を使う必要がある。そうしたら、その間で使った辺をすべてペアのもう片方に置き換え、逆から辿ることができて、 $e_2$ からスタートして $e_1'$ で終わるような道もあることが言える。 $e_1$ の始点から $e_2'$ の終点への道が $e_2$ の始点から $e_1'$ の終点への道になってしまうが、問題ない。なぜなら、今 $e_1$ の始点と $e_2$ の始点は同じ強連結成分に属していて、その2点を含むループを先ほどのように反転することで $e_1'$ の終点と $e_2'$ の終点を含むループが得られる、つまり2点が同じ強連結成分に属するとわかるからである。

強連結成分間を渡るとき、すでにペアのもう片方を使った辺、つまり使用済みの辺を考えてしまい1WA。上の議論において $e_1\rightarrow e_2'$ の道と $e_2\rightarrow e_1'$ の道に共通する強連結成分があると、途中で混ざってしまい $e_1\rightarrow e_1'$ を辿ってしまうかもしれないので、ちゃんと一度使った辺を弾く必要がある。逆にこれ以外の場合では壊れない。ペアの片方の辺がどこかの強連結成分に含まれるなら、もう一方の辺も別の、あるいは同じ強連結成分に含まれるから。

9問目が34分1ペナで-27pt、10問目が79分1ペナで-68pt、合計-95pt。10問目はかなりやりごたえがあって面白かった。9問目が本当にわからないので、日曜日深夜のTLを注視したい。

6月中旬～7月中旬の新刊ラノベをチェックして注文した。15冊。06/17発売予定の富士見ファンタジア文庫の新刊が、どれも書籍注文サイトに表示されず、予約できなかった。1件ヒットと書いてあるのに一覧が空だったりして謎。そのうちリアル書店で買うか、機を見て再度注文したい。

午前6時くらいから日記を書き始め、YouTubeを見つつ午前10時に書き終えた。文章量がそれなりにあったので時間がかかったのもまあ納得できる。見ていた動画の一つはこれ↓。先週日曜日に見たカバンチェックと同じく大喜利企画だが、こちらはあまり面白く感じられなかった。8分17秒時点、「酒を呑ませて酔わせて倒す」と言われ即座に「なんで八岐大蛇と同じなんだ」と突っ込めるのはすごいと思う。見ていてびっくりした。

www.youtube.com

https://www.youtube.com/watch?v=WtSwAAOpZl0&t=497s

チャンネル登録者数500人を達成した。しばらく450人手前で停滞していて、そこから3本動画を出して一気に到達。Twitterアカウントの規模が大きめなので、そこから誘導することでインプレッション数が稼げている。

チャンネル登録者数500人！ありがと～ pic.twitter.com/3L9xCUmzVM
— こたつがめ (@kotatsugame_t) 2022年6月15日

競プロ実況と銘打っているが、決して解説ではなく、ただコンテスト上位に入る人間がどのような速度で解いているのか見せたいという考えで動画を作っている。だから「動画を見て憧れた・モチベが上がった」という感想を見たときは非常に嬉しくなったし、「理解する前に先に進んでいった」という感想に対してはすまないがそういう動画だとしか言えない。幸い僕がTwitterでエゴサする範囲では動画は好意的に受け止められているものの、YouTubeというプラットフォーム上で何かフィードバックがあったわけではない。動画とTwitterにおける個人が切り離されているように感じていて、自分の影響が及ばないものの評価を見守っている心境で少し怖い。

学食で食事。ちゃんとレジで宣言して納豆2パックを購入してきた。このメニューを選ぶのはもうこれで何度目かわからないくらいで、今日は合計606円になるはずがなっていないことに気づいて会計漏れを指摘した。

食事 pic.twitter.com/BwYQvWzg3N
— こたつがめ (@kotatsugame_t) 2022年6月15日

帰宅して布団に横たわり、またYouTubeなりにじさんじ非公式wikiなりで無為に過ごしてしまった。wikiはアンジュ・カトリーナさん。動画は以下の切り抜き。

www.youtube.com

午後1時前に就寝。

06/15(水)

午後4時直前に起床。即座に会議に接続してペアプログラミングを始めた。

序盤はだいぶ頭が回っていなくて反応が鈍かったと思うが、どちらかというと前回（06/03）のペアプログラミングの記憶がほとんど抜けてしまっていたのが問題だった。意識も記憶も回復したので何とか普通に進んでいって、最後、コードが正しく動くか確認しながらしばらく雑談さえ挟み2時間程度で終了。今書いたコードで学習を回し始め、しばらく見守って問題ないことを確かめてから二度寝した。

午前0時半起床。相変わらず学習はちゃんと動いているようでよかった。同じPCでちょっとYouTubeでも見ようかとしたらGPUのメモリがギリギリになったので、慌てて会議アプリだったりSlackだったりを落とした。こういうの、一度起動するとバックグラウンドで一生走り続けるのであまり好きではない。通知を送る以上仕方ないことではあるのだろうが、それは別のPCかスマホから見るので十分なので、毎回手動で落としている。

ハーメルンに気を取られつつ明日、日付が変わったので今日に控えたセミナーの準備をする。もう何回同じページ予習するんだという感じなので、あまり気が乗らなかった。また証明を再現して、今回は万が一にも炎上しないようメモとかではなく丸々書いた紙を用意しておいた。どうせ念入りにやっていたらあまり進まないということが分かっているので、量は控えめ。ハーメルンとセミナー準備を体感2対1くらいで行って、午前7時前には切り上げて布団に入った。そこからさらにハーメルンを読んで午前8時就寝。

06/16(木)

午後2時過ぎ起床。火曜日に投稿したCF #799の実況動画だが、順位が確定していたのでサムネイルを作って設定した。上に二つあった灰色・無色のアカウントが両方消えて8位に上がっていた。

ちょっと遅めの時間に出発し、生協でパンやおにぎりを買って教室へ。おにぎりだけ食べてすぐセミナー開始。今日は僕の発表だと思っていたが、実際はもう一人と時間を半々に分け合う予定だったらしく、さらにその人の発表が長引いて今日は聞いているだけになった。

岡目八目とはよく言ったもので、証明の簡単そうな別方針だったり黒板に書かれていることの反例だったりがいくつか思い浮かんで指摘したりした。そういうことをする立場は気楽だが、指摘される側はたまったものではないのだろうなとも思う。自分も昔黒板発表で炎上して頭が真っ白になった経験がある。先生からもいろいろ指摘を受けていて、今日はとにかく大変そうだった。これについては途中から先生が発表者の発言を遮りがちだったのも問題に思える。

ただ自分自身をネガティブに言い続けるのは、聞いていてこちらの気も滅入ってしまう……自分で自分を信じられなくなったら終わりですよ。

学食で一緒に食事し、別れて帰宅。ふぁぼん氏が氏の食生活についてブログを書かれていた。僕の「ペペロンチーノの作り方」のオマージュらしい。ところで、オマージュとリスペクトは大体同じ意味のようだが、自分で自分のブログ記事がリスペクトされていると言うのは語感からして尊大すぎるので、ここではオマージュという語彙を選択した。

yuyusuki.hatenablog.com

kotatsugame.hatenablog.com

親が大量にパスタソースを購入してくれるのでそれしか使わなくなったり、茹でる前のお湯でインスタント味噌汁を作ってそれを飲むため普通に2分以上待てるようになったり、いろいろ変化があります
— こたつがめ (@kotatsugame_t) 2022年6月16日

でもあなたが食事をしている間にライバルが競技プログラミングの問題を解いているのは変わりませんね
— こたつがめ (@kotatsugame_t) 2022年6月16日

そもそもライバルとして見定めている人はいないのだった。さらに競技プログラミングの問題もあまり解かなくなってしまった……。

シャワーを浴びて午後8時くらいには布団に入った。少しハーメルンを読んで午後9時くらいに仮眠に入り、午後11時過ぎに何とか起床した。午後11時半からCF #800 div.1。

Dashboard - Codeforces Round #800 (Div. 1) - Codeforces

Aは $i\rightarrow i+1$ の操作と $i+1\rightarrow i$ の操作が同じ回数だけ行われるので、それによる影響を前または後ろから順に見ることで操作回数を決定していける。僕は後ろから見た。操作回数が負になる場合と、途中で $0$ になる場合、つじつまが合わない場合がアウト。Bは葉から順に自分の子に流せる値の最大値を求め、それが $l$ 未満なら $r$ に、 $r$ より大でも $r$ にするということを繰り返すのが最適。 $l$ 未満から $r$ にするときに操作回数が $1$ 増える。

Cはよくわからない。単純にdpしようとすると、 $u$ に対して $u\rightarrow v$ なる辺を見て $dp_v+1$ を求め、各値に対してそれより大きな値に繋がっていた辺をすべて削除するときのコストを足したものの最小値が $dp_u$ になる。ただしループがあるのが問題。単に頂点 $1$ からDFSして、ループを検出した場合dpの値を $\infty$ にするようなコードを書いたら落ちた。そこで逆に頂点 $n$ からdijkstraのように求めることを考えた。 $dp_{v_0}$ が決定したとき、 $u\rightarrow v_0$ に対して $dp_u$ を、 $dp_{v_0}+1$ に「まだ使っていない $u\rightarrow v$ の本数」を足したもので更新できる。なぜなら、今dijkstraをしているので、まだ使っていない $u\rightarrow v$ について $dp_v\ge dp_{v_0}$ が成り立ち、足した値が先ほどの「それより大きな値に繋がっていた辺をすべて削除するときのコスト」に相当するからである。これで通った。未だに最初のコードの何が悪かったのかわかっていない。

ここまで26分。残り1時間半はDで詰まって椅子を温めていた。まったく良い性質が見つからない。実験などを経て先頭から増加列・減少列を適当な規則に従って貪欲に更新することで判定は行えるとわかったので、その二つの列を上手いこと更新して尺取りのようなことができないか考え、できずに終了した。3完速解きで77位、レートは2906→2875(-31)。

火曜日にラノベを予約した時表示されなかった商品が表示されるようになっていたので、改めて注文した。7冊。

またしばらくYouTubeを見ていた。以下の動画。以前剣持刀也さんの話術について日記に書いたことがあったが、やはり屁理屈が上手い人として認識されていたらしい。また7分24秒時点の「天変地異」は遊戯王のカード名の意味で取ると話が繋がりそう。お互いデッキを逆さにしてプレイするという大胆なカード。

www.youtube.com

https://youtu.be/ZN1MBVAWqPw?t=444

ラストでスタッフを煙に巻くシーンがあって、急に入社日マウントを取り始めるのが本当に好き。話題とは一切関係ないことをすぐに持ち出せる発想力がすごい。22分27秒時点。 https://www.youtube.com/watch?v=KwxIJYdRl3s&t=1347s
週記（2022/06/06-2022/06/12） - kotatsugameの日記

ハーメルンを1作読了。「この手のひらで踊れたのなら」。超然とした主人公が好み。しかしどうやら体を勝手に操られていたらしいということが明らかになってきて、かなり不穏な気配が漂っている。

syosetu.org

GCJ Tシャツに関するメールが届いていたので注文し、それから日記を書き始めた。かなり長い時間をハーメルンに吸い取られてしまい、この部分まで書き終わったのが午前10時。メールを見たら、ABC253の賞金が届いていた。この回は全体3位、日本人2位で、優秀賞と基礎科学研究奨励賞（数学専攻のため）で合計18万円。当然これまでもらった額では一番大きい。正直現実味がない。

1時間弱で全完したコンテストで18万円稼いだ。これまでの人生で最も時給が高かった瞬間らしいです
— こたつがめ (@kotatsugame_t) 2022年6月17日

三└(┐卍^o^)卍ドゥルルル pic.twitter.com/1bjtsdYDes
— こたつがめ (@kotatsugame_t) 2022年6月17日

競プロしててお金もらえるのマジで夢あるな。AtCoderとスポンサー各社に感謝
— こたつがめ (@kotatsugame_t) 2022年6月17日

いったん布団に入るもあまり眠れる気がしない。眠気はあるが目が冴えている。再度起きて少しおすすめのなろう小説まとめを書き進めた後、午後1時前後に一瞬出かけた。学食で食事し、購買でラノベや菓子パンを購入し、原付に給油してきた。帰宅して布団に入り、ハーメルンやYouTubeで時間を溶かして午後4時就寝。

www.youtube.com

見ていた動画はこれ↑。最初、花畑チャイカさんの演技のみの切り抜きを見て、とんでもなく面白かったので他の人のも全部見た。結局彼のものが一番面白く感じられたので、それについては字幕が付いた切り抜き動画のほうを下に貼っておこう。他の人のもそれぞれで良かった。社築さんの「俺がついてるだろ」は自分でも知っているくらいの、音ゲーマーの間では有名なネタ。つまり内輪ノリの一種に感じられて、それを知らないだろう他のVtuberの反応が聞いていて辛かった。変な笑いが出てきたので、そういう面白さもあったということか。そもそも面白さを競う企画ではないのだが……。

www.youtube.com

06/17(金)

午後11時過ぎ起床。ICPCのチームが組まれていて、登録した情報が足りないというエラーが出ていた。Companyの欄を、特に必要とも書かれていないのに埋めなければならないらしい。Noneと書いておいた。

ブックマークしている小説の作者さんが別作品を書かれたそうなので、読んだ。5話完結でさっくり。特に好きではなかった。ノクターンノベルズなのでリンク先R18。

https://novel18.syosetu.com/n6221hr/

そのあとは朝までずっとおすすめのなろう小説まとめを書き進めていた。ちょっと読み返してみたり、読了当時の日記を見たりして何とかコメントを捻り出していたので、数時間かけて10作品分しか書き進められなかった。かなりの難事業。今日は読み返しのつもりで熱中するようなことはなかったが、その代わりうっかり捜索掲示板を漁り始めたりランキングを見たりして、最終的には別のハーメルンを読み進めつつ書く状態になっていた。

午前9時半就寝。

06/18(土)

午後3時前に目を覚ました。ハーメルンを読みつつ冷凍弁当の配達を待つ。

まず1作読了。「貴方は中央トレセン学園から追放されることを希望しています。」。

syosetu.org

悪印象を与えようとして取った行動が好意的に受け止められてしまう勘違いもの。トレーナーが主人公のウマ娘二次創作としては、口調が乱暴だったのが印象的。たいていは丁寧であるか、そこまでいかずとも愛想がないだけのことが多かったはず。話の設定上自然とは言え、正直良い気分はしなかった。

話は、主人公視点で数話進んだ後、そこで発生した勘違いの経緯を周囲の人物視点で1話描くことによって説明する、というのを繰り返す構造になっている。自分の知る範囲では目新しくて良かった。個人的には周囲の人物からの評価をもっとネットリ記述するようなものが好みだが、こうやってテンポよく新しい勘違いが発生し続けるのも読みやすくてよかった。

午後4時半ごろに弁当を受け取り、さらにハーメルンを読み続けてもう1作読了。「追放系お嬢様」。この2作は最近並行して読み進めていて、ちょうど同時期に最新話まで追いついたということ。

syosetu.org

「輝きたくて」の作者の新作。勘違いもの。前作でも被虐願望のあるTS転生者を描いていたが、今回の性的嗜好はもっと悪化していた。正直ついていけない。勘違いの内容についても今のところ特に印象に残ったものはない。ただ、なぜ勘違いされてしまうのかの理由が明らかにされたときは、なるほどと思った。前作では途中から主人公に対する評価が自分の中で変わった記憶があるので、今作もそんな感じの展開があることを願う。

午後5時半ごろに二度寝。そこからなかなか起きられず、午後8時半に何とか布団から出た。食事してすぐABC256。

Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256) - AtCoder

Aはやるだけ。dcの4Bを9秒時点で提出してFAを逃し、直後にbcの2Bが存在することに気づいた。もうダメダメ。そこからはC++。Bは何を言っているのかよくわからなかったので、言われた通りに書いた。Cは左上 $2\times 2$ を全探索。Dは $L_i$ でソートして先頭からマージできるならしていく。Eは $i\rightarrow X_i$ と辿っていくとループに辿り着くので、それぞれのループ内で最も小さい $C$ だけ答えに足せばよい。同じループを2回以上数えないように注意。

Fは面倒。 $C$ を等差数列を区間加算できる遅延セグメント木で管理して、区間和で $D$ を求めた。Gは $N$ 角形の頂点を一周しつつ、頂点の色と各辺上にある白い石の個数を持つdpを考えて、後者は互いに関係がないことに気づき、前者だけで行列累乗した。ただしこの考察の流れから、 $2\times 2$ 行列の各要素を長さ $D+2$ のベクトルにして、ベクトル同士の加算乗算を要素ごとに行うような方針を取ってしまい、実装にちょっと苦労した。各辺上の白い石の個数を先に決め打ったほうが明らかに楽。

Exは同じ値になった区間をマージすればあまり種類数が増えなさそう（未証明）だったので、それをmapを使って実装する。ただし区間和の取得は難しいので、区間setと区間和取得が行える遅延セグメント木も用意して、適宜書き換えた。3125ms。

ノーペナ全完で16位。Eの解説を読んで、これまでfunctional graphという言葉を誤用していたことに気づいた。正しくはすべての頂点の出次数が $1$ の有向グラフであるようだが、自分は加えて入次数も $1$ であるようなものだけそう呼んでいた。日記におけるこれの出現を調べると、全部順列をグラフに直したときの表現だった。入次数が $1$ であることに着目しないとグラフ全体がいくつかのループに分割されることが言えないので、functional graphだからループに分けて云々みたいな説明が意味をなさなくなってしまう。では入次数も $1$ のグラフはどう呼べばよいのか？適切な表現を知らず直すのが面倒なので、放置。

午後11時半からCF #801 div.2に出た。レジったページを開きっぱなしにしていたら時計の誤差が積み重なり、ページ上のカウントダウンが残り10秒を切ったぐらいでリロードしたらもうコンテストが始まっていてびっくりした。

Dashboard - Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round - Codeforces

Aは最大値のマスを必ず含むような縦幅・横幅を考える。最大値が $A_{i_mj_m}$ だったとすると答えは $\max(i_m,n-i_m+1)\times\max(j_m,m-j_m+1)$ になる。Bは $n$ が奇数なら $a_1$ を $0$ にすることで先手勝ち、そうでない場合は二人とも取る山が同じなので、 $1$ 個ずつ取っていったとき初めてなくなる山、つまり $a$ の最小値と等しい最も先頭の山がどちらのプレイヤーに対応するか調べる。何を考えたか総和の大小を比較して1WA。Cはbitsetでdp。

D1は、一つ必ず聞く頂点を決め、そこを根とした根付き木を考える。子を二つ以上持つ頂点について、その子らはそれより下の頂点を聞かないと区別できない。よって各頂点に対し、部分木の頂点を全部区別するために必要な聞く頂点の個数を求める木dpが考えられる。dpの値がちょうど $0$ の子、つまりそれ以下の頂点を一切聞かなくてよいような子、が二つ以上あった場合にそのうち一つ以外を追加で聞く必要がある。そしてこのdpは、各頂点の値が隣接する頂点の値だけから計算できるので、全方位木dpに書き換えられる。

先にD2に提出し、通るのを確認してD1にも出した。D2の点数のほうが低いのでこうすべきだと考えたが、冷静になって考えてみると、間違っていた場合のリサブのペナが定数であるのに対し、時間による点数の減衰は元の点数に比例するので、ちゃんとD1から出したほうが良かったらしい。何なら全方位木dpに書き換えるのに手間取ったので、 $O(n^2)$ が書けた時点でD1を提出するべきだった。

Eはちょっと面白い。二人が置いたドミノをマスを結ぶ辺だと思うと、全体はいくつかの長さ4以上の偶閉路に分けられる。ここでドミノをマスではなく値を結ぶ辺だと思い、各辺を2回ずつ使っていくつかの長さ4以上の偶閉路に分割できれば、縦 $2$ マスのマス目に置くだけで盤面と二人のドミノの配置を決定できる。ただし片方の人だけが同じドミノを2回使ってはいけないことに注意。これで偶閉路にうまく分割する問題になった。

ひとまず、連結成分ごとにすべての辺を2回ずつ使って一つの偶閉路が構築できる。具体的には、適当な全域木を取って辺属性オイラーツアーのように並べ、余った辺はどちらかの端点にいる際に往復すればよい。このようにして作った偶閉路（を適当な位置で切り開いた列）について、それぞれ二本ずつ含まれる同じ辺の出現位置の偶奇は異なるため、そこから決めたドミノの配置で片方の人だけが同じドミノを2回使うことはない。長さに関する条件は、辺を一本しか含まないような連結成分でなければ満たされる。dfs木を取って実装した。多重辺や自己ループの扱いが難しい。

あとは復元。二人のドミノの配置を作るのがちょっと面倒だった。まあジャッジのためには仕方ないか。うっかり1ペナ付けつつ全完、システスも全部通って11位。

ABCのコードゴルフをする。Aは速度で負け。Bは全完後に考えると後ろからの累積和が $4$ 以上であるような要素の個数だと分かったので、dcで実装して17B解を作ったものの、まったく同じコードがコンテスト開始すぐに提出されていてひっくり返った。朝方になって-1Bできた。CはAWK。 $2\times 2$ マスの全探索の最中にうまくループの範囲を調節することで、確認すべき条件を減らしている。DもAWK。imos法。EはRuby。すでに通った頂点を検出するまでfunctional graphをたどり続け、今のループで通った頂点が見つかったらその部分が初めて見るループなので、答えを求めて足す。以降は手付かず。

日記を書き、しばらくYouTubeを見てから布団に入った。実は布団に入ってからもYouTubeを見ていた。午前9時半就寝。

06/19(日)

午後0時半くらいにうっかり目を覚ましてしまった。

今日のOpenCupが開催されるのかわからないとツイートしたところ、Telegramで情報が得られると教えてもらった。というかOpenCupに招待されたときにちゃんとそのリンクが貼られた文章が共有されていたようだ。全然見ていなかった。

今日のOpenCupはあるのかい！代理コンテストなのかい！どっちなんだい！

ん〜〜〜〜〜〜パワー
— こたつがめ (@kotatsugame_t) 2022年6月19日

そこを見て、この時間になっても特に更新がないことを確認。今日は代理コンテストになりそう。午後9時からのARCに被せないため午後4時から5hで参加しませんかとチームメイトに聞いてみると、了承・同意が得られたので、そうなった。というかこの時間に連絡つくのは感動。コンテスト直前まで起きられず寝起きで5hに突入するのって僕だけらしいです。

明らかに寝足りないので午後4時直前まで二度寝するぞと思って再度布団に横たわるも、なぜか眠れない。午後3時くらいまで布団で身悶えして、仕方なく起き上がった。今日は睡眠時間3時間で5h+2h+3hに挑む。

まず、午後4時からOpenCup代理コンテスト。コンテストタイトルはPTZ 2022 Winter Day 6 (ICPC Camp Day 1)であった。チームでGHICAの5完で、担当したのはAだけ。それも未証明で通したので、解法をあまり真面目に書く気がない。

06/21追記：https://www.acmicpc.net/category/detail/3056

頂点数 $N$ で辺数が $2NK$ 本以上の無向グラフから適当な頂点集合を重ならないように二つ取り出して、それぞれの集合のすべての頂点がもう一方の頂点集合に隣接する頂点を $K+1$ 個以上持つようにせよという問題。Diestel Graph TheoryのTheorem 1.4.3が「平均次数 $4K$ 以上のグラフは点連結度が $K+1$ 以上の部分グラフを持つ」という主張なので、この証明を追えば解けると思って結構長い間粘着した。結局点連結度は何の役にも立たなくて、次数が $2K$ 以下の頂点を削除していくことで次数 $2K+1$ 以上の頂点のみからなる $2K+2$ 頂点以上の部分グラフが得られることだけが分かった。

しかしこれは当然の話。次数が $2K$ 以下の頂点を削除しているのだから最小次数が $2K+1$ 以上になるのは当たり前、次数が $2K+1$ の頂点が存在すればそれ自身を含め頂点数が $2K+2$ 個以上になるのも当たり前。頂点 $1$ 個と辺を高々 $2K$ 個組にして削除しているので、常に平均次数が上がり続けるのだから、グラフは空にならない。今年のGCJ R3では平均次数が小さい状態が保たれていたが、それとは逆向きの評価を行っている。見覚えのある議論だと思っていたらProp 1.2.2に全く同じことが書かれていた。

以上がとりあえず正しいとわかっていること。あとは、残っているグラフの頂点を二つに分割して隣接する頂点の個数に関する条件を満たせばよい。頂点集合を $A$ と $B$ として、最初全部 $B$ に入れておいてどんどん $A$ に移すという操作を行った。操作後に $B$ の各頂点がそれぞれ $A$ に隣接する頂点を $K+1$ 個以上持つようにはできたので、 $A$ でも同様の条件を同時に満たすため $A$ と $B$ を入れ替えて同じことを何度も繰り返すというコードを書いたら通った。

残りの問題は何もわからない。Jの考察に参加して、チームメイトがそれっぽい解法の実装に入ってからは完全に集中力が切れていた。さすがに数時間椅子を温め続けると厳しい気持ちになる。

直後、午後9時からARC142。

AtCoder Regular Contest 142 - AtCoder

Aは $K$ を反転しても小さくならないことを確認し、 $N$ 以下の範囲内で $K$ またはそれを反転したものの末尾に $0$ を加え続け、カウントする。 $K$ が回文である場合に注意。Bは連番で埋めた後、奇数行→偶数行の順で並べるだけでよい。

Cは $3\le u\le N$ に対して $d_{1,u}+d_{2,u}$ を求め、これが $k$ であるような $u$ の個数がちょうど $k-1$ 個となる最小の $k$ がだいたい答え。ただし $d_{1,2}=1$ である場合が問題。このとき、全ての $u$ に対して $|d_{1,u}-d_{2,u}|=1$ なので、まずこれをチェックしておく。この判定に通るのに $d_{1,2}\gt 1$ となる場合は、 $N=4$ で1-3-4-2のような並びをしている場合しかないと思って、これを特別扱いしたら通った。出力形式ミスで1ペナ、コーナーケースの処理をミスして1ペナ。

Dは面倒。良い操作はそれを戻すこともできるので、操作の度に初期状態と1回操作後の状態を繰り返すかチェックすればよい。操作の際に移動した駒を元に辺を向き付けると、互いに重ならない長さ2以上の有向パスがいくつかできて、各有向パスではもともと終点以外のすべての頂点に駒があったことになる。逆に、木をこのような有向パスに分解して今述べたように駒を置くことで、良い操作が可能な駒の置き方を全部生成できる。

あとは操作を2回繰り返したときに元に戻る、つまり2回目の操作に対応する有向パスが必ず1回目を反転したものになるという条件について。まず、駒がない頂点が隣接してはならないので、パスは木の頂点すべてをカバーしている必要がある。さらにパス同士の位置関係について丁寧に考えると、パスの内部の点に別のパスの端点が隣接してはならないこと、パスの始点が隣接しないこと、パスの終点が隣接しないことを満たしていれば良さそうだと分かった。

木dpをする。部分木について、その内部を条件を満たすように有向パスに分解する方法を数え上げる。これを根の状態を解説通り五つに分けてそれぞれで持ち、気合いで遷移を書く。細かい説明は放棄する。子全部を見るループを7回書いたが定数倍的には余裕だった。精神的には全然余裕ではない。しばらくの間上に挙げた三条件のうち一番目を見落としており、サンプル3だけが全然合わずかなり絶望した。何とか合わせて提出し、WAで、端点の隣接関係を勘違いしていたところを書き直してAC。

残り20分くらいでEへ。フローだと決め打ってグラフをエスパーしようとし、失敗。諦めモードになりつつしばらく考察していた。魔法使い $i$ について、その強さ $a_i$ は $L_i=b_i$ 以上であるか、または $R_i=\max_{\exists(i,y)}b_y$ （ペア $(i,y)$ が存在するような $y$ を渡る最大値）以上である必要がある。とりあえずこのどちらかを満たすまで強さを増やしておく。さて、この状態でまだ良いペアになっていない二人の魔法使いについて、片方は $L\le a\lt R$ であり、もう片方は $L\gt a\ge R$ である。よってこのようなペアに辺を張ると、出来上がったグラフは二部グラフになる。

適当に塗り分けて連結成分ごとにどちらかの色だけ条件を満たすように増やすとよいのではないかと思い、実装してラスト1分で投げて当然のように落ちた。後からケースを確認すると、prefixが05_maximalのケースだけ全部落ちていて面白かった。まあそれが30ケースあるので惜しくもなんともない。

4完。やはりDから難しかったようで、26位になっていた。Cは実は嘘解法だった。 $N\gt 4$ の場合でも上で無理やり弾いたのと同様のケースが発生してしまう。

C、
5
1 5
5 3
3 2
5 4
で落ちる人居ないのかなぁ
— ひゅ〜Men (@men_cotton) 2022年6月19日

午後11時半からCodeChef。June Lunchtime 2022 div.1。

https://www.codechef.com/LTIME109A

1問目の問題IDはもともとLOSTARRAYだった。開いて、10分弱かけてコーディングまで済ませたのだが、提出ページが開けなかった。慌ててコンテストトップに戻りページをリロードしたところ問題が消え去っていた。キレそう。ただ他の問題のACがほとんど出ておらず、みんな同じ現象に遭遇していたことが伺えたので、そこだけは救いだった。とりあえずツイートでキレ散らかしておく。

インド、問題が消えとる。ふざけるのもいい加減にしろよ
— こたつがめ (@kotatsugame_t) 2022年6月19日

後になってLOSTARRAY_というIDの問題が追加され、コンテストが10分延長された。コンテスト中に問題が消えたり増えたりするdiv.1 rated（結局ratedだった！）って景気がよすぎるだろ。頭お花畑か？絶対語り継いでやるからな。どうやら、古い問題とIDが被ってしまって、意図せずそちらの問題が表示されてしまっていたようだ。

以下解いた順に。MAXCYCSHIFTは累積XORの（多重）集合の変化が「要素を一つ削除する」「削除した要素を全体にXORする」「新しく一つ値を追加する」の3手で書ける。よって集合全体にXORされた値を持てば削除と追加だけで再現できる。XORXORSUMは難しい。最上位桁から見るのは失敗。最下位桁から見るのがよい。最下位桁が同じ数同士で組にする必要があって、 $0$ である数は全部 $2$ で割って再帰的に解く。 $1$ である数はその次の桁が $0$ のものと $1$ のものでペアにする必要があって、2種類に分けた後全部 $4$ で割り、「二つの集合から一つずつ選んでペアにする場合の数」を求める関数を用意して解く。この関数もまた再帰関数として実装できる。

LOSTARRAY_はもともと1問目に置かれていただけあって簡単。 $N$ が奇数のときは $A$ 全体のXORが決定して、偶数の時はそもそもどれを全体のXORだと思っても適切な $A$ が復元できる。XORDETECTIVEは、まず $X=0$ を聞いて $A\oplus B$ を手に入れ、この値で立っている最上位ビットの割り当てを決定する。そこから上下に広がるように一桁ずつ決めればよい。下のほうは、 $A$ でも $B$ でも立っていないビットを $X$ で埋めることで、 $X$ による繰り上がりを $A\oplus B$ で立っているビットまで影響させることで区別できる。上のほうも考え方は同じ。問題文をよく読んでおらず、 $T$ と $Q$ をそれぞれ読み損ねて2WA。愚か。

あとは部分点。MINXORSEGはBinary Trieを必要なところだけ作るセグ木だと思って、更新する度に現在の集合に対して問題を解いた値を求めておいた。これでMo's Algorithmを実装し、小課題3までの50点。手元のランダムケースで20秒弱かかっていて満点は絶望的だが、なぜかしばらく粘着していた。16秒くらいにはなった。インデックスを持っていた部分をポインタにしたら、そのポインタが差す先が実はvectorの要素で、メモリ再確保が発生し値が壊れてしまったりした。最初に十分な量reserveしておくことで対処。

INC0XORはbitDP。小課題2までは自明、と言いつつ $2^7$ の桁まで繰り上げる必要があるケースで引っかかった。小課題3、4は逆に各桁についてどの要素を繰り上げるか全探索すると思ったのだが、答えが合わない。残り時間が少なく、何が間違っているかもわからないままコンテストが終了した。

480点で13位、レートは2761→2730(-31)。XORXORSUMは最下位桁から見ると条件を満たす相方の数がただ一つに決定するらしい。言われて考えてみれば確かにそう。最上位桁から見て列を分割していく方法を最初に考察し、最後までそれに引きずられていた。

消えてしまったLOSTARRAYのほうもコードは完成していたので通しておいた。区間に対しbitwise ANDを行う更新で条件を満たし、区間bitwise ORを求めることでちゃんと条件が達成されているかチェックできる。適当に遅延セグ木で書けそうだったが、念のためビットごとに累積和を取ったりする方法で実装した。

https://www.codechef.com/viewsolution/67201656

TCB48が終了していた。全完優勝。そもそも全完が二人しかいなかった。9完の人とあまり点差がなかったので危ないところだった。

ARCのコードゴルフ。Aは適当にPerlで書いておいた。Bはなんと $2,1,4,3,\dots$ と出力するだけで通る。ただし $N$ が奇数のとき $N^2$ と $N^2+1$ を交換しようとしてはならないことに注意。dcで21Bで書けてしまった。 $N\times N$ に整形する必要がないのはいつものことだが、それにしても行・列を完全に無視できるうえ、ここまで単純になるのはびっくり。各行について値の大きさがジグザグになっていればよさそうという考えから試した構築方法だった。残りは手付かず。