05/23(月)

日曜日、週記を投稿してからはすぐ布団に入って寝た。午前9時半だった。

午後3時起床。先週の週記に書いたように、今日はこれから大学で座談会に出席する必要があるため、インターン先の定例会で進捗報告ができない。よってスライドだけ作成して、事前に公開しておくことになる。その作業を起きてから行おうとしていたのだが、思ったより遅い時間まで起きられなかった。結構焦っていたつもりなのに諸々確認していたら完成まで30分以上かかってしまった。

急いで準備して出発。原付を飛ばしたら開始の5分くらい前に到着できた。生協に寄っている暇はなかったため、腹を空かせた状態で一時間ほど講演を聞いていた。座談会という名の通りそこそこ緩めの内容だった。細かい証明は明日からの集中講義で触れられるのだろうが、ちゃんと追うのは体力を使いそう。終了後に同級生数人で学食に向かい、僕だけさっさと食べて帰宅した。

家についてすぐ定例会に参加。自分の口から進捗報告する機会もあったので良かった。勉強会では発表後の質疑応答でいろいろ議論が活発に行われ、普段より遅めの時間に終了した。

そういえば、今日が締め切りの課題が2つあるのだった。終わらせにかかる。まずハードウエア基礎の課題で、ダイオードとトランジスタの仕組みを問うようなものだった。特にトランジスタが大変難しく感じられた。講義資料とにらめっこして何とか今日の分は解けたものの、理解はできていない。

次にゲーム理論の課題で、これまで有限個の戦略を扱っていたところ、商品の価格や仕入れする数などで連続的な量を扱うようになった章の内容。表だったりゲーム木だったりを手書きする必要がなくなり、式を適当に弄くり回すことで答えが出るようになって書くのが楽だった。先手と後手のゲームを拡張し先手が親と子に分かれた場合を考察せよという問題があった。ターン数が3になって先手がもう一回行動するということか……？と思っていたが、講義動画をチェックして、親と子も別陣営と見なして先手が2人同時に行動を選択する場合を考えていると理解した。同時手番と逐次手番を組み合わせたゲームを扱おうという意図だろう。

合間で一瞬だけインターン関連の作業、ドキュメント整備をした。前に書いた版では特に意識せずディレクトリという言葉を使っていたのに気づいた。フォルダーと言わないと一般には通じなさそう。

何とか課題を終わらせられたので、午後11時半からECR129に出た。

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

Aは手持ちの最大値を初手で出すのが最適。それぞれの最大値を調べて、先手が後手以上だったら先手勝ちになる。Bはただrotateを繰り返しているだけなので、操作を全部まとめて $\left(\sum b\right)\bmod n$ 回rotateすることになる。Cは一致する値の処理が面倒。先頭からソートされた列を構築していくのが簡単そう。ソートされていない部分の $\min$ をそれぞれ計算して、 $(\min a,\min b)$ というペアを探し手前に持ってくるのが良い。

Dは大変。桁数と出現する数字の集合のペアを状態として達成可能な最大値を求めるBFSをしたら落ち、操作回数を加えてdpに書き直したらpretestは通った。しかし後からHackされた。当たり前で、掛け算した後どのような数になるかが異なるのに状態をまとめてしまってはいけない。正しい解法は、作れる数が $x\times 2^{e_2}3^{e_3}5^{e_5}7^{e_7}$ という形をしていて十分少ないため、普通にBFSするというもの。

D で dp[操作回数][0～9 のうちどの数が現れるか] の bitDP をすると 19 685800 で 14 を答える (13 が正しい)
今 0～9 のうち現れるものの集合が同じでも、何かを掛けても同じであるとは限らないため
— SSRS (@SSRS_cp) 2022年5月23日

Eは面倒。レイヤーの番号が大きくなる方に移動することを考える。「レイヤー $i$ のドア $1,2$ からレイヤー $i+1$ のドア $1,2$ に行く距離」を $2\times 2$ 行列で持つとdpがトロピカル半環上の行列積になるのでセグメント木に乗るといういつものやつ。ドアそれ自体が「レイヤーの間」を表すのに、さらにドア間の移動、いわば「レイヤーの間の間」を扱うため添え字にはかなり注意が必要だった。しかも行列積の単位元を間違えていてデバッグにかなり時間を使った。

Fは全方位木dp。各辺 $(u,v,x)$ について、「 $u$ から見た $v$ の部分木で $v$ から値 $x$ の辺を使わずにたどり着ける頂点」と、その $u$ と $v$ を入れ替えたものが計算できれば良い。適当に根付き木にして、 $u$ が $v$ の親になったとしよう。各値 $y$ に対し「 $v$ の部分木で値 $y$ の辺を使わないとたどり着けない頂点」の数を求めようとしてみると、mapとマージテクで計算できることがわかる。 $x$ に対するカウントを $v$ の部分木のサイズ $c_v$ から引くことで、求めたいもののうち片方は求まった。

もう片方を全方位木dpで求める。最初のDFSが終わったとき、各値 $y$ に対し「根から値 $y$ の辺を使わないとたどり着けない頂点」の数が求まっている。これの根を取り換えながらもう一度DFSする。辺 $(u,v,x)$ を使って $u$ から $v$ に降りる際は、値 $x$ に対するカウントだけ変更すればよい。 $v$ の部分木に限定した値は一回目のDFSの時点で記録しておけて、残りの $v$ から見て $u$ の先にある頂点たちは全部 $(u,v,x)$ を使わないとたどり着けないので、 $n-c_v$ を足す。このテーブルと先ほど求めた値さえあれば答えはすぐ求まる。

最後の $n-c_v$ を足すあたりの考察で、辺 $(u,v,x)$ についての「 $u$ から見た $v$ の部分木で $v$ から値 $x$ の辺を使わずにたどり着ける頂点」が結局「 $v$ から値 $x$ の辺を使わずにたどり着ける頂点」であったということに気づいたが、いずれにしても全方位木dpをするためには最初のDFSで前者の値を求めておく必要がある。

火曜日提出の離散数学の課題も終わらせた。特筆すべきことはない。

朝まで日記を書いていた。布団に入ってしばらくハーメルンを読み、午前8時ごろ寝落ちした。

05/24(火)

午後1時半起床。今朝読んでいたハーメルンの最新話に追いついた。

syosetu.org

「実況パワフルプロ野球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を眺めながらボーっとしていた。

www.youtube.com

そのうち少し眠ってしまったので気合いで起きてシャワーを浴び、ラノベを読み始めた。明日はこのくらいの時間から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。

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

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時だった。土曜日の後半と日曜日の部分しか書いていないのにこれだけ時間がかかっているのは異常。なろうを読んでみたりハーメルンを読んでみたりでかなり頻繁にキーボードを打つ手が止まっていたようだ。集中力がなさすぎる。

kotatsugameの日記

週記（2022/05/23-2022/05/29）