週記（2020/11/30-2020/12/06）

11/30(月)

真夜中（午前零時）、起きる。こんな時間に起きたらまた夕方眠くてしょうがなくなってしまいそう。

chokudaiさんがテレビに出るやつが昨日の夜放映されたらしい。直感的には出演者が全員胡散臭く見える。でも実はまともなことを言っているらしい。自分の偏見がすごい。新しいものがすべて胡散臭く見える。

キッチンに立って食事していたら、器をひっくり返してしまった。飛び散らかり方が微妙で、写真をupするのもあんまりおもしろくなさそうだった。さっさと片付けることにする。

先週の週記を書き上げて投稿。そのあと、AtCoderをしたりPCKを埋めたりラノベを読んだり淫夢実況を見たりしていた。

午前10時くらいにリクルートから電話がかかってきた。11/18の面接に合格したので、次の面接をセッティングするらしい。実は先週の金曜日くらいにも同じ電話番号から電話がかかってきていて、こちらは寝ていて取れなかった。

面接は1回で終わりだと思っていたので、次の面接があることを聞いて非常にびっくりした。結果を聞くだけだと思って飴を口に含んだまま電話に出たが、さすがにまずそうなので一言断ってかみ砕いた。

サインペンと白紙のメモ帳が必要らしい。本来はホワイトボードに書いたりするはずだったのかな。紙に書いて画面越しに見せるという用途なら、サインペンを指定する意味も分かろうというものだ。買いに行かなければならないと思っていたが、念のため部屋にある文房具を調べたところ、存在した。たしか実家に届いた何かの書類に署名が必要になって、書類と署名用のペンを実家から送ってもらったのだったか。

また昼までPCKを埋めていた。学食が閉まりかけたので、久しぶりに行く。生協の営業時間が15時までから17時までに伸びていてうれしくなった。学食は相変わらず14時から16時まで閉まるようだ。家に帰ってきて、また同じ行動を延々繰り返していた。つまり、PCKを埋めたりラノベを読んだり淫夢実況を見たりしていた。

じゃりみちさんのSatisfactory実況が完結した。毎回の更新を楽しみにしていた。始めから終わりまでずっと追い続けた実況シリーズはこれが初めてかもしれない。

Satisfactory、とても面白そう。かなり心惹かれるものがある。やむなくさんがプレイのスクリーンキャプチャを上げているのを見て内心羨ましがっていた。しかし僕は自分自身に家でゲームすることを禁止しているので、あまり深く考えないことにする。大体minecraftもまともに続けられないのに自由度の高いゲームは不可能。

夜、サークルの解説会に出る。今日はABC184。僕は今日は発表しないので、聞くだけ。終わった後にGoogle Driveに使ったスライドをアップロードしてもらったのだが、東北大学から発行されたアカウントで作成したファイルはリンクを作っても外部の人に見せられないようで、僕が個人アカウントで再アップロードすることになった。

解説会でAOJ-ICPCの600点の問題が紹介されていた。解いていなかったのでムキになって解いた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=5024092#1

かなり面白い。発想はかなり天才的であると感じたが、実装要素が多めなのでICPC感もある。

日付が変わる前あたりに布団に倒れこみ、そのまま寝落ちした。

12/01(火)

午前7時くらいに起きる。かなりいい感じ（真人間っぽいという意味）の起床時刻だが、睡眠時間を考えるともっと寝ておきたかった。11月が終わっていてかなりびっくり。11月、30日しかないことで有名。

作業用BGMとしてYouTubeで垂れ流していた音楽がそのままだった。一晩中流れ続けるBPM998。

知り合いの競プロerの作ったスマホゲームがリリースされていた（名前を出していいのかよくわからないのでとりあえず隠しておく）。ここに告知ツイートを貼っておく。

ゴミ出しをしてきた。11月分の読書記録集計をツイートする。今年は毎月やっていたけど、週記で取り上げるのは初めてかもしれない。

1日1冊は本当に難しくて、累積も計算していたらひどくみっともないことになってしまった。来年は「買った本＜読んだ本」を目指します。

面接に関するちょっとしたアンケートに回答する。文章をうまく作れず、かなり苦労してしまった。ちょっとした、とは何だったのか。

PCKを少し進めてsolved 5500問に到達した。ここでいうsolvedとはrating-historyで集計できる分のことだ。

ラーメンズの小林賢太郎さんが引退したことを知った。かなりショック。ショックを受けた状態でいろいろ検索していたら、小林賢太郎さんが東京パラリンピック閉会式の演出を担当する予定だったことを知った。引退しても舞台裏での活動は続けるらしいので、担当を降りるということはないだろう（そもそもそうやすやすと降りれないとは思うが）。ちゃんと注意して観ておきたい。

それにしても、結局ラーメンズの公演には一度も行けなかった。最後となった第17回公演「TOWER」ですら僕が9歳のころだ。母や姉はどれかに行ったことがあるはずだが、どれだったか忘れてしまった。DVDが家にあったのでそれを観て育ったが、DVDに収録されていない公演やコントも存在するし、網羅できているとは言えない。

寝ながら問題を考えようと思って布団に入りハーメルンを読んでいたところ、午後6時くらいに寝落ちした。

12/02(水)

真夜中に起きる。yukicoderのアドベントカレンダーコンテスト1日目の解法をツイートしたあと、Twitterのトレンドに「小林賢太郎」があるのを眺めて感慨にふける。ほかにもいくつかラーメンズ関連のワードが急上昇しているようだ。僕の感覚的にはラーメンズはマニアックなコンビだが、こんなにもたくさんの人がラーメンズを知っているのだと幸せな気分になった。知らない人はYouTubeに公式でコントが100本もアップロードされているので、貪るように観よう。

www.youtube.com

モンスターハンターポータブル3rdの発売10周年らしい。僕の小・中時代を彩った最高のゲーム。CEROレーティングを気にしてはいけない。集会浴場のクエストは友達と行って全部クリアしたが、村クエの最後、「終焉を喰らう者」だけはどうしてもクリアできなかった。そもそも一人で上位個体に挑むような勇気もなかった。集会浴場のクエストはほぼ全て友達と複数人プレイでクリアしていた。

流しっぱなしだったYouTubeの作業用BGMを止めて、もう一度寝た。次に起きたら午前7時だった。かなり長い睡眠をとれて気分がいい。寝すぎたのか、少し頭痛がある。

最近部室が使えるようになったらしいので、活動計画書や感染対策の書類を提出する必要があるようだ。よくわからないので適当にそれっぽいことを書いて提出した。

週記（2020/11/09-2020/11/15） - kotatsugameの日記

これが受理されていたので、今日から部室の鍵を借りられるようになったようだ。結構適当に書いたつもりだが、何も言われなくて安心。ただ、今は部室にWi-Fiも飛んでいないし、部室を使うような用事はないだろう。

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0354/review/5027552/kotatsugame/C++14

左下から右上へ並ぶ1列の白マスに配置された蟻の動きを考える。違う列の蟻は動きに関係しないので、個別に考えてよい。黒マスに配置された蟻は、先に1歩動かしておけば白マスに配置されたものとして考えることができる。

x座標の偶奇で分けて、それぞれ考える。x座標の偶奇が異なる蟻が出会うのは黒マスであるため、互いに干渉しない。

ここまで分類すると、残りは蟻の番号の様子を観察すればよくなる。ここで、盤面を右に45度傾けて考えると、蟻は互いにぶつかり合って交差しないため、番号の順番が変わらないことに気づく。あとは蟻の縦向きと横向きの個体数を数えることで、左から何匹は縦向きの移動で落下する、残りは横向きの移動で落下する、ということがわかる。ぶつかり合う蟻を互いに交差しているととらえるのは蟻本の由来ともなった超有名問題だが、それを援用することで落下する座標が得られるので、スタートの座標を引くことで落下するまでの時間が計算できる。

この問題を考察している最中、うっかりTwitterでゴキブリの動画を視聴してしまい、蟻だったイメージがゴキブリに変化してしまってつらかった。

問題を解いたりラノベを読んだりを繰り返していると、学食が閉まってしまった。そろそろ一度本屋に行っておきたいので、今日外出するのもいいかも、という気分になるが、昨日シャワーを浴びていないし夜はサークルで少し活動がありそうだしで何となく判断を保留にし、そのままラノベを読んでいた。結局家から出られず夕方になってしまったため、今日の外出はあきらめる。明日またチャレンジしたい。駅前まで出て行って、ここ最近とんと行っていない大きめの本屋に足を運びたい。

夜、サークルでこどふぉ #681 div.1のバチャを行う。3完だがペナルティが大量についてしまった。D問題は1時間考えてわからないので解説を読んだ。まず最初のステップ、つまり中途半端に取る数列は高々1つであるということの証明にびっくりした。そんなこと1度も考えなかった。しかしそのあとも難しい。

左と右から累積dp配列を持っておくのがよくある実装だが、左右のマージにO(K^2)かかって間に合わない。分割統治法というのを使うとよいらしい。

https://codeforces.com/contest/1442/submission/100206224

それっぽいコードを書いたらそこそこのスピードでACできてしまった。解析すれば確かに計算量的に間に合うことはわかるのだが、直感に反する。これで計算量が落ちていることはかなり驚愕の事実といった感じ。

月曜日から3日分の日記を書いて、寝た。

12/03(木)

正午くらいに起きる。メールを読むと、毎週ぐちぐち言っていた金曜日の課題が今週はすでに投稿されているようだ。今日やっておけば安心。しばらく布団でスマホを触っていたが、学食が閉まりかけたので行く。

帰りに生協で「放課後探偵団2」という本を買った。たしか1巻（そもそもシリーズ化される予定がなかったのか、ナンバリングはされていなかった）が出版されたのは10年くらい前じゃなかったかと思う。実際あらすじを読んでも10年越しの云々と書いてあるわけで、僕の記憶は正しかった。1巻は記録によれば昨年古本で買って読んだようだ。

昨日言及した通り、今日は駅前の本屋に行く。自転車を漕いで行くつもりだったが、どうにも空模様が怪しいので地下鉄に乗ることにする。交通系ICカードにチャージしていたら（この場合の助詞は「に」が正しそうだ）、電車を1本逃してしまった。10分くらい待つ。最近話題になった匿名ブログを読んだことを思い出し、この「電車の時間を調べずに駅に来る」行為のすばらしさに改めて思いを致していた。

待っていたら中高生らしき人が大量にホームに表れてかなりビビる。駅に来た時はそんな人影は道路にもなかったので、本当についさっき現れた集団なのだろう。一体何用だろうか。こんな人混みにいたらそりゃ感染るだろうという気持ちになる。

駅前の丸善に行く。まず一般書のコーナーに立ち寄る。特に何か買おうと考えていたわけではなかったが、宮内悠介さんの「あとは野となれ大和撫子」が文庫化されていたので買う。以前に「盤上の夜」を読んでから少し気にしている作家。また「虚構推理」のシリーズも以前から気になっていて、どうやらシリーズ3冊がそろって平積みされているようなので、いい機会だと思い買う。

ラノベのコーナーに行って新刊をチェックする。こちらは出版予定カレンダーをずっとチェックしているので、買うものは決まっている。丸善のラノベの品ぞろえはあまりよくないので、特に衝動的に買うものは見当たらない。手に持つのが少しつらくなってくるが、以前より興味を持っていた「文学少女対数学少女」が出版されているようなので、探す。検索機で見つけたので店員さんに案内してもらう。滞りなく入手。

紙袋に入れてもらったら思いのほか大きく、以降はずっと片手に紙袋を携えながら行動することになってしまった。

まだラノベの新刊を買い切れていないので、メロンブックス・アニメイト・ゲーマーズをはしごして買い漁った。かなりお金を使ってしまっているので、衝動を抑えて素直にチェックしていたものだけ買う。

ブックオフにも行った。最近全然足を運んでいなかったので、かなり久しぶりに訪れる。ラノベコーナーが小さくなっていてびっくりした。あんまり買いたい本もないし、荷物も重いので、さっと出る。出るときにうっかり目に留まった本を2冊掴んでしまい、購入した。

本屋巡りは終わりにして、ゲーセンに行く。4時間くらいチュウニズムをプレイした。夕食を何にするか、そもそもこの荷物の多さですぐに帰らないのはどうなのか、など考えた結果、立ち食い蕎麦を食べた。

成果をツイートする。シャワーを浴びてからしばらくパソコンに向かう。

今朝確認した金曜日の課題を思い出して、やっておこうと課題ページを開いたところ、問題は講義用PDFファイルに記載されると書いてあった。これ自体は毎回書いてある文言なので深く考えていなかったが、冷静になると講義用PDFファイルは明日の講義開始時刻にならないと投稿されない。課題ページだけ先に作ったようだ。課題の存在を知らせるという目的なのだろうが、そもそも講義の時間を正確に守らせようという考え方が気に食わない。義務教育でやってろ。

かなり眠いので無理せず寝ることにする。就寝は午前零時半だった。

12/04(金)

起きてからしばらく布団でスマホを弄っていた。これ毎朝やってるな。午前10時くらいに起床報告して起きる。今日は面接の日。

起きた瞬間に課題のことを思い出した。期限まであと2時間くらい。内容は小テスト程度のものなので、十分間に合う。学食に行く前に取り掛かることにする。

思ったより時間を費やしてしまった。結局1時間半ほどかけた。二面体群に関する問題。詳しい行列の形を定めず、群論的な考察だけで証明しようと思ったのだが、うまくいかなかったので、あきらめて回転行列と対称移動の行列を書いて計算した。反転してθ回転させて再度反転するのは-θ回転させるのに等しい、ということを簡潔に書くのはどうすればいいのだろう。ググったら三角形の合同を用いて証明したものが見つかったが、まず軸等の設定が面倒そうで参考にはしなかった。

12時近くになってしまった。この時間は昼休みと被っているので、学食が混み合う。昼は家で食べることにする。

エリュシオンに降り注ぐ雨www.pixiv.net

こぞうさんのイラストが投稿されていた。久しぶりに更新を見るな、と確認したところ、ほとんど1年ぶりの投稿のようだ。昔からかなり好きで、こぞうさんがイラストを担当したラノベもいくつか買っていた（最近も1作あったが、それは買っていない……）。

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0378/review/5032279/kotatsugame/C++14

?（任意の1文字）を含む文字列のマッチングがFFTでできるという話を覚えていたので、試した。?を0に、その他の文字をユニークな正整数に対応させて、Σ_{i-j=k}a_ib_j(a_i-b_j)^2を計算する。マッチするのと和の値が0になるのが対応する。bを反転して式を展開すると、それぞれの項がFFTで計算できる形になる。後からnoshiさんの話をよく聞くと、a_ib_jの部分は_!='?'でもよいらしく、値域を削減できるらしい。確かに。

最初は1行ずつマッチさせていたが、全然間に合っていなかったので全体をまとめ、間を?で埋めることで文字列を1行にし、一気にマッチさせた。解説を読むとbitset高速化らしい。言われてみればこういうbitsetで速くなる書き方ができるんだなあとなる問題だった。

リクルートの面接に臨む。一次面接とは違い、面接内容を第三者に共有することが明確に禁止されているので、内容には一切触れることはできないし、ツイートもしていない。ただまあ、

学食の夜の部の開始を待って、向かう。裸足にクロックスで自転車を漕いだところかなり辛かった。ただ靴下を履くのが面倒なのでクロックスは止めがたい。

「数字で救う！弱小国家」5巻を読んだ。月曜日に1、2巻、水曜日に3、4巻を読んで、これで現在刊行されている分はすべて読んだことになる。非常に面白かった。単純に異世界転生軍記ものとして面白い。ただまあ、数学要素には一切期待してはいけなくて、誤植（だと僕が思っているもの）が目についてげんなりした。せっかく図解として1ページ割いているんだから、その中の式くらいまともにチェックできなかったのか。

「文学少女対数学少女」を読みかけるが、こどふぉがあったので出ることにする。C問題で信じられないくらい迷走した。上のほうでは正しいことを書いているのに、下の部分を書いているときには問題を誤解してしまっており、求めなくてよいものを求めるために必死に頭を働かせていた。その流れでD問題も誤読したまま実装まで終わらせてしまい、修正に時間を取られた。ただ、E問題が一瞬で解けたので、順位はそうひどいことにはならなかった。E問題は何がボトルネックになってしまうのかを考えると明らかなように思えた。木でdfsをするが、根だけ処理を変えることに気づくのに少し手間取った。

かなり眠くなってきたし、こどふぉはあまりよくない結果だったので、SRMを見送ることにする。布団に入ってからしばらくハーメルンを読んでいたが、眠気に耐え切れなくなったので午前2時頃就寝。

12/05(土)

午後1時頃、起床。夢を少し覚えていたので、夢日記を書いてツイートする。おおむね2パートに分かれていると感じていたが、前半の記憶はすでにほとんどなくなってしまっていた。

家に弁当がないので、本を読みながら今日の配達を待つことにする。いつ来るかわからないのでうかつに大便もできなくてちょっと困る。結局午後4時くらいに到着した。

さらに本を読み続ける。昨日読みかけになっていた「文学少女対数学少女」だ。本文中にいくつか古典ミステリの話が出てくるが、読んでいないのであまりわからない。別にわからなくても問題はないのだが、しかし読んでおいたほうが望ましいことも確かだろう。本に登場人物表が挟まっていてびっくりした。連作短編の形式で、主人公格3人以外が短編をまたいで登場することはほとんどないのだが、なぜ挟まっているのかわからない。中国語の人名は覚えにくいなどの話があるのかな。漢字を使ってはいるが、日本語話者にとってあまり直感的でない読み方、もしくは直感が働かない漢字が用いられているので、確かに頭の中で音にしつつ読むのは難しい。

今日はARC110。1時間ほど前にレジろうとしたら、いろいろな情報の入力を求められてびっくりした。これギリギリでレジろうとしてたら辛いな。企業スポンサードなARCであることを意識していなかった。よく見たら賞金もついている。

ARC110はABCDFの5完30位、パフォーマンスは2894でレートは2647→2675と+28できた。ここ3か月くらいずっと2600後半でウロウロしており、非常にもどかしい。

A問題はRakuでsay 1+[lcm] 2..+getを提出欄に直接打ち込んでそのまま提出した。ACできたからよかったものの、結局FAは取れなかったので、無理してサンプルを試さないリスクを負うこともなかったなという感想。2..getを2..+getにした（getをIntにキャストした）のは、Rakuの挙動を詳しく把握していないがゆえの安全策。結果的には必要なかった。例えばrangeの始点がStrだったらマジカルインクリメントを用いた展開がなされるので、困ったことになる。

また、コンテスト後に提出一覧を見て気づいたのだが、最大ケースに対応する答えを出力すれば他のケースの要件も満たすので、Textで解けてしまうようだ。これは気づかなかった。Rakuで[lcm]を使ったりとかなりシンプルかつ短く書けてしまうので、そこで思考がストップしてしまっていた。

D問題はコンビネーションの場合の数的な意味、つまりボールを選び出すということに注目してイメージを作っていくと解けた。最初少し迷走していたが、まあそこそこ速いACだったと思ってよさそう。

この時点でF問題のみACが出ていたので、とりあえず両方読む。Fを少し考えて、いつだったかに解いた「そーっとソート」を思い出すが、どうにもうまくいかなさそうなので、あきらめてEに向かう。

atcoder.jp

Eを30分くらい考えていたが、解けなかったので諦める。ABCの数値への対応のさせ方が悪かった。012と足し算・引き算ではダメで、123とxorならばうまくいくらしい。そのあとのことは解説を読んでもよくわからなかったので今も放置している。

最後30分を切ったあたりでE問題に見切りをつけてFの考察を再開する。どうやらi=0を連打しているとそこそこうまくいくようだ。ある個所を連打するのは「そーっとソート」から得た着想。より具体的に言えば、i->P_iで辺を張るといくつかのループに分かれるので、全体が1つのループになればよい。

ループに分解した後、2つ以上に分かれたならば1回のswapでマージできる個所を探してマージする、できなければ-1を出力する、を繰り返すことにする。結果ループが1つだけのグラフが得られるので、心行くまでi=0を連打すればよい。これを提出したところ、あっけなく通ってしまった。Eを考えている時間さえなければもっと良い順位だったのに、と思ってしまうが、まあ全ては結果論。ところでこれはハックケースがある。

何回もswapしていたらこのケースもいずれ1つのループになれるが、1回swapしてダメだったら即座に-1を出力してしまうコードを書いていたので、僕のコードはこのケースで落ちる。

コンテスト後に残り少なくなった「文学少女対数学少女」を読んでいたら、「競技プログラミング」という言葉が登場して非常にびっくりした。

午前3時頃、読み終わる。非常に面白かった。数学の命題や定理、逸話を作中作と対応させるという試み、また対応させる方法が面白かった。本文中では古典ミステリーばかり取り上げられていたが、あとがきや解説で触れられる本や作者は最近のものが多く、僕でも知っている・読んだことがあるものの名前が登場して嬉しくなった。まあミステリ評論自体は相変わらずよくわからないわけなのだが。例えば僕は青崎有吾さんの代表作「裏染天馬」シリーズを単純に学園ミステリの一つとして何気なく読んでいたわけだけど、この方は「平成のエラリー・クイーン」として高く評価されているようだ。

（溜めてしまっていた）日記を書いて布団に入ったら午前8時くらいだった。ハーメルンを少し読もうと思ったら信じがたいスピードで寝落ちした。

12/06(日)

午後3時ごろ、起床。明日は1限の時間から4年セミナーの説明会があって、参加する必要があるのだが……。

食事をして、サークルにメールが1通来ていたのを返信する。一瞬どんなメールが来たのか書こうとしてしまったが、それはいけない。こちらからは、プログラミングを学ぶ手段としての競技プログラミングについて（聞かれてもないのに）語ったメールを返信した。こんな感じの文章だ。

ほかの部分も含めて結構頑張って推敲していたら、メールの返信だけで1時間くらい使っていた。びっくり。

少しPCKの問題を解いたほかは、ラノベを2冊読んだ。1冊目は「お見合いしたくなかったので、無理難題な条件をつけたら同級生が来た件について」という本。内容はさておき、あらすじには特に書かれていなかったが、設定が結構特殊だった。普通の現実世界（恋愛）ジャンルの話だと思ったら、作中では結婚可能年齢が男女とも15歳に引き下げられていた。あと、登場人物が軒並み名家の御曹司・令嬢だった。この2つの設定はどちらも単独で主人公がお見合いをすることの理由になりうるが、2つ合わさっても別に最強には見えない。その設定両方いる？

2冊目は「元スパイ、家政夫に転職する」。展開がいちいち好みで良かった。主人公が目立つ・注目を浴びるシーンが好きで（これ以前の週記でも書いたと思ったけど見つからなかった）、その観点から言ってこのラノベはそういうシーンがかなり出現するので良い。

解けたはいいけど実装が面倒な問題があって、コードの設計を練っていたのだが、こどふぉ30分前になってしまったのであきらめてシャワーを浴びた。今日はCGR12で3時間。明日朝早いけど気にせず出る。CGRは皆勤。

ABcCDEFhを解き、システスもすべて通って37位だった。レートは98上昇し、2707になるようだ。

AとBはギャグ。Aはなぜかかなり面倒な実装をしてしまい、5分もかかっている。Bもギャグに気づくのに3分くらいかかってしまった。

C1は非常に難しかった。盤面の配置に依存する方針で解くとまずそうなので、そうでないものを考えた結果、i+j mod 3で分類することを思いついた。念のため必要ないマスは変更しないような実装をした後、提出直前に少し考えていたら、そういう余計な実装をしなくていいことに気づいてしまった。妙な場合分けはバグの温床なので削除するか考えたが、書き直すのが面倒でそのまま提出した。C2も同様の方針で解けたが、ここでもしばらく迷走してしまった。

Dもパッと見難しいが、数列の先頭と末尾をチェックして縮めていく感じで解けそうだったので、実装したところサンプルが合ったのでそのまま提出。あまり深く考えていなかったのでシステスが非常に怖かった。

EとFのsolved数が逆転していたのでFを読む。同じ数が隣接しているところで切って、繋げなおす。繋げるときに端の文字が同じだとダメなので、その時は片方を引きちぎって挟み込むことになる。引きちぎる回数を最小化したい。一切証明していないが、こういう同じ数だとダメみたいなやつは出現回数最大とそれ以外の2種類に単純化しても変わらないことが多いので、今回もそうだろうと決めつけた。

Eは最小の点を決め打って最短経路を計算すればよさそうだったので実装したが、WA。しばらく考えて、ロジックに誤りが見つからなかったので途方に暮れてコードを開いたところ、配列サイズが小さかった。アホくさ。

また順位表を見て、solved数に従ってH1に行く。ほとんど諦めモードだが、配点だけ見ればFと同じ問題。まず、なんちゃって証明とエスパーを駆使してDPに落とし込む。遷移をよく見ると、DP配列を+1/-1ずらすのと1つ飛ばしで隣り合う項の和を取る操作の2種類に単純化できることが分かった。ずらすのは先頭indexを持っておけばよくて、和を取る操作はパスカルの三角形になる。最後にDP配列を復元する。サンプルが合ったので提出したら通ってかなりびっくり。そのあとしばらくして、分母が0になり得るかもしれないと思って真っ青になったが、実装上modint(0).inv==0だったので助かった。冷静になると、制約から分母は0になりえない。

大成功して気分がいい。日記を書いていたら午前4時になってしまった。明日は8時50分からzoomで説明会。どうして……。