kotatsugameの日記

「実況パワフルプロ野球20xx　「球界の至宝」取得RTA投手チャート」。「ソードアート・オンライン　ラフコフ完全勝利チャートRTA　2年8ヶ月10日11時間45分14秒(WR)」を書いていた方の新作。主人公の性格はそちらと変わっていないようで、冷徹さというか、人の感情を計算に入れない行動がやはり好みだった。前作は主人公が悪人側だったので、いずれ訪れる崩壊への恐怖で心の底から楽しめていたわけではなかったが、こちらはそんなこともない（し、そもそも原作を知らない）ので非常に面白かった。

一旦購買に行ってお菓子やパンとラノベを購入し、帰宅。食べてまたすぐ家を出て、今度は山に登った。いよいよ集中講義一日目である。学部時代には集中講義というものを受けたことがなく、たった一週間で一セメスター分の学習時間を要請するのだから長い間講義漬けになるのだと思っていたが、予定では午後3時から3時間だけらしかった。

講義。今日は一般のグラフについて用語を定義したり、性質を示したり。平面グラフを扱う講義ではあるが、それに特有の性質までは踏み込まなかった。特に後半では、どんなグラフでも次数が奇数の頂点は偶数個存在するという事実を用いて、いくつかのパズルをうまくグラフに言い換えて解いており、面白かった。この事実には「奇点定理」という名前がついているらしい。当たり前の事実ながら応用の幅はかなり広いようだ。

$n$ 頂点のラベル付き単純グラフは何種類あるかという問題があった。競プロをやっていれば一瞬で $2^{n(n-1)/2}$ とわかる。誰も答えなかったので勇気を持って発言したら褒められて、かなり良い体験だった。ちょっと子供っぽいか？ともかく、今日はそうやって真剣に講義に参加していて、他にいくつか質問したり指摘したりしたのも楽しかった。こんなにのめり込みながら講義を受講したのはいつ以来か、学部時代よりさらに昔である気がする。講義の内容が自分の興味に概ね一致していて、かつ対面で参加できたのが大きい。

午後5時には終了。予定より早く終わったのについて講師の方に聞いてみたのだが、一日2時間のつもりで準備してくれ、と言われていたらしかった。3時間とは質疑応答を含めても余裕のある予定だったようだ。

今日は昼にミールカードを使い切っていたので、そのまま帰宅。しばらくグダグダTwitterを眺めてから出発し、午後7時くらいにゲーセンに行った。

途中夜ご飯のために離脱しようかなと思っていたが、かなり上手い日だったので眠気で鈍らないようにとそのまま閉店まで遊び続けた。今日の成果は理論値7譜面、14+のSSS1譜面、SSS+1譜面。

人生攻略☆Tips 理論値！！！ pic.twitter.com/V9keGdosHA
— こたつがめ (@kotatsugame_t) 2022年5月24日

曲がかなり好きでしばらく前にも狙ったものの、中盤のハネリズムがボロボロだったのですぐ諦めた記憶がある。ハネを意識しすぎた結果むしろ微ズレのような押し方になっていると気づいたので、今日は早め早めを意識してみたところ、なかなか上手く行った。あとは最初と最後に何度も降ってくる階段も含めた噛み合い待ち。一つ一つはそれなりの確率で通るが連続して来るのですぐ崩れてしまい、かなり苦しかった。ちゃんと決めきれたのは嬉しい。

the EmpErroR SSS
14+未鳥1 pic.twitter.com/hJz5kv4vf6
— こたつがめ (@kotatsugame_t) 2022年5月24日

これまでは最後の左右に振れるトリルが全然できなかった。脱力を意識しスライダーを叩いた時の反動だけで手を浮かせるような感覚でやってみると、速度的には十分間に合うし、力んでいないので手を左右に動かすのも簡単。今日一発目でニューレコードが出たので、SSSを狙うことにした。そのトリルもたまに酷い失敗をしてしまうので、結局これも噛み合い待ちになる。最終的にはなかなか高いスコアが出たと思うが、ここまでくるとSSS+欲しかったなという気持ち。107小節から118小節で0-2出していて、その部分は今もよくわかっていない。

Love & Justice SSS+
14+全鳥！！！！！！！ pic.twitter.com/uNxi7Sbaev
— こたつがめ (@kotatsugame_t) 2022年5月24日

上手い。間違いなく。

追加されたのが旧筐体のラスト。最後を全押しして3kに乗せ、むしろ前半が全然できなかったので放置した。その後新筐体になると最後の全押しが全然通らなくなってしまった。これはfpsが倍になったことによるのだろうか？ともかく、全押しで通らないならもう伸びないだろうなと半ば諦め気味だった。ところが最近になって何回か触ってみて、前半……というかラストまで普通にSSS残せるようになったと気づいた。特に運指を組んだわけでもなく、シンプルに押せるようになっていたということ。

14+の最後の一つとなったので、今日改めて譜面を確認しながらプレイしてみた。まず45、46小節と85、86小節。指押しからタップスライドに切り替えるタイミングを間違えることが多かったので、それぞれ一回目より二回目のほうが少し指押しが長いことを覚えた。もともと四鍵固定で押せていたので、なかなか安定するようになった。またその直後、それぞれ48小節と88小節はどちらも右手トリルと左手8分で押すことにした。後者は直前の指押しからそのまま入ると左手トリルすることになるので注意。

あとは最後。3小節の指押し地帯が二回降ってくる。このうちの前半は軽傷で済むことが多かったので、いったいなぜ押せているのか確認したところ、真ん中のノーツまで右手を動かして取っていることに気づいた。これが左右反転した後半は、左手が右手に比べて弱いせいでボロボロになってしまっていたらしい。なので、後半も右手を酷使することにした。それでプレイしてみるとまあまあ改善されて、両手トリルの入りも確認しないとと思っていたところで急にめちゃくちゃ噛み合い、上に載せたような2-0という信じられないリザルトが出た。記憶では48小節の終わり際と、102小節でそれぞれ出したはず。最後、無我夢中でやっていたらスルッと通って本当にびっくりした。

残り時間は適当な14+を触って終了。Ai Novの鍵盤も見えるようになっていて感動した。一番町で酔っ払いに混じってラーメンを食べ、帰宅。疲れ果ててしばらくYouTubeを眺めながらボーっとしていた。

Dashboard - Codeforces Round 794 (Div. 1) - Codeforces

そのうち少し眠ってしまったので気合いで起きてシャワーを浴び、ラノベを読み始めた。明日はこのくらいの時間からCFがあるので、敢えて生活リズムを崩壊させておく必要がある。

「お隣の天使様にいつの間にか駄目人間にされていた件」6巻読了。この巻は徹頭徹尾主人公とヒロインがイチャイチャし続ける巻だった。ストーリー的に進んでいるのかはよくわからない。僕は両想いのカップルがイチャイチャするシーンというよりも、その結果人前でも二人だけの空間を作り出してしまうようなシーンが好きなので、前半は正直あまり楽しめなかった。後半は夏祭りに出かけていたので個人的に美味しい展開だった。

またしばらくYouTubeを見てから午前8時就寝。

05/25(水)

午後2時起床。

先日本番環境にデプロイされた機能がブラウザで表示されないというメッセージが来ていて一気に目が覚めた。実は自分の普段使いしているPCでも同様に見えていなくて、PCを変えたりスマホからだと見えるのでいいやと思っていたが、それは実際の使用者にとって解決策にはならないわけだ。キャッシュの問題だろうと当たりをつけてスーパーリロードしてみるも効果はなく、デベロッパーツールのほうからClear site dataを行うと見えるようになった。スーパーリロードと何が違うのかよくわからない。設定からまとめてキャッシュを消したらどうなるのだろうか。とにかく、こうすると対処できましたということを伝えておいた。

講義開始まで時間がない。ブラックサンダーを一つ食べてすぐ山に登った。

講義。今日はグラフ理論におけるオイラーの公式を示して、それを用いて平面グラフの辺の数を評価したり、正多面体を列挙したりした。また、平面グラフの特徴付けとして、 $K_5$ や $K_{3,3}$ をマイナー（あるいは細分に限定してもよい）として持たないことが紹介された。さらに、多面体から作ったグラフの全域木と多面体の展開図の対応についても話された。ラベルなしの全域木を数え上げるのはかなり難しい話らしい。競プロで木を数え上げると聞くと行列木定理やケイリーの公式を思い浮かべるが、確かにどれもラベル付きであって、単純に階乗で割ったりしても全然見当違いの値が出てきてしまう。

学食で食事して帰宅。しばらくTwitterをしていたがどうにも眠い。深夜のCFに向けて念のため目覚ましを設定したら、その直後うっかり布団に倒れこんで寝落ちしてしまった。午後7時半から午後11時半まで寝ていた。

起きてからはラノベを読み、午前2時半からCF #794 div.1。

Aは、まず $n$ が奇数の場合は不可能。偶数の場合はとりあえずソートして、前半を円環状に並べた間に後半を置くのがよさそう。 $a_{n/2+1}$ を $a_1$ と $a_2$ の間に置くか、 $a_{n/2}$ と $a_1$ の間に置くかで2通り考えられる。前者で破綻する場合を注意深く確認すると、最小または最大の要素が $n/2$ 個より多くある場合と、それ以外の要素が $n/2$ 個以上ある場合がまずいようだ。後者は $a_{n/2}=a_{n/2+1}$ の場合即座に破綻してしまい、これは前者で破綻するケースを完全に含んでいる。よって前者で構築するほうが良い。さらに、ある要素が $n/2$ 個存在するとき、それを一つ置きに配置するしかないということを考えると、前者で構築できないパターンは全部不可能と分かった。

BはAとBの文字数を数えてチェックしておくと、ABとBAを使い切る問題になる。文字列を同じ文字が隣接する場所で切っておくと、それぞれがABAB...やBABA...になる。この長さ $l$ で用途を分ける。 $l$ が奇数の場合は、ABとBAをどのように切り出しても合計で $(l-1)/2$ 個になる。 $l$ が偶数の場合は、対応するABまたはBAのみを切り出す場合だけ $l/2$ 個となり、逆のタイプを少しでも切り出そうとすると合計 $(l-2)/2$ 個になる。つまり、ABとBAはそれぞれ対応する偶数長の文字列→奇数長の文字列→対応していない偶数長の文字列、の順で切り出していくのがよい。特に、対応していない偶数長の文字列から切り出すときは、長さが長いものを優先的に使うべきであることもわかる。

Cは初手がわからず結構悩んだ。いつもの $\pm 1$ 累積和がreverseでどのように変化するか確かめてみると、 $\dots,S_l,S_{l+1},\dots,S_r,\dots\rightarrow\dots,(S_l+S_r)-S_r,(S_l+S_r)-S_{r-1},\dots,(S_l+S_r)-S_l,\dots$ になると分かった。 $S$ が負になる項を全部含み、かつ $S_l+S_r$ が最大となるように $l,r$ を定めるとき、 $S_0=S_{2n}=0$ なので必ず $S_l,S_r\ge 0$ とできる。操作後、もともと負だった位置は必ず正になるので、問題は $S_m=\max_{l\le i\le r} S_i$ について。 $S_l+S_r\ge S_m$ の場合はこの1手で累積和を全部非負にできる。では $S_l+S_r\lt S_m$ の場合は……なんと、 $(l,r)\leftarrow(l,m),(m,r)$ とすることで2手で必ず可能。あとは累積和のインデックスを文字列のインデックスに直して出力。

D1は簡単め。 $q_i=p_{q_{i+1}}$ となるように並べるのが一番嬉しい。つまり $p$ の逆順列 $p^{-1}$ を用いると、 $q_{i+1}=p^{-1}_{q_i}$ としたい。 $i\rightarrow p^{-1}_{i}$ という辺を張ったグラフが一つの大きなループになっていればそれが達成できるが、一般にはいくつかのループに分かれてしまうので、できるだけコストをかけずにマージせよという問題になる。 $1$ を含むループを元にし、現在のループに含まれない最小の頂点 $i$ を取り、それを含むループを現在のループにマージしていく。このとき頂点 $i-1$ は必ず現在のループに含まれ、特に構成方法から次の頂点が $p^{-1}_{i-1}$ になっているので、その間に $i-1\rightarrow p^{-1}_i\rightarrow\dots\rightarrow i\rightarrow p^{-1}_{i-1}$ と挿入すると、コストの増加を $|(i-1)-p_{p^{-1}_i}|+|i-p_{p^{-1}_{i-1}}|=2$ だけに抑えつつマージできる。マージするとき2か所以上繋ぎ変えるためコスト $2$ は必ずかかりそうなので、これが最適っぽい。

$n\le 200$ なのに $O(n)$ で解けてしまって大変怖い。D2は $q$ を辞書順最小にせよという問題で、先頭の項から $O(n^2)$ 回かけて決めつつD1を応用してチェックを $O(n)$ で行えば解けると思った。しかし実装が爆発し、コンテスト終了。

システスは全部通って22位。D1とD2の間の崖が大変大きかったようだ。変な時間のコンテストということもあり人が少なく、この順位でもレート変動は2916→2953(+37)。あと1、2回勝てば伝説に手が届きそうなレーティングまで戻ってきた。頼む。

コンテスト後はまたラノベを読んでいた。午前7時半ごろ布団に入り、さらにハーメルンやなろうを読んで午前9時就寝。

05/26(木)

午後1時半起床。あまりにも眠すぎてグダグダTwitterするのが精いっぱいだった。午後2時半前に家を出て、購買でパンとラノベを買い、今日はそのまま山に登って講堂のロビーで食事した。

講義。いよいよグラフの彩色の話が始まった。五色定理の証明が紹介されて、そこから四色定理の誤った証明が述べられた。さて、どこが間違っているでしょう……ということで、競プロで培ったコーナーケース発見力を発揮しようと熱心に考えていたのだが、数分でスライドが進められてしまった。結局、着目していたポイントは悪くなかったものの、スライドに描かれた図に思考が誘導されていたので、別に惜しくもなかった。これを「誤っている」と知らない状態で見つけるのは確かに偉業と感じられる。

五色定理 - Wikipedia

平面グラフの彩色は前半で終わってしまい、残りはもっと種数が大きな閉曲面での彩色数の話に発展していった。想像するのが難しくて直感が働かないし、変なコーナーケースがいろいろあるしで難しい。

午後6時帰宅。適当な時間に学食に行くつもりだったが、ラノベを読んでいたら行き損ねてしまった。そのまま読み続けて1冊読了。

「デート・ア・ライブアンコール」11巻。やはり良い。大学生になった組も高校生になった組もそれぞれフォーカスされた短編があって、大変満足のいく巻だった。まだまだ読み続けたいが、後書きを読んだ感じ、まだ未収録の短編が残っているものの次の短編集が刊行されるかは未定らしい。確かに、新シリーズも抱えていらっしゃるのに完結したシリーズを延々擦り続けるのは、新規のファンが増えず作家としては良くないのだろう。

この前のあーだこーだーで面白かった本として「儚い羊たちの祝宴」をお薦めしたら、読んでくださった方がいらっしゃったらしい。大変ありがたいことである。

この前の「あーだこーだー」でこたつがめさんが面白かった本で挙げてた「儚い羊たちの祝宴」が面白い
短編のうち最初の2つしか読めてないけどこの2つだけでも満足するくらいに面白いし落ちが凄い
— H20 (@H20_dhmo) 2022年5月26日

ラノベをもう1冊読了。「僕たち、私たちは、『本気の勉強』がしたい。」。かなり面白かった。チラシや通販サイトでは作中の「才能がなくても東大に入れる」というセリフを引用して紹介されており、過激な作品という印象が先行していたが、実際読んでみると地に足のついた勉強方針が描かれているなと感じた。そして、そういう描写を受け入れてみればストーリー的にも十分面白く、主人公が勉強にのめり込んでいくシーンの一人語りは読んでいて心を動かされ、じっとしていられなくなるような気分になった。

朝方、少しだけ集中講義の課題を進めた。講義スライドの途中で出てくるたび、頭の中で解けることを確認してはいたのだが、対面で質問できる機会は明日が最後なので、本当に疑問点がないかもう一回チェックしようと思っていた。結局記述の面倒くささが勝って、また頭の中で解ける解けると思うだけに留まってしまった。

ラノベを読んで午前9時就寝。雨が降っていて、明日の登校が憂鬱。

05/27(金)

午後2時起床。あまりにも眠すぎる。また生協に行く時間がないので、カロリーメイトが昼食となる。

地面が濡れているので雨が降っているのだろうと考えカッパを着て、さあ出発だと外に出たら、ちょうど晴れ間の時間帯だった。部屋に戻ってカッパを脱ぐ。帰るころには降水確率10%になっているので必要ないかとも思ったが、念のためリュックに押し込んで再度出発した。

講義。この一週間の睡眠不足が祟って耐え難い眠気に襲われ、前半は意識を飛ばしがちだった。非常に残念。いや朝までラノベを読んでいたのは自分なのだが……。ただでさえ初めて触れることばかりで難しいのに、少し聞き逃してしまい、理解があいまいな部分がある。

今日は昨日の後半の続きで、種数が大きな閉曲面に埋め込まれた特殊なグラフの彩色数。正直な感想としては、そんな特殊な場合の話をされても、というような定理たちであったが、その証明手法は非常に面白かった。気合いで塗り替えてみたり、謎の値を2通りで評価してみたり、代数構造と対応させてみたり。グラフの生成定理も出てきた。僕が少し前に読んでいた論文もグラフの生成定理だったので興奮した。

四色定理がコンピュータによって証明されたということを知ってはいても、コンピュータが一体何を計算したのかは知らなかった。実は四色定理もグラフの生成定理を用いて示されたらしい。平面の三角形分割は一種類の変形のみで $K_4$ に帰着できるものの、これだと変形を逆に見たときに彩色数を保てないので、ちゃんと保てるように変形を複雑化させて個々のケースをコンピュータで処理したということのようだ。どこかで「四色定理を示すには有限個のパターンについてだけ塗り分けられればよいことが分かった」という文章を読んだ記憶があって、ずっとグラフの一部を取り出したパターンが有限個しかないということだろうと思っていたのだが、確かに、それではローカルに塗り分けられたとしてもグローバルに整合性が保たれるかはわからない。

講義を終えて、同級生数人と学食で食事。カレーの中サイズと丼の中サイズを注文して、一人だけフードファイトしていた。カレーが大変辛かった。満腹中枢が反応する前に食べ切ろうと可能な限り急いだ結果、他の人と同じくらいの時間で完食した。

食事 pic.twitter.com/gnT1G8FhIu
— こたつがめ (@kotatsugame_t) 2022年5月27日

その後道端で3時間ほど喋っていた。4年ゼミで一緒だったのが大学院に入って研究室が変わった結果顔を合わせる機会が極端に減ってしまったので、名残惜しむように話題が途切れなかった。実際は途切れても無理やり話し続けたというのが正しいか。いろいろなことを数学にこじつけて話していた。煩悩は108個あるとされているが、 $2^2\times 3^3$ と素因数分解できることに意味はあるのかなど。検索してみると $6\times 3\times 2\times 3$ と分解されていて、みんなしてへえ～と言っていた。

午後9時を回って帰宅。しばらくニコニコ動画を見た後ふらっと布団に倒れこみ、即座に寝落ちした。午後10時半から午前4時まで寝ていた。

起きてからはまたニコニコ動画を見たりラノベを読んだりした後、日記を書き進めた。月曜日に書いてからずっと溜めてしまっていた。午前10時に再度就寝。

05/28(土)

午前11時55分に目覚ましで起きたはず。正午からAHC011が始まるので、Shortest狙いでできるだけ早く問題文を読もうとしていた。しかし実際は布団から身を起こせず、ハッと気づいたら正午から10分経過していた。慌てて読んで提出。このあたりのことは、一応この頃の順位表から読み取れるはずなので、コンテスト終了前に公開される日記に書いてもよいはず。

再度就寝。午後4時前に冷凍弁当を受け取り、また眠って、午後7時に起床。日記を書いて時間を過ごし、午後9時からABC253に出た。

NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） - AtCoder

AはとりあえずAWKで書いた後dcで縮めた。結構時間をかけてチェックしていた。BはC++で素直に。Cはmultiset。Dは全く同じ問題を見た覚えがあると思って、 ${\rm lcm}$ が書きやすいRubyを持ち出した。しかし再現したコードとサンプルが合わないのを見て、前の問題では個数を求めていたのに対しこの問題は総和を求める必要があることに気づいた。包除原理という方針は同じなので、少し書き換えるだけでよい。Eはdp。Fは行と列それぞれ持つだけで終わりかと思ったら、行の書き換えの時に列に足されていた値も考慮する必要があった。取得クエリの直前の書き換えクエリを見つけて、その位置でも列の値を取得するようなコードを書いて通した。最初に $i=1\dots N$ に対し $(2,i,0)$ というクエリを用意しておいて、クエリを逆順に見る実装をした。

Gは簡単。 $x=1\dots N$ に対し操作を行う $(x,y)$ を列挙すると、 $y$ は区間になっている。その区間が最大、つまり $y=x+1\dots N$ のすべてで操作が行われるなら、まとめると列の後ろ $N-x+1$ 要素のrotateになる。そうでない場合は操作を愚直にシミュレートしても合わせて $O(N)$ である。 $x=1\dots N$ のそれぞれで操作し終わるたびに先頭 $x$ 項が決定するので、列をdequeで持って毎回pop_frontすることにすれば、rotateも末尾からpopして先頭にpushするだけで書ける。

Exは、 $K$ 本の辺をループができないように選ぶ場合の数を求めて $K!/M^K$ を掛けると答えになる。選んだ辺の本数は操作後の $G$ の連結成分数から復元できるので、どのような連結成分を作るかで $3^N$ のbitDPを行う方針が立つ。すると、頂点の部分集合すべてについて、それを木にするような辺の選び方が求まればよくなる。一瞬元の問題と同じに見えてしまったが、「森」であった部分が「木」になっているのが違い。つまり全域木を数え上げることになって、行列木定理で一発である。

ノーペナ全完で3位。数学を専攻する学生でもあることだし、これまで経験がないくらい大量に賞金が貰えそう。かなり多くの人がEの $K=0$ でペナを出していたらしい。自分は書きながら気づいて、dpの枠組みで対応するのも面倒だったので即座に $M^N$ を出力するようにしていた。

コードゴルフ。Aはdcが1B縮んだようで負け。BはPerlのshebangを使ってうまく書けた。for/o/gでループすると、同じ行に二つ'o'がある場合に二つ目の情報だけ取得してしまうが、ここをwhile/o/gにするとうまくいくようだ。しかし文字列にマッチした位置のオフセットを取得するところで@+や@-が使えるのを完全に忘れており、負け。Dはdc、GはRuby。

CはC++でmapを使う。まず僕が書いて、それがどんどん縮められて、ちょっとした隙をついて今はまた僕が最短コードを持っている。この問題のように複雑な形式のクエリをscanf一発で読み込む手法が出ていて、かなり興味深かった。単に"%d%d%d"と書くと次の行まで読まれてしまうし、これを"%d %d %d"としたとしても、スペースの部分で任意の個数の「空白文字」、つまり改行も読まれてしまい先ほどと状況は変わらない。ここでスペースのみを読み込むように指定できれば、そこに改行が来た場合何も読み込まずに止まってくれて、次の行を読むのを抑制できる。文字集合の指定によって実現され、今回の場合%[ ]になる。読み捨ての記号*を追加して、以下の提出のようなフォーマット文字列が得られる。

Submission #32068201 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

C言語入門 - scanf関数 - スキャン集合を使った文字列 - ホワイトスペース - Webkaru

午前1時からSRM830に出た。

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

Easyはちょっと面倒なdijkstra。pitsを踏んだかどうかだけフラグで持っておく。

Medはdp＋復元で、復元部分が面倒。モールス符号は問題文からコピペして、先頭と末尾に"を付け加えて文字列の配列に変換した。Vimのビジュアルモードで一発。構文をしっかり解釈すると、文字を|または||で分割していればOKということがわかるので、直前が文字であるかセパレータであるかの2状態を持っておくだけで十分。これで変更する文字数の最小値を求めて、逆から辿っていく。2状態を取り違えまくって実装に苦労した。逆から辿るときは完全に正しいコードを書かないとすぐ遷移元が見つからなくなって無限ループしてしまうので、テスト実行の待ち時間が煩わしかった。無思考でBatch Testを連打するのも考え物。

Hardは実験＋エスパー＋埋め込み。 $(R,B)$ をいくらか計算して出力し睨みつけたところ、縦にも横にも倍数の関係があることが見て取れた。 $B\le 1$ の場合 $(R,B)=(1,0),(0,1)$ 以外全部 $0$ なので別に計算することにして、 $B\ge 2$ とすると、まず $(0,B)$ が $(2B-3)!!$ で表せている。さらにそこから下に $R$ 回進むときは、 $B-1$ 倍、 $B$ 倍、……と増えていたので、 $\prod_{i=1}^R(i+B-2)$ を掛ける。これでテーブルを再現できるはず。

今 $\bmod{10^9+7}$ なので、 $2B-3\ge 10^9+7$ のときの値は $0$ 。そうでないとき、 $(2B-3)!!=\frac{(2B-2)!}{2\cdot 4\cdot\dots\cdot(2B-2)}=\frac{(2B-2)!}{(B-1)!2^{B-1}}$ 、 $\prod_{i=1}^R(i+B-2)=\frac{(R+B-2)!}{(B-2)!}$ と変形すると、どの分母も $\bmod{10^9+7}$ で $0$ にならないのでちゃんと計算できる。あとは階乗を高速に計算するだけ。高速階乗なんていうライブラリがどこかに落ちていたはずと思って探してみると、畳み込みを使っていて大変そうだった。yukicoderにそのままの問題があって、過去の自分が埋め込みで通していたので、これをコピペしてきた。適当に大きめのケースを試すと少しTLEしてしまったので、埋め込む間隔を $10^7$ から $3\times 10^6$ に書き換えておいた。

#164690 (C++14) No.502 階乗を計算するだけ - yukicoder

Easyで古い問題文が表示されていたらしく、システムテストに更新後の制約である $100\times 100$ の入力が含まれていたようだ。後からリジャッジされるらしい。僕もEasyが落ちてしまっていたが、MedとHardは通ってくれて3位になっている。僕より上にいた人が何人かHardを落としているので、Easyのリジャッジが行われた後もかなり良い位置につけているのではないかと期待が持てる。

Hardの証明は、集合の分割を二分木として見るとよいらしい。まず $B$ だけで分割方法を考えると、 $B-1$ 個を分割する二分木のどこかのノードに $1$ 個子を生やすことになって、木のノードは分割のために縦に伸びた分も含めて $2$ 個増える。つまり $B-1$ 個追加時点では $2B-3$ 個のノードがあり、そこから $1$ つ選ぶ方法だから $2B-3$ を掛けることになる。 $B=1$ に帰着されるまで辿ることで $(2B-3)!!$ が得られる。あとは $R$ を追加する方法で、 $(R,B)=(1,0),(0,1)$ 以外のノードに $1$ 個子を生やせるので、追加するたびに使えるノードが $1$ 個増え、 $i=1\dots R$ に対し $(2B-1)-B+(i-1)=i+B-2$ 通りとなる。

ラノベを1冊読了。「好きで好きで大好きなので、いっしょに好きを伝えたい」。ヒロインがVtuberをしているらしいので購入。しかし別にVtuberをメインにしているわけではなさそう。少なくともこの巻は主人公とヒロインの馴れ初めを描くのに紙幅を費やし、Vtuberをしている描写は冒頭とラストに少しずつ現れるだけだった。そのラストの部分でVtuber活動に影響を及ぼすような出来事が起こるので、2巻ではよりクローズアップされるものと思うが、結局Vtuber活動を通してヒロインを描くだけで、舞台装置の一つ以上の役割にはならないだろうと予想している。

それから朝まではずっと日記を書いていた。午前10時就寝。

05/29(日)

午後3時半起床。食事して午後4時からOpenCup、の代理のコンテスト。先週と同じで、通常のOpenCupがない週のためadminから配られたコンテストにバーチャル参加するやつ。午後9時からARCがあるので、それに被らないような時間から開始するということでチームメイトと合意していた。今日のコンテストタイトルはPKU Contest 1, PTZ Summer 2021 Day 4。

チームで5完。自分はAとFを担当した。Aはひとまず重複してカウントするような辺を許して数え、後から間に辺が存在するような頂点対の分だけずらす。数える部分は畳み込みの形になるので、convolution_llを使う。順位表では結構ペナが出ていたようだったが一発で通った。自己ループの処理に少し気を使ったので、そこで間違えた人が多かったのだろうか？Fはrange addとrange chmaxで実家dpができる。制約が $2\times 10^5$ でTL 1secと設定されており、beatsの定数倍が悪いこともあってかなり不安になったが、OpenCupなら通るだろうと強く主張した。ライブラリを持っていないのでチームメイトの全部盛りbeatsを拝借してそのまま出したら0.9secで通った。持つ情報をもう少し絞ればもっと速くできるだろう。

残り時間はHとBで半々くらい使った。Hは結局解けず。Bはカクタスグラフを扱う問題で、紙の上ではできているものの実装に失敗という感じ。ループの繋がり方を見るためにBlock Cut Treeを持ち出してガチャガチャしており、何回か提出して全然通らず、この先合わせられる自身がなかったので別の問題のためにPCを譲った。その問題はコンテスト終了8分後に通っていた。ちょっと申し訳ない。

午後9時からARC141。

AtCoder Regular Contest 141 - AtCoder

Aはとりあえず $9$ の連続が作れて、それより大きな数は桁数が $N$ と同じになるので、 $m$ の桁数を全探索するのが良さそう。 $m$ としては $N$ の先頭から取ったものをそのまま使うか、1だけデクリメントしたものを使うかだけ考えれば十分。Bは簡単。 $B_i\lt B_{i+1}$ という条件から $A_{i+1}$ のMSBが $B_i$ において立っていないことが言える。さらに $A_i\lt A_{i+1}$ よりMSBの位置は単調増加なので、特に狭義単調増加になる。それより下のビットは自由に決められるので、MSBの位置を添え字に持つdpを行えばよい。 $N\gt 60$ の場合答えは $0$ なので、先に弾いておく。

Cは信じられないくらい難しかった。とりあえず $P$ から取り出せる限りの情報を取り出してみる。まず、 $S_{P_1}$ は'('であり、それより前の文字はすべて')'でなければならない。今決まった')'を使い切るより前に $S$ のもっと先の要素を使う場合は、それもまた'('であるとわかり、 $P_1$ との間がまた全部')'とわかる。このようにして、 $\max P_{[1,i]}=i$ であるような位置までは完全に決定してしまう。ではその次の文字はどうなるだろうか。 $P_{i+1}=i+1$ である場合は、正しい括弧列になる限り何でもよい。 $\max P_{[1,i+1]}=i+1$ が成り立っていれば、という風に見ることもできる。 $P_{i+1}\gt i+1$ の場合、 $i+1$ 番目には')'が使えなかったとわかる。つまり $S_{P_{[1,i]}}$ だけを見たとき、そこで完結した正しい括弧列になっていなければならない。そのあとは $P_1$ 以降の議論の繰り返しになる。

まとめると、 $\max P_{[1,i]}=i$ であるような位置で分割したとき、長さが $1$ より大きいブロックと先頭のブロックは完全に決定し、またそれらの直前までが正しい括弧列になっていることも要請される。 $Q$ についても同様の処理を行って、2通りの文字列が完成した。 $Q_i\leftarrow 2N+1-Q_i$ として $P$ に対するものと同じ処理をしてから反転するのが楽だった。

この2通りの文字列をマージしたとき、まだ決定できない箇所が存在する可能性がある。その位置、一般には区間は、 $P$ から見れば順に使われ、 $Q$ から見れば逆順に使われる。 $P$ から見て破綻しない限り')'を優先的に使うとよいかと考えたが、 $Q$ 由来で中途半端な位置で決定している括弧をちゃんと考慮するのが難しい。そこで、開き括弧と閉じ括弧の個数の条件を $P$ 由来のものも $Q$ 由来のものも全部左から見た $\pm 1$ 累積和の条件に言い換えて、これが非負でなければならない区間（ $P$ 由来）と非正でなければならない区間（ $Q$ 由来）に分けてみた。ここまでするとどちらかの括弧を優先的に使うことができる。

最後に出来上がった文字列をチェック。ここまで書いてきたコードでもいたるところにチェックが入っている。3400Bにも膨れ上がったコードを提出するとREで、絶望。しかしREしか出ていないのはおかしいな……と思ってよく見ると、配列サイズが $2N$ 必要なところ $N$ しか用意していなかった。ここを修正してAC。1時間ちょっとかかってしまっている。

残り時間はDを考えて、手も足も出なかった。3完92位。

Cの解説は天才的。 $S$ が正しい括弧列であるかその反転である場合は、確かに高々一通りに定まるらしい。では一般の $S$ に対しても本当に正しいのか？今 $S$ とそこから作られる $P,Q$ があったとして、新たに正しい括弧列 $T$ を $S+T$ のように付け加えることを考える。このとき、 $Q$ においてはインデックス $|S|+1\dots|S|+|T|$ を優先的に使うことになるので、 $Q$ の先頭に新たに $|T|$ 要素増えるような変化をすることがわかる。 $P$ のほうは末尾に $|T|$ 要素増えて、いずれにしても連続部分列として現れるのでちゃんとそれぞれ復元できるということらしい。

また、僕がコンテスト中に考慮していた「2通りの文字列をマージしたときまだ決定できない箇所」は存在しないということもわかる。実際、その部分のコードをごっそり削除しても通ってしまって涙が止まらなかった。今日記を書きながら改めて考えてみると、 $P$ で決定できない箇所に累積和が非負のフラグを立て、 $Q$ で決定できない箇所に累積和が非正のフラグを立てて、両方のフラグが立っている箇所があったら即座に $-1$ を出力していたので、もし決定できない箇所があったら必ず $-1$ を出力することになっていたらしい。この部分で実装にかなり苦しんだのに、まさかそうなっていたとは……。

昨日のSRMの結果が出ていた。全完2位で2699→2815(+116)。highest。

日付が変わったあたりから日記を書き始めて、校閲まで終わったのが午前8時だった。土曜日の後半と日曜日の部分しか書いていないのにこれだけ時間がかかっているのは異常。なろうを読んでみたりハーメルンを読んでみたりでかなり頻繁にキーボードを打つ手が止まっていたようだ。集中力がなさすぎる。

2022-05-23

週記（2022/05/16-2022/05/22）

05/16(月)

先週は週記を投稿してからすぐ布団に入った。しかしそこからしばらくYouTubeを見てしまって、寝たのは正午だった。

午後4時前に起床。インターン先定例会までの短い時間で、多少なりとも進捗を出しておこうと思って調べ物をしていた。それでも進捗はゴミカス。今週は火曜日にミーティングがあるので、否が応でも何か進むだろう。

他の人の発表を聞きつつ、勉強会スライドの確認と手直しをしていた。文字に色を付けたり。定例会が長引き、普段より遅い時間から勉強会が始まった。使用したスライドは公開してある。

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

テーマは関数型言語で、ラムダ計算の導入、そのSKIコンビネータによる表記、またそれを用いたHaskellにおけるポイントフリースタイルへの書き換えを話した。ただでさえ普段より遅く始まった勉強会で長い時間喋り散らかすのは躊躇われるため、スライドの式変形を大胆にカットして雰囲気で進めたつもり。しかし1時間ちょっとはかかっていたようだ。

発表に対して頂いたコメントで、結構置いてけぼりにしてしまったことを知った。当たり前で、ラムダ計算という目新しい表記を導入しているのに、それを使ってバリバリ計算するような内容を急いで喋っていては理解できるものも理解できない。勉強会でこういう「自分はよく知っているが他の人があまり知らない分野」について話すときは入念な戦略が必要である。例えば今回であれば、僕が最も伝えたかったのはポイントフリースタイルへの書き換えであったから、ここを重点的に……いや、それでもラムダ計算の導入は必要なのか。難しいな。

いくつかの部分ではラムダ式をPythonコードにしたものも添付していたので、その辺りは視覚的な面白さもあったのではないかと思っている。コンビネータSとKをそれぞれPythonのラムダ式で書いて、そこからIを作り、実際に適当なラムダ式を書きなおしてみる。すると見た目にはとんでもない文字列になるが、正しく動作する。この見た目に圧倒されてくれれば僕としてはもう満足。ただ理解の助けになったかというと微妙。Pythonのラムダ式で書いたところで、そもそも「関数を返す関数」が理解しにくいので、わかりやすくはならない。

スライドを投稿してからゲーム理論の教科書を読み始めた。今日期限の課題が1個ある。集中を切らしてラノベを読んだりYouTubeを見たりしつつ、何とか期限の30分前に完成して提出できた。お互い7個の戦略を持つ戦略系ゲームの表を書かされる問題があって、手書きで書き始めたことを後悔していた。その後さらに2時間かけてもう一つ課題を倒した。

少しコードゴルフ。ARC140C。最短コードがdcでびっくりしたが、軽く読んだ感じ普通に場合分けしているように見えたので、もっと単純な方針をまともな言語で書いたら短くなると考え、やってみた。ただその単純な方針を考えるのに、他のコードがあまり参考にならずかなり苦労した。

$1\dots N$ を2つに分割して、適当にreverseした後交互に出力するというもの。前半後半に分割しただけでもほとんどの場合うまくいって、 $N$ が偶数かつ $X=N/2$ の場合、または $X=N/2+1$ の場合のどちらかを特別扱いする必要がある。先に分割してしまうとうまくいかなかったため、分割する前に適宜reverseする方法を思いついた。整理していくと、後ろから $N/2$ だけpopした後に残ったもののreverseとzipするだけで書けてしまい感動。reverseが2か所に出現するのがちょっと気になるが、Vimで書くと2度目の出現をほとんど省略できるのでむしろ短くなるのかも。ということで、そのVimで書いたものが最短になっている。

Submission #31753205 - AtCoder Regular Contest 140

午前4時頃にゴミを出した。この時間でももう外が薄明るくなっていて、夏（正確には夏至）が近づいてくるのを感じる。とはいえド早朝であることに違いはなく、誰もいないだろうと外に出たら、なぜかアパートの前の道路を原付がゆっくり走っていた。できるだけ見ないようにしてごみ集積所まで往復。大変怖い思いをした。

布団に入ってしばらくなろうを読み、午前7時就寝。

05/17(火)

30分おきに設定した目覚ましを何度か無視し、正午にやっとかっとで起床。昨日寝る前にしこたまなろうを読んだのが本当にバカ。まだ身を起こせるほどではなく、しばらくはまたなろうを読んでいた。

30分ほどコーディングした後、午後1時から1時間ミーティング。あれよあれよという間に、僕が書いていたコードが「本番環境に」デプロイされそうな感じになった。実は今までデプロイデプロイ言っていたのは全部ステージング環境の話だったのだ。そう変なコードを書いたつもりはないが、もし僕の作った処理が原因で落ちるなどしたら大変なことである。まあ、祈るしかできない。

そのあと作った処理のドキュメントを書いていた。書きあがって担当の人にお見せするとき、ついでにユースケースに合わせるような仕様の変更案を伝えると、実現すればかなり嬉しいという反応があったので、そこからしばらくはそのためのコーディングをしていた。デプロイ直前にこうやってコードに更新を入れるのは、当たり前ながら一般的に良くない。それに気づかずに更新しますという宣言をして、ひとしきり議論が発生した。この決着について話そうとすると、僕がやっていることをこれまでより詳細に説明する必要が出てくるため、割愛。午後5時くらいに一段落した。

コードゴルフをした。APG4bのEX11。以前までの最短はPerlで普通にevalするものだったが、AWKでコードを組み立てdcに食わせるコードで縮められていた。errorの場合分けもAWKのほうで行うとうまくいくらしい。これを単にVimに書き写してもどうしようもなかったので、もうちょっと本質的な改善を考えたい。実はerrorの場合分けはdcで行うほうが短くなるのではないか？[error]pqのような文字列をスタックに積んでおいて、ゼロ除算とそれ以外でスタックの様子に変化があるのを利用して検出し、実行する。Vimでうまいことコードを組み立てると何とか縮んでくれた。

その後、こちらもAWKで組み立てたほうが2B短くなることに気づく。しかしqでdcを抜けると終了コードが非ゼロになり、REとなってしまう。これを解消するため、+1Bでdcからシェルスクリプトを呼び出すテクを使うことになり、合わせて1Bの短縮となった。

Submission #31763359 - C++入門 AtCoder Programming Guide for beginners (APG4b)

コードゴルフをしていたら学食が閉まってしまった。しばらくなろうを読んでから食事し、いよいよおすすめのネット小説をまとめようと思って、とりあえず今年読んだものを週記からリストアップしていた。はてなブログの下書きの状態で塩漬けにしてある。多分、これ自体も昨年のように形式を整えて年末に投稿することになるだろう。昨年は1年分の週記をチェックするのが大変だったので、こうやって定期的に集めておくと便利そう。

今年読んだネット小説のまとめ - kotatsugameの日記

最新の週記まで確認し終えたところで気が抜け、しばらくなろうを読んでいた。するといつの間にか椅子の上で少し寝入ってしまったので、布団に移動。そこからもしばらくなろうを読み続けて、午前1時半ごろに寝落ちした。

05/18(水)

午前8時頃起床。手癖でYouTubeを開いたら犬山たまきさんが配信を行っていて、何気なく視聴してみたらしぐれういさんがいた。朝から声を聴けていい気持ちになれた。アーカイブはメンバー限定公開になってしまうようなので、一期一会。

【深夜テンション】佃煮のりおの顔面【メン限アーカイブ】 https://t.co/NnPWYU96BO

地獄のようなアーカイブはメン限に行きました…🚙💭
パズルを手伝いに来てくれたみんなありがとう✌

おやすみなさい
— 佃煮のりお/犬山たまき🐶💙 (@norioo_) 2022年5月18日

しぐれういさんがこの配信の通話から抜けた段階で自分も視聴を止め、もう一度寝ようと考えた。しかしすっかり眠気がどこかに行ってしまったようで、適当にスマホを触っていたらうっかりハーメルンを1作読み始め、読み終えてしまった。「転生したら美少女VTuberになるんだ、という夢を見たんだけど？」。チートガン積みでかなり良かったが、配信風景の描かれ方と同接数やスパチャ額が見合っていないように感じられた。とんでもない数字を叩き出すのだから、本人の言動以外の部分だけでももうちょっと厳かというか、偉大さのある描かれ方をしていてほしかった。

PWMUL - Editorial - editorial - CodeChef Discuss

そのあと、昨日書いたデプロイについて少し確認とやり取りをして、午後1時に再度就寝。午後6時に起床。

先週日曜日に出たCodeChefの4問目の解説が公開されていたらしいので、読んだ。 $\gcd(a',P-1)=k$ 以降嘘しか書いていないが、方針は分かった。頂いたリプライも参考に、 $B^k\equiv C^k\pmod P\Rightarrow \exists t\in\mathbb{Z}\;s.t.\;A^t\times B\equiv C\pmod P$ の証明を自力で付けてみる。ここで $k$ は $A^k\equiv 1\pmod P$ を満たす最小の正整数、つまり乗法群における位数である。

元の解説は読んでないんですが、(Z/PZ)^*ではなくZ/(P-1)Zの言葉で読んだ方がわかりやすそうです。M=P-1として、aを取り替えてak=Mとしてよく「bk=ck mod M⇒at+b=c mod Mが成立するtが存在する」を示したくて、bk=ck mod M⇒b=c mod (M/k=a) なのでそれはそう
— hidesugar(9) (@hidesugar2) 2022年5月18日

まず原始根 $g$ を取って $A\equiv g^a$ 、 $B\equiv g^b$ 、 $C\equiv g^c$ とおき、全体を指数の法 $M=P-1$ による合同式で書き換える。 $0\le t\lt k$ なる整数 $t$ に対して $at+b-c\bmod M$ の値を見て、 $0$ にできればOK。

ここで $\bmod{M/k}$ を考えてみる。まず $k=M/\gcd(M,a)$ より $M/k\mid a$ となるから、 $at\equiv 0\pmod{M/k}$ 。また仮定より $bk\equiv ck\pmod M$ であるが、このとき両辺を $k$ で割ると $b\equiv c\pmod{M/\gcd(M,k)}$ が得られる。 $\gcd(M,k)=k$ なのでここでも $\bmod{M/k}$ が出現して、まとめると $at+b-c\equiv 0\pmod{M/k}$ が言えた。つまり $at+b-c$ 、ひいては $at+b-c\bmod M$ は常に $M/k$ の倍数。

$k$ の定義より $t=0\dots k-1$ で $at\bmod M$ は一致しないので、 $at+b-c\bmod M$ も一致しない。今 $[0,M)$ に $M/k$ の倍数は $k$ 種類しか存在しないため、そのすべてを1度ずつ取ると言える。当然その中には $0$ も存在する。以上より、どこかの $t$ で $at+b-c\equiv 0\pmod M$ が満たされると分かった。証明終。

少しコードゴルフして、午後8時くらいに外出。もっと早く家を出たかったが思ったより二度寝で爆睡してしまった。ゲーセンに行く。05/02に帰省の途中で大宮のゲーセンに寄って以来なので、二週間以上間が空いたらしい。

今日は新曲を埋めた後14+を適当に触った。新曲から理論値+2、また14+のAJも+2。

みずいろレインドロップ　理論値
ジェネリック緋蜂みたいなの大変だった pic.twitter.com/DKrV6v4Ht0
— こたつがめ (@kotatsugame_t) 2022年5月18日

ジェネリック緋蜂とは片手で連打しつつもう片手が同時押しだったり交互だったりする配置のことを指している。そこの噛み合い待ちで、ほかの場所、例えばジェネリックAttraqtiAはバッチリだった。

IMPACT AJ pic.twitter.com/RK4spop2o8
— こたつがめ (@kotatsugame_t) 2022年5月18日

前にプレイしてからしばらく日を置いたらスッと出た。最高精度は以前日記でも触れた6-1-0なので、これでも倍以上の赤を出してしまっている。ただ14+で9950↑は初なので、嬉しい。記憶によれば1000コンボ時点で10個出ていたはず。最高精度を出したときはそこまで理論値だったので、前半の癖が残っていたのだろう。

Scarlet Lance AJ pic.twitter.com/LgJw7q6tTN
— こたつがめ (@kotatsugame_t) 2022年5月18日

久しぶりのプレイから2回で出た。こういうリザルトが特に苦労もせず出るようになったという点で自分の成長を感じる。昔は両手それぞれに認識難で片手トリルが降ってくる配置とか、ラストの高速四連打繰り返しに苦しめられていた。

閉店までいたあと油そばを食べて帰宅。実はゲーセンに入る前にも立ち食いそば屋で食事していて、それからあまり時間が空いていなかったので、食べきるのに結構苦労した。

帰宅するとatgolferに更新が複数流れてきていた。Perlに新手が出たらしい。shebangでオプション-aをつけて実行すると、入力が自動的にsplitされて@Fに保存される。splitだけだと自分で書いたほうが短いように見えるが、変数に入れるところまでやってくれるという点が二回以上使う場合に効いてくる。さらにオプション-pで出力を省略することで、実際に最短コードを更新するほど短くなったらしい。自分でもいろいろチェックして少し見つけたほか、それで縮んだものをさらに縮めようとしてしばらく考えていた。午前4時になって切り上げた。

Submission #31788047 - 九州大学プログラミングコンテスト2018

TLでpaiza_runがpaiza_botとして復活したことを知った。出力が画像として返ってくるようになっている。昔僕がQuineを投げて無限ループさせたから……。当時のtogetterを見返しつつ自分の感覚を整理してみると、反省はしているけれど後悔はしていない、というくらいになった。当時の自分にカウントダウンQuineが組めるくらいの力があれば良かったのに。ところで、画像欄で遊んでいたのは普通にマナー違反だった。

なぜ無限ループに対応していなかったのかについては恐らくTwitterのリプライの仕様変更が効いている。もう僕も記憶があいまいだが、リプライ先IDがリプライの文面に含まれないようになったのがこの少し前だったはず。その前は勝手に文章の先頭にIDが書かれた状態になっていたので、Quineしようとしたとしても普通にinvalidなツイートが生成されるように見える。

プログラムをツイートすると、実行結果が返ってくるpaiza_runがpaiza botとして復活したらしい！
「@paiza_bot 言語:コード」または「#paiza_bot 言語:コード」で実行結果が返ってきます。#paiza pic.twitter.com/otgGALyVpi
— 片山良平@paiza代表/一緒に働きたい人募集中 (@rk611) 2022年5月18日

togetter.com

明日のセミナーの準備を始めた。先週発表しなかった分があるとは言え、きちんと準備できていないし、1週間経って内容も頭から抜けてしまっている。特に、教科書を読んでいるときその場で考えて埋めた行間をちゃんとメモしていなかったので、その再現と、必要であれば改めてメモしておくことを行っていた。

全然終わっていないのだが、朝になってしまったのでいったん眠ることにする。午前5時半くらいに布団に入って、そこからなぜか30分YouTubeを見てから寝た。

AtCoder Beginner Contest 252 - AtCoder

05/19(木)

昼前に起きて、混む前に学食に行って、一旦帰ってセミナー準備をしようと思っていた。実際は正午になっても起きられず横たわっていた。

午後1時前にスマホに通知が来て、何かと思ったらもうすぐインターン先の会議が始まるとのこと。と言っても僕にとってはただ参加して聞いているだけでOKの、何というか大きな枠組みでの会議。そもそもインターン生が参加することを想定されているのかなど気になることはあるが、いいきっかけなので頑張って身を起こした。

会議を聞きつつ教科書を読み進めていた。全然終わらない。そもそもどれだけ飛ばしても今日1日で発表しきれる分量ではないな、と気づき、後半部分をすっぱり諦めることにした。

準備して午後2時半に出発。途中生協でラノベを受け取りつつ午後3時の直前に教室についてみると誰もいなかった。買ってきたパンを食べつつ先生にメールを送ってみるも、返事がない。

もう一人の同級生にLINEを送ってみると、その人が今日集中講義でセミナーに出られず、そのことを伝えられた先生も帰ってしまったということが判明した。ギリギリに来てしまった僕もちょっと反省すべき。とりあえず今日は帰宅することにして、来週は二人とも集中講義なので、次は再来週になる。

暇になったので読むぜ pic.twitter.com/48dva3yqnY
— こたつがめ (@kotatsugame_t) 2022年5月19日

上のようなツイートをしたが、実際には読まず、院生室でしばらく駄弁っていた。入学から4年以上経った今でも僕が同級生の名前をほとんど覚えていないという話が出て（出したのは僕ではないことを念のため注意しておこう）、実際その時喋っていた2人のうち片方の人の名前がわからないということをカミングアウトした。ショックを受けたような反応をされてかなり申し訳なさがある。

その人とは昔から頻繁に生協で遭遇するしよく話すので、僕はもちろん友達だと思っていたし、反応から彼も僕のことを友達と思ってくれていたのだろう。当然顔を見れば一発で認識できる。ただ自分の中で、ある人が友達であることと、その人の名前を知らないことは矛盾なく両立してしまうのであった。名前を知らなくても適切に代名詞やジェスチャー・目線を使えば会話は問題なく行えるし、仲良くなってから改めて名前を確認するのは躊躇われる。今日ちゃんと名前を聞いたので、このような強烈なエピソードもあるから多分忘れない、と思う。

夕食を食べる約束をしていたホスフィンにセミナーが消えたことを連絡しておいたら、わざわざ院生室まで来てくれた。元からいた2人と別れてセミナーが行われるはずだった教室に戻り、2人でゼミっぽいことをした。お互いに今やっていることを喋るやつ。教科書はまだ読み始めたばかりなので、その前に読んだ論文について喋った。ホスフィンはもう具体的な問題に取り組んでいて、学士で卒論を書く必要がない数学科のぬるま湯加減が意識された。

午後6時くらいになって教室を出て学食に向かった。普段使う理薬食堂は今工事中で閉まっているので、少し歩いてけやきダイニングというところに行った。ここは窯で焼いたピザが売られている、ちょっとオシャレなところだった。ところで、3本の直線によって円は最大7個の領域に分割されるが、これを一般化すると怠け仕出し屋の数列というものになるらしい。

ヤバい！3本の直線で7個の領域に分割してしまった pic.twitter.com/BpFLGkxWVk
— こたつがめ (@kotatsugame_t) 2022年5月19日

コンビニで原付の軽自動車税を支払いつつ帰宅。次の1か月の新刊ラノベをチェックした。買うことにしたものが19冊あり、2冊は予約受付が終了していたため、残り17冊を注文。予約受付の終了とはおそらく既定の冊数に達したからだと思うが、発売まで1週間以上あるのにもうそういう売り切れっぽい状態になっているのは驚き。人気シリーズの続刊なので理解できないことはないか。

今日のCF combinedはwriterが青だったのでサボって、深夜までラノベを読んでいた。FFの方が仙台に来ているようだったので、リプライを送って明日会う予定を立てた。

午後11時半からTCB47に出た。日曜日終了なのでここに各問題へのコメントを書く。

1問目はうっかりbit全探索を書こうとして、問題名が答えになっていることに気づいた。4問目はなかなか難しい。 $\min(X,A_i)\le 1$ の場合だけ加算する。 $\min(X,10^9)$ も一緒に管理して解いた。7問目は面倒。「楽しさが $X$ より大である間常に行う」としたとき $T$ 回以内に収まる最小の $X$ を二分探索した後、残りの行動を全部楽しさ $X$ で行ったとして値を求める。ここで二分探索の範囲は必ず $X\ge 0$ となるように決める。

8問目は難しかった。初手では適当に取る順番を決めて、swapしたときの合計時間の変化を見るものと考えたが、全然うまくいかない。しばらく考え込んで、取る順番より経路をもとに考えたほうが良いことに気づいた。ある経路を通るとき、各パンはそこを最後に通った瞬間に食べるのが良い。こうすると、まだ食べていないパンの区間を狭めていくようなdpが考えられる。区間のどちらの端にいるかも次元に持って、そこのパンを食べた後区間を一つ狭めつつどちらの端に移動するか決める。配列外参照で1WAと、時間も結構かかってしまい-29pt。

9問目は棒を取れる $r$ の範囲をそれぞれ求めて区間スケジューリング。範囲の両端は2乗したものが有理数になるのでそれで持って、比較は__int128を使った。後からよくよく式をチェックしてみれば、確かに分子が $10^{16}$ オーダーになり得るものの、比較で出現する有理数のペアはどちらかの分母が必ず $1$ となっていたりして、うまいことオーバーフローしないようだ。直線と点の距離が線分と点の距離になる条件を記述し忘れ1WAで-15pt。

10問目はそれぞれの木で貪欲法を使い最大マッチングを求めた後、マッチングに使わない点同士を優先的に辺で結ぶのが良い。連結成分ごとに使わない点の個数を持って、残り1個同士をできるだけ結ばないようにする。

合計-44pt。WA2つがそれぞれしょうもない理由なのがつらい。8問目の配列外参照は、それだけでほとんどのケースに落ちるということが信じられず、他に原因があるものと思ってかなり念入りに確認していた。

少しコードゴルフしてから日記を書き、シャワーを浴びたりラノベを読み進めたりして午前4時半に布団に入った。そこからハーメルンの更新分を読んで午前5時就寝。

05/20(金)

午前11時起床。昨日、正午あたりには仙台駅近くにいると宣言したので、その通りにするため準備して出発した。

狙い通り到着。駅ナカのドトールで食事がてら時間をつぶし、お相手の方から仙台駅に着いたとの連絡を貰ってすぐ駆け付けた。それほど自由に行動できない状況らしかったので、サッと会ってパッと帰る感じ。自己紹介して、アカウントのホーム画面を互いに撮影して、一人とツーショットを撮って、あとは少し喋って別れた。

仙台駅を庇い石にされてしまったアンパンマン @Pura_prime @3210eltrut @shiomusubi496 pic.twitter.com/fTLZAmdby0
— こたつがめ (@kotatsugame_t) 2022年5月20日

そのままゲーセンに向かい、午後1時半から夕食を挟んで午後10時半まで遊んだ。

まず夕食前の成果。理論値が2譜面、14+のSSSとSSS+がそれぞれ1譜面、15のSSSが2譜面。15のSSSが2譜面！？

SINister Evolution SSS
14+未鳥2 pic.twitter.com/FCHTSBuigv
— こたつがめ (@kotatsugame_t) 2022年5月20日

2回ある高速乱打がどうにもならず、追加されてすぐ出した鳥寸からちっとも伸ばせていなかった。今日は見えたまま手を動かしたらスルスル通って、2回目で鳥に。普段と何が違うのか全然わからないので、結局そうやって「押せる日」を待つしかないように思える。その分押せる人にとってはかなり簡単な部類の譜面だとされていて、実際これが14+初AJの人をTwitterで何人も観測した。

真千年女王 1-0！！！しゃあなし！ pic.twitter.com/PscJwVgrdX
— こたつがめ (@kotatsugame_t) 2022年5月20日

非対称トリルっぽいところ、具体的には85小節目で出したはず。ここは譜面が見えておらずいつも勘で押しているので仕方ない。今日はそれ以外の部分で全然出さず、我ながら上手かった。

雪男 SSS pic.twitter.com/acYW1fYfAq
— こたつがめ (@kotatsugame_t) 2022年5月20日

今日解禁してすぐSSSまで出た。普通にやると追いつかないが、追いつかないくらい速いので擦っても通る。ありえないくらい簡単だった。これが15なら確かにContrapassoもotoriiも15。

POTENTIAL SSS pic.twitter.com/59FTyngPTa
— こたつがめ (@kotatsugame_t) 2022年5月20日

特に運指は組まず全部見えたまま押して、癖がつく前に噛み合った。今日は信じられないくらい上手。スコアも今のところ15で最も高くなっている。

何度も上手上手と連呼しているように、今日はこれまでとは別次元に上手い日だった。もっと15のSSSを出せるかと思ってX7124と蜘蛛の糸も狙ってみたが、それぞれ7k弱、5kで断念した。癖がついてしまったので、やはり15と向き合うときはちゃんと運指を組まないといけないようだ。しかしそう考えるとPOTENTIALは上手かったな……。

ラーメンを食べて別のゲーセンでもう少しプレイした。食後すぐは眠かったのと、少しすると音ゲーサークルの人々が来て待ちが発生したため、適当に14+を触るくらいで終わった。とは言えこれも上手く、いくつか伸びたのと、larvaのAJを出した。本当にスッと出て、直後は手が震えていた。ただ精度は不甲斐ない。理論値を狙う時と同じ判定なのに、難しい譜面だとFASTに寄ってしまっている。赤Jでも通ればいいやとプレイするのではなくて、ちゃんと光らせることを意識してもいい頃合いなのかもしれない。そういう意識を持てるほど落ち着いてプレイできるようになったはず。

larva AJ pic.twitter.com/1P8NXtQzzD
— こたつがめ (@kotatsugame_t) 2022年5月20日

午後11時前に帰宅。疲れ果てて長い間ネットサーフィンをしていた。日付が変わったあたりでRebellionの理論値ツイートが流れてきて目を剥いた。

恐怖！0時Rebellion AJC男 pic.twitter.com/CT0D0y9ZQn
— すとらです (@Kokor0_N) 2022年5月20日

ニコニコ動画を見ながら日記を書いていた。午前6時くらいに切り上げ就寝。

05/21(土)

午後4時起床。二度寝はしないことにして起き上がった。用を足してすぐ生協の冷凍弁当の配達があって、少し早かったら応対し損ねるところだったと冷や汗をかいた。

YouTubeに時間を吸い取られつつ日記を書いて、午後9時からABC252に出た。

Aはdcで2B。BはRuby。ここからC++に切り替えた。Cは揃える文字を全探索して、どう止めるのが最適か考える。リールにおける文字の位置の被り具合を見ることで少なくとも何周する必要があるか求まるので、最後の周はどの位置まで回す必要があるかを確認すればよい。Dは手癖で $j$ を固定しようとしてうまくいかなかったので、異なる3要素の取り方を求めて並べる方法を数えようとしたら、 $i\lt j\lt k$ とした場合と $A_i\lt A_j\lt A_k$ とした場合が一対一対応することに気づいた。Eは初手がわからず少し悩んだ。初めの $d_2,d_3,\dots,d_N$ からどれくらい増えるか考えようとして、各頂点への最短経路をうまく選べば一切変えない状態が達成できると気づいた。

Fはかなり悩んだ。解説にあるような操作の二分木への言いかえを真っ先に行ってしまって、そこから各要素に深さを割り当てる方法をずっと考えていた。なんとなく見覚えがあるのに全然解けないな……と思いつつソートしてdpなど考えているうちに、急に脈絡なく最小要素2つのマージを繰り返す方法を思いついた。正当性もわからないが、自分の直感や既視感はこれが正しいと強烈に主張しているので、実装。しかしWA。実はそれ以前の考察で $\sum A\lt L$ の場合は最初に使わないパンを切り離してよいという大嘘をついていた。幸い「使わないパンはまとめて切り離す」というところまでは考えていた証明も正しそうなので、 $A_{N+1}=L-\sum A$ と追加して同様のことを行ってみたら通った。

Gは簡単。区間 $[l,r)$ が頂点 $l$ を根とする木になる場合の数を、区間dpで求めてみる。特に工夫しないと区間ごとに $O(N^2)$ のdpで計算する方法が考えられて、とりあえずサンプルは合う。ここで区間ごとのdpをよく見ると、左端を固定したとき右端を伸ばすごとに $O(N)$ で更新するように書けていることがわかる。区間dpで扱う区間の順番を $l$ 降順・ $r$ 昇順に書き直して、 $r$ を動かすときにdp配列を使いまわすようにして $O(N^3)$ になった。

Exは、後から振り返ってみれば惜しいところまで行ったようだ。まず、ネックレスの作り方がそれほど多くないことに気づく。適当にdpして調べてみると、 $N=70$ で最大 $10^{11}$ くらいにしかならないらしい。よって半分全列挙ができる。列挙したものを $A,B$ として、 $B$ をBinaryTrieに持っておく。美しさが $X$ 未満になるようなネックレスの作り方の総数を求めるときは各 $a\in A$ に対し $\#\{b\in B\mid a\oplus b\lt X\}$ を求めればよく、これはBinaryTrieで $O(\log\max B)$ になる。 $X$ を二分探索することで $\log$ が2つついた解法が得られた。案の定TLEして、BinaryTrieの構築だったり探索をベタ書きして高速化を試みたが、結局通らなかった。

7完で58位。Fが遅いのは反省。二分木へ言いかえる前に操作を逆順に見ることができていれば、これがマージテクと全く同じであることに気づけただろう。少なくとも、このことを知ってからはそうとしか見られない。既視感もこの事実からきているはずだ。

コンテスト後にExを改めて考えてみた。コンテスト終了直前は、すべての $a\in A$ に対して毎回BinaryTrieを根から辿るのではなく、ある程度まとめつつ辿ろうとしていた。つまり、そのノードに到達する $A$ の集合を管理するということ。そうやって $X$ 未満になることが確定した個数をカウントする実装をよくよく見ると、 $X$ のbitが立っているときだけカウントが増えていることに気づいた。このことから、BinaryTrieを辿りつつ $X$ の上位bitから立てるか立てないか選ぶことで、カウントした値を二分探索のしきい値ギリギリにできることがわかる。BinaryTrieの $\log$ と二分探索の $\log$ をまとめられて、無事AC。

コードゴルフ。Aは提出スピードで辛くも勝利を掴んだ。13秒。画面の録画を確認したところ問題一覧ページへの遷移に5秒かかっているので、A問題のURLを用意しておけば夢の1桁秒ACが達成できたのかもしれない。B、CはRaku。DでもRakuのBagを使ってみて、TLEしなかったもののRubyのtallyのほうが短くなった。FはPythonのheapqで、負け。A=sorted(A)みたいなことを書いていたのは反省。これはA.sort()である。他は手付かず。

午前1時からTCO22 R2A。Stage3でR4への進出が確定しているはず……であるが、CLISTはあくまで非公式であるから、絶対確実とまでは信頼しきれない。公式からの発表はまだないため、そこそこまともな問題が出るとの評判も聞いたことだし、念のためR2にも参加しておくことにした。

TCO22 Stage3の結果が今日のSRM826で確定していた。僕はSRM825に参加していないのでちょっとひやひやしていたが、それ以外の成績がまあまあ良かったので問題なくRound4への進出が叶った。TCOの予選はcombinedのratedなので、毎年通行料などと言われて評判は良くない。Topcoderのシステムでcombinedにするのはさすがに時代遅れ。ナウなヤングはFull-Feedbackにしか出ない。 https://clist.by/standings/tco22-algorithm-stage-3-28608402/
週記（2022/03/28-2022/04/03） - kotatsugameの日記

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

参加者を見て赤が多いなと思っていたが、combinedだけあって部屋分けで分散し、Roomには僕含め3人しかいなかった。

Easyはタコ足配線の問題だと気付いて問題文をスラスラ読めた。分岐できるものをとりあえず並べて、空いたところに残りの家電を差していく。どこがどれだけ空いているかを適当なコンテナで管理して、使うたびにpopしていくような実装をした。

Medはカス。これをTopCoderのシステムで出題するのは人の心がない。いろいろ方針はあると思うが、自分の解法を説明する。まずleading zeroを作ることによって桁数を減らして、 $Y$ の桁数未満にする。できなければ $Y$ は一桁なので、 $X=1$ としておく。次に $9$ を並べた形を作ってインクリメントすることで桁数を増やし、 $Y$ の桁数と一致させる。特に、一致した時の形が $10$ のべき乗であるようにする。先ほど $X=1$ としたのはこれを満たすためである。あとは最下位桁を弄ってswapを繰り返すことで、基本的には目的の値が得られる。

ただし、 $Y$ の最上位桁以外がすべて $0$ の場合は注意する必要がある。最上位桁を揃えた後swapすると、最下位桁に $1$ が来て $X=Y+1$ となってしまう。これはどうしようもないので、代わりに $Y-1$ を作ってインクリメントすることにする。 $Y$ が $10$ のべき乗の場合は桁数が減ってしまうが、その時は元から $X=Y$ となっている。あとは念のため $Y$ が一桁の場合も別に処理しておいた。

Hardは半分全列挙やるだけ。なぜ900点がつけられているのだろうか。3問提出して25位あたりで、残り時間はMedを $1\le X,Y\le 1000$ で走らせてチェックしていた。WAが大量に表示されて心臓が消し飛びそうになったが、チェッカーの間違いだったことに気づいて一命をとりとめた。

今回はChallengeフェーズも頑張る必要がありそう。しかしMedは読みたくないので、Easyだけ集中的に読んでいた。その甲斐あって、本当に久しぶりに一つ落とすことができた。一つしか口がない分岐について、それを別の分岐と繋ぐために使ってしまったのに、さらに家電を差そうとするコードがあった。そういうものをスキップするときにwhileではなくifを使っていた、というミス。

システスは全部通って、12位まで上がった。レートは2655→2699(+44)。部屋のEasyがもう一つシステス落ちしていて、何かと思って読み直したところ配列外参照らしかった。たとえ気づいていたとしてもこれにChallengeする勇気はない。

日付が変わる前あたりにあったしぐれういさんの配信アーカイブを見た。待機画面のイラストに描かれたロリういの表情がかなり良い。その後、朝まで日記を書いていた。午前7時に布団に入り、そこからなろうを読んで午前9時半就寝。

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

05/22(日)

今日がAHC開始の日だと思っていて、正午にかけておいた目覚ましで起床。慌ててコンテストページを開き、一週間後であったことに気づいた。即座に二度寝。

午後4時半起床。今日は通常のOpenCupがなく、代わりにadminから配られたコンテストにバーチャル参加することになっていた。チームメイトの一人が通常の開始時刻である午後5時に間に合わないらしかったが、バーチャル参加なので開始時間には融通が利く。3人揃ってから開始することにして、チームメイトを待つ間はラノベを読んでいた。

午後6時半からスタート。今日のコンテストタイトルにはPTZW 2022 Day 3（Kazakhstan Contest）と書いてあった。

チームで6完。自分が担当した問題は……ない！なんと5時間で1問も解けなかった。ひっじょ～～～に苦しい。途中から思考がフワフワしてしまい、取り組む問題をコロコロ変えていたのだが、これを1問に絞ったところでどうしようもなかっただろうと断言できるほど手も足も出なかった。このコンテストにはいっそ感動した。わざわざadminが選んで配布したコンテストだけあって、どれも問題文がシンプルで、その上ハチャメチャに難しいわけだ。自分の伸びしろを感じる。しかしこの伸びしろを、僕はおそらく埋められないままICPCを引退するのだろう。

直後、午後11時半からCF #793 div.2。

Aから少し難しい。 $s$ と ${\rm rev}(s)$ を並べ、一文字削除して一致するという条件を線を引くなりして確認してみると、ある範囲の文字がすべて一致している必要があるとわかる。最近ARCで見たことがある気がする。とにかく、 $s$ の中心から同じ文字が連続する範囲を求めればよい。 $|s|$ の偶奇には気を使う必要があった。

A - Remove One Character

Bは $i\ne p_i$ なる $p_i$ 全体のbitwise ANDが答えになる。これでソートできるのは、その値を動かすことで一つ一つ揃えていけることから明らか。逆に、 $p_i$ を動かそうとするときは $X$ を含んでいる必要があるので、 $X$ は動かす必要のある $p_i$ 全体のbitwise ANDに含まれることになる。

Cは同じ値ごとにまとめて、 ${\rm LIS}(a)$ と ${\rm LIS}(a')$ のどちらに含めるか決めていく。同じ値の要素が二つ以上あるなら両方に一つずつ含めることができて、一つしかないなら現状短いほうに含める。一つしかない値が一種類以上あった場合、そのうち一種類を両方に含めることができるので、これを最後に処理する。これまでと同様短いほうを一つ伸ばすとしてよい。

Dは $s$ に含まれる'1'の個数が奇数またはゼロのとき以外必ず構築可能。隣接している頂点をマージしていくことで交差が発生しない。'1'は必ず一個以上存在するので、'0'と'1'が並んでいるところをマージし、新たに'1'であるような頂点と見なす。これを繰り返すと残り全部'1'になって、このとき頂点数が偶数個になっているため、適当な頂点を中心にしてウニグラフを作ればよい。

Eはかなり面倒だった。swap操作を辺と見ると森になっているので、木ごとに解く。葉から順番に揃えてよいという大嘘をついた。 $p=\{2,4,1,3\}$ と $(1,2),(2,3),(3,4)$ が反例。

一度辺（swap）を使うとそこで木が分割され、以降二つの木の間で要素を移動できないので、使える辺を見つけるために適当に根を取って各部分木について足りない要素・余っている要素の集合を管理することにした。これは集合のXORで書け、下から順にマージテクで求められる。 $u\rightarrow v$ という親から子への辺について、 $v$ の部分木に対する集合が $\{p_u,p_v\}$ であればよい。そのように使用可能な辺を見つけたら即座に使い、 $v$ 以下については別の関数で対応する。「使用可能な辺を即座に使った」という条件から、 $v$ 以下の部分木で次に使える辺があるとしたらそれは $p_v$ が書き換わったばかりの $v$ に接続していなければならない、ということを利用して、下りながらどんどん使っていく。

使える辺を探すときは $u$ から出ている辺を全部チェックすればよいと考えていたが、それでは $p_u$ が書き換わり新しく使える辺が出現する場合に対応できないことに気づいた。何とかしてチェックを高速化する必要がある。ここで、求めた集合のサイズが常に $0$ または $2$ であることに気づいた。このことはvalidな順番に並べたswapで後ろから帰納法することで確認できる。そして、再度「即座に使う」条件を用いて、 $v$ の部分木に対する集合はサイズ $2$ かつ一方が必ず $p_v$ であることも言える。なぜなら、 $v$ 以下の辺が使われるのは $u\rightarrow v$ の辺が使われた後であり、 $p_v$ は必ず辺 $u\rightarrow v$ の $u$ 側に行かなければならないからだ。

よって、「 $p_v$ でないほう」をキーにして辺を保存しておくことで、使える辺＝キーが $p_u$ である辺を即座に取得することができるようになった。今、集合のサイズが高々2であることから、各部分木に対する集合を直接保存しておけるため、 $u\rightarrow v$ を使った後 $v$ 以下を揃えるときは、それを参照しつつ木を下っていける。提出したら何とか通った。

Fは見た目こそヤバいものの簡単。コストの条件からより近い頂点に向かって流すと嬉しいとわかる。コストを分割して考えると、 $l\le i\lt r$ について $a_i$ と $a_{i+1}$ の間を通るフローの流量は $\left|\sum_{k=l}^i b_k\right|$ であると言える。よって $S_j=b_1+\dots+b_j$ として、 $(a_{i+1}-a_i)\times|S_i-S_{l-1}|$ の $l\le i\lt r$ に渡る和を求められれば良い。 $S_i\gt S_{l-1}$ の場合と $S_i\lt S_{l-1}$ の場合に分け、 $S$ の降順・昇順に見て、 $a_{i+1}-a_i$ と $(a_{i+1}-a_i)\times S_i$ それぞれの和を管理するセグメント木を用意しておけばよい。実装が間に合わなかったが、システス後に書き上げて提出したら通った。

システスは全部通って5完28位。Eの正当性は日記を書きながらassert等で必死に確認したものであって、コンテスト中は正直半信半疑だった。

TCB47が終了していた。3位。2位とは1pt差で惜しいところ。1位はこのセットでも満点近くを叩き出している。自分もしょうもないWAがなければなあ、とそれなりに悔しさを感じた。

日付が変わったあたりで先生からメールが来ていたのに気づいた。来週火曜日から金曜日は集中講義であるが、それに関連する座談会なるものが月曜日に予定されていて、対面で出席してくださいとのこと。直前に言われるとかなりびっくりしてしまう。インターン先定例会と被ってしまうためオンラインで勘弁してほしい気持ちが強いものの、こういうところでは学業を優先するのが正解なのだろうとわかっている。定例会を休むと伝えておかなければならない。

朝までかけて日記を書いていた。今週もかなり溜めていて、木曜日以降を一息に書き上げた。土日はコンテストが少なく時間に余裕がありそうだなと思っていたのに、実際は何もできていない。月曜日締め切りの課題が2つあることに今更気づいたりもしてしまった。謎の忙しさをずっと感じている。おすすめのなろうを纏められていないし、いくつかまた溜まっている質問への回答もできていない。しばし待たれよ。

2022-05-16

週記（2022/05/09-2022/05/15）

05/09(月)

午後2時前に起床。1時間ほど布団でゴロゴロした後、シャワーを浴びて購買に向かった。この時間帯、すでに購買のパンやおにぎりは売り切れている。仕方なくお菓子とカロリーメイトを買って、帰り道でコンビニに寄り昼食を確保した。

先週金曜日の配信アーカイブを改めて確認していると、チャットリプレイができないことに気づいた。設定を弄った記憶はなかったが、調べてみるとカット編集を行ったアーカイブはそれができないようになってしまうらしい。配信画面にコメントを表示するのはこれの対策という意味もあったのだと知った。昔は設定していたものの、いろいろソフトの連携が必要で面倒になり、最近は止めてしまっていた。

午後4時半からインターン先の定例会。GWを挟んで2週間分の進捗を報告する。といっても先週は帰省先でのんびりしていたので、なんとさらに一週前の火曜日にコーディングしたのが最後の進捗であった。ここまで間が開いてしまうと、考えておいた改善点や実装案も全部頭からすっぽ抜けてしまってかなり効率が悪い。たまにドカッとやるよりは、毎日少しずつでも進めたほうが良さそうだとだんだんわかってきた。最近は1on1の頻度も低い。1on1駆動開発を再開するべきなのかもしれない。

勉強会はgitの操作について。Online Judge Verification Helperを導入していると、ファイル編集を行った後はいつも自動でverifyが行われるのだが、このときタイムスタンプが記録されるようになっている。そのせいで、ローカルの変更を続けざまにpushした場合、間でタイムスタンプが更新されているとローカルが最新でないと言われて怒られてしまう。そのあと何とかして直してもcommit履歴によくわからないものが入ってしまって気に入らないなあと思っていた。同様に怒られる事例が紹介されていたので、謎のcommitを出さない方法を質問したところ、pull時のマージ戦略を適切に設定すればよいと言われた。細かくは理解できていないが、そういう方法があると知れてよかった。調べるとよくある話らしい。

Merge branch 'master' of github.com:kotatsugame/library · kotatsugame/library@f2689ee · GitHub

Merge branch....みたいなコミットログをなくす - by shigemk2

終了後、先週の日記を書き上げた。YouTubeに目を奪われつつ読み返して校閲し、午後10時を回って何とか投稿した。

ABC250Exを通した。ブルーフカ法という話を聞いていたので、考える方針だけは与えられた状態だった。各家から多始点dijkstraをして、別の家にたどり着いたらその間の距離をMSTの辺にする、ということをしたい。しかし実際に実装してみると、ある家から別の家に向かうパス上では当然逆方向からも近づいてくるので、真ん中でぶつかってしまっていた。そこで、ぶつかった瞬間にパスの距離を計算することにした。各頂点について、そこに最も近い家 $u$ とその距離 $d_u$ を記録し、別の家 $v$ からスタートしたパスが距離 $d_v\ge d_u$ でそこにたどり着いたとき、距離 $d_u+d_v$ の $uv$ パスをMSTの候補にする。これはうまくいった。別の家 $w$ と $d_w$ があって $vw$ パスを考えたいとき、 $d_v+d_w\ge d_u+d_v,d_u+d_w$ であるから、いったん $u$ を経由しても損しない。公式解説の別解と近いかと思ったが、それよりユーザ解説にリンクがある記事と全く同じだった。

Submission #31574240 - AtCoder Beginner Contest 250

tokoharuland.hateblo.jp

午前2時までかけて課題を2つ倒した。その後ラノベを読み、午前5時に寝た。

05/10(火)

午後2時起床。しばらくYouTubeやハーメルンで時間を溶かし、午後4時くらいになってようやく布団から出た。

さくらインターネットからメールが来ていた。atgolferのサーバが攻撃の踏み台にされているらしい。

Trafficに覚えがなさ過ぎて顔面蒼白 pic.twitter.com/vj7X7IHGh5
— こたつがめ (@kotatsugame_t) 2022年5月10日

さくらインターネットからメールが来てログ添付されてて、読んだ限りログイン失敗してるから……ええかｗｗｗとか思ってたんだけど、それは僕のサーバーを踏み台にした攻撃を受けたところのログで、僕のサーバーはもうNTRされてたってワケ
— こたつがめ (@kotatsugame_t) 2022年5月10日

特に重要なデータを置いているわけではないので、サーバの中身はもう何も触らずOSを再インストールした。そこから改めてPythonの環境を整え、atgolferを実行できるように。何もかも初期化された後の最初の実行は、現存するすべての最短コードが新たに打ち立てられた扱いとなるため、ツイートしない設定で行う必要がある。--verboseオプションをつけて進捗をしばらく見守っていたのだが、かなり時間がかかるようだった。一度キャッシュが保存されればいくらか高速になるのだろう。

chokudaiさんにリプライを送ってみたところ、今日あーだこーだーが行われること、そこにゲストとして呼んでいただけることが確定した。いよいよである。

午後8時を過ぎたあたりでchokudaiさんがあーだこーだーの予定を忘れていたことが発覚し、今日は配信しないことになった。来週はGW中で自分が帰省しているので、また再来週以降となる。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

学食で夕食を摂り、しばらくラノベを読んで、午後8時から配信の視聴を開始。30分前には入っていてと渡されたZoomリンクを待ちきれず踏むと、僕の準備ができていることをchokudaiさんも認識したらしく、今日のお知らせが少なかったこともあって少し早めに登場することになった。

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

そこからはずっとマシュマロやチャットに寄せられた質問に答えていた。答えたい質問を拾ってと言われても全部答えたくなってしまう。自分に興味を持ってもらえるのは嬉しくて、さらに自分のことについて話すのが好きなこともあって、実に80分も喋っていたらしい。いくらchokudaiさんに許しを得られたとはいえ、普通一時間のあーだこーだーを40分も延長してしまったのは少し反省。ただ喋っている間は本当に楽しかった。同時接続数も安定して200人を超えていて、ありがたい限り。

配信を終え、chokudaiさんに出演料としてアマギフを頂いて、解散。エゴサーチをしながらしばらく余韻に浸っていた。

声が好きだというツイートをいくつも目にしてかなり嬉しかった。以前から配信する度たまにそういう感想を見つけていたのだが、より多くの人の耳に入り、より多くの人に言及されたという事実を確認して、自尊心が非常に高まった。さらに、発言の間を埋める意味のない言葉が少なくて良いというツイートもあった。配信に乗るからには常に意味のある言葉を喋るよう努力すべきであると考えていて、ある程度達成できていたからこういうことを言っていただけたのかなと思う。これも大変嬉しい。一方で、よく整理できていないうちに話し始めてしまうことも多かったと感じているので、うまいことバランスを取れるようになりたい。

さらにいくつかの出来事を述べる。まず父からLINEが来て、受け答えがしっかりしていると褒めてもらえた。次に、配信で言及したこの「kotatsugameの日記」が、新しく記事を出したわけでもないのに一日のアクセス数400を記録した。最後に、マシュマロの画面を配信に直接映しながら新しい質問を確認したのはちょっと不用心であるとの指摘があった。いやはやその通り。度を過ぎればマシュマロ側で弾かれるとは言え、問題のない質問ばかり来ていたのは単に運がよかっただけに思える。

赤になったときにGoogleフォームで質問を受け付けたのだが、これをもう一度やってほしいと要望があったので、用意した。もう一つ、最近おすすめのなろうを教えてほしいという質問を保留しているので、これも含め近くこのブログでちゃんと回答する。しばらくお待ちいただきたい。

午後11時半からCF #790 div.4があったので参加した。2回こどふぉって45分スタートになっていた。

Cまではよい。Dは交点を決めた後、毎回斜めに和を取っても十分間に合う。Eもよい。Fは誤読して大変だった。 $[l,r]$ が数列の区間を表すと思い込んで実装。幅の最大値ではなくそれを達成する $(l,r)$ を出力しなければならないことに気づいて書き換えるなどした後サンプルを実行すると、値が全然違っていてちょっと固まった。読み直して間違いに気づき、ソートしてランレングス圧縮して解いた。この問題は8分もかけてしまった。Gは頂点番号の大きいほうからループを回せばdfsの必要がない。Hは普通。

コンテスト直後の結果は12位。ただ上のほうに怪しいアカウントがいくつかあって、後から確認したら10位に上がっていた。SSRSさんが言語の壁を物ともせずに優勝しているのはすごすぎる。Fの誤読がなかったとしても全然敵わない。

ラノベを1冊読了。「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」2巻。ヒロインが能天気なのはイライラするが、面白い。主人公と現学園最強がバトルするようだったので楽しみにしていた。主人公の油断具合がちょうど良かった。見くびっているのではなく、情報を集めるために手加減していたという描写。主人公は未だに実力を隠したままなので、人目につかないところで戦っていた。まあ2巻から大々的に公開するわけはないか。巻末の次巻予告を見ると、今よりもっと人前に出るような立ち位置になるらしいので、どんな感じに実力が明かされていくのか非常に楽しみである。そのカタルシスを辛抱強く待ちたい。

しばらくYouTubeを見て、日記を書き、午前4時半就寝。

05/11(水)

いつ起きたのか不明。正午あたりにChromeの履歴が残っていて、おそらくそれからYouTubeを見ていたのではないかと思う。二度寝できていなかったはず。

午後2時半くらいに布団から出た。1時間後に健康診断があるので、それに向けて準備する。シャワーを浴びるのすらグダグダしていたので、かなりギリギリの時間に出発することになった。

健康診断は事前の予約制で、10分刻みで定員がしっかり決められていたため、全く待ちもなくスムーズに終了した。身長が記憶より縮んでいて悲しい。実は僕の世代は麻しんワクチンを一回しか接種しておらず、紙に「二回接種していない人は別の医療機関で健康診断してください」と書いてあったのが気になっていたが、ダメもとで聞いてみたら問題なく受けさせてもらえた。助かる。

生協で運よく売れ残っていたおにぎりやパンを買った後、しばらく講義棟を徘徊して、競プロサークルのチラシを探した。

うおおおあった pic.twitter.com/tZ2PGsnu4n
— こたつがめ (@kotatsugame_t) 2022年5月11日

帰ってきて、明日のセミナー発表に向け教科書を読み始めた。DiestelのGraph Theoryという本。結構頻繁に集中を切らしていたので、その時何にかまけていたかを順に記録する。

イラストレーターのrurudoさんもVtuberとして活動されていることを知った。この方の声も良い。

るるどらいおん - YouTube

すとらさんのチュウニズム配信を見ていた。15の理論値を狙い始めて、午後9時過ぎ、ついに「Trrricksters!!」の理論値が出た。見ているこちらまで心臓が痛くなってくるので、作業中に流し見できるようなものではなかった。そのしばらく後に「Killing Rhythm」の最後のタップスライドで散った回があったのだが、こちらは結局出ずに終わった。片方出るだけでも時代が変わったのを感じる。

ラノベを1冊読了。「英雄と賢者の転生婚」。主人公最強＋学園モノで面白かった。クラスメイトのかませ犬みたいな立ち位置のキャラもそこまで嫌らしくなく、実は立派な人間であったという風に描かれていて気持ちが良い。主人公がなぜ強いのかはまだ全く明らかにされていない。後書きを読む限り考えなしなわけではなく、ただ秘密にされているだけのようだが、特に意味なくハチャメチャに強いとしてもそれはそれで面白いかもしれないなと思った。

教科書を読む作業は思うように進まなかった。YouTubeを見てしまったので当たり前か。GW前、先生に「2章までは終わらせてきたいですね」と大言壮語してしまったが、結局1章も終わっていない。午前6時になって、寝坊のリスクを避けるためいったん寝て明日起きてからまたやることにし、就寝。

05/12(木)

午後0時半起床。

1時間ほど頑張って、とりあえず1章の最後まで目を通すことに成功した。証明も自分の中では納得した気になっている。それが正しいかどうかを確かめていないが、もう時間もないので、破綻していないことを祈るしかない。あとはセミナーの準備として今日話す内容を整理する必要がある。しかし持ち時間1時間で何をどう話せばよいのだろう。適当に先頭から命題を書き出してみるも、どう考えても終わらない量になっている。後半まで突入したら教科書をチラチラ見ながらやらせてもらうか、と諦めて、途中で切り上げてYouTubeを見ていた。なぜYouTubeを見ているのか。

家を出て時間通り教室に到着。午後3時からセミナー開始。結論から言うと、今日はもう一人の発表内容が難しくて皆でいろいろ考えていた結果、僕の発表が来週に持ち越しになった。

先々週の予告通り、今週はコンビネータ論理の話。面白そうと言っていたが手を動かすのが楽しいだけであって、命題の証明は大変そうだった。

もう一方の発表は面白かった。面白かったというか次回が面白そうというか。ラムダ計算自体にはあまり触れたことがないが、SKIコンビネータはUnlambdaの経験があるのでそれなりに手を動かしたことがあり、そのパズルみたいな作業が面白かった記憶がある。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

不動点コンビネータの話になった。Unlambdaで再帰関数を実装するのに使った覚えはあるが、今は自力では書けないだろう。まあその仕組みは今日の本題ではない。不動点コンビネータは教科書に載っているもののほかにも大量に（無数に）あり、Wikipediaでも数種類紹介されている。そのうち見た目が面白いものについて、先生にどうなっているか確かめてみよと言われた。

不動点コンビネータ - Wikipedia

L=\abcdefghijklmnopqstuvwxyzr.(r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))とおいて、Y=(L L L L L L L L L L L L L L L L L L L L L L L L L L)とするもの。昔見たときはややこしそうだと思っただけで放置してしまっていた。今日改めて考えてみると、非常に簡単というか、なんだそんなことかとなるような仕組みであることに気づいた。YはLが26個続いた形であり、Lは26個の引数を取る関数であるから、そのうち25個までがLで埋められてY=\r.(r (L L L L L L L L L L L L L L L L L L L L L L L L L L r))=\r.(r (Y r))となる。「this is a fixed point combinator」は文字rが末尾にしか登場しない27文字のものであるということだけが重要だったようだ。当然、変数を束縛する順番を入れ替えればもっと自由にできる。

かなり延びて午後6時半に終了。川内で食事して帰宅。ABC250BがRakuで縮められていた。やっていることはPerlと同じに見える。自分でも書いてみたらさらにいくらか縮んだので、それで取り返した。

火曜日に設置したGoogleフォームにそこそこの数の質問が来ていたので、ちゃんと記事を1本作って回答することにした。午後8時に書き始めて、午前7時まで書いていた。もちろんその間には何度も集中を切らしていたわけであるが。

作業用BGMとして、ずっと花譜というバーチャルシンガーの動画を流していた。もともとVtuberが出したフォニイの歌ってみたをいくつかループ再生していて、オリジナルが実はボカロではない合成音声だということを聞いたので気になって調べ、「可不」のオリジナルである「花譜」にたどり着いたという経路。特徴的な歌い方・掠れたような声にハマった。

朝になって眠くなってきたのでいったん切り上げることにした。午前7時半就寝。

05/13(金)

午後1時くらいに目を覚ました。二度寝するつもりで布団に横たわったままYouTubeを見たりハーメルンを読んだりして、午後5時まで起きていた。その後もう少し眠って午後7時にまた起床。さらにハーメルンを読み続けて、午後8時に1作読了した。「転生したら始祖で第一位とかどういうことですか」。勘違いものの宿命か、主人公が内心でナヨナヨしているのがあまり気に入らなかった。

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

起き上がって食事。腹が減っていたのでパスタを200g茹でた。こういうことをするといつも多すぎて後悔する羽目になっていたが、今日はスルッと食べられた。

pic.twitter.com/pLncbyWFLn
— こたつがめ (@kotatsugame_t) 2022年5月13日

パスタって200gあんねん
— こたつがめ (@kotatsugame_t) 2022年5月13日

少しコードゴルフしたあと、また質問に回答する記事を書いていた。yukicoderは、僕がテスターした問題が2問出題されているが、今週もサボり。先週金曜日に配信画面に映してしまった問題の一部なので、出題の直前にそういうことをしてしまったということでことさら申し訳なくなった。

yukicoderで1問テスターを行った。詳細は当然書けないが、面白い問題だと思った、くらいは言っていいだろう。
週記（2021/10/25-2021/10/31） - kotatsugameの日記

午後11時半から2時間、ECR128に出た。

Aは最大値と最小値を同じにできるかで場合分け。Bは一番上の行にある一番左のロボットを左上に寄せたとき、その下の行で左にはみ出るロボットが存在するか判定。

Cは難しい。さらにコストが2数のMAXではなく和だと誤読して、一度実装までしてしまった。 $c_i$ で $[0,i)$ に存在する'1'の個数を表すとすると、 $i\le j$ に対して $\max(c_{|s|},j-i)-(c_j-c_i)$ がコストとなる。コンテスト中はここから $i$ としては $j-c_{|s|}$ か $0$ だけ考えることにしてもよいとして実装したが、その理由は全くもって正しくなかった。 $j-i\ge c_{|s|}$ のときコストは $(j-c_j)-(i-c_i)$ なのだから、 $-c_i$ ではなく $i-c_i$ のMAXを管理しなければならない。

しかし通った。日記を書いているときに調べてみると、 $j-i=c_{|s|}$ の場合だけチェックすれば正しい答えが得られることが分かった。これはなぜかというと、 $(i,j)$ がそのような条件を満たすとき、 $[i,j)$ の'0'とその外側の'1'の個数が等しくなるからである。そこから $i$ を左右にずらすとどちらかは大きくなるので、コストも大きくなってしまうというわけ。運がよかった。

Dも難しい。まず $a_i=0$ の場所を埋めるときは、高々1つ中途半端になる値を除いてすべて $\pm k$ であるとしても良さそう。最初にその個数を求めておくと、今見ているインデックス、 $+k$ を何個使ったか、中途半端な値を使ったかの3つから現在の位置を計算できる。これでdpすればよいかと思って、左端のMINを達成する方法と右端のMAXを達成する方法をそれぞれ持って実装してみたら、最後のサンプルで落ちてしまった。

考え直して、とりあえず中途半端になる値の位置を決め打ってみることにする。すると残りは $\pm k$ で埋めることになるが、ここで $i$ 番目の移動で最小値を達成する場合を考えると、 $i$ 番目までにできるだけ $-k$ を使って、それ以降は $+k$ を優先的に使うのが最適だと分かった。最初に $+k,\dots,+k,-k,\dots,-k$ と埋めておき、1個ずつずらしていく差分更新を遅延セグメント木で行うことで、 $O(n\log n)$ で全ての場合が計算可能。これで解けた、と思ったがWAが取れず、いったんEに移った。

Eは簡単。2行それぞれ駒が存在するかの4通りを次元に持つdpを左右両方向から行って、合流する地点を全探索すればよい。問題なく通ってDに戻ったところ、 $i$ 番目の移動で最小値ではなく最大値を達成する場合についても考えなければならないことに気づいた。つまり最初の状態が $-k,\dots,-k,+k,\dots,+k$ の場合。書き足してDもAC。残り時間はFを考えて、すべての奇閉路に含まれる辺があればよさそうと思ったが、実装してみても全然検出できずに終わった。遅めの5完で順位は崩壊してしまった。

コンテスト後も記事を書き続け、午前3時半にようやく投稿できた。質問に答えるのは楽しいことではあるが、やはりエネルギーを使う。自分の考えをうまく言語化するのは難しいし、質問を読んで考えたことを全部書くのが良いわけでもない。質問の意図から外れていそうなことは言うか言わないか決める必要があって、もし言うと決めたならせめても論理の流れが自然になるように気を使いたい。とにかく、普段日記を書くよりよほど力を入れて文章を書いたのだった。

kotatsugame.hatenablog.com

そのあとは日記を書いていた。午前7時くらいに切り上げて布団に移動し、ハーメルンの捜索掲示板をいろいろ眺めた後、読み止しにしていた作品を少し読み進め、午前10時前に就寝。

05/14(土)

午後3時起床。しばらく布団でYouTubeを見ていたら、午後4時過ぎに生協の冷凍弁当が配達された。今日は午後6時半からCFがあるので、そのまま起きていることにした。

コンビネータ論理について少し考えていた。Haskellのコードゴルフテクニックにポイントフリースタイルというものがある。abstraction eliminationが、これを機械的に行う方法に見えてきた。しかしさすがにSを多用するわけにはいかない。僕の経験によれば、ポイントフリースタイルは基本的に関数合成演算子.を使って進めていくものだったはずだ。Wikipediaを見ていると、さらにC=\f x y.(f y x)とB=\f g x.(f (g x))を定義する場合もあると見つけた。Cは明らかにflipである。では、Bは(.)ではないだろうか？

まずBの型を考えてみる。 $f:a\rightarrow b$ とすると $g(x):a$ であるから、 $g:c\rightarrow a$ と $x:c$ がわかる。つまりBは $(a\rightarrow b)\rightarrow(c\rightarrow a)\rightarrow c$ である。Hoogleで調べてみると、見事に(.)がヒットした。感動。意味を考えれば当たり前であるが、純粋に形式的に導けたのが嬉しかった。

(a->b)->(c->a)->c->b - Hoogle

しばらく日記を書いて、午後6時半からCF #791 div.2。

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

Aは、まず $n$ が $4$ 以上の偶数である必要がある。後は $n/2$ を $\bmod 2$ と $\bmod 3$ で場合分けすればよい。Bは要素ごとの書き換えタイミングと全体の書き換えタイミングを記録して頑張る。Cは行ごと・列ごとにいくつルークがあるかセグメント木で持っておいて、区間MINでチェックした。setを使う方法をTLで知って、そちらのほうが楽そうだなと思った。Dは二分探索。各頂点についてそこから何回操作できるかをdfsで求める。ループ検出も良しなに。

Eはちょっと大変。回文の中心を決め打ち、長さを伸ばしていくことで、各部分文字列が回文になる場合について「自由に決められる'?'はいくつか」「どの文字が使えなければならないか」を全体 $O(n^2)$ で計算できる。自由に決められる'?'の個数を持っていても扱いづらいので、使える文字の種類数を決め打って場合の数の形に直しておく必要がある。'?'の個数が $O(n)$ 通り、使える文字集合が $2^{17}$ 通りでヤバそうに見えたが、部分文字列を見ているとき同時に計算すると実は $O(n^2)$ 通りであるとわかった。あとは使える文字集合についてゼータ変換。

Fは面白かった。操作は巻き戻すことができるので、何らかの正規形を考えて数え上げる方針を取りたい。操作で作れる数のうち辞書順最小のものを選ぶとよいのではないかと思った。 $n$ 桁から $9$ の位置を決めて、 $8$ の位置を決めて……とすると組み合わせで立式できた気がするが、各数字を使った個数を覚えておく必要があり不可能。桁dpのほうで実現できないか考えてみる。前にある大きな数字とそれより小さい数字を入れ替えられなければよいので、最後に使った数字を持てばよさそう。これを実装するとサンプルは合った。しかし5ケース目でWA。

ランダムケースで試してみると、結構小さいケースでも間違っていることが分かった。 $(u,v)=(0,1),(1,2)$ のケースでWAになることを発見したので、10進法ではなく3進法に制限していろいろ出力してみたところ、 $201$ からより小さい $120$ に変換できるのに別のものとして扱っていることに気づいた。 $0$ と $1$ を入れ替えても小さくならないが、それより先と入れ替える場合も考慮しておく必要があるケース。そこで、最後に使った数字ではなく「今何が来ればより小さいものに変換できるか」の文字集合を持ってdpすることにした。その集合が $U$ の状態で、新たに数字 $d\not\in U$ を追加したとき、 $d$ と交換できる文字集合を $V$ とすると $U\leftarrow\{v\in V\mid v\lt d\}\cup(U\cap V)$ とすればよい。追加した数字と交換した時点で小さくなるか、あるいはそこを乗り越えていけるケース。これで通った。

全完7位。かなり良かった。僕の上に4人も日本人がいてかなり面白かった。

午後9時からABC251に出た。

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) - AtCoder

AはVim。typoで1WA、 $|S|=1$ のケースで足りておらずもう1WA。最悪。BはRubyで書こうとして、先ほどAでWAを吐きまくったのだから慎重にと思い直してC++で実装したのに、うっかりRubyで提出してしまい1ペナ。言語選択ミス、相当久しぶりにやらかした。Cはset。Dは6桁の数を2桁ごとに分割する方法を初手で思いつけた。コンテスト後のTLを見た感じかなり冴えていたらしい。Eは一周回るdpを一か所固定して切り開くやつ。

Fの $T_1$ は水曜日にグラフ理論の教科書で見たばっかり。こういう性質を持つ全域木にはNormal treeという名前がついているらしいが、図を見て一目でDFS木だとわかった。例えばLowLinkはこの性質を利用している。 $T_2$ については $T_1$ と対にして聞かれていることからメタ読みし、DFS木から連想してBFS木を考えてみるとピッタリ当てはまった。

Gで大炎上。多角形による点の包含判定は、右に半直線を伸ばして辺と交差した回数を数える形でライブラリ化されていた。凸でない多角形に対応するためこのような実装になっていることに気づかず、しばらくこの方針で考えていた。他に、逆にクエリの点をずらした多角形が $P$ に内包されるかチェックするようなことも考えるも、いずれも現実的なオーダーにならない。多角形の共通部分を計算するしかないのかと思っていろいろ検索すると、平面走査して特定の $X$ 座標における多角形の辺の $Y$ 座標を管理する方法を見つけた。これを使えば共通部分を計算しなくても判定できるかもしれない。つまり、 $M$ 個の多角形が直線 $x=a_i$ とそれぞれ2点で交わり、その間に $b_i$ が位置しているかをチェックする。多角形の上側だけ考えて実装すれば、下側は符号反転で対応できる。その上側について、辺を線分とみなせばCHTで解ける。さらに今凸多角形を考えているので、辺ではなく直線を考えてもよいということに気づいた。これを最初に気づけていれば……。

うしさんのライブラリを窃盗し、 $O(NM)$ 個の直線をCHTに追加してみると、まずコンパイルが通らなかった。どうやらテンプレート引数に浮動小数点数が渡せないらしい。ライブラリ自体を文字列置換で書き換えた。ACLのセグメント木の単位元を無引数関数で受け取る実装は、こういうケースを想定していたのかもしれないと思った。さらに、ライブラリで一様に型 $T$ となっている値のうち一部は整数型でないとまずいことにも気づいた。幸い、今回値を取得する点 $x$ は常に整数なので、これも何とかなる。そのほかいろいろ間違いがあったのを修正して残り80秒で投げると、1ケースだけ落ちてしまった。浮動小数点数の比較にEPSを使うようにして残り14秒で投げなおし、念のため別のEPSも試そうとしたらコンテスト終了。祈りながら結果を確認すると……AC！かなり嬉しかった。

7完81位。ギリギリまで粘って通せたため気分はよいが、全体として見れば愚か者の一言に尽きる。

間20分ですぐGCJ R2。コードゴルフは後回しになった。

https://codingcompetitions.withgoogle.com/codejam/round/00000000008778ec

Aは移動できるマスの差分を観察する。 $N=5$ の図を見ると、一周目から二周目へは $(+15,+13,+11,+9)$ 、二周目から三周目へは $(+7,+5,+3,+1)$ となっていることがわかる。また、例えば $+11$ を使った次は $+7,+5$ は使えないこともわかる。通常の移動では常に $+1$ なのだから、そこからの差分はすべて偶数。つまり、まず $N^2-1-K$ は偶数である必要がある。これがチェックできたら、あとは全部 $2$ で割って、 $(N^2-1-K)/2$ を $(+7,+6,+5,+4)$ 、 $(+3,+2,+1,+0)$ でうまく構築できないか考える。

実は貪欲でよい。貪欲に取ると最大で $+7+3$ が作れて、これはそれぞれの四つ組から一つずつしか取れないことを考えれば確かに最大。それ以下の数が全部作れると仮定して、四つ組の個数で帰納法を回すことで証明できる。実装の際は、差分を達成できるマスを求めておく必要がある。一周目から二周目のマスだけ手で埋め込んだら残りは規則的に決めていける。このとき埋め込むマスを間違えて1WAしつつ、なんとか通した。

Bは難しい。まずround関数とsqrt関数の組み合わせでどのような値になるのか観察する。roundを表す数学記号が思いつかないのでこうやって文字で書くことになってしまった。ある整数 $X\gt 0$ をsqrtしてroundすると、値が $Y\gt 0$ になったとしよう。このとき $Y-1/2\lt\sqrt X\le Y+1/2$ である。辺々2乗して $Y^2-Y+1/4\lt X\le Y^2+Y+1/4$ 。 $X$ として整数だけ考えているので、 $Y(Y-1)\lt X\le Y(Y+1)$ と書き直せた。このような $Y$ は確かにただ一つ定まる。

この式を使って、draw_circle_perimeterで塗られるマスは必ずdraw_circle_filledでも塗られることが確かめられた。 $x=0$ または $y=0$ の点はどちらでも必ず塗られるので、第一象限だけで数えて4倍することにする。 $1\le x,y\le R$ かつ $x^2+y^2\le R^2+R$ なる $(x,y)$ それぞれについてdraw_circle_perimeterで塗られるかチェックしたい。これは $x^2+y(y-1)\lt r^2\le x^2+y(y+1)$ または $y^2+x(x-1)\lt r^2\le y^2+x(x+1)$ を満たす整数 $r$ が存在するか確かめることで行える。式が2本あるのがつらいが、よく見ると $x\le y$ の場合前者だけでチェックしてよいことがわかる。

さて、ここで $x$ を固定して、 $r^2$ の分布と $y(y+1)$ の分布を考えよう。 $y(y+1)$ のほうが密に存在し、それを $+x^2$ で $r^2$ が疎になるほうへずらすので、 $x^2+y(y-1)\lt r^2\le x^2+y(y+1)$ を満たす解 $r$ は常に高々一つになる。つまり、チェックしたい $y$ の個数と解になり得る $r$ の個数をそれぞれ求め、引くことで、解が存在しない $y$ の個数を一息に求めることができる。 $x=y$ の場合を丁寧にケアして実装し、実験コードとしばらく比較して小さいケースで一致していることを確かめ、提出した。

Cも難しい。それぞれの子供について、1番目のお菓子以下の距離にあるお菓子を列挙し、辺を張ってみる。最も近いお菓子しか取れないという条件をなくせば二部マッチングになる。そうやってマッチングしたペアが、実際に残っている中で最も近いものならそれでよい。どの子供もそうでない場合、適当にマッチングを組み替えられるのではないかと考えた。ここにユークリッド距離を使うという問題設定が効くのだと思ってしばらく考えてみたが、まったくうまくいかない。純粋にグラフ的なアプローチを取るしかなさそう。

今、うれしい点として、残っているすべての子供についてマッチング先のお菓子より近くに別のお菓子が存在している、つまり二部マッチングを計算したグラフで子供から出ている辺は常に2本以上存在するということがある。これなら適当にdfsすれば交互閉路が見つかりそう。それっぽく実装するとWAだったので、もうちょっと丁寧に考えてみる。まず、ある子供のマッチング先を最も近いお菓子に変えようとしてみる。当然そのお菓子にはマッチングしている相手がいるので、今度はその子供に注目して最初からやり直す。こうして子供を辿っていくと行き止まりにはならないため、いつか必ずループする。ループの始点は最初に見た子供ではないかもしれないが、とにかくそのループに入っている子供のマッチング先を一斉に最も近いお菓子に変えても破綻しないことになる。実装を頑張って何とか通った。

残り15分ちょっとしかない。Dのsmallを通せないか頑張ってみる。とりあえず正の位置にあるビーチボールだけで考えてよい。 $0$ と $1$ で分けてソートしてみると、わざわざ交差した感じでペアにする必要はない。つまり今どのボールまで回収したかを持つ $O(N^2)$ のdpができて、これはsmallなら通る制約になっている。ここまでの考察がトントン拍子に進んで、実装もシンプルだったためすぐ書いて提出。何とか通せた。

Hiddenのジャッジ結果が出て、ABCdで29位。かなり良い順位。途中800位台で少し焦っていたが、Hiddenまで通していた人が思っていたより少なかったようだ。自分に自信を持ってもっとどっしり構えていたい。

ABCのコードゴルフに戻る。Aは速度でも長さでも負けていてボロボロ。BはOctaveで書いてみたら縮んだ。CはシンプルなAWKが最短になっていて、Vimで粘ってみたが最短タイから縮まなかった。Dは $i=0\dots 299$ に対して $\lfloor i/3+1\rfloor\times 100^{(i\bmod 3)}$ を出力するのが天才的。EはRuby。以降は手付かず。

その後朝まで日記を書き、布団でしばらくハーメルンを読んで、午前9時くらいに寝落ちした。

05/15(日)

午後3時半起床。ハーメルンを読み続けて、午後5時半に1作読了。「Vの者！～挨拶はこんばん山月！～」。

AtCoder Regular Contest 140 - AtCoder

昨年末から読んでいた。かなり面白かった記憶だけ残っていて、どこがどう良かったのかはあいまい。普段の面白おかしい配信の様子とシリアスなシーンの寒暖差がかなり大きくて大変だった。ただどの章もハッピーエンドで終わってくれたので一安心。キャラクターの元ネタは、僕が分かったものは全部現実の芸能人・Vtuberだったので、そのあたり詳しければまた違った読み方ができたのだろうか。起こった出来事のいくつかに他のVtuber小説で見覚えがあったので、それも実は現実のVtuber界隈で起こったことなのかもしれない。

布団から出てずっと日記を書いていた。午後9時からARC。

Aは $|S|$ を周期的にすることを目指す。周期を全探索。BはA...ARC...Cという部分文字列に分割して、奇数回目の操作は長さを $2$ 減らすことになるので長いものから、偶数回目の操作は部分文字列を1つ削除することになるので短いものから優先的に使う。Cは $\{\dots,2,N-1,1,N\}$ か $\{\dots,N-1,2,N,1\}$ が嬉しさ $N-1$ と最大で、これを達成できない場合は $\{1,\dots,N\}\setminus\{X\}$ で同様の列を作って先頭に $X$ を置くと、嬉しさを $1$ だけ減らした状態にできる。ここまで20分弱。

残り100分はずっとDを考えていた。全然解けなかった。連結成分を作らない辺の本数を数えることと、各連結成分で最も小さい頂点番号の頂点を数え上げることを考えて、どちらもうまくいかず苦しんでいた。終盤になって、各連結成分がなもりグラフになること、さらに最初から連結になっている成分ごとに行き先が決まっていない頂点が高々1個であることに気づいて、その成分に分割した後ループの個数を数えるdpを書こうとしたが、値が全く合わずに終了。

3完171位。3完最速は昨日に引き続き愚か者。本当に助けてほしい。

午後11時半からCodeChefでMay Lunchtime 2022。

https://www.codechef.com/LTIME108A

ANDEQは残る値が必ず全体のbitwise ANDになる。この値になるように左からまとめていくと、達成した瞬間そこで切っても良いことがわかる。最後だけ達成できない可能性があるので、ちゃんと検出する。

B01Tは最初の部分点が大きなヒントになった。 $u$ の部分木について $1$ の個数から $0$ の個数を引いた値を $c_u$ とおくと、 $c_1/2=-\sum_v c_v$ が満たされればよいことになる。 $N$ が偶数なので、 $c_1/2$ は必ず整数になる。ここで最初の部分点は直線グラフだから $c_1/2=-c_v$ を満たす $v$ を見つける問題になるが、木をどんどん降りていくと $c_v$ は $\pm 1$ ずつ、つまり十分連続的に変化するので、どこかで必ず見つかるという寸法。そしてこれは、木の頂点をDFS順に並べることでも同じことが行える。

RERNGは最後のステップに時間がかかった。 $P_i\lt P_{i+1}$ を分割する必要があるのは、 $L\le j\le R$ であって $P_i\lt P_j\lt P_{i+1}$ なる $j$ が存在する場合であるとわかる。いったん $j$ の制限をなくして左右からそれぞれ最も近いインデックスを探し、 $l_i,r_i$ と名前をつけておくと、クエリに対する答えが $\#\{L\le i\lt R\mid L\le l_i\lor r_i\le R\}+1$ と書ける。条件を反転して $R-L-\#\{L\le i\lt R\mid l_i\lt L\land R\lt r_i\}+1$ を求める。

$R=1\dots N$ の順番に求める。 $i\lt R$ かつ $R\lt r_i$ であるようなインデックスの集合は管理できるので、それらから $l_i\lt L\le i$ なるものの個数を数えることになる。 $l_i\lt L$ だけ見ると、区間に対してある数未満の値をカウントするデータ構造が思い浮かぶが、僕が持っているものは静的である必要があったため使えない。しばらく考えて、遅延セグメント木の $(l_i,i]$ に $1$ 加算しておけば実現できることに気づいた。これで実装。加算する区間の右端が $i$ であることに気づかずに1WAしつつ、通った。

PWMULは3つ目の部分点まで。 $A$ の位数が小さければ愚直に計算できる。大きければすぐ見つかると信じて答えを全探索し、BSGS。このときBaby StepとGiant Stepのどちらかはテーブルを前計算できるので、そちらをunordered_setに持っておくこと、またもう片方のサイズを小さめにすることで高速化ができる。4つ目の部分点も通らないかと定数をいろいろ変えて投げていたが、全然ダメだった。BSGは1つ目の部分点まで。Aliceは最も左にある $0$ か最も右にある $1$ を、それと最も近いものとペアにするのが最適。Bobはその2つをペアにするのが最適。よって $0$ のインデックスと $1$ のインデックスをそれぞれ集め、列の左右からどこまで使ったかを持って $O(|S|^4)$ のメモ化再帰ができる。

375点で10位。2628→2708(+80)。

午前5時まで日記を書いていた。平日頑張って書き進めても、週末に5個もコンテストに出るともう追いつかなくなってしまう。一段落ついたところでインターン先勉強会の準備を始めた。なんと明日（狭義には今日）の勉強会は僕が担当なのであった。前々からわかっていたのにちっとも準備せずのんびりしていたツケを必死に支払うことに。一応何について話すかは考えてあったので、ガリガリスライドを作っていた。

午前10時になってひとまず完成。いったん寝て、起きて時間があればもうちょっと確認しておきたい、というくらいの出来。そこから1時間ほどかけてこの日記の校閲をした。

2022-05-14

kotatsugameに質問 Part2

kotatsugame.hatenablog.com

嬉しいことにまた質問を受け付けてくれという要望があったので、Part2を開催します。Part1は赤になったときの記事をご覧ください。

以下のGoogleフォームはまだしばらく開けておく予定なので、これからもドシドシご投稿ください。

forms.gle

質問

次回の小説の構想はありますか

最短経路問題で何か書こうと思っているのですが、話が全然組み立てられません。起承転結の「転」の部分が思いつかないとどうしようもない感じがしますね。

大学卒業して院にいったんですか？

そうです。そもそも飛び級制度が早期「卒業」であることを抜きにしても、特に何かスキップしたりはしていません。

学業と競プロはどのように両立していますか

両立していません！……と言いたいところですが、ストレートで卒業できたのでそれなりに両立できていたほうなのでしょうか。課題は提出しましたし、テスト前にちゃんと勉強していた記憶もあります。逆にそれ以外、予習復習などの継続的な勉強はしなかったので、そのように必要最低限のことしかしないようにするというのは一つの方法かと思います。もちろん成績は落ちるはずなので、どちらにどれだけ重きを置くかですね。と、さもいろいろ考えていたように言っておいて、実際のところは自分がそのとき一番やりたいことを破綻しない限り貪欲にやっていただけかもしれません。

「質問などなんでも」って書いてあるの何個ありましたか？

1つです。と思っていたらこの記事の下のほうで2つ目がありました。

読むラノベ / ネット小説はどのように選んでいますか？

ラノベはタイトルとあらすじですね。まずタイトルを見て、気になったもののあらすじを確認して買うものを決めます。買ったものを全部読めているわけではないためしばらく机に積まれるのですが、そこからその時一番気になっているものを選んで読んでいます。

ラノベのパッケージングとして表紙イラストは重要な位置を占めています。しかしこれだけを頼りにラノベを購入するのはあまり良くありませんでした。なぜなら、当然ながら、文章の好き嫌いとイラストの好き嫌いには一切関係がないからです。

ネット小説は、TLに流れてきたり、読んでいる作品ページの下のほうでレコメンドされたものから選ぶ場合と、自分でタグやキーワードで検索する場合があります。後者はハーメルンの捜索掲示板で行うこともあります。どちらにしても、それぞれの作品はあらすじと最初数話を確認して読み続けるかどうか決めます。

例えば東方Project二次創作の古代スタートものが読みたいとか、金融知識を縦横無尽に振るう話が読みたいとか、気分は細かく変化すると思いますが、そういうニーズに対応するためには検索機能が非常に有効です。またさらに、一つ好みの作品を見つけた場合に、そのタイトルで検索することで似たような作品を探すこともよく行います。捜索掲示板でそれを行い作品がどういう文脈で紹介されているかチェックすることは、自分が一体何に心惹かれたのか言語化する助けになります。そこで得たキーワードで検索をかけるのもお勧めです。

こたつがめさん大好きです！もっと動画出してください！

ありがとうございます！動画、出したいんですけどね……。画面キャプチャの撮り溜めはあるのですが、それを編集する気力がない状態です。なぜかちっとも手が出なくて自分でも驚いています。もうしばらくお待ちください。

こたつがめさんは'''糧'''という単語を使いがちだと思うんですけど、うちの広辞苑を見てもないです。こたつがめさんの広辞苑には載っていますか？

糧、を引用符で強調しているだけです。当然広辞苑に載っています。食べ物のことをちょっと捻った言い方をしたくて使っているだけなので、普通に辞書的意味を当てはめていただければと思います。

東北大学にちょっと興味を持っている高校生なのですが、東北大学での学生生活はどのような感じでしたか？また、競プロerからの視点で大学の良い点や嬉しい点なども教えてください！

学生生活は非常に良かったですね。仙台市は、駅前は十分発展した都会ですが、そこから少し離れればごみごみしていない住宅街が広がるという点で、住みやすさと便利さを両立した街だと感じます。

競プロerからの視点としては、競プロが盛んな大学であるのが良い点だと考えられます。サークルには黄色の方もたくさん在籍しており、大学として年々強くなっていると思います。同じ趣味を持つ仲間がたくさんいて、ICPCにチームを組んで出るのもサークルを経由すれば簡単でしょう。一応、予選突破がだんだん難しくなるだろうことは注意しておきます。

あーだこーだーの切り抜きお願いします

しません。僕から見て切り抜くほど特徴的なシーンはないからです。……しかし考えてみると、僕は80分も喋っていたんですね。これは確かにアーカイブを見るのも大変です。

大学院での目標を教えてください

心身の健康です。特に精神的に調子を崩す話をよく聞くので、ちょっと怖がっています。

【睡眠用ではない】耳が完治したのでASMRやる【怒らないで】【Not suimin】 - YouTube

いいですね。前半は思ったより良かったです。後半はごちゃごちゃしていてよくわかりませんでした。しぐれういさんは配信で普通に喋っている声も耳に心地よいと感じているので、わざわざASMRである必要はないかなと思いました。

なんでフォロバしてくれるんですか？

僕のツイッターの運用方針がいわゆるフォロバ100%だからです。なので、申し訳ないのですが、フォロバしたからと言って個人をちゃんと認識しているわけではありません。

最終的にInstagramはログインできたの？

一度もログインできていません。指定された番号を手書きした紙とともに顔面を写した、まるで犯罪者みたいな写真をメールで送信しましたが、音沙汰なしです。

ブラックサンダーの良いところを教えてください

ちょうどいいサイズと価格、また箱買いが簡単なところです。

streakを維持することはレートに寄与しますか

寄与しないと考えています。自分の好きなペースで解いていくのが一番です。熱中した結果として維持されていることもあるでしょうが、目標に据えるのはお勧めしません。なぜかというと、いずれ無理が出てくるだろうからです。別のことに熱中したりして忙しい場合はすっぱりお休みするのが健全でしょう。その結果競プロから心が離れていくのなら、残酷ですがそれまでの話だったというだけです。

今年のICPCはどんな感じですか？

チームも含め、何も決まっていません。

お尻のほうを使ったことはありますか？

ありません。

学食での1回の食事でサラダと納豆をそれぞれ最大で何個まで頼んだことありますか？

スマホのアルバムを見返してきました。まず、納豆は二パックです。これは結構頻繁に注文しています。サラダはおそらく四つで、これを副菜という範囲に広げると九つ食べたときの写真が見つかりました。

ドレッシング四種制覇 pic.twitter.com/yMIB5GZvUf
— こたつがめ (@kotatsugame_t) 2018年6月26日

1,122 JPY
名前が写り込んでいたのでツイートし直しです pic.twitter.com/Ac0yfTCScv
— こたつがめ (@kotatsugame_t) 2018年5月21日

「眠らないビル」の更新を待ってます。

ありがとうございます。ただ、一番上の質問でも答えたように、書こうと思ってもなかなか書けない状態にあります。別の話を書くとして「眠らないビル」のキャラを使いまわすかも迷いどころです。気長にお待ちください……。

文章を読むときに頭の中で声が聞こえますか？（聞こえる人と聞こえない人がいます）

この質問、認知特性を診断するテストでよく聞かれますよね。僕はそのたびに悩んでいるのですが、この質問を目にしてから文章を読もうとしても雑念が入ってしまい、なかなかよくわかりません。とりあえず、「文章を集中して読むときは聞こえる」と答えておきます。ネット小説は気楽に読むので聞こえていないはずで、ラノベなど物理書籍になると聞こえてくるときもある、はずです。

日本語の文章を書くときもVimを使ってますか？

レポートで $\TeX$ を打つときはVimです。それ以外だとTeraPadを使っています。「眠らないビル」もこれで書きました。

「父も配信を見てくれて、受け答えがしっかりしていたと褒めて貰えました☻」とおっしゃってましたが、父親にはこたつがめもTwitterアカウントバレてるのでしょうか？致したとかツイートしてて大丈夫なんですか？

バレているというより、自分のTwitterアカウントはこれであるとこちらから伝えた覚えがあります。「致した」については聞かないでほしいとお願いしてあります。僕はそれで触れられなければ大丈夫で、話題にしない以上父がどう思っているかは気にしてもしょうがないと考えています。

アニメやマンガよりはラノベ(Web小説含む)派ですか？ラノベを読むと問題文の把握が速くなったりしますか？

前半については、明確にその通りです。むしろ意識的にアニメや漫画を避けています。これ以上物語に手を出す余裕はないはずだと考えているからです。後半について、問題文の把握には関係ないと思います。より一般に、いわゆる国語力は競プロの問題文の読解力と関係ない気がしていて、これを鍛えるには競プロの問題にいろいろ触れるのがいいでしょう。

精進にあたって書籍は必要だと思いますか？

今時はネットに大量の記事があるので、必ずしも必要とは言い切れないのかなと思います。ただ、買って損はないです。書籍の最初から最後まで目を通すことで体系的に知識を得る、あるいはそこまで至らなくてもどんな問題を解くアルゴリズムがあるか知ることは重要です。また蟻本については、たまに（第2版の）ページ数を使って特定のアルゴリズムに言及されることがあります。

日記を読んでみたいのですが，どこから読むのが良いですか．

興味を持っていただきありがとうございます！日記を読み物として捉えてみると、別に僕の日常は山あり谷ありというわけでもないため、どこを読んでも面白さは大して変わりないのかなと思います。そのため、とりあえずリアルタイム性を重視して最近のものを読むとして、そこから引用の形でリンクされている過去の日記（そういう引用は結構な頻度で使っています）を読んでみるとかは考えられます。または同じイベント、例えばコンテストに僕とあなたが同時に参加していたなら、その日のものを読むのもありかもしれません。

板タブの次に買おうと思ってるデバイスはありますか？

今のところPC環境には満足しています。タブレット端末にはちょっと興味がありますね。

ベランダさんの作品のおすすめはなんですか

「黒髪少女の羞恥快楽地獄」/「ベランダ」のシリーズ [pixiv]

アマギフの使い道

毎月ペットボトルの爽健美茶を1箱買っていて、それの支払いで2000円弱ずつ消えています。また過去にはモニタを買うのにも使いました。

ハンドルネームの由来

TwitterのIDの末尾の_t というのはsize_tのように構造体であることを明示するためですか違います。これは僕の苗字のイニシャルです。
AtCoder 赤色になりました - kotatsugameの日記

名前はこたつ亀ですか？こたつ game ですか？亀です。こたつむりという言葉のシノニムのつもりです。こたつむりはあまりに一般的すぎるので、このように変えました。
AtCoder 赤色になりました - kotatsugameの日記

大学院後の進路

大学院の後は企業への就職です。では大学院をどこで終えるのかについて、博士課程は……どうでしょう。今のところなくはない、くらいの気持ちでいます。

タイピング早すぎませんか？寿司打の記録と練習方法を聞きたいです。自分は寿司打高級コース+3000円前後くらいしか出せません（泣）

高級コースでプラスになるのは十分速い部類に入るはずですね。上には上がいるということで、僕より速い人も界隈では珍しくなさそうです。寿司打のプレイを続けると単語に慣れて速度は出るのかもしれません。「生麦生米生卵」を時間内にタイプできますか？僕はなかなか苦労しましたが、覚えると安定します。また、少し速度を落としてでもミスを減らせば、却ってスコアが上がることが知られています。

他に僕が意識していることとして、FキーやJキーを積極的に使うこと、記号キーを確実に押せるようにすること、「ん」をタイプするのに不必要な連打を減らすことが挙げられます。一番最後は難しいですが、画面のローマ字表示を参考にすると多少やりやすくなるように感じます。

コードゴルファーで「この人すごいな」と思った人はいますか？

tails（Atcoder ID：saito_ta）さんを挙げます。AtCoderにはほとんど提出されないため競い合わせていただいた経験は少ないですが、そのいずれも隙のないコードで、当時感服していました。他の人と競い合って負けてしまった問題にも、いくつもすごいなと思う最短コードがあります。ただ、すごいと思ったコードではなく人ということなので、この方を挙げました。

sgruiのえっち絵で好きなやつ教えて下さい

Pixivでフォローしている絵師さんが描かれたのを目にすることはありますが、特に好きではありませんでした。性欲の対象になっていないと思います。

質問などなんでも

「質問などなんでも」カウント+1

競プロを始めたのはいつですか？競プロ以外でプログラミングすることはありますか？

競プロを始めたのは、あーだこーだーでも答えた通り2016年5月、高校2年生のときです。競プロ以外のプログラミングも多少します。長期インターンで業務としてコーディングしていますが、稼働時間が短めなので多少という言い方になっています。あとは、自分でクローラを作って最短コードをクロールしているのも競プロ以外にカウントされるでしょうか。

日記やTwitterで「シュッと」という表現（「シュッと解けた」など）をよく使っている印象があるのですが、この表現をいつから使うようになったかなど覚えていたら教えてください（個人的にほかではあまり聞かない表現なので気になりました）。

それぞれ検索して探してみました。Twitterのほうはこのころから時たま出てきていたようです。そちらにしても日記にしてもそれほど頻度は高くないので、あまり聞かない表現と感じたからこそ印象に残ったということなのでしょうか。どういう経緯で使うようになったかはよく覚えていません。ニュアンスは伝わるかと思いますが、それを擬音で表現しようとした場合、自分の中では「シュッ」が該当しました。また、検索すると大阪弁に存在するという話がヒットするため、その地域の方と交流する中でうつったのかもしれません。

東大生はコミケにシュッと行けるけど東北大生は羽生結弦選手のパレードにシュッと行ける
— こたつがめ (@kotatsugame_t) 2018年4月17日

Cはそこそこびっくりしたがシュッと解けた。
週記（2021/01/11-2021/01/17） - kotatsugameの日記

ホロぐらってやつ、オススメですhttps://www.youtube.com/hashtag/%E3%83%9B%E3%83%AD%E3%81%90%E3%82%89

別にホロライブが好きなわけではないんだよな……と言いながらいくつか見ましたが思ったより面白かったです。ありがとうございます。

これ好きなので是非感想をください！【みっころね24】みこち、ゲラを止められなくなる【ホロライブ切り抜き】 - YouTube

さっきのやつなんですが、こっちを観てください【神回】医者からyoutuberになろうとする父から始まるシャクレ家族の家庭崩壊ｗ【ホロライブ切り抜き/みっころね24/天音かなた/常闇トワ/姫森ルーナ/大神ミオ/戌神ころね/さくらみこ】 - YouTube

誰もよく知らないんですがそれでも面白かったです。パパが強硬に退職を主張する部分が特に好きでした。ありがとうございます。

銅冠、銀冠、金冠、鉑冠になる予定はありますか？

銅冠にはなりたいなと思っています。それより上は……正直難しいでしょう。

英語の問題文を読む時に、翻訳機(deeplなど)を使っていますか？

単語ごとの意味はよく検索していますが、翻訳機に文章を投げることはしません。競プロの問題文はとにかく正確に読まなければなりませんから、単語・熟語の意味はともかく構文の認識は自分で行うべきだと考えています。特にDeepLはいくら自然な日本語に翻訳されるとは言っても、途中の文章を脱落させるケースがあると聞いていますから、競プロで使うべきではないはずです。少し上で競プロの問題文の読解力について触れましたが、多く読むことで鍛えられるのは英語の問題文についても同じです。頻出する表現に慣れれば格段に読みやすくなるのではないでしょうか。

あーだこーだーだと変な質問できなかったので Google フォームによる質問感謝します！！！！！

どういたしまして。答える側としてもこうやって質問がたくさん来てくれると嬉しいです。質問する側に立ってみると、その匿名性が重要なのかなと考えて、それで僕の作ったフォームは回答者の名前を聞かない構造になっています。マシュマロも匿名性という点では同じですが、こちらの感覚が配信で答えるのと違うこと同様、質問者にとっても違う感触なのだろうなと思います。

Chromeのブックマーク管理についてお願いします（配信で写っていたのを見て綺麗だなーと思いました）

これ、特別なことをしているつもりはないので、何をどう答えるかかなり悩みました。ブックマークのフォルダ分けについてよく使うところを大まかに説明すると、競プロのコンテストサイトやそれに関するデータを表示するサイトをまとめたフォルダと、コーディングで参考にしたサイト・ページをまとめたフォルダを用意してあります。後者はさらに、特別頻繁にアクセスするものを除き、言語ごとにサブフォルダでまとめてあります。

覚えておきたいコードゴルフのテクをまとめるため、そのテクが出現した提出の詳細ページをブックマークしているのですが、これが調べてみたら300個以上ありました。なのでサブフォルダでもまとめておく必要があったわけです。そうやってフォルダ分けされて階層的にずらっと表示されると確かに綺麗に見えますね。この質問はそういうことなのでしょうか。

2022-05-09

週記（2022/05/02-2022/05/08）

05/02(月)

先週の週記を投稿してからの話。徹夜を決めた。ついでに新幹線の予定も早めることにしたので、時間的な余裕はすでにほぼなく、そそくさと出発。高校生の通学ラッシュと重なってしまい、駅から吐き出されてくる人々に逆らって歩くことになった。

仙台駅に着いて、朝食のパンをコンビニで購入して乗車。さすが朝早めの新幹線、さらに仙台駅始発ということもあってか、中はガラガラだった。

車内ではラノベを読んでいた。ふとTLを見ると、日曜日のOpenCup-Aが怪しいという話が流れてきた。詳しくは先週の週記に追記しておいた。解説のリンクをまだ手に入れられていないため、想定解がどのようになっているのかわからない。問題文に縦と横にしか切れないという注釈を書き忘れているのだろうと思うが……。

2022/05/04追記：Aは自明ではない。より正確に書けば、H×WH×Wのシートから同じ大きさの正方形をKK個切り出すとき、正方形の1辺の長さは最大いくらにできるか？という問題。特にH=WH=Wの場合、有名な未解決問題になる。問題文のどこを探してもそのようなことは書かれていないが、縦と横にしか切れないという制限を勝手に設けて解くと上に書いたようになる。
週記（2022/04/25-2022/05/01） - kotatsugameの日記

午前10時過ぎ、大宮に到着。このときもまだ車内はガラガラだった。僕が乗った先頭車両には他に1人しかいなかった。乗り換え待ちが40分程度あるので、一旦改札を出て駅前のゲーセンへ行き、1クレだけプレイ。素手なので軍手をつけている普段と感覚が違い、全然精度が取れなかった。

すぐ戻ってきてホームに上がると、今度はかなり人が多いようだった。列に並んでしばらく待ち、乗車。新幹線を外から見たときはかなり混んでいるように感じたが、何人か降りたのか多少座れる余地はあった。10分前から並んでいたこともあり、無事座ることに成功した。

車内ではカクヨムを1作読了。「絶対に目を付けられてはいけないVtuberに見つかってしまった」。正直あまり好きではなかった。登録者数1万人の主人公が登録者数100万人のヒロインに見つかってグイグイ迫られる、という展開に面白さよりも先に恐怖が来た。ギャグ時空なのでそういうことはないとわかっていても、めちゃくちゃ炎上しそうな展開に見えてしまう。主人公が弱気なのも好みではない。

外務省海外安全ホームページ｜ゴルゴ１３の中堅・中小企業向け海外安全対策マニュアル

ちょうど読み終わったあたりで黒部宇奈月温泉駅に到着。そこから父の車に乗り、食事しつつ富山市に向かった。どうせなら最初から富山駅で降りれば良かった。

パスポートセンターでパスポートの受け取り。3月末に代理申請をしてもらっていたのだった。受け取りの際に生まれ年の干支を聞かれ、答えに窮してしばらく上を向いて黙っていたら、係の人から「卯年ですか？」と助け舟を出された。そういうのでもアリなのか。

富山県のパスポートセンターに電話して代理申請について聞いてみた。こちらは僕が6か月以内に受け取りに行くことも含めて問題なく行えそうだったので、必要な書類を聞いておいて、再度パスポートセンターに行って申請書＋委任状をもらい、またその近くの写真屋でパスポート用写真を撮ってきた。これらとパスポートを合わせて、近々仙台に来る親に渡せば間に合いそう。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

本屋に寄りつつ何も購入せず帰宅。パスポートセンターで貰ってきた、ゴルゴ13と外務省のコラボの海外安全対策マニュアルを読んだ。めちゃくちゃシュール。ゴルゴはそんなこと言わないだろというセリフばかり登場する。漫画は過去の話をコピーしてセリフだけ置き換えて作っている、と書いてあったような気がするが、そうだとしたらそれは凄いことだと思う。ネットでも読めるようなのでリンクを貼っておこう。

話自体に見覚えがあったので、もしかしたら5年前にパスポートを作ったときも同じ冊子を貰ってきていたのかもしれない。2021年に版が変わって後ろにコロナについての話が増えたようなので、そこは確実に今日初めて読んだとわかる。

パスポートセンターで貰ってきて読んだ pic.twitter.com/5N95SnLMV2
— こたつがめ (@kotatsugame_t) 2022年5月2日

布団に入って少しカクヨムを読み、午後6時就寝。

05/03(火)

午前4時起床。

カクヨムを1作読了。「幼馴染がVtuberになった、何故か配信の度に俺がトレンドに上がるようになった。」。面白かった。イラストレーターがVtuberになりそうになっているので気に入った。実質しぐれういさんみたいなところがある。ただ最近の更新は、女性Vtuberであるヒロインが男性である主人公に言及するのは炎上の元になるという話が始まって、少し不穏。

【PV１７０万突破】ぼっちの俺がゲームスキルで大人気配信者になった件（相野仁） - カクヨム

もう1作Vtuberモノのカクヨムを開いてしばらく読み進めたが、途中で止めた。俺TUEEEは否定したくないが、ヨイショが鼻につきすぎる。この感覚は作者の別作品を書籍で読んだときにも感じたもので、自分の苦手な作者であるとの認識を強めた。

午前7時から午前11時まで二度寝。起きてから部屋の掃除。実家に届いていた学位記の写真を撮った。

pic.twitter.com/POHWOaYkQA
— こたつがめ (@kotatsugame_t) 2022年5月3日

食事してしばらくハーメルンを読み、午後1時から灘校文化祭コンテスト 2022 Day1に出た。ソロ。

灘校文化祭コンテスト 2022 Day1 - AtCoder

Aはよい。Bはギャグみたいなもの。Cは2回くらいBFSをする面倒なやつ。Dは大変苦労した。全探索で解を見つけて、 $\{0,1,-2,3,\dots,N/2,\dots,-3,2,-1\}$ となっていることをエスパーした。これに気づけたのはかなり奇跡的な気がする。EはEven Degtreesを思い出せば連結成分ごとにかなり好き勝手できるとわかるので、見ている頂点の次数の偶奇を持って木dp。Fはfunctional graphに言い換えれば自明。Gは行ごとのdpを考えると遷移が多項式のべき乗になったので、二分累乗法で通した。700ms。

Hは与えられた点を連結にする辺だけ残した部分木を考えて、それの辺数の2倍から直径を引く。残す部分木の辺数（の2倍）については、dfs順に並べて円環と見たとき隣接する点の距離を足し合わせたら求まるらしい。典型90問で知った話。直径は、与えられた点だけを見てdouble sweepすれば求まる。葉となりうるのがそれらしかないため。Jは素因数を $1000$ 未満と以上に分けて、未満はそれぞれセグ木に乗せ、以上は個数をカウントした。何も考えずにセグ木を全部更新するとTLEしたので、関係する素因数のところだけ見るようにしたら1000ms。

Iは区間に辺を張るテクをしてdijkstra、700ms。Kはかなり苦労したが、タイルIを2枚横向きに置く枚数を固定したら解けた。タイルLは2枚組で使う必要があって、Iの2枚組とLの2枚組を並べた後、間にタイルIを置いていく。タイルLに挟まれた箇所では横向きになるが、結局どこでも1枚ずつ置いていくことになるので、単純な重複組み合わせで書ける。最後にタイルLの向きを考えて $2^{A/2}$ 倍する。

残り20分でLに特攻し、解けなかった。11完で9位。Dは $\{-0,1,-2,3,-4,\dots,-(N-2),N-1\}$ と見るとわかりやすいようだ。2個ずつ見れば $\pm 1$ で、これで上手く行く理由も納得できる。Gは考察すると普通にcombinationで解けるらしくびっくり。自分が使った多項式は $\sum 2^{M-i-1}x^i$ で、これを $2^{M-1}\times\sum 2^{-i}x^i$ と見ると、確かにべき乗後の各項が閉じた形で表せる。

Iは頂点でコストがかかると考えれば辺のコストが0になって、dijkstraによる更新が高々1回になるので一度見た頂点は消して良くなるようだ。Kの解説はよくわからなかったが、 $f(x)^n$ の先頭 $N$ 項を求める話は $n$ が負でも適用できるということらしい。フィボナッチ数列の畳み込みをOEISに投げて一般化した漸化式をエスパーした人もいたので、そのような漸化式の存在が先頭 $N$ 項を求める話にも効いているのだろう。

コードゴルフ。Aはdc 13Bでホクホクしていたら12Bに縮められた。 $\lfloor N^2/2\rfloor-\lceil N/2\rceil$ 。BはRubyのcombinatio.sizeをそのまま使える。Vimで書いたものに1B更新があって取られた。Dは2段落前に書いた集合をRakuで実装。符号を切り替える部分がどうにも短くならず、あまり納得のいかないコード。他は手付かず。

upsolveを2問行った。まずコンテスト中に考察していたL。方針としては、頂点を深さごとに分類して、ある深さの頂点について問題を解くときに、1段深い頂点たちについて同じ問題を解いたときの辞書順で並べておいて使うというもの。考察のダメだった点として、頂点数の少ない子を先に使えばよいと考えていたのがある。一番浅い頂点が先に来るので嬉しいと思ったのだが、それ以前に部分木で大小関係が決まってしまうことがある。次に実装で、同じ部分木を生成する頂点には同じ順番を割り当てなければならなかった。この2点を修正してAC。

次にO。各机について、右にどこまで寄せられるかを計算できればよい。ある机 $i$ に対して、 $i\lt j$ かつ $A_i+A_j\gt K$ となるような最小の $j$ を求めてみる。この机 $j$ を限界まで右に寄せた後、机 $i$ もその1つ左まで寄せられるのではないかと考えた。これは $A_i\le A_j$ のとき正しい。机 $j$ の左に出てくる机は机 $i$ とも交換できるようになるため。そうでない場合は $2A_i\gt K$ なので、代わりに $A_i\le A_j$ なる $j$ を求める。机 $j$ の左に出てくる机を机 $i$ と交換できることを保証するため。机 $j$ の右には行けないのでその1つ左……とはならず、 $i\lt k\lt j$ で机 $i$ の左に出せない机の数も考慮に入れる必要がある。範囲内の $k$ ではすべて $A_k\lt A_i$ なので、 $A_i+A_k\le K$ ならほかの机も越えて机 $i$ の左に出すことができる。 $j$ を求めるのは区間MAXのセグ木の二分探索、後半の区間カウントはライブラリになっている。

ラノベを1冊読了。「転生ごときで逃げられるとでも、兄さん？」3巻。凄かった。凄い理由は一応ネタバレ配慮ということで次とその次の段落に書くので、これから読もうとしている方は注意して読み飛ばしてほしい。ストーリーに注目して感想を述べれば……いや、この本に限ってはそんなことをしても意味はないだろうか。前半もちょっとダークな感じではあるものの、素直にドキドキしながら楽しんでいた。

終盤のちゃぶ台返しがすごかった。これまでの展開が全部無意味になってしまった。ストーリーが意味を成さないというのはそういう意味。裏表紙のあらすじにある「神の筋書きさえ殺す」というのは完全にメタ的な意味だったらしい。章題も書き換えられていた。イラストページの最後にこの巻の目次がついていたのだが、実はそれは途中までしか載っておらず、本の途中で目次が追加されるというかつてない体験をした。300ページ以上ある本の目次なのに200ページちょっとで小節が途切れているのに違和感を抱くべきだった。

登場人物一覧も改めて書かれて、結構な数のキャラがあっけなく殺されてしまったらしく横棒を引かれていた。これも信じていいのか迷ってしまう。横棒が書かれている→死んでいる、ということは別にどこにも明記されていない。ただ、そういう機能的なページでは嘘をつかないみたいな信条もありえるので、本当にわからない。

部屋の整理を始めた。仙台から実家に送った段ボールのまま放置されていた既読本を本棚に詰める。現在すでに部屋の棚が満杯なので、これからは物を減らす必要がある。中学校のときに使っていた絵の具セットやらを捨ててとりあえず空けてみたが、キャスター付きの棚だったので本をギチギチに詰めるのはマズいようだ。実際、詰めてから動かしてみて、敷物から恐ろしい音が鳴っていることに気づいた。そこで、その場所に別の棚から物を移して場所を空けることにした。とりあえず今ある分は収納できたものの、すでに横向きに本を詰め込んでギリギリのため、本当にマズい。

入った pic.twitter.com/eEIKGhyHND
— こたつがめ (@kotatsugame_t) 2022年5月3日

F問題のコードゴルフを少し。コンテスト中はcombinationライブラリを持ち出したが、よく見るとただの階乗だったらしい。dcでも通ったので、それで縮めておいた。

布団に入ってハーメルンの更新を確認。読んでいるうちに寝落ちした。午前2時だった。

05/04(水)

午前9時前起床。しばらくカクヨムを読んでいた。

帰省してからテザリングばっかりしているので、気になって通信量を確認していた。過去の月も見ていると、面白い期間を見つけた。目に見える変化が3回しかない。ちょっと学食に行くだけではこんな急激には増えないので、この3回はそれぞれゲーセンなどのため街に出かけていった日を示しているはず。当時の日記を調べてみると、02/16、03/03、03/08、03/09にそのような外出をしていたとわかった。03/08-03/09をくっつけて考えれば、確かに3回であるようだ。

この月めちゃくちゃわかりやすいな。3回外出したらしいです pic.twitter.com/Bw1TXdsuMA
— こたつがめ (@kotatsugame_t) 2022年5月4日

午前11時になって布団から脱出。昨日寝る前に縮めたF問題が更に縮められていた。適当にテストケースハックを試みると通ってしまったので、さらに-2Bで取り返した。

部屋の整理の続き。思い切ってゲーム機を捨てることにした。インターネットに接続して、DSiのうごメモを熱心に集めていた記憶がある。その中でもやはり有名なのは100%さんの棒人間バトルだろう。この作品（と関連作品）でSouthern Crossを知った人も多いと思う。検索すれば動画が出てくるのでピンと来ていない人はぜひ見てほしい。コピーが多すぎて、原作を見つけたときはかなり興奮した記憶がある。

懐かし〜 pic.twitter.com/7ege0iZ7Bm
— こたつがめ (@kotatsugame_t) 2022年5月4日

うごメモもインターネットにおける時代の流れに取り残されてしまったデータであるようだ。うごメモ発掘云々というタグが存在するのを見つけた。それなら、今手元にあるメモたちをただ捨ててしまうよりはいいかと思って、とりあえずSDカードのデータを吸い出しておいた。3165個。

日記のこの部分を書くときいろいろ調べているうちに、当時僕が熱心に作品を追っていたミラーパネルさんが今も活動されていることを知った。YouTubeに上がっているPV集がエモい。ただ僕としてはオリキャラの話やPVのほうが好みだったので、それが上がっていないのは寂しい。男の子2人と女の子1人の3人組がいたことを覚えている。

ミラーパネル【松坂奈夜】 - YouTube

午後1時から灘校文化祭コンテスト 2022 Day2。ソロ。

灘校文化祭コンテスト 2022 Day2 - AtCoder

Aは $M/\gcd(M,K)\mid N$ を判定。Bは $A=\max A_i$ を固定すると使える区間が定まって、 $A\gt 0$ なら $\min B_i$ は小さいほうがいいので使える区間を目いっぱいに選択、 $A\lt 0$ なら $\min B_i$ は大きいほうがいいので1点のみの区間を選択。 $A=0$ なら $0$ である。全ての $A$ について計算したものの最小値を答える。Cは今日もまた面倒なBFS。それで前計算してbitDPで答えを求める。

Dにかなり苦労した。グラフが連結であれば、辺数が頂点数以上であることを確認するだけでよい。よって連結成分に分解する方法を考える。1点 $u$ を選んで、それと接続されている頂点を全部集めたい。ある頂点集合 $U$ の中に接続されている頂点が存在するかどうかは、クエリ $U$ の答えよりも $U\cup\{u\}$ の答えのほうが大きいことを確かめることでチェックできるので、 $U$ を半々に分割していくことでそれなりに高速に求められそう。今の操作は $\{u\}$ がもっと大きな頂点集合になっても同じように行えるので、増えなくなるまで繰り返せば良いとわかった。ただ数ケースQLEしているらしい。苦し紛れに、QLEする直前にNoを出力するようにしたら通ってしまった。

Eはシュッと解けた。 $\sum_{i\ne j}\min(|A_i-A_j|,|B_i-B_j|)$ を求めたい。まず $A_i\lt A_j$ 、 $B_i\lt B_j$ 、 $A_j-A_i\le B_j-B_i$ と固定してみよう。すると $A_j-B_j\le A_i-B_i$ が得られるので、 $A-B$ を座圧してセグ木に $A$ の和と個数を乗せることでこのケースの総和が求まる。 $B_j-B_i\ge A_j-A_i\gt 0$ なので $B_i\lt B_j$ は自動的に満たされる。 $A_j-A_i\gt B_j-B_i$ の場合は $A$ と $B$ を入れ替えることで同様に。 $B_i\gt B_j$ の場合は $A_j-A_i\le B_i-B_j$ より $A_j+B_j\le A_i+B_i$ なので、 $A+B$ を座圧することになる。 $A$ と $B$ を入れ替えてもう一度やるのも同じ。以上で $A_i\lt A_j$ としたときの全ての場合を求めたので、2倍すれば答えになる。

Gは商列挙が面倒。 $\forall i.k\mid C_i$ という条件で数え上げた後、倍数のケースを引けば求まる。 $1\le k\le M$ について求めるのではなく $1\le k\le 10^5$ について求めなければならないのは注意。 $k$ を固定すると、各 $i$ に対して $C_i$ は $\lfloor B_i/k\rfloor-\lceil A_i/k\rceil+1$ 通り存在するので、これをかけ合わせればよい。区間の端点が変化するポイントは $O(\sqrt{A_i}+\sqrt{B_i})$ 種類しかないので、全部列挙してちまちま弄っていく。全体の積をセグ木で求めたらTLEしたので、掛け算と割り算を繰り返すことにした。ただしゼロ除算が困るので、そのようなケースは別にカウントしておく。これで4000ms。商列挙でMLEしてしまったので、pair<bool,int>をintに押し込んでデータを圧縮している。

Fは最小費用流。区間の端点を列挙することで、使える給水機の集合が等しい区間に分割することができる。分割した後の区間をそれぞれ1つのノードと見て、始点→給水機→区間→終点という感じに辺を張ればよい。コストが負になってしまうが、負閉路は存在しないので、最初のポテンシャル計算を手で行うことで問題なく計算できるやつ。今回はそもそもDAGなので、頂点番号がトポロジカルソート順になるように振って、先頭から順に計算した。後からよく考えれば、この場合はdijkstraがそのまま使えるので、ポテンシャルを0にしておいて問題なかったようだ。1回目の提出が2087msで、定数倍高速化して約1600ms。

Hは二重頂点連結成分分解。名前だけ知っていて、実装したこともこれを使う問題も解いたことがなかった。いろいろ調べるうちに、こちらも二辺連結成分分解と同様、分解後のグラフを木に見立てることができると知る。しかしその方法はかなり複雑に思われた。自分で実装できる気がしなかったのでもうちょっと調べ、以下のブログに何もかも書いてあるのを見つけた。このライブラリを貼り付けた後木dp。各頂点についてそれをLCAとするペアについて計算したが、解説を見て、単にそこを通る回数を数えればよかったということを知った。

Block-cut tree - ei1333の日記

Iは面倒。整理すると、長さ $N$ の順列であって、特定の $c$ 個の要素が $1\dots K$ 、 $K+1\dots 2K$ 、……の少なくとも一つを埋め尽くしているような場合の数が十分高速に求まればよいとわかる。包除原理で $O(c)$ で求まる。……と思ったのだが、この場合の数を後から指数として使うので、 $\bmod 10^9+6$ で求める必要があることに気づいた。恐る恐るfactorに投げると $2\times 500000003$ と素因数分解されたので、 $\bmod 2$ と $\bmod 500000003$ をそれぞれ求めれば復元できるようだ。後者は十分大きな素数なのでいつも通りmodintで計算できる。前者はリュカの定理などを使って気合いで頑張る。 $O(c)$ が十分高速であることは全く確認せず、とりあえず投げてみたら、通った。解説を見て $\sum c\le\sum_i\log A_i$ であることを知り、納得。

残り20分はK問題に取り組んでいた。どうせAlienDPだろうと思って適当に実装し、サンプルまで合わせるもWA。適当にポンポン投げて4ケースWAまでにじり寄ったが結局通せなかった。9完9位。

Bは試すべき区間を $N+1$ 種類に絞れるようだ。解説がなかなか理解できず苦労した。長さ1の区間で十分と書いてあるところは、 ${\rm argmax}_i\;A_i$ か ${\rm argmin}_i\;B_i$ を選ぶ場合を考えればわかる。Dはある頂点に隣接する頂点を全部一気に求めるのではなく、1つずつ求めるようにすればよかったらしい。 $U$ を半々に分割するとき、隣接する頂点を1つだけ検出する場合は、片方だけ聞いてどちらを次の $U$ にするべきか判別できるからだと考えた。ここで両方聞いてしまったときの定数倍が効くのを意識していなかった。

Eの解説の式変形は頭が良い。 $\max(|x_i-x_j|,|y_i-y_j|)$ を差の絶対値の和に置き換える箇所は、普段マンハッタン距離で45度回転しているテクの逆と見なせるようだ。初めて見る気がする。GはMLEした部分のデータの持ち方が違うだけで、変わらず商列挙が想定解だった。Fは解説と全く異なっていた。実行時間的にも想定解でないのは明らかで、何も考えずフローを流してしまいすみませんという感じ。

コードゴルフはA問題だけ。dcで解いておいたら、夜になって実は $\gcd$ を求めなくてもよいことが判明し縮められていた。 $M\mid NK$ を判定すればよかったらしい。言われてみればそれはそう。

Kのupsolveをした。AlienDPであることは間違っておらず、絵を取り外す時ではなく残すときにペナルティを与えるようにしたら通った。びっくり。これが本質的な違いとは思えなかったため、誤差が問題になっているのではないかと考えた。それで、日記を書いているとき、試しに全体を2⁶⁴倍して__int128で実装してみたところ、見事通った。この方法はちょっと覚えておきたい。ただ、long doubleでもそれほど変わらない桁数の精度があるはずなので、相変わらずよくわからないままである。

食事してしばらくSSを読んだ後、深夜まで日記を書いていた。今日の部分までたどり着かないうちに眠くなったので切り上げ、布団に移動。

そこからTLに流れてきたハーメルンを開き、1作読了した。「【ダンジョン配信】元社畜TS異世界転移者のホームレスから始まるダンジョン配信者生活!!」。主人公が強いのはいいが、現在初心者からステップアップするフェーズにあまり興味が持てない。正直なことを言えば手っ取り早く地位を上げてほしい。こらえ性のない人間になってしまった……。

https://ncode.syosetu.com/n3202hp/

05/09追記：ハーメルンのほうでは削除されてしまっていた。なろうでは連載が続いているので、リンクを貼っておく。

午前2時過ぎ就寝。

05/05(木)

午前9時前に起床。昼前までずっと一度読んだなろうを読み返していた。

少し日記を書いてから祖母宅に行き、顔を見せた。会う度に僕の小学校入学以前の思い出を無限に語られるので正直辟易してしまう。思い出話を聞くのも孝行の一種であろうと理解はしているが、どうしてもそっけない対応になってしまう。ただ、じゃあ自分から話題を振って、今やっていることなどを説明したいかと言われると別にそうでもない。こうやって溝が深まるうちに残りの時間を過ごすのも、最近はまあそういうものかと受け入れてしまっている。

帰宅してまたしばらくなろうを読み、夕方になって焼き鳥屋に行った。混み具合はそこそこ。帰ってきてからもまた夜までなろうを読んでいた。

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

今日読み返していたのは「逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！」。完結済みで、2月に閑話のようなものを毎日更新していたらしい。それを読んでからうっかり読み返しを始めてしまったというわけ。その閑話、配信アーカイブと名付けられている1話ごとの話が非常に良い。完結してからの話なので難しいことも苦しいこともなく、永遠の安寧を味わえる。

ハーメルンでいろいろVtuber小説を漁ってから読み返してみると、かなり毛色が違う作品だったなあと思った。かなり初期のVtuber界隈を題材にしており、Live2Dによる生配信ではなく3Dモデルによる動画投稿がメインの活動となっている。スーパーチャットの描写もなく、コメントとは会話せず、Vtuberから視聴者へは一方通行である。

https://ncode.syosetu.com/n3530fy/

午後11時半まで日記を書き、眠気が強くなったので布団に移動。少しハーメルンを読んで就寝。かなり久しぶりに、徹夜明けでもないのに日付が変わる前に寝られた。

05/06(金)

午前9時起床。

ハーメルンで読んでいた作品が1作、完結した。エピローグ5話がかなり良かった。中学卒業後からバンバン時間が飛んで、主人公たちの将来を描く。そういう締め方は一般に健康に良いとされている。

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

仙台に帰る準備を整える。ラノベを3冊持ってきたのに、来るときの車内で読んでいた1冊以外はちっとも読み進められず2冊持って帰ることになった。昨日一日ネット小説に吸い取られてしまったのが痛い。昼前に家を出発。

昼食は回転寿司に行った。一応平日の昼間なのにそれなりに待ちがいてびっくり。写真の右に見えているのは白エビ軍艦。何気なく取ったら760円の皿で、大変恐縮しながら食べた。甘みがあり、巻いているとろろ昆布も合わさって非常においしかった。

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

黒部宇奈月温泉駅から新幹線に乗り、大宮へ。車内ではラノベを読んでいた。大宮に近づくにつれ人が増え、僕の隣の席も埋まってしまった。

大宮に到着。事前のチェックでは乗り換えの時間が5分でちょうどいいなと思っていたのだが、乗る予定だった列車がGW中の特定の日しか運行しておらず、30分後の新幹線を待たなければならなくなった。改札を出てゲーセンに行くとチュウニズムが埋まっていたので、待たずにすぐ引き返した。まだ微妙に時間があるので、ゲーセンとは反対側の出口にも出てみることにした。そちら側はペデストリアンデッキがあって、仙台駅を思わせる感じでなかなか面白かった。

こっち側初めて来た〜♥ pic.twitter.com/rPA9VBUcM3
— こたつがめ (@kotatsugame_t) 2022年5月6日

ようやく来た新幹線に乗り仙台へ。人はそこそこ、1席開けて座れるくらい。また車内ではラノベを読んでいた。午後6時に到着。ホームに降りてみると、今乗ってきた列車にここから乗り込むらしき人が大量に列を成していてびっくりした。

駅前のヨドバシカメラで板タブを購入。液タブのモニター機能がないやつ。昨年からオンラインのゼミだったり競プロ配信だったりで、手書きの図を即座に画面に映せるようにしたかったのだ。この先使う機会がどれくらいあるかわからないので一番安いものを購入。それでも6000円くらいした。

たいぺーから誘われたので一緒に食事する。待ち合わせはサイゼ。行ってみるとたいぺーがスープを注文していたので、間違い探しをして待っていた。今日はかなり冴えていて、たいぺーが食べ終わる前に10個全部見つけることに成功した。気分よく店を出てしばらく食事する場所を探し、やよい軒に入った。

食べた後少し本屋をうろついて帰宅。しばらくYouTubeを見てからシャワーを浴び、板タブの設定を始めた。初期設定では3枚並べたモニターが横幅を圧縮されて小さいタブレットの画面と対応しているようだったので、これを1画面のみに対応させたい。設定画面に最初からその対応を弄るページがあることに気づかず、wacom IDの作成と製品登録が必要だと早合点してしまった。このIDの登録にもかなり苦労した。twitterログインだけだとダメで、直接メアドで登録したら成功。ここでようやく最初から設定できたことに気づいて、無事1画面だけに対応するようにできた。

ラノベを1冊読了。「時々ボソッとロシア語でデレる隣のアーリャさん」4巻。夏休みの期間ということで、この巻では生徒会長を目指すバトルはお休みし、全編ラブコメだった。前半のデート2本はシンプルに好みのシーン。そこから生徒会合宿に行って、そこでヒロインからの恋心に主人公が気付くシーンがある。普通はくっつくまでずっと勘違いじゃないか悶々しているところ、途中でそうやって明言するのはなかなかびっくり。確かに、この主人公ならそういうところも目ざとく気付くほうが納得感がある。一方で主人公からヒロインに向ける感情にはまだ決着がついておらず、この巻のラストはそれに続くようなシーンで終わった。途中の伏線らしき描写から予想していたのとは違う人物が最後の挿絵に描かれていて、どういう関係だったのだろうかとかなり気になっている。

午前1時から、今日買ってきた板タブを考察に使ってみようと競プロ配信を始めた。

まず、この配信内で起こしてしまったことについて。yukicoderを解いていて、うっかり問題一覧のページに遷移したところ、僕がテスターをした未公開問題の問題名・難易度・タグ・writerが一瞬配信画面に映ってしまった。その時点での視聴者数は7人。即座に配信の巻き戻し機能をオフにし、また配信終了後にアーカイブを非公開にしたのでそれ以上の拡散はないものと信じているが、これ以上は視聴者の良心に恃むしかない。writerに連絡を取って何とか許していただけたものの、作られた問題には代わりとなるものが存在せず自分では何をどうしても贖うことができないため、大変肝を冷やした。

配信で解いたものについて。最初にCF #764 div.3を埋めた。A、Bはよい。Cは先頭から見て、残りの要素で作りにくい値を作るようにしたら通った。コメントで値を $n$ から降順に作ればよいと言われてびっくり。 $n$ 以下になるまで $2$ で割った後、同じ値を同一視してよいことを意識していなかった。このことがわかれば、僕の解法の「作りにくい値」とはすなわち作れるうちで最も大きな値であったこと、それを貪欲に作ってよかったことがわかる。Dは作る文字列の長さの偶奇を決め打つ。Eはdp。Fは二分探索。適切に $c$ を定めて、 $\lfloor x/n\rfloor$ が増えるかどうかを判定の条件とする。ちょっと面倒。Gは辺集合を持ち、上位bitから見て、そのbitが立っていない辺だけ使っても全域木が作れるなら辺集合を更新することを繰り返したら通った。

次に、今日のyukicoder 342のA-Eを解いた。A、Bはよい。Cは、子の数が1の頂点にそれ以下であぶれた部分木のうち最大のものをくっつけてやりたいので、あぶれたものをマージテクで管理。Dは半分全列挙。Eはちょっと難しい。最初、bitごとに考えようとしてしばらく詰まっていた。 $i$ を固定すると $j$ の条件が $i\le j\le L+R-i\le R$ と書けるため、 $2i\le i+j\le L+R$ とわかる。区間全体のXORを、さらに $L\le i\le (L+R)/2$ でXORするため、 $(2L,2L+1),(2L+2,2L+3),\dots$ のようなペアごとに出現回数の偶奇が変わる。ここで、ペアになる2数のXORは $1$ であるから、奇数回出現するペアを数えるだけでよい。 $L+R$ が偶数の場合はそれだけ単独で出現するので、別に数えておく。

yukicoder contest 342 - yukicoder

コメントでオススメされて少し前の問題を1問解いた。実際面白かった。とりあえず重複を取り除く。張る辺の $\gcd$ を決め打ってみると、 $g$ で割り切れる要素のうち最小のものとそれ以外を繋ぐことだけ考えれば十分とわかる。そこから、各頂点に対して接続している最も重みが小さい辺を求め、それらで最小全域木を作ろうとしてしまいしばらくWAを重ねた。実際は、先ほど絞り込んだ辺を全部使って最小全域木を作らなければ連結にできない場合がある。

No.1917 LCMST - yukicoder

午前3時半ごろ配信終了。配信アーカイブは非公開のままにするのではなく、見せてはいけない部分だけカットして公開してはどうかと言われたので、そうすることにした。アーカイブをダウンロードして、手元でカットして再度アップロードする必要があると思っていたが、実はYouTube Studio上で簡単に行えるようだ。そういえば、Vtuber小説で配信アーカイブのカット編集に言及していたものがあった気がする。ずいぶん手軽そうに書いてあったのは、こういう機能が存在したからなのか。先ほど触れた配信の巻き戻し機能のオン・オフもVtuber小説から得た知識で、ちゃんと現実にも存在しているんだなあと感動した。

カットした動画が反映されるのにはしばらく時間がかかるようなので、今日は非公開にしたまま布団に入った。午前5時就寝。

05/07(土)

午前10時半起床。YouTubeを見たり本を読んだりしていた。

フォローしているアカウントを頂点、共通のフォロワー数が多いペアを辺としてグラフを作り表示するサービスがTLに流れてきたので、自分も試してみた。頂点が多いのでかなり壮観。ただめちゃくちゃ重いし、出力した画像のサイズもそのままではツイートできないくらい大きくて大変だった。

Furland

6172頂点64248辺#bunnypaws pic.twitter.com/qdX8WsLaFY
— こたつがめ (@kotatsugame_t) 2022年5月7日

昨日の配信アーカイブの編集が完了していたので、ほかに映ってはいけないものが映っていないことを確認して公開設定に戻した。

午後3時就寝。次に午後5時半、目覚ましで起床。またしばらくYouTubeを見て、午後7時くらいに布団から起き上がった。食事し、シャワーを浴び、人の日記を読んだり自分の日記を書き進めたりして時間を過ごし、午後9時からAGC057に出た。実に5か月ぶりのratedである。

AtCoder Grand Contest 057 - AtCoder

A。 $a$ が $b$ の部分文字列であることは、 $b$ の最上位桁か最下位桁を落とすことを繰り返して $a$ にたどり着けることと等しい。よって、数を頂点とし、最上位桁か最下位桁を落とした数に向かって辺を張った有向グラフを考えると、良い集合はすべてのペアがこのグラフで互いに到達不可能でなければならない。ここで、このグラフで入次数が0である頂点を選ぶのがよいと思った。確かコンテスト中は、入ってくる辺があるならそれを逆に辿った頂点を選ぶことにしてもよいから、と考えていたはずだが、これは良い集合の状態を保てない操作のため、理由としては間違っている。しかし結論は合っていて助かった。

入次数が0である頂点を数えるため、桁数に注目する。 $R$ の桁数を $r$ としたとき、 $r$ 桁の数は全部数えて、 $r-2$ 桁以下の数は数えない。 $r-1$ 桁の数については、最下位桁に $0$ を増やすか、最上位桁に $1$ を増やした数が $R$ 以下ならば数えない。つまり $r-1$ 桁の数 $x$ は $\min(x+10^{r-1},10x)\gt R$ のとき選べるということで、この不等式から $x$ の下限が出せる。 $L$ 以上という条件を確認し忘れて1WAしつつ通した。

B。2進数で桁を揃えたい、というところから考察を始めた。 $X$ の影響を実験してみると、 $A$ の上位桁であって数回操作しても弄れないところは、そのあと何回操作してもずっと弄れないままであると感じた。そうならば、最小値を達成する桁数はそれほど大きくならないはず。各要素の操作回数を決め打つと、達成できる値が区間で表せて、このときの最小値は区間の右端の $\min$ から左端の $\max$ を引いた値（負なら $0$ ）になる。左端が最も小さい要素を選んで1回操作し、また最小値を求める、ということを繰り返せばよさそう。 $\max$ は単に変数を更新すればよく、 $\min$ にはmultisetを使うことにした。区間の右端で判定するとオーバーフローしたり操作を試す回数が足りなかったりしたらしく、左端が2⁶²未満の間という条件でようやくACした。2200ms。

残りのsolved数は絶望的。若干多かったDに進んだ。とりあえず $S$ が奇数の場合は自明で、しばらく実験して $S$ を割り切らない最小の数 $p$ が重要そうなことに気づく。 $\{S/2+1,\dots,S-1\}$ という集合があって、ここからいくつか選んで $x\leftarrow S-x$ とする（反転と呼ぶ）と考えられるが、このときまず反転後に $p$ の倍数になるものが選ばれる。それ以降は大きい順に、反転しても良い数列になるなら反転することを繰り返すことになる。 $S$ を作れないという条件は、反転した数だけ無視してチェックしても答えが合ったので、そうした。

そうやって $p$ の倍数にならないのに反転するものを出力してみると、ある数 $x$ が反転されたら $x-p$ も反転されているようだった。なので、 $x\bmod p$ ごとに最大の $x$ を求められればよさそう。そのような $x$ について、 $S-x$ は $S$ を $p$ 未満の数で割った数の近くになっていそうだったものの、この時点で時間切れ。適当にコードを弄って実験結果と一致するか試すのを何度も行っていたので、もうちょっと頭を使うべきだった。

2完3ペナ118位、パフォーマンス2670、レートは2852→2835(-17)。軽傷で済んでよかった。まずAの考察が正しくなかったのがヤバい。Bもまともな考察をしていなくてヤバい。左端の上限をちょっと下げるとすぐWAになってしまうので、通ったのは本当にたまたまだったらしい。

コンテスト中にとんでもないリザルトが出回っていた。つい最近別の人が1落ちを出していてかなり驚いたものだが、そこから理論値がなかなか出ず、大変苦労している様子がTwitterで見られた。その人を差し置いて先に全部噛み合わせたのは、やはりこの人だったか、という感想。

混沌を越えし我らが神聖なる調律主を讃えよ
ALL JUSTICE CRITICAL‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️‼️
閉店滑り込みで間に合ったー！！！！！！！ pic.twitter.com/QvwjjnzpRw
— す (@Kokor0_N) 2022年5月7日

AtCoder Beginner Contest 250 - AtCoder

解説を読んでDを通した。反転する数の集合を考えるのはよくて、それが和で閉じていることには一切気づけていなかった。ここは考察が必要だったところ。解説の「 $X$ に追加できる次に小さい数を探す」の部分はかなり難しい。これまで反転した数だけで作れる値を $\bmod p$ で分類し、それぞれ最小のものだけ保存しておく。次に追加する数 $\bmod p$ を全探索する。先ほど保存したそれぞれの数 $T$ について、 $T$ に今追加する数を何回足せば $T\bmod p$ と $S\bmod p$ が一致するかが前計算でわかる。そうやって一致させたときに $S$ 以下になっていると、さらに $p$ を足して $S$ を作れてしまうので、これが $S$ より大になるという条件が追加する数の下限を与える。 $T$ を全部試して $\max$ を取り、全探索した中でこの値が一番小さいものが、次に追加できる数となる。それを用いて $T$ の集合を更新する。

コンテスト中にたどり着けたところからもまだかなり遠かったな、という印象。無理だ。

日記を書き始めたが、朝方はかなり集中を切らしてなろうを読んだりしていた。寝る前にatgolferを確認するとAGC-Aが結構縮んでいたので、自分もゴルフしてみた。 $L\le l$ として、区間 $[l,R]$ が良い集合であるときの $l$ の最小値を求めたい。二分探索せずとも定数時間で求まるらしい。 $R$ の桁数を $r$ と置いて、 $l=\max(L,\lfloor R/10\rfloor+1,\min(r-10^{r-1}+1,10^{r-1}))$ としたら通った。これをdcで書いて60B。

dcコードをずっと睨んでいたが特に縮まないうちに椅子の上で一瞬寝てしまったので、布団に移動。午前9時就寝。

05/08(日)

午後2時半起床。しばらくYouTubeを見てから起き上がり、日記を書いていた。

午後5時からOpenCup。Grand Prix of Yuquan（と書いておかないと後から読み返したとき辛いことに気づいた）。今日はかなり調子が良かった。チームでFDJBCHILMAの10完11位、自分はDBCIを解いた。M問題の問題文に急に魔理沙のイラストが出てきて面白かった。

www.pixiv.net

Dはソートして小さいほうから順に取る場合しか考えなくてよい。全部同じケースで配列外参照を起こしたり、割り算を掛け算に直して比較するときにオーバーフローしたりで2ペナ生やしてしまい大変だった。Bはある条件を満たす数を数えるという問題だが、条件がかなり厳しいので、実験して全部埋め込めそうと感じた。PCが空くのを待って実験を回すと、なんと1つしか見つからなかった。サッとコーディングしてAC。Cは、チームメイトの考察を眺めていると連結成分ごとにサイクル基底を取ればよいことに気づいた。同意を得られたので実装。 $S=T$ のケースにしてやられ、1ペナで通った。

Iも順当に解けた感じ。 $u\lt v$ かつ $p_u\lt p_v$ とすると、 $u\lt i\lt v$ かつ $p_u\lt p_i\lt p_v$ なる $i$ に対して一気に差分が求まればよい。 $A_i-B_i$ で場合分けしてみると2通りしかないようだったので、それぞれ対応する列に持っておいて、大小関係を満たす要素をカウント。これはrangefreqというライブラリにしてある。書き始めてから $C_u$ と $C_v$ の更新がそこそこ大変であることに気づいたが、変更される位置を集めて $A_i$ 、 $B_i$ の計算をやり直せばよかった。実装はかなり面倒。一発で合って嬉しかった。

以降は考察のみ。MはMAOであることを指摘し、しばらく考えてみたものの、操作回数の上限が $2L^2$ で全然ダメだった。通したチームメイトの手法もよくわからない。Kは難読。必死に解読するも微妙な箇所が残ってしまった。基本、言われたとおりに書けば工夫せずとも通りそうだったが、ABCが近づいてきたのでHackMDにいろいろ書いて逃亡。結局僕が書いた考察もまだ難読だったらしく、実装はされなかった。

午後9時からABC250。

Aで入力の1行目と2行目を取り違え1WA。Bはよい。Cは順列と、各要素からインデックスを引けるテーブルを持てばよい。このテーブルは逆順列である。右端のswapを誤読してサンプルが合わずびっくりした。Dは $q\le \sqrt[3]{N}$ を全探索。Eは、数列 $A$ の各項に対し、その要素が数列 $B$ で出現する位置のうち最も左のものを計算する。そうして作った数列の先頭 $x$ 項における最大値が $y$ 以下のとき、 $A$ の先頭 $x$ 項は集合として $B$ の先頭 $y$ 項に含まれるとわかる。逆も行うことで集合としての一致が判定できる。Fは操作を何回でも行えると誤読してかなり長い時間固まっていた。1回しか行えないので尺取りでOK。

Gはなかなか解けず、苦労した。売値が高い日から貪欲に売ってみたりして迷走し、残り10分になって考え方を変え、ようやく正しい解法が得られた。先頭から見て、売る日・何もしない日を管理する。今見ている日の株価が $P$ であるとする。この日はまだ買う日にはなれない。売るとした場合、何もしない日を1日選んでその日に買ったことにするか、売る日を1日選んで、それとペアになっている買う日を代わりに今見ている日とペアにするか。前者は単純に何もしない日が1日減り、後者は売る日が1日減って何もしない日が1日増える。どちらか利益が大きいほう、または何もしないことを選ぶ。

これが最適であることは、コンテスト中は証明しようとしなかった。サンプル3を試したら合っていたので提出、残り2分で通った。今日記を書いているときにも考えてみたが、どうにもよくわからない。公式解説における説明もかなり難しかったので、行間を少し埋めておこう。まず、多重集合の操作は「 $A$ を2個追加」→「最小の要素 $m$ を削除して答えに $A-m$ を加算」と言い換えられる。 $A$ を1つだけ追加する場合が、 $m=A$ となって対応している。このことは最短コードを読んで気づいた。

$dp$ の折れ線は $j=0$ からスタートして単調減少、加えて上に凸である。傾きはある位置を境に $-A$ 以上から未満に切り替わるので、 $\max(dp_+,dp,dp_-)$ はその位置に横幅 $2$ 、傾き $-A$ の線分を付け加えた形になる。これは $j=-1$ スタートになっているので、一番左から横幅 $1$ の線分を削除する。つまり、傾きの列である多重集合に $A$ を2個入れて、最小の要素を削除。操作が正しいことは確認できた。

答えに加える値も見る。 $j=0$ における値の変化を追いたい。もともとそこにあった点は、折れ線 $dp_+$ において $j=-1$ の位置にずれ、次の折れ線に必ず存在してくれるため、ここから $j=0$ に戻せばよい。まず $dp$ が $dp_+$ になるタイミングで上に $A$ ずれて、その後右に $1$ 個ずらすとき下に $m$ ずれるため、合わせて確かに $+A-m$ となっている。

7完98位。Fも遅いしGも解けないしでプライドがボロボロになりそうだった。何とか耐え。Eは解説とかなり雰囲気が違う。いろいろやり方があるらしい。

コードゴルフ。Aは $4-(\lfloor 1/R\rfloor+\lfloor R/H\rfloor+\lfloor 1/C\rfloor+\lfloor C/W\rfloor)$ をdcで書いた。[x code]dxのテクを使って、まったく同じcodeを2回実行する。スタック操作をうまく組み合わせるとそこそこ縮んで21B。BはPerlで書いた。あまり短いとは思えないが自力では縮まない。なんだか僕が考えもしなかった書き方がありそうな雰囲気。DはRubyで書いてVimで縮めた。解説とは逆に $q$ を全探索することにすれば、全探索できることが容易にわかるし、 $p$ をカウントするテーブルも同時に作ることができる。というかstackに直前の素数を入れて、条件を満たさない間popしていけば十分。他は手付かず。

午後11時半からCF #789 div.1に出た。

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

Aは $c$ と $a$ をこの順に $n$ から全探索。 $c$ を減らす前にカウント配列の $(p_c,n]$ に $1$ 加えると、 $b$ を決めるごとに $d$ の個数が即座に求まる。 $a$ を減らす前に $b=a$ とした場合の $d$ の個数をそうやって求め変数に足しておき、減らした後の $a$ が $p_a\lt p_c$ を満たす場合にそれを答えに加える。特別なデータ構造を使わず全体で $O(n^2)$ になり、気持ちよかった。

Bは縦横をそれぞれ計算。横は、各 $1\le i\le nm$ について $(i-m,i]$ に'1'があるか調べ、あったなら $i,i+m,i+2m,\dots$ に $1$ 加算。 $i$ に加えてから $m$ 個おきの累積和を取る。縦はインデックス $\bmod m$ が不変なので、その列で初めて'1'になるインデックスを求め、それ以降に $1$ 加算。縦横が入り乱れてちょっと頭が壊れそうになったが、一発でサンプルが合って興奮した。

Cはfunctional graphと見て連結成分に分解。頂点の値を昇順に並べると、係数を $\dots,-2,-2,(0,){+2},+2,\dots$ のようにするのが最適。何回か見たことがある。3種類それぞれカウントして、 $1$ から順に小さい係数を割り当てていく。最初、頂点番号の係数ではなく区間の係数を見てしまい、最適な割り当てを作れずに1WAした。

Dは難しい。まず、操作はバブルソートの一部になっている。 $k$ 回操作したら後ろ $k$ 項は決定される。逆にこれを巻き戻してみよう。例えば $k=1$ のときを考える。末尾の $n$ がそれ以前にどこかにあったはずで、その位置は、先頭であるか、または先頭から見て累積maxが変化する点の直後である。また累積max以外の場所は一切変化しない。途中に $n$ を置いた場合はその直前にある値に乗り換え、同様にして先頭までたどり着いたら巻き戻しが完了する。ここで（ $n$ 以外の）累積maxの個数 $c$ を考えてみると、1回操作を巻き戻した後、その個数は $0\le i\le c$ について $i$ 個になるのが $\binom{c}{i}$ 通り存在する。無視していた $n$ を戻して $i+1$ 個。 $n$ の代わりに $n-k+1,\dots,n$ として順番に巻き戻した後の場合の数を数えたい。 $c$ を次元に持つdpを手で計算して $k$ ごとにOEISに投げると、 $k!(k+1)^c$ であると判明した。

後は、 $k$ 回操作後の列を $c$ ごとに求められればよい。挿入dpに $c$ を保持する次元を増やすと多項式と見れて、遷移が1次以下の式の掛け算になった。大量の1次式の積をセグ木みたいにまとめていって $O(n(\log n)^2)$ で計算するやつを実装。最大ケースでも1.3sec程度になったので提出したら、爆速で通った。そういうケースがpretestに入っていないようでかなり心配だが、まあ解けたのでヨシ！

残り1時間。Eのsolvedがかなり少なくほぼ諦めモードだったが、何とか気力を奮い立たせて考察を始めた。とりあえずbeautifulな区間の右端を $r$ と固定してみる。この時、左に見て累積maxが更新される位置の列を $\dots,(m_a,i_a),(m_b,i_b),\dots$ （ $m_a\gt m_b$ 、 $i_a\lt i_b$ ）として求められる。 $\max=m_b$ と決め打ち、 $l$ であって $i_a\lt l\le i_b$ かつ $p_ip_j=m_b$ となるような $l\le i\lt j\le r$ が存在するものを求めよう。

$1\le j\le r$ のそれぞれについて、 $m_b/p_j$ が整数となるか調べ、整数ならば $m_b/p_j$ が列のどこに位置するか取得して、その位置 $i$ であって $i\lt j$ を満たすものだけを集めて最大値 $i_{m_b}$ を計算すれば、 $l$ は $i_a\lt l\le \min(i_b,i_{m_b})$ とわかる。 $i_{m_b}$ の計算では、 $m_b$ と制限せず $p_j$ の倍数を全部調べる方法で、 $r=1\dots n$ 全体が調和級数 $O(N\log N)$ で計算できる。

さて、 $r$ を $1$ から順に調べるごとに、累積maxの列の $(m_b,i_b)$ それぞれを見て上のような区間に1足せば、 $r_i=r$ であるようなクエリについて $[l_i,r_i]$ の区間和を求めることで答えがわかる。しかし累積maxを毎回見るのはどう考えても間に合わないため、高速化が必要。ここで、 $i_{m_b}$ の更新回数が $O(N\log N)$ であることに注目する。現在列に存在する累積maxであって更新されたもののみ取り扱えばよさそう。今取り扱わなかったものについては直前と全く同じ値が足されることになるが、その「同じ値」が足される回数は、対応する $i_{m_b}$ が最後に変化した位置（あるいはその累積maxが出現した位置）と $r$ の差で求められる。つまり $r$ の1次式なので、区間和と同様遅延セグメント木に乗せ、取得の際に $x=r$ とすればよい。

かなり大変そうだが何とか書き始められそう。実装したら、コンテスト終了の10分ほど前にとりあえず書きあがった。デバッグも含めると間に合わないかな、と思いつつサンプルを試したら、なんと一発で全部合ってしまった！恐る恐る提出すると通った。これで5完。

システスも全部通って27位、レートは2869→2916(+47)。DとEがかなり通されていて、思ったより伸びなかった。Dは求めたい値が多項式 $f$ に対する $f(k+1)$ だったので、最初から $x=k+1$ として積を取ればよかったらしい。 $n\le 10^6$ で $O(n(\log n)^2)$ を2secは攻めているどころの話ではない。ただ僕が書いたコードはかなり高速だったようで、コンテスト後にいくらかHackの試みを観測したが結局落ちていない。Eは2次元の領域和で解いた人が多い。そちらはよくわかっていない。

OpenCup-Kを解いた。問題文に書いてある表から数値を取り出してコードに埋め込むだけ。コンテスト中に残した読解が微妙な箇所は、僕が考えていたことが間違いだったようだ。経験値を溜めてレベルを上げるとき、特定のレベルで一旦ストップしなければならないと書いてあったのを、経験値をたくさん稼いで一気にスキップできないだけだと勘違いしてやたら面倒なことをしていた。実際は、そのレベルに到達した瞬間未反映の経験値が全部消し飛ぶらしい。端数を管理しなくてよいので簡単になる。

OpenCupのページでは問題文が画像で表示されるため、僕は以下の表を全部手動で埋め込んだ。しかし、実はPDFの問題文も存在するらしい。

OpenCup-K通した。バカが書いた問題文 pic.twitter.com/re72y0NxFU
— こたつがめ (@kotatsugame_t) 2022年5月8日

05/09追記：原神というゲームの経験値テーブルだったらしい。OpenCupでこのゲーム見るの何回目だよ。レベルシステムをちょっと調べてみたところ、途中のレベルでストップしていたのはレベル上限の解放が必要だったからということが分かった。それなら未反映の経験値が全部消し飛ぶのも納得。こういう知識がないとまともに読めないような問題文はカス。経験値テーブルをドンと置いて何食わぬ顔をしている時点でカスか。また、以下のツイートにあるリンク先のテーブルは微妙に異なるようだ。具体的には49Lvにおける値が違うのと、81Lvに80Lvと同じ値が1個挿入され、以降一つずつずれている。

なんか、こんなものをわざわざ問題のために用意するはずがないと思ったらこれが出てきて、これコピペすればってなってたhttps://t.co/M25UIdDSMy
— 有為 (@uwitenpen) 2022年5月9日

朝まで日記を書いていた。今週は微妙に遅れ続けており、今日は土日の部分を書いていた。朝方、ABC-Gの正当性を考えていたら急激な眠気に襲われたので、週記の完成を明日に回して寝ることにした。午前8時半就寝。

2022-05-02

週記（2022/04/25-2022/05/01）

04/25(月)

先週の週記を投稿してから。学食に行って食事し、今日もまた予約していた新刊ラノベを受け取って帰ってきた。そこから1時間インターン関連のコーディングをした。一度寝たら定例会まで起きられないことが分かっているので、寝る前に進めておこうという魂胆。一応少しだけ進んだのでちょっと満足し、切り上げた。後は布団に入ってすぐ寝るつもりが、うっかりハーメルンを読み始め、睡眠時間が1時間ほど減ってしまった。午後1時就寝。

午後4時起床。布団の上で20分くらい意識朦朧としていた。何とか起き上がって定例会へ。今日報告する進捗は朝方の1時間のみで、内容が薄い以外は問題なく終了。

勉強会の内容は数学だった。体であり、全順序を持ち、連続の公理を満たし、 $\{0\}$ でないならばそれは実数体と同型であるという話。そういう実数の構成は初めて知ったので面白かった。ただ微妙に正しくない読み取り方ができる。例えば有限体は要素が有限個しかないのだから、適当に並べれば全順序を入れることができる。それに意味があるかはさておき。調べてみると、「体であって全順序を持つ」の部分は正確には「順序体」である必要があって、その定義には体の演算と全順序の関係が記述されていた。先ほどのような、有限体の演算を無視した全順序ではダメだということ。この演算と全順序の関係を暗黙的に仮定していたか、あるいは自分がひねくれている。

勉強会も終わりかけの時間にコンテストTシャツが届いた。この時間なら確実に起きているということで再配達を依頼していたのだが、自分が勉強会にコメントした直後に来たので非常に危ないタイミングだった。Mサイズだったので自分には少し大きい。ちゃんとSサイズに設定を変えてあるので、なぜMサイズが送られてきたのか謎。しかしよく調べると、このTシャツを獲得したコンテストは「Deltix Round, Summer 2021」という去年の8月末のコンテストだったから、その時の設定で送られてきてしまったのかもしれない。届くのが遅すぎる。

課題を1つ倒し、CF #784 div.4を解いた。全部自明だったので特に問題ごとの言及はしない。一応コンテストリンクだけ貼っておこう。

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

しばらくハーメルンを読んでから、今日の分の日記を書いた。このとき、今朝方投稿した週記のタイトルに日付の終端がないまま投稿してしまっていたことに気づいた。修正しておいたがツイートの文面に名残が残っている。

はてなブログに投稿しました #はてなブログ
週記（2022/04/18-） - kotatsugameの日記https://t.co/eOGAOAqFbh
— こたつがめ (@kotatsugame_t) 2022年4月25日

午前0時半就寝。

04/26(火)

午前5時過ぎに目を覚ましてしまう。うっかりハーメルンに熱中し、午前11時まで布団で読みふけっていた。1作読了、「転生男の娘は道化の海賊を王にする」。

ワンピース二次創作。主人公が副船長という立ち位置であったり、一つの能力で多彩な攻撃が行えたりということから「正体不明の妖怪(になった男)、情緒不安定な百獣の腹心になる」と似たものを感じていた。それの設定が好きだったので、こちらも好き。当然細部は全然違っていて、こちらだと主人公に多少の人間味があって良かった。能力の設定も良い。一か月ほど前にワンピースネタバレがTLに流れてきたが、そこで見た展開がこちらにも盛り込まれていたのも好きだった。主人公が強いと嬉しいから。

布団から出て学食に向かう。今日は麺の気分だったので、それを出す店が開く午前11時半以降を狙っていた。結局出るのが遅れて45分に着いた。もう人だらけで大変だった。正午を過ぎると本格的に昼休みになるため、帰宅時は凄まじい行列を横目に帰ってきた。そのような時間帯にはできるだけ大学に来るべきではなくて、今日のようにギリギリアウトみたいな時間になりそうだったら午後1時になるのを待つほうが良い。気を付けよう。

帰宅してしばらくパソコンを触った後、午後1時半からインターンのコーディングに取り掛かった。昨日、これまで書いたコードをテストするためのデータをいくつか用意してもらったので、それの前処理と、実際に実行してみる部分。手作業で前処理するのはかなり面倒だった。いずれもっと多くのデータでテストするつもりなので、前処理をどのように自動化するかも考えなければならない。

実際に実行してみると、自分が考慮していなかったケースがいくつも見つかって、それの対応も少し行った。エクセルで結合したセルの内容は、結合した領域の左上のマスに入っている。ただ、領域のそれ以外のマスにも内容が入っている場合があって、それを適切に無視しなければならなかった。普通に結合操作を行うとそのようなマスの内容は破棄されるので、なぜこんな状態になっているのかわからない。最初、エクセルで開いても見えない値がプログラムから読まれていて、しばらく頭を抱えていた。

午後3時から1時間1on1。先ほどまでやっていたことを説明しようとして、全く整理できておらずかなりとっ散らかった感じになってしまった。とりあえず一通り話した後、前処理の自動化などについて相談して終了。一段落するまでさらにしばらくコーディングをして、今日は終了。

最近は星街すいせいというVtuberの歌ってみた動画をループして作業用BGMとしていた。するとYouTubeのおすすめに配信切り抜きの手描き動画が出てきて、うっかり視聴してしまった。かなり良い。それにしても手描きとは、熱意がすごすぎる。

しばらくパソコンを触っていたが、今日はもう眠い。午後8時からあーだこーだーに出る予定なので、しばらく仮眠することにした。

僕が登場するあーだこーだーは再来週の火曜日、04/26になりそうだ。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

寝過ごさないようこまめに目覚ましをかけつつ横たわっていたが、午後8時に近づいても連絡がない。自分も眠くてギリギリまで寝ていた。午後8時を過ぎたあたりでchokudaiさんがあーだこーだーの予定を忘れていたことが発覚し、今日は配信しないことになった。来週はGW中で自分が帰省しているので、また再来週以降となる。正直、今日は生活リズムが合っていなかったため助かった。

完全に忘れてたので別日で！ごめんなさーい！！
— chokudai(高橋直大)🍆@AtCoder社長 (@chokudai) 2022年4月26日

そのまま布団でハーメルンを読んでいたら、午後9時半ごろに寝落ちした。

04/27(水)

午前3時起床。明日のセミナー発表のために論文や教科書を読んでいた。午前7時を過ぎて眠気が強くなってきたので、二度寝しようと思って布団に移動。しかしそこからうっかりなろうを読み始めてしまった。昼間までなろうを読んだ後はラノベを開いた。さらにしばらく読んで、午後4時になってようやく就寝。

午後9時、目覚ましで起床。生活リズム的にこのくらいの時間には起きたいと思っていた。しかし実際に起きてみると眠すぎる。もう少し眠りたいと思いつつ、その決心もつかずにしばらく布団からスマホで論文を読んでいた。午後11時になって布団から脱出。

寝る前に見ていた切り抜きをツイート。なぜ切り抜きを見ているのか。しかしこのフニャフニャ感はかなり健康に良かった。

Unlambda -Function Coding-

GWに後顧の憂いなく帰省するため、課題を倒した。今週までの課題と、来週までの課題。来週までのものは講義スライドだけ公開されていて動画はまだないのだが、わざわざ待っていられないので提出してしまった。課題が提出できるようになっているということは、向こうも動画を見ていないくらいで何か言うことはないということだろう。

今日の作業用BGMは星街すいせいの歌枠だった。正直、歌枠という配信アーカイブを作業用BGMにするのは微妙かな。ほとんどの曲を知らないのであまり面白くないというのと、歌を聞きたいのだったら歌ってみたとして作られた動画をループしたほうがいいと感じた。これは生歌がどうこうではなく、後ろの曲がよく聞こえなかったということから。合間にあるトークを求めるのならトークメインの配信アーカイブを使えばよさそう。

ラノベを少し読みつつ、明日のセミナー発表の準備を始めた。結局、今週読んでいた論文を発表するのは諦めて、先週眺めたものから1つ取り上げることにした。用語は教科書で確認できたのだが、事実とされていることが全然わからないし、証明もそこだけ読むのは厳しかった。一方先週のは何とかなりそう。多分。

論文のほうは飛ばし飛ばしで1つを眺め終えた。眺めているだけでは何もわからない、というのはそれはそうとして、別に読めないわけではなさそう。ただ用語がところどころ怪しくて、少なくとも何か参照するべき教科書が必要と分かった。
週記（2022/04/18-2022/04/24） - kotatsugameの日記

結局ずっと歌枠を流し聞きしていたので、ラノベはあまり集中できず全然読み進められなかった。発表の準備は紙に話したいことと話さなければならないことを書き出しただけ。グラフの論文を初めて取り扱うので、一応グラフ周りの用語定義から始めるつもりである。

午前8時半就寝。

04/28(木)

午後1時、目覚ましで起床。寝過ごすと怖いので二度寝は諦め布団から出た。のどが渇いていたのでお茶をグビグビ飲んだらてきめんに腹を壊してしまい、数回トイレと部屋を往復した。

腹の調子が持ち直したところで、セミナーに向け出発。学食に滑り込む。閉店する午後2時の直前だった。そこで食事して、帰省のための学割を発行してから山に登ると午後2時半。セミナーまであと30分ある。こう、学食の営業時間と微妙に噛み合わないのが辛いところ。院生室に友人がいたのでしばらく喋った。

午後3時からセミナー。まず僕の発表について、昨日考えた順番で説明していったつもりなのに説明忘れだったり余計なことを口走ったりして、自分でも一貫した流れの発表になっていないなと感じた。こういうのはやはり自分で一度説明してみるべきだったのだろう。必要な用語をきちんと洗い出せてすらいなかった。黒板の使い方も下手くそで、真ん中のほうに重要なことを書いてしまって、その左右を往復したりしていた。内容はまあ満足。

もう一方の発表は面白かった。面白かったというか次回が面白そうというか。ラムダ計算自体にはあまり触れたことがないが、SKIコンビネータはUnlambdaの経験があるのでそれなりに手を動かしたことがあり、そのパズルみたいな作業が面白かった記憶がある。まあ今日は久しぶりすぎて失敗したわけだが。

\x.\y.\z.x(yz)をSKIコンビネータで書く話。まず\z.x(yz)=S(\z.x)(\z.yz)=S(Kx)yとして、次に\y.S(Kx)y=S(Kx)として、最後に\x.S(Kx)=S(\x.S)(\x.Kx)=S(KS)Kとなる。いやこれだとちょっと不正確か。同じ変数名を使っているところは同じ値に関数適用したい、という気持ちで読んでほしい。関数適用するためには基本的にSを使うしかないのだなあと思い知った。やっていることをよく見ると、Unlambdaを書いているとき参考にしたサイトで紹介されていた方法と同じだったのもびっくり。当時は単純に記号を置き換えるだけで、意味を深く考えてはいなかったか。

午後5時くらいに終了。お腹も空いていなかったので即座に帰宅した。

今日はしぐれういというイラストレーターの配信アーカイブを流しながら日記を書くことにした。聞き流すのに心地よい声だと感じる。と、チャンネルに行ったら、ちょうど今日の午後11時から配信があることに気づいた。試しにリマインダーをオンにしておいた。

pic.twitter.com/pr9uZPuUWv
— こたつがめ (@kotatsugame_t) 2022年4月28日

いくつかアーカイブを渡り歩きながら日記を書き進めていたのだが、全然進まなかった。動画に集中してしまったというよりは、日記に集中できていなかった。何を書くか文章に迷っていた時間が長かったように思う。午後11時になったので配信の視聴を開始した。

鍵RT：
・しぐれういなら大丈夫、配信頻度も多くて週1くらいだし
・配信開始前にコメント欄でういういしてきたって言うんだぞ
・配信前にちゃんと概要欄のルールは読んだほうが良い（悲しみを生みかねないので）
— こたつがめ (@kotatsugame_t) 2022年4月28日

pic.twitter.com/Z8MWKhg6rR
— こたつがめ (@kotatsugame_t) 2022年4月28日

──よし……と pic.twitter.com/657tox2she
— こたつがめ (@kotatsugame_t) 2022年4月28日

……見事に2時間見続けてしまった。その間も日記を書き続けて、何とか今日の分までたどり着けた。

その後またしばらくYouTubeを見た後、ゴミを出して布団に入った。少しラノベを読もうとしたがあまりに眠く、目が滑りまくる。諦めて就寝。午前4時だった。

04/29(金)

午前11時くらいに目を覚ます。

腕が筋肉痛になっていてびっくり。実は心当たりがあって、昨日、院生室に転がっていたダンベルを持ってしばらく腕を動かしていたのだった。やり方がまずかったのだろうか。特に腕を伸ばした時の痛みがひどい。

それはそうと、昨日の睡眠時間的にもう少し寝ておきたいなと思った。そう思いながらもYouTubeを開いてしまい、そのまま眠れなくなった。午後2時半くらいに諦めて起き上がって、布団で見ていた切り抜きから1つツイートした。

今セメスターの時間割をツイートした。一度コマがずれている状態でツイートしてしまったので、消してツイートしなおした。セミナーは対面で行うので教室名を書き入れておきたかったが、よく覚えていないので空欄のままにしてある。数学棟3階はその教室と図書室しか見当たらないので、番号を覚えていなくても間違えようがないのだ。ではその上の「数理論理学特論」と同じ教室ではないのか。しかし、もしそうだとしたら、1部屋しかないのに305という名前がついていることになって謎。

M1春学期さん、対戦よろしくお願いします pic.twitter.com/0AOYzU9V67
— こたつがめ (@kotatsugame_t) 2022年4月29日

本当は今日ゲーセンに行くつもりだった。月曜から帰省する予定なので、仙台にいるうちにチュウニズムを1度プレイしておきたい。イベントの終了が近付いている。しかし天気が悪いのと、中途半端に眠気が残っているのと、先ほども述べたように腕が痛いので見送ることにした。再度布団に戻り、しばらくラノベを読んで就寝。ちゃんとラノベをそばの机に置いたので寝落ちしたわけではないが、就寝報告のツイートをしておらず、またChromeの閲覧履歴からも復元できないため、時刻は不明。午後6時前ではないかと思う。

04/30(土)

午前1時起床。ハーメルンからVtuberものでまだ話数が少ない作品を2作読了。

「TSして人生やり直すことになったのでVtuberやる」。逆行転生して世界初のVtuberになるやつ。5話で幼少期の努力から準備まで完了してテンポが良かった。似たような作品の「逆行転生したおじさん、性別も逆転したけどバーチャルYouTuberの親分をめざす！」は11話だったので、どちらにしても多少短いくらいが過去の厚みとしてちょうどいいのかも。活動開始後の配信の内容、また登録者を増やす過程はそれとはまったく違った感じで楽しめた。いずれにしてもバズらないと大変なんだなあと感じた。

「秋宮ゆららは青を喰む」。序盤はかなり闇が深そうなことが書いてあるが、現在更新されている分では特に何事もなく安穏と活動している。キャラたちの関係性は楽しめたものの、その闇がこれからどう関わってくるのかちょっと気になってしまう。

その後ラノベを1作読了。「王様のプロポーズ」2巻。今巻には展開やシーンとして僕にぶっ刺さるような箇所がなかったため、ちょっとがっかり。もちろん、細かく散りばめられたギャグはどれも面白く、ずっと笑いながら読んでいけた。しかし全体を振り返ったとき、あのシーンが良かったなあとか、この展開は僕好みだなあとか思うところがなかったということ。主人公があまり活躍しなかったのが残念。ラストで、この本が構成としてなかなか粋な演出がされていることに気づいて興奮したが、これはfunnyではなくinterestingである。

午前7時、再度就寝。次に午前11時起床。布団でしばらくYouTubeを見た後起き上がった。

今日はコンテストもないし、天気も良いので絶好の外出日和。ただ1点まだ腕が痛むのが気になるが、無理を押してゲーセンに行くことにした。ついでに帰省のための切符も買う。GWに入ってみどりの窓口が混んでいるみたいな話を聞くので、当日買うのでは時間がかかるだろう。窓口でコミュニケーションに失敗しないよう買う切符を文章にまとめて、必要な金額も大まかに計算しておいた。

自転車で家を出発。二郎ラーメンの店の前を通ったら、近くの交差点まで続く列ができていてびっくり。こんな混むなら駅前の人混みは酷いだろうなと思いつつ進み、つけ麺屋で食事して仙台駅へ。確かにペデストリアンデッキは人まみれだったものの、みどりの窓口はガラス戸の中に入れるくらい人が少なく助かった。20分弱並んで無事購入。ゲーセンに移動。SEGAがGiGOになっていて面白かった。

誰よその女！ pic.twitter.com/pNYDA87pN6
— こたつがめ (@kotatsugame_t) 2022年4月30日

午後3時から閉店までチュウニズムをプレイ。8時間半で実に47クレ使ったらしい。今日は理論値8、14+のSSSが1、SS+が1、そして15のSSSが1つ。15は他にも2つほど伸びた。

まず理論値について、前から1クレ3曲全部新規理論値ということをやってみたいと考えていて、今日はかなりいいところまで行ったのだが、緊張に負けて1つ出してしまった。また今日はVtuberのオリジナル曲もいくつか出そうとした。特に星街すいせいの「自分勝手Dazzling」を狙ってみたのだが、信じられないくらい難しい。どこででも出る。かっこいい曲ではあるのだが、リズムが取りにくかったり音が少なかったりで、音ゲー向きではない。

1クレ全部新規理論値……失敗 pic.twitter.com/FW7D9dXGMU
— こたつがめ (@kotatsugame_t) 2022年4月30日

「TiamaT:F minor」のSSSを出した。狙ったのは今日が初めてだが、ゲーセンに来るたびにプレイしてはいた。いつの間にか後半はそれなりに通るようになっていたので、問題は前半。譜面を見て運指を組んだらシュッと出た。運指を組むといっても擦りの手順を覚えるくらい。気を付けるポイントとしては、五鍵は思ったより遅いこと、後半のフリックとタップ＋エアーの忙しい箇所は無闇に手を速く動かすのではなく、ちゃんとフリックが取れるよう大きく動かすこと。

TiamaT:F minor SSS pic.twitter.com/9dlYyy3Zxw
— こたつがめ (@kotatsugame_t) 2022年4月30日

ここはよくわからない。数個くらいアタックを出してよいので安定する運指を、と考えたらこうなった。やってみた感じ、ミスはあんまり出ない気がする。直後の両手トリルはいつの間にか普通に押せるようになっていたので感動した。それ以外にも押そうとしてみたら案外行ける配置が多く、自分の成長を感じた。

いつもの立ち食いそばではなくラーメンを食べた。呑み屋街はあり得ないくらい人がいた。日付が変わってから帰宅。

疲れ果ててパソコンの前から動けなくなり、しばらくYouTubeを見ていた。

かわいいの権化みたいな咳でめちゃくちゃ健康にいい。「○○助かる」とコメントしている人の気持ちが分かった気がする。我々ばかり健康になっても意味がないので、しぐれういさんにもぜひ健康でいてほしい。

咳をしてもかわいい（尾崎放哉）
— こたつがめ (@kotatsugame_t) 2022年4月30日

シャワーを浴び、布団に入ってカクヨムを開く。眠気に耐えつつ更新分を読み、午前4時就寝。

05/01(日)

午後1時過ぎ起床。YouTubeを見たりカクヨムを読んだりした後、OpenCupまでの間に二度寝できないくらいの時間になって布団から出た。

Square packing in a square - Wikipedia

「ふ～許せん！」が好きすぎる。好きすぎて元動画でしばらく探していた。35分10秒くらい。「お茶を飲んで落ち着くね」と言ってしばらく静かになった後、怒りの吐息が漏れ出すところからマジで可愛い。どうなってるんだ。吐息助かりまくり。僕が一人で勝手に助かるだけ。

昨日サークルの活動日が決定していた。今セメスターは月曜午後4時半から。これは僕のインターン先の定例会と完全に被ってしまうため、参加が不可能になった。日程を決めるアンケートに票は入れていたので、やむなし。まあ4月中まったく参加しなかったので、日程が合っていたとして定期的に参加するかは微妙か。新歓に顔を出せなくなったのはちょっと残念かな。~~何気に対面の新歓で新入生を迎えたことがないため。~~M1とかいう老人に迎えられてもお互い困るか。

2022/05/04追記：大嘘。2019年は対面で新歓を行った。複数人が同時にテキストを編集できるツールを使って画面共有みたいなことをしながら、ABCの問題を解いた記憶がある。

4月が終わったので、読書記録をツイートした。今月は先月にもましてネット小説にメタメタにされてしまった。ここでちょっとネット小説もカウントしてみよう。いつの間にかカクヨムでは自分が読んだ文字数が記録されるようになっていて、確か最後に見たときは230万文字くらいだったはず。これに加えてハーメルンでも150万文字くらい読んでいるので、文字数ベースでは500万文字くらいになるだろうか。全部ラノベに割り当てると考えれば、2019年4月に記録した月40冊ペースくらいになりそうとわかる。ところで、カクヨムが公式でデータを出してくれるのは大変ありがたいが先月分が見れないのは困る。

4月の集計
買った：24冊
読んだ：6冊
積読：+18冊
積読（累積）：+33冊
— こたつがめ (@kotatsugame_t) 2022年5月1日

食事して午後5時からOpenCup。

Aを読んだら自明二分探索だったので慌てて書き始めた。 $\lfloor H/M\rfloor\times\lfloor W/M\rfloor\ge K$ を判定する。しかしよく考えると誤差が怖い。幸い $K\le 10^9$ なので、境界ギリギリでは浮動小数点数でも十分表現できそう。念のためlong doubleを使って書いたら通った。少ししてHとJがポンポンと通された。

2022/05/04追記：Aは自明ではない。より正確に書けば、 $H\times W$ のシートから同じ大きさの正方形を $K$ 個切り出すとき、正方形の1辺の長さは最大いくらにできるか？という問題。特に $H=W$ の場合、有名な未解決問題になる。問題文のどこを探してもそのようなことは書かれていないが、縦と横にしか切れないという制限を勝手に設けて解くと上に書いたようになる。いわゆるバカ発見器。恥ずかしい。

これ見て一般解あるわけなくね？って言ってた pic.twitter.com/cR6bCXYm6D
— のいみ (@noimi_kyopro) 2022年5月1日

しばらく時間が空く。Eは単なるBFSで解けそうという話になったので書いてもらっていた。しかし題意の微妙な違いに大変苦労したらしく、コンテスト開始2時間で通った。その後すぐC問題が通された。実験してエスパーしてOEISだったらしい。その後、僕がGを書き始めた。この時点でまだ提出すら1つもなかったが、やればできそうに見えた。

値または値への参照を持つ変数と、それらを引数に取る関数を宣言する構文が定義されて、借用チェッカを実装しなさいという問題。問題文がカス。例えば、値を持つ変数は一度使うと無効化される一方、参照を持つ変数は使っても無効化されないらしい。また、ある変数の値が書き換わった瞬間、以前の値への参照もすべて無効化されるらしい。この2点は問題文中のどこにも書いていないため、clarを投げた。Rustと言っておけば伝わると思うなよ。また関数名のダブりについても確認して、これらをはっきりさせたら、あとは構文解析。関数シグネチャをチェックした後、そこで使われた変数を一つ一つ見て無効化されていないか確かめる。値の無効化時にそれへの参照も全部無効化していいので結構楽だった。変数に変数を代入するのは注意が必要。a:=&aとすると、これ自体はvalidな文だが、aが指す値はすでに無効化されたとみなされるらしい。サンプル2にあって助かった。さらに適当な変数bを経由してこのように代入される場合もあって面倒だった。1ペナ吐いて、3時間22分時点で通したのが全体で2番目だった。

何やら誤読していたらしいIが通ったのを横目にDを考察。二分木のrotate操作で木を平衡化できれば解けそうとなって、splay木のライブラリを持っていたチームメイトに実装を託してBに進み、何もわからず終了。Dもバグらせてしまったらしく通らず、7完で16位となった。なかなか調子が良かったように見える。まあ自分は自明のAとカス問題文のGしか解いていないわけだが。他に通った問題の考察をちっとも追っていない。

しばらく日記を書いて、午後11時半からCodeChef、May Cook-Off 2022 div.1。

https://www.codechef.com/COOK141A

TRIPLE_INVSで人生終了。自明なのにうっかり復元しようとして30分をドブに捨てた。何とか書きあがってからサンプルを見ると出力例にYES・NOしかなく、さすがに声が出た。自分のコードの出力部を消してAC。この時点で100人近くのsolvedがいて目の前が真っ暗になった。DIFSUBARRAYSは同じ値をまとめ、出現回数の降順に並べたものと、それの先頭から一番出現回数が多い値（のうち一つ）を全部後ろに回したもののペアだけを解の候補とすればよい。これでダメなケースは、過半数が同じ値か、または同じ値が $N/2$ 個ずつあるか。前者は明らかにNOで、後者も同じ位置に同じ値を置いてはいけないことを考えればNOとわかる。

SPLITPOWOF2はdp。集合の和の差（ただし常に正とする）を考え、下の桁から見て、繰り上がりを次元に持ってみる。繰り上がりが $i$ 個ある場合、 $i\ge 1$ ならその次への繰り上がりは $0$ 以上 $\lfloor(i+A)/2\rfloor$ 以下のどれでもOKであるとわかる。 $i=0$ の場合は $0$ 以上 $\lceil A/2\rceil$ 以下で、 $A$ が奇数の時は操作回数に1加えられる。これらを見ると、繰り上がりの範囲の代わりに上限だけ考えて遷移してもよいことがわかる。遷移時に2で割って切り捨てるのが難しいので、逆に $i$ を取得するときに $2i$ と $2i+1$ を両方見るようにすれば、各 $i$ に対して $0\le A\le B$ での遷移が区間和で書けるようになる。imos法で実装。状態数 $2\times \max B\le 10000$ 、遷移回数 $N\le 5000$ で不安になるが、普通に書いたら0.43secで通った。

MAXMINCRCDIFは解けなかった。ソートした後 $(A_i,A_{i+N/2})$ みたいなペアを適当に入れ替えて並べればよいのではないかと思い、それっぽいものを実装するもWA。その後 $n=9,10$ での実験を経てこのエスパーは正しいことが分かったものの、入れ替えと並び替えの規則性が全く掴めず、いろいろな方針を試してみるも大した進展はなくコンテスト終了。3完。1問目があり得ないくらい遅かったにしてはまあまあ耐えて23位、レートは2654→2628(-26)。

朝方、日記を書きつつカクヨムを1作読了。「煽り系ゲーム配信者（20歳）、配信の切り忘れによりいい人バレする。」。かなり面白かったがもうちょっと視聴者とのプロレスを描いてほしい気持ちになった。最近の更新分はリアルの話が多め。また、主人公がさすがにいい人すぎる気もする。これで煽り系をやっていたとなると近いうち心の健康を損ないそう。まあそういう作品なので仕方ないか。

https://techful-programming.com/faq/problem#q2

今週はコンテストが2回しかなく、文字数は最近のものと比べると控えめになった。とはいえそれらが日曜日に集中した結果それなりに時間を使い、今、ここまで書いて午前6時。明日が帰省で、できれば午前9時発の新幹線に乗りたい。ヤバい。一瞬諦めてカクヨムを読んでしまったのが響いている。書き上げて推敲のため読み直していたら午前6時半。あ～あ。

2022-04-25

週記（2022/04/18-2022/04/24）

04/18(月)

04/17 午後11時半ごろ起床。ちょうどCF div.2が始まったころだが見送った。

すぐ日付が変わって、TCB46の結果が出た。3位と1点差で2位。1位とはかなり差を付けられていてショック。問題ごとの減点を見返してみるに、やはり2度以上提出するのが大きく響くようだ。スコアの計算式を改めてよく見ると、まず提出回数によって基本スコアが減らされて、さらにそれを元にボーナス2種類が計算されているらしい。つまり得点全体を減らしているようなものなので、影響が大きいのも納得。

ちょっとカクヨムを開いたらかなり面白い場面で、そのまま午前1時半まで読んで最新話に追いついた。「自作3Dモデルの素材を宣伝するためにVtuberになったら予想外に人気出てしまった」。

Vtuberではなく中の人とその周囲をメインに描いている。複雑に絡み合った人間関係が徐々に明かされて行って、そのこんがらがった様子がかなり面白かった。Vtuberと中の人の関係は一般に秘密にされるということも効いている。一方配信活動の描写はそれほど力を入れていなさそうで、その分特に大きなイベントが起こったりもしない安定したVtuber活動が見れるのは安心感がある。以上がVtuberモノとして見た時の感想。他に、主人公がめちゃくちゃ鈍感なのが僕の好みだった。女性に粉をかけられているのに全然気づいていない描写など最高にニヤニヤできた。

そこから午前4時半くらいまでは別のカクヨムを読んだりハーメルンを読み返したりしていた。いい加減二度寝するのを諦め、布団から起き上がって食事した。

ちょっとコードゴルフをしたところ、提出制限が「2つ前の提出から5分間提出できない」になっていることに気づいた。以前は間隔が1分間だった。一応、1つ前の提出からは相変わらず5秒でよいようだ。これは先週の週記でも触れた、無限ループを延々投げられることへの対策だろうか。5分だとさすがにちょっと辛いので、コンテスト中だけでも制限が弱まったりすると嬉しい。

かなり久しぶりにラノベを1冊読了。「男子だと思っていた幼馴染との新婚生活がうまくいきすぎる件について」。至って普通のラノベではあるのだが、上流階級出身でお見合いでヒロインと結ばれるという設定と、幼馴染だったヒロインを昔は男子だと思って接していたという設定が、それぞれ同レーベルの現在売れている別作品と被っているのが気になってしまった。まあ前者はお見合いをする必然性からどうしても入ってしまう設定か。似たようなことを、その別作品を読んだ時にも考えていた。後者に至ってはタイトルからわかることだし……。内容としてはラストで祖母との確執がスムーズに解決するのが良かった。

作中では結婚可能年齢が男女とも15歳に引き下げられていた。あと、登場人物が軒並み名家の御曹司・令嬢だった。この2つの設定はどちらも単独で主人公がお見合いをすることの理由になりうるが、2つ合わさっても別に最強には見えない。その設定両方いる？
週記（2020/11/30-2020/12/06） - kotatsugameの日記

先週遅れて課題を提出した講義に、その課題の講評が投稿されていた。そこに僕の回答も紹介されていて嬉しくなった。真偽が明確に定まる文を自分で作り、その真偽を判定せよという問題。定義があいまいな事物を持ち出したり、断りなく変数を導入したりした回答がダメ出しされていた。さらに真偽の判定についても、例を挙げるなら具体的でなければならないということを突っ込まれていた。一方、僕の回答である「『この課題を遅れて提出した人がいる』は真である、何故なら自分がそうだから」は完璧だったらしい。

すでに期限が過ぎた課題を見つけた。今週分のようだ。遅れると1日ごとに点数が引かれていくシステムだったので、慌てて提出しておいた。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

昼前まで先週分の週記を書いていた。完成させて投稿、さらに今日の分の日記を少し書き進めもした。また、上で触れた講義の今週分の課題を提出した。そうやって時間を過ごし、いい感じに昼休みが終わったのを見計らって学食に行って食事。予約していたラノベを受け取り、床屋にも寄ってきた。

帰宅してから1時間ほどかけ、「研究倫理教育」という大学院ガイダンス時に貰ってきた書類に書いてあったものをこなした。ネットでテキストを読み、選択問題の小テストを解く。もう全然やる気がなくてテキストはまともに読んでいなかったが、小テストはそれっぽい選択肢を常識に基づいて選ぶだけでそこそこ正解できた。合格点に届かなかった場合も、解答を確認した後即座に再挑戦できて、今度も問題の並ぶ順番がシャッフルされるくらいの違いしかないので、覚えておけば簡単。

今週は午後4時からインターン先の定例会。普段より30分前倒しになっていることに気づいておらず、予定アプリの通知が来なかったら危なかった。先週の分の進捗報告は本当にみそっかすみたいな内容しかなくて、自分で振り返りながら唖然としていた。一体自分は先週何をやっていたのだろう。まあ僕のうっすい報告以外は特に何事もなく、勉強会まで終了。勉強会では思わぬところから圏の話が出てきて、その枠組みで取り扱おうという気持ちすら全然わからなかった。

健康診断のため、ライフスタイル調査というものに答えていた。食生活に関する質問で、朝昼夜のどれをよく欠食してしまいますかだとか、間食・夜食はどれくらい摂りますかとか聞かれた。これは非常に難しい。そもそも朝昼夜という枠組みで食事をしているわけではなく、お腹が空いたら食べるということを繰り返しているから。時間帯も深夜が多く、何とも言えない。食べた順番に朝昼夜か？その場合、間食は原理的に発生しなくなるが、よいか？深く考えても仕方ないと思ったので、適当に朝食にしておいた。そういえば、「朝ごはんを食べると一日元気に過ごせますよ」とは、起きてからすぐ食事すればよいという理解でいいのだろうか。

日中耐え難い眠気がありますか→日中は寝ているため、ない
— こたつがめ (@kotatsugame_t) 2022年4月18日

定例会が終わってから少しラノベを読んでいたのだが、あまりに眠くまともに読み進められないため、とっとと寝てしまうことにした。ただ、布団に入ってからもうっかりハーメルンを読むなどしていた。午後9時就寝。

04/19(火)

午前2時半ごろに起きていた形跡がある。午前3時にはまた二度寝できたようだ。次に、午前7時半起床。

ハーメルンで1作読了。「ディストピアゲーに転生したら行政側だった件について」。連載が始まったばかりで10話しかなく、一口サイズ。内容はかなり面白かった。ワクワクする設定が大量に散りばめられている。

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

起きて、健康診断の予約をした。そのまましばらくパソコンを触った後外出。まず原付に乗って生協に行った。以下で言及した教科書が届いたらしいので、それとラノベ1冊を受け取り、あとはミールカードを使い切るためお菓子や飲み物を買って帰宅。またすぐ、今度は自転車に乗って街のほうに出た。

ゲーム理論の講義を取ったのだが、これは教科書が指定されていて、来週からその演習問題が課題として出るようだ。今のうちに手に入れておく必要がある。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

今日はゲーセン。食事を挟んでちょうど40クレ、実に9時間ほどプレイした。アップデートで追加された新曲を埋めていた。今日はかなり上手で、低難易度を埋めていた時に初見AJを10連続で達成した。しかも初見理論値を3譜面含んでいる。特にカウントもできていないが、Lv.14までの新曲は全部99AJを出したはず。

10連続初見AJ pic.twitter.com/N67tvx2Oe9
— こたつがめ (@kotatsugame_t) 2022年4月19日

14+はまだ埋め切れていない。頑張って初音天地開闢神話のAJを出した。レートの最高値も16.93に上がった。プレイする度に赤が増えていく。それでも99AJを達成できる精度くらいなら頻繁に出ていたのに、いざAJする時だけギリギリ足りなくなってしまって悲しい。毎回毎回アウトロが苦手で、この時も2個出して絶望していた。

初音天地開闢神話　AJ！！！
99AJ欲しかった…… pic.twitter.com/9cFm0J6JZ1
— こたつがめ (@kotatsugame_t) 2022年4月19日

時間は前後するが、午後4時半ごろに食事した。油そば。大盛300gという記述を見て、朝にパンを食べたきりだから余裕かなと思っていたのだが、僕が注文した太麺の商品は大盛が400gになるらしい。食べている最中にそのことに気づいて、一気に満腹になったような気分を味わった。何とか腹に押し込んだ。麺が硬かったので、300gも400gも体積はほとんど変わらなくて、密度の違いが表れているのだろう。

朝早く起きたので眠気もあり、疲れ果てながら帰宅。買ってきたプロテインの写真を撮ってツイートした。これまでバニラ味とココア味を食べたことがあって、バニラのほうが好みだったので大袋で購入。蓋つきの容器に入っているプロテインは300g弱で2000円ちょっとする一方、大袋だと1000gを超えるのに価格は5000円と、めちゃくちゃ安くなってびっくりしてしまった。一体なぜなのだろう。

ザバスざます pic.twitter.com/QFkE3sUiy0
— こたつがめ (@kotatsugame_t) 2022年4月19日

先週、あるアカウントがABC248-Exに無限ループを延々投げ続けるということがあった。今日のこの時間にまったく同じことがVjudgeを経由して行われていた。AtCoderはノックアウト形式ではない、つまり一度ACではないとわかっても変わらず以降のテストケースを実行してくれるし、TLEは念のため後2回実行されるしで、こういう攻撃には他のコンテストサイトより弱くて大変そう。

We have detected a malicious source code submission to atcoder via “Vjudge” and have temporarily frozen Vjudge.
— AtCoder (@atcoder) 2022年4月19日

午前10時くらいにABC248に提出するとめちゃくちゃジャッジが詰まっていて、何かと思って全体の提出を見ると、Ex問題に延々無限ループを投げ続けているアカウントがあった。
週記（2022/04/11-2022/04/17） - kotatsugameの日記

シャワーを浴びたら少し目が覚めたので、コンテストに出ることにした。午後11時半からCF #783 div.1。

Aは250点がつけられており、瞬殺しなければならないという意気込みで臨んだ。 $b$ はどこか1か所で必ず $0$ になるべきなので、その位置を全探索する。すると残りは左右それぞれ貪欲で良い。一応、値があまり大きくならないことも確かめた。素直な考察で解けて安心。Bは難しい。まず考察として、総和が正にならない連続部分列は1要素ごとにバラしても損しないことがわかる。あとは総和が正になる場合。累積和を座圧してインデックスにしたセグ木があれば、1点更新区間MAXで貰うdpが計算できそうだな、しかし $n\le 5\times10^5$ だしちょっと不安だな……と思いつつTLを見たら、なんと4secだった。これに気付いて、解法が正しいことの確信を得た。

Cは実験。まず、他の駒を飛び越えてよいのか気になったが、代わりに飛び越えた駒が移動すると考えればよいことに気づいた。左上から埋めていく枝刈り全探索を書いて回し、出力を図に書いてみると、何となく構造が見えた。左上に駒を固めて置いて、縦横の移動で行と列をある程度潰し、最後に残った長方形領域を斜めの移動で潰す。どのような置き方をしても残ったマスは（間隔の空いた）長方形みたいな形をすることになるので、この考え方は不変。残る長方形を効率よく埋めるにはできるだけ固まってくれたほうが嬉しいので、左上に駒を固めて置くのもそう決め打ってよい。駒を $k$ 個置くとすると、残った長方形は縦横 $n-k$ で、対角線の本数 $2(n-k)-1$ は $k$ 以下である必要があるため、逆に $k\ge \lceil(2n-1)/3\rceil$ とわかる。実験の範囲では、この下限が達成できているようだ。

あとは、それを満たすような構築を探る。 $k$ が奇数の場合が一番ギリギリなので、それをいろいろ試してみると、右上から左下の向きの線を2本引く感じに置けばよいことが分かった。それぞれ $(k+1)/2$ 個と $(k-1)/2$ 個で、縦横が被らない範囲で詰めて置く。 $k$ が偶数の場合は、 $k\leftarrow k-1$ の場合の構築をした後 $(k,k)$ に置けばよい。念のため $n\le 1000$ を全部試してから提出した。

Dは当然難しい。そもそも眠気が強くなってきて、考察しながら意識を飛ばしそうになっていた。しばらく考察して、頂点の次数に着目するといい感じなことに気づく。次数は、最初の時点での偶奇により、偶数→奇数の変化の回数と奇数→偶数の変化の回数がそれぞれ固定できる。この変化が辺の両端点で一致するときにその辺を削除できる。木dpすることを考えると、変化のどちらが余っているかを状態として持つことになりそう。dpした後もう一度dfsすることで復元も可能に見える。書いて、2ペナかけ残り10分時点で通った。復元するときに操作列を連結する操作が必要になると思ってlistのマージテクを書いたのだが、うっかり片方を反転してしまう実装になっていたのが1ペナ。実際は操作列を後ろに伸ばすことしかしないので、完全に無駄な工夫だった。

4完49位で2881→2887(+6)。結果的には出てよかった。

午前2時から日記を書き始めた。途中で昔読んだハーメルンを読み返したりしつつ、午前5時くらいに切り上げて布団に移動。そこからハーメルンの更新を読み始めたが、耐えられずすぐに寝落ちした。

04/20(水)

正午くらいに起床。

そのまま布団でハーメルンを読み、1作読了。「解説の宮永さん」。原作は少しだけ読んだことがあるはず。その内容の記憶はないが、面白かった。主人公が強いので。相手の能力に対するメタの強さというのもまた一味違った無双で良かった。

この作品の「読者層が似ている作品」から別のハーメルンを1作読み始めた。午後5時くらいに寝落ち。

04/21(木)

04/20 午後11時半ごろ起床。水曜日がほぼ終わってしまっている。先週木曜日、先生からグラフ理論の論文を紹介してもらって、次の次の週に少しセミナーしてくださいということを言われていた。つまりまだ1週間猶予があるわけではあるが、それにしても1週間読んでみてどんな感じだったかは言えるべきだろうし、もし手も足も出ないほど難しかったらそのことを伝える必要があるので、今週のうちにある程度読んでおかなければならなかった。ということでスマホにPDFをダウンロードし、ハーメルンと交互に読み進めていた。

午前6時に再度入眠し、午前10時に目覚ましで起床。それからもまた同じことをしていた。論文のほうは飛ばし飛ばしで1つを眺め終えた。眺めているだけでは何もわからない、というのはそれはそうとして、別に読めないわけではなさそう。ただ用語がところどころ怪しくて、少なくとも何か参照するべき教科書が必要と分かった。

午後1時に布団から脱出。とりあえず学食に行って食事し、予約していたラノベを受け取って一旦帰宅。荷物を置いて、今度は山に登った。

今週は、博士課程の留学生の方が研究していることについてセミナーしてもらうという内容。もうめちゃくちゃ大変だった。まず英語が聞き取れない。統計学の話のため語彙が全然なかったことが一番の問題じゃないだろうか。数式をいろいろ書いてもらい、ようよう理解していくような形だった。そんなことをしていたら当然発表は先に進まず、先生の指示でかなり序盤のほうで切り上げることになり、最後は線形代数に関する単純な事実を一つ確認して終わった。これについても学部時代の知識がほとんど抜けており、大変苦しんだ。

院生室に寄ると人がいたので、一緒に学食で食事し、路上で1時間ほど駄弁って帰宅。即座に布団に入り、午後8時半就寝。

04/22(金)

午前2時半起床。ハーメルンを読み続け、1作読了。「プレイしていたゲームの能力で転生するやつ」。

Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） - AtCoder

「魔法先生ネギま！」は途中まで読んだことがある。大変面白かった記憶。ではなぜ途中で止まっているかというと、その漫画が自分のものではなく、途中から自分で買う気力もなかったため。中途半端にしか内容を知らないので、二次創作を読むのを微妙にためらっていたのだが、ついに手を出してしまった。こちらもめちゃくちゃ面白かった。設定としては、オリ主が大量の別ゲーキャラの能力をネギま世界に持ち込むといういかにも地雷っぽいものである。しかし原作キャラとのバランスが良かった。オリ主が当然強い一方で、原作で強いキャラも強いままに描いてくれている。

そのあとPixiv小説やノクターンノベルズをいくつか漁り、午前8時くらいに起き上がった。YouTubeを見たりカクヨムを読んだりしていたら午前11時。学食に行って食事し、予約していたラノベを受け取って帰宅。

食事 pic.twitter.com/UKU66VG9rF
— こたつがめ (@kotatsugame_t) 2022年4月22日

昔、個数制限なしナップサック問題の解って言われたことがある
— こたつがめ (@kotatsugame_t) 2022年4月22日

「個数制限なしナップサック問題の解」と言われた。
週記（2021/05/10-2021/05/16） - kotatsugameの日記

帰宅して即座に布団に倒れこむ。しばらくラノベを読んで、午後1時就寝。

04/23(土)

04/22 午後11時起床。ラノベを2冊読んだ。

1冊目、「鴉と令嬢」。面白かった。主人公が強くて嬉しい。学校では実力を隠していて、さらに嬉しい。テロリストが襲ってくるシーンがあって、1巻から隠された実力が明らかになるかと思ったが、今回は陰からのサポートにとどまった。どのタイミングでどれだけの人に実力が知れ渡るのか、以降の展開が楽しみ。またヒロインに学校で声を掛けられて目立ってしまうシーンも好み。様々なラノベで使われるだけの良さがある。

異能強度という10段階の指標が用意されていた。これの分布についてはちょっと疑問が残る。下から3段階に7割がいて、下から6段階では9割になる。一番上の段階は0.00001%らしい。正規分布の上側だけで考えれば、順に $0.5\sigma$ 、 $1.3\sigma$ 、 $5.2\sigma$ くらいで、間隔がよくわからない。また、上から4段階までの人間は1割もいるのに希少と言っていたのも正しくは見えない。その位置にいるヒロインに訓練の相方が見つからないという描写があったが、複数クラス合同の授業でそのレベルの人間が1人しかいないということはないだろう。ただ、冒険者ランクなどの分布に言及している作品で感覚的に正しいことを言っているものを読んだことがないので、仕方ないのかもしれない。

この作品はカクヨムコンの受賞作らしい。ということはカクヨムで探せば続きが読めるのでは？と考えてコンテストページを確認して、もとになったものを見つけた。しかし1巻分しか連載されていないようだ。残念。いや、最近こうやって見つけたネット小説に時間を吸い取られることが多かったから、そうならなくてむしろ良かったのかもしれない。ところでこの作品は書籍化に当たって改題されていて、もともとはネット小説にありがちなあらすじそのままのタイトルだったらしい。シンプルなタイトルからあらすじタイトルへの改題はよくTLで話題になっているが、逆は初めて見た気がする。知らなかっただけか。

2冊目、「俺は星間国家の悪徳領主！」5巻。相変わらず良かった。ただし何が良かったのか言語化するのが難しい。設定とキャラがめちゃくちゃ気に入っているから当然好き。仕方がないのでこの巻で好きだったシーンでも挙げておこう。やはり第七話「剣聖」とその前のバトルシーンだ。主人公が存分に無双しているのは読んでいて楽しい。

さらに別のラノベを開いて少し読んだ後、午前10時に就寝。次、午後4時半に生協の弁当を受け取るため起きて、そのあと二度寝できなかった。ハーメルンやカクヨムの更新を漁っていると時間が過ぎて、午後7時くらいになって布団から出た。

食事したりちょっと日記を書いたりして、午後9時からABC249。

Aはどう見ても短くはならないので、先にBを解いた。sedで条件を3つ書く。次にAに戻って、とりあえずC++で通すことにした。 $X$ 回ループを回すのが一番簡単そう。以降もC++。Cは「ちょうど」 $K$ であることに気づかず1WA。Dはサンプル3が合わなくてしばらく苦しんだ後、どこにも $(i,j,k)$ が相異なるとは書かれていないことに気づいた。優しすぎ。この場合出現回数をカウントした配列 $c$ を作って、 $c_ic_jc_{ij}$ を $1\le i,j\le 2\times 10^5$ で単純に足し合わせるだけでよくなる。調和級数。

Eはなかなか難しい。適当にdpを書こうとすると、 $X$ の長さと $Y$ の長さを次元に持って、さらに遷移が $O(N)$ になってしまう。ここで遷移をよく見ると区間加算の形で書けるため、imos法で高速化。Fは簡単で、 $t=1$ の操作を決め打って、以降の $t=1$ の操作を全部無視した後 $y\lt 0$ の操作もできる限り無視するのが良い。後ろから計算し、無視できる $y$ の集合を優先度付きキューで管理することで $t=1$ の操作を全部試せる。 $(t_0,y_0)=(1,0)$ という操作を追加すると実装が簡単になる。キューの中身を正しく動かすのに失敗して1WA。

Gは難しい。しばらく考えていると $A_i\times 2^{30}+B_i$ の基底を取ればよさそうなことがわかってきた。 $A$ の上位bitから決めて、あるbitを入れない代わりに残りの基底をどれでも使っていい状態を計算する、というのを繰り返すことになる。最後、 $A$ の総XORがちょうど $K$ になる場合も別で計算しておく。カードを1枚も選ばない状態を検出するのが難しい。まず基底が $N$ 個未満だった場合は、総XORを $0$ にできるので、答えの最小値は $0$ になる。そうでない場合に $B$ も含めた総XORが $0$ になることはないので、逆にそうなったら1枚も選んでいないとわかる。判定の位置をミスしたため1回目にACした提出にはHackケースが存在するが、通った。

Exは全く分からず、7完8位。賞金が得られそうでうれしい。

コードゴルフ。Aはdcで $O(1)$ 解法を書いた。Bはコンテスト中にテストケースハックで少し縮んでいた。大文字と小文字が両方出現することをチェックするとき、大文字と小文字がこの順で隣接していると決め打ってよい。「この順」というのが嘘。CはRubyだと思っていたらPerlで縮んでいた。粗探しして-1B。DはAWKで、カウントのループと答えを求めるループをまとめた。といってもループの最初のほうでカウントして、カウントが終わってから答えを求め始めるだけ。ちょっといじってループ回数を少しだけ減らし、何とかTLEの回避に成功した。以降は手付かず。

午後11時半からCGR20。

Dashboard - Codeforces Global Round 20 - Codeforces

Aはよくわからなかったのでgrundy数で解いた。解説を見たら、操作によらずゲームが終了するまでのターン数が決まるようで、確かに……という気持ちになった。Bは'B'よりも前にある1個以上の'A'と一緒に消すと考え、後ろから見て「まだ'A'とくっつけられていない'B'の個数」を管理すれば判定できる。末尾が'B'でない場合は場合分けで取り除いておく。Cはdpしそうになったが、面倒そうだったのでちゃんと考察して解いた。1回以上操作するなら最後に操作した位置で必ず $a_i=a_{i+1}$ となるので、もともと同じ値が隣接していた位置をすべて含むように操作しなければならない。そのような位置の両端を調べて間を埋めるための操作回数を計算する。調べた値から1回も操作しなくてよい場合も検出できる。

Dは操作を、 $a_r$ の直前に $a_l=a_r$ を挿入すると捉える。両方の数列を後ろから比較していって、異なった場合はこの操作で前から持ってきたことにするか、もしくはそこから後ろに飛ばしたことにするか。前者を優先的に使う。Eはまず $h_w=1$ となるような最小の $w=w_0$ を二分探索で求め、以降は行数を全探索する。行数 $h$ に対しては $w=\lfloor (w_0-1)/h\rfloor$ として $h_w=h$ であることをチェックするだけでよい。もし $h_{w-1}=h$ だった場合、1行にまとめたときの幅が $hw$ 以下と分かって $w_0\le hw\le w_0-1$ になってしまうから。この問題はシステスで結構落ちていて、みんなうっかり $w=0$ でクエリを投げてしまっていたようだった。自分は $h=1$ をスキップしていたので助かった。

F1は簡単。2点swapなので、値たちを頂点とし、操作前と操作後を辺で結んだときの連結成分数を最小にしたい。値ごとの出現回数 $cnt$ を求めると、連結成分数は必ず $\max cnt$ 以上になって、これが達成可能。実装は、値ごとに出現する位置をvectorで持ち、それらの先頭 $1\le i\le \max cnt$ 番目だけを取り出してループにするのが簡単だった。F2は同様の考察から連結成分数が必ずこの値であるか調べればよい。連結成分数がこれより増えるときは、必ず1つ以上の閉路が ${\rm argmax}\;cnt$ を含まないので、逆に ${\rm argmax}\;cnt$ からスタートして同じ値を2度含まない閉路だけで全部の辺を取り切れるかチェックすることになる。よく考えると、これは ${\rm argmax}\;cnt$ に接続された辺を全部削除した後のグラフがDAGであるかチェックする問題になる。

ここまで1時間もかかっておらず爆速で、F2まで通した時点では全体5位だった。その時点ですでにH問題にそれなりのsolvedが出ていたのでGを飛ばすことにした。しかし以降2時間手も足も出ず、そのまま終了。最終的にH問題は100人以上が通したため87位まで落ち、レートは2887→2868(-19)。Eのシステス落ちが結構いて少しだけ傷が浅くなった。

コンテスト中のHの考察について。010...や101...のグループに分割して、左端から貪欲に繋いでいくのがよいと考えていた。ある2つを繋ぐときは、その間にあるグループを先に全部削除しておく必要があるので、繋ぐ関係が交差してはいけない。「現在末尾が0・1のグループが左にあるか」を持つ4状態のdpを書いてみると、遷移が足し算とminの操作によって行列とみなせる（トロピカル半環）ため、これをセグメント木なりに乗せればクエリに答えられる。しかし5ケース目で落ちたまま一生先に進めなかった。ランダムケースを書いてみるも、そもそも正しい答えを計算するのが難しい。誤った考察を元にコードを書き、ランダムケースの出力もその方法で作っていたので、当然それで落ちるわけもなかった。

正しくは00や11の個数に着目して、その多いほう $+1$ らしい。一度の操作ではそれらを最大2つ巻き込むことができるが、00と00を巻き込んだ場合は残った0と0がくっつくので00は1個しか減らず、00と11を巻き込んだ場合はどちらも1個ずつ減る、という考察で示せるようだ。考えもしなかった。

夜中、日記を書きつつハーメルンを1作読了。「とある転生者の遊興日記」。前世の知識で競馬で大儲けする話だと思ったら、あれよあれよという間に雑誌記者になっていた。物語として面白かったが、逆行転生大好き人間としては最初1、2話の雰囲気が良かった分、後半はあまり……。