04/17(月)

午後4時過ぎから小刻みに目覚ましをかけつつギリギリまで寝ていた。なんとか起床に成功し半から定例会。

この2週間は機械学習の精度評価周りを実装していたこと、今週で完了させる予定であることを報告した。その後議題としてコーディングスタイルの統一に関する話が出て、フォーマッタの選定・設定などかなり長い時間全員で話し合っていた。午後7時半頃になってようやく一段落。勉強会は行われなかった。

夜中まで先週の週記を書いていた。特に金曜日のyukicoderの部分に時間をかけた。自分は何を気に食わないと感じているのか、その悪感情に自分はどういう正当性を見出しているのか、かなりじっくり考えていた。吐いた唾は飲めない。書いては消してを繰り返し、最終的な文章はかなり短くなった。午後11時半に投稿。

今年の履修計画を見直した。集中講義を二つ取って卒業要件をピッタリ満たすというのは流石に危ういと感じ、講義を一つ追加した。セミナーと被っているが資料はClassroomに上がるしレポート評価なので問題ないはず。

朝までMuscatキャンプの参加記を書き、投稿した。ジャッジにアクセスできなくなる前に完成させることができて良かった。キャンプ後一ヶ月くらいしか使えないと予告されていたので、もういつ消えてもおかしくなかった。

kotatsugame.hatenablog.com

学食で食事し、帰宅してから布団でラノベを読んでいた。「日本語が話せないロシア人美少女転入生が頼れるのは、多言語マスターの俺1人」3巻を読了。

2巻発売から1年以上が経過し打ち切りかと思っていたが、ヒロインがロシア人ということで少し、まあ、あったらしい。性格にはもうちょっとややこしい設定があって、同じくロシア人ヒロインの「時々ボソッとロシア語でデレる隣のアーリャさん」と同じようにはいかないというのは理解できる。ともかく無事出版されてよかった。この巻でシリーズ完結。かなり駆け足だったのが気になると言えば気になる。しかしその分美味しいシーンがたくさんあって、読んでいて非常に楽しかった。

TLに以下のような会話が流れてきた。同じ趣旨の問題を本で読んだことがあり、かなり印象深かったので覚えていた。なんでもない話にこの考え方を適用できる発想力がすごいなと思う。

「選挙カーうるさい、カス、絶対投票しねえ」みたいに言ってる人も、無音の選挙カーに対して「オッ素晴らしいな、この人に投票しよう」とはならなくない？（気づけばなるか？）
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2023年4月18日

聞こえた中で一番小さい音に投票されるため、音量下げチキンレースが始まる回
— もつ鍋xe (@xenon_motsu) 2023年4月18日

どれだけでかい音で敵の名前出せるかだぞ
— drogskol (@cureskol) 2023年4月18日

これ初めて知ったのはこんな問題だった：

王様が二人の王子に「これから一人一頭のラクダで砂漠を横断せよ。遅く横断し終えたラクダの持ち主を次の王とする」と言った。しかし王子たちは先を争うように砂漠を駆け抜けてきた。なぜか。
— こたつがめ (@kotatsugame_t) 2023年4月18日

午後1時過ぎ就寝。

04/18(火)

消えた。

04/19(水)

午前5時起床。今日はセミナー準備を終わらせた後ゲーセンに行って夜はさっさと寝ようかな、などと考えながらコンテスト日程を確認したら、今日のCodechef Startersが全員Ratedになっていた。予定崩壊、どこかで仮眠を取る必要がある。

今後1ヶ月くらいで出版される本の予約を行った。今回は22冊。他に1冊、なぜか予約サイトに登録されていない本があったので、そのうち店頭で注文しておきたい。

セミナー準備をした。Thm 6.2.2、Ford-Fulkersonの定理の証明の部分。分量的にはもう少し用意する必要があるが気が抜けたので一旦布団に戻った。ラノベを2冊読了。

1冊目、「自作3Dモデルを売るためにサキュバスメイドVtuberになってみた」。カクヨムでも好きだったし、改めて読んでもやはり面白かった。登場するキャラクターのうち誰と誰が実は同一人物で、というような複雑な人間関係が明らかになっていく部分にワクワクする。1巻はそういう風呂敷を広げっぱなしだったが、実はカクヨムで先のほうまで読んでいてもそれほど積極的には回収されない。その分たまに回収されるとかなり嬉しい。

2冊目、「女友達は頼めば意外とヤらせてくれる」。ラノベというより官能小説だった。一般のレーベルから出す必要があったとはあまり思えない。単に本番シーンを描写できないという制限が付いただけではないだろうか。ストーリーもないことはなかったはずだが、それがメインには見えなかった。官能小説としては結構良かったと思う。

午後5時半から仮眠した。2時間くらいで頭の痒みにより一度目を覚まし、シャワーを浴びた。特大の睡眠で気づかなかったが前回シャワーを浴びてから43時間経過していた。

午後11時起床。祖母が寝たきりになったとの連絡が来た。食事して半からCodechef Starters 86。

https://www.codechef.com/START86A

STRAMEからよくわからない。まあどうせどんな操作を行っても回数は一定だろうと思って出したら通った。ペナがないのでできる戦略。後から $S$ に0と1が両方ある限り操作できると知った。それはそうすぎる……。

LARGESTYは、bitであって $A$ に立っている数と立っていない数が両方含まれるものを考える。そのようなbitのうち一つ以上が $Y$ で立っていなければよい。このbitを一つ固定すると、 $Y\le X$ なる $Y$ の最大値は単純な場合分けとbit演算で求まる。

MINIMUMOP。最初から揃っていないならば $M\ge 3$ であり、このとき $X=2,3$ で操作すれば必ず条件を満たせるので1手の判定ができればよい。2以上の数に揃えられるかは $\gcd(A)\gt 1$ をチェック。

1に揃えられるなら $X$ を素数 $p$ としてよいので、 $A$ を素因数分解して一度も現れない $p\le M$ が存在するか判定する。素因数分解は前計算で各数に対し素因数を一つ求めておくことで十分高速に行える。条件を満たす $p$ の存在判定は適当に素数を舐めておけばよい。見ることになる $p$ の個数が $A$ の素因数の総数で抑えられるので、確かに $\sum M$ の制約がいらない。

SUMOVERALLは難しかった。scoreは $B$ をソートしたときのbeautyである。よって $A$ における要素の頻度配列を固定してscoreを求め、多項係数で $A$ を数え上げる方針が立つ。しかしこれはどうにもならなかった。そこで寄与に分解してみた。

要素 $a$ が $A$ （をソートした列）において0-indexedで $[l,r)$ にのみ現れるとする。このとき $a$ のscoreへの寄与が求まるので、 $a$ 未満の数と $a$ より大きな数の分布をそれぞれ考えて得られる係数などを掛けて答えに足したい。

$f(n,k)$ を「長さ $n$ で和が $k$ の非負整数列 $c$ について $\prod\frac 1{c_i!}$ の和」と定めると、この係数は $n!\times f(a-1,l)\times f(X-a,N-r)\times\frac 1{(r-l)!}$ になる。 $f$ をdpで計算する際の遷移を多項式で表すと $f(n,\ast)=(e^x)^n$ となった。よって $f(n,k)=[x^k]e^{nx}=\frac{n^k}{k!}$ と求まる。

ここまで来ればあと一息だろうと思ったのに、 $(a,l,r)$ の全探索から計算量が落ちない。次の問題のほうがより多く解かれていたのでそちらに進んだ。

LEASTSIZEはかなり簡単だった。 $S=\{R\}$ とするのを目標にする。 $R$ として木の重心を選ぶと、 $R$ を取り除いて得られる各部分木のサイズは $N/2$ 以下となっている。ここから隣り合う2点が常に異なる部分木に属するように頂点を並べることができて、達成。

構築の際は頂点たちをLCAが $R$ になるようなペアに分解してから並べたが、単に大きな部分木から見て答えの偶数番目→奇数番目と埋めていっても良かった。

SUMOVERALLに戻ったら解けた。 $a$ のscoreへの寄与は、小さい方から $i$ 番目なら $s_i$ 、としておくと $s$ の累積和 $S$ を取ることで $S_r-S_l$ と書ける。これで $a$ 、 $l$ 、 $r$ が完全に分離できて、 $(a,l)$ を全探索して $r$ の式をWolfram|Alphaに投げたら閉じた式になった。 $l$ と $r$ を逆にしても同様。

べき乗があるので、単に実装すると $O(NX\log N)$ となってTLEしてしまう。逆元を取ったり、取れないものについては場合分けで処理することで $O(NX)$ にしたらようやく通った。

もう残り時間はほぼなく、そのままコンテスト終了。5完15位で2848→2828(-20)。厳しい。

祖母に会うための帰省のタイミングとしてAGC後の05/01を提示したところ、そこまで保つか怪しいとのことだったので、明日移動することにした。それまでに済ませなければならないことがいくつかある。

まずセミナーの準備を完了させ、次にインターンの進捗を少しだけ産んで報告しつつ金曜日の1on1をキャンセルした。これで朝になってしまったので就寝。午前6時過ぎだった。

04/20(木)

午前9時起床。強い眠気に抗いつつ、寝落ちだけしないように30分ほど布団に横たわっていた。起き上がって食事し登校。今日も微妙に遅刻してしまった。

最初1時間は複素関数の問題を解いていた。 $z\ne 0$ で $\exp\left(-\frac 1{z^4}\right)$ 、 $z=0$ で $0$ を取る関数 $f(z)$ が連続かどうか調べるというもの。偏角 $\pi/8$ の方向から $z\rightarrow 0$ と近づけると常に $|f(z)|=1$ となることを計算し、連続でないと結論づけた。計算に微妙に手こずってしまった。

$\exp\left(-\frac 1{z^4}\right)$ が $z=0$ を真性特異点として持つことから、その近傍で像が稠密になることを言う定理がある。それによれば $f(0)$ をどのように定義しようとも連続にはなれない、という問題だったらしい。言われてみれば……程度の記憶しか残っていなかった。

次の2時間は同級生の発表。前回詰まった部分について再度説明されるはずが、冒頭のミスを指摘したところ修正困難でまた来週になり、今日はそこを飛ばした先をやった。終盤また詰まっていた時間で自分だけパンを食べた。

昼休憩を挟まず自分の発表を開始し、Ford-Fulkersonの定理をアルゴリズムの実演も交えて説明した。その後微妙に時間が余ったので、次回話す予定のflow polynomialの関連として彩色多項式について喋った。Diestelだとこちらは本文中になく、Exerciseに追いやられている。二つともほぼ同じ計算をするからだろうか。

午後3時終了。購買に寄ってラノベを受け取り帰宅した。

しばらく週記の本の感想部分を書いていた。本が仙台にあるので、これも帰省前にやっておくべきこと。またAtCoderの仕様変更でatgolferが動かなくなったことにも気づいたが、修正する時間はなかったのでIssueだけ立てておいた。そのうち頑張って調べて対応する。

【おしらせ】コンテストの提出一覧ページを閲覧する際にログインが必須となりました。ページが見られないなどの問題に遭遇した方はログインをお試しください。
— AtCoder (@atcoder) 2023年4月20日

github.com

午後5時半出発。仙台駅に向かい、みどりの窓口に並んで学割で切符を購入した。自由席に乗って行こうとするとECRに間に合わないようだったので指定席にした。

大宮までは本を読み、そこで乗り換えてからは寝ていた。富山駅からは父の車に乗り、午後10時くらいに実家に到着。すぐに夕食と入浴を済ませた。

CFを開くとCodeTON Round 4の賞金のメッセージが来ていた。これまで配られた仮想通貨は全部無視してきたが、改めて調べると結構馬鹿にならない金額だったので、walletを作って受け取ってみることにした。

午後11時半からECR147。

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

Aは先頭が0にならないように埋めればよい。最初うっかりマッチする数の総和を求めてしまった。

Bは選べる $[l,r]$ は $a\ne a'$ なるインデックスをすべて含み、区間内で $a'$ が昇順になっている。逆に入力の制約からそのような区間はすべて可能。よってまず前者の条件を満たす極小な区間を取り、後者の条件を調べつつ左右に貪欲に広げることで長さを最大化した。

Cは残す文字を全探索する。残す文字で $s$ を分割し、それぞれ何回の操作で消せるか考えると、それらの最大値を取ることですべて消すための操作回数が求まる。長さ $l$ の文字を消すための操作回数を $f(l)$ とすると $f(l)=f(\lfloor l/2\rfloor)+1$ なので前計算しておいてもいいし、単に2進数の桁数を数えてもよい。

Dはよく分からなかった。貪欲が通るならD問題にはならないはず。そこで最後に黒くした区間 $[l,r]$ を全探索した。するとそこより左の区間は全部黒くするあるいはしないのどちらかである。一つの区間を黒くするのには一律で2手かかるから、長い区間を優先的に黒くしたい。

優先度付きキューで区間の長さを管理し、長さの総和がギリギリ $k-(r-l+1)$ 以上になるような区間の個数の最小値を求めたが、WA。あまり遠くのセルまで黒くするのも手数が多くなるから、ギリギリ $k$ 以上になる個数から $k-(r-l+1)$ を下回らない範囲で全部試す必要があったらしい。次からは長さ $r-l+1$ の区間が使えるので、これを行っても計算量は壊れない。

Eは対応する括弧のペアを区間だと思うと包含関係にある区間のペアの数がコストになるようだ。よって多くの区間を含むような括弧のペアを $k$ 個選び、操作によって二つの括弧を隣り合わせるのが最適に見える。しかしこれだと $k\le 5$ である理由がわからない。何かあるんじゃないかと疑って、いくつ括弧を取り除いたか・挿入したかを $O(k^4)$ 状態で持つdpを書いた。

Fは左の木から順に、できるだけ左の方向に切り倒すことを考えてdpした。遷移が多項式 $f$ の掛け算になるので、 $f^m\bmod{x^{n+1}}$ を求めて係数の和を取ると答えになる。2分累乗法による $O(n\log n\log m)$ でpretestは1900msちょっとだった。

コンテスト後にFがhackされて5完54位。Dは長さ2以上の区間は貪欲に黒くしてよいらしい。Eは最初に書いた方法で通った。どちらも貪欲がなぜダメなのか・ダメだと思ったのかしっかり考えなかったのが悪かった。

Fをupsolveした。 $f$ はループで計算していたが、丁寧に考えると $x^{k+1}\times\frac{2-x^{n-k}-x^k}{1-x}$ となった。 $\bmod{x^{n+1}}$ での値を考えることで $-x^{n-k}$ の部分を無視できて、分子が二項定理で求まる。最終的な計算式は木を切り倒す方向を決め打つ包除原理と全く同じになった。

少しだけ日記を書いて、眠気に逆らわず午前4時くらいに布団に入った。しかしそこからハーメルンに没頭してしまい就寝は午前6時半となった。

04/21(金)

正午前に起床。昼食を摂って祖母宅に見舞いに行った。昨晩からモルヒネの投与が開始され、今日は朝から飲まず食わずでずっと眠っているらしい。声を掛けても顔に触れても反応はなかった。

帰宅して少し仮眠しようと思ったがハーメルンを読んでしまった。「ぼっち・ざ・へゔぃめたる」を読了。なかなかいい感じのオリ主設定。ちょっと年齢差が気になるので、同じ主人公が登場するバンドリの二次創作である前作も読みたい。

syosetu.org

午後3時から公文式の教室を訪れ、先生と話したり臨時で採点バイトをしたりした。久しぶりだとは思っていたが、日記を確認するとおよそ3年ぶりでびっくり。帰省のタイミングと教室の休みが被りがちでなかなか顔を出す機会がない。

高校のころまで通っていた公文式を訪問して先生とひとしきりお話をしたりした。
週記（2020/08/24-2020/08/30） - kotatsugameの日記

午後7時過ぎ帰宅。夕食と入浴を済ませ、しばらく日記を書いて午後9時20分からyukicoder 385に参加した。

yukicoder contest 385 - yukicoder

Aからちょっと難しかった。 $j$ を $\pm 1$ できることから $i$ が等しい座標へ移動する方法の数はすべて一致する。この値を管理した。

Bは?のうち左からいくつかをAに、残りをCに置き換えるのが最適。適当に前計算して境目をずらしながら差分更新することで全探索できる。

Cは主張 $(A,B,C)$ によって、 $A$ がどちらか確定したときに $B$ も確定するだけでなく、逆も言えることに注意。正直者と嘘つきで $2N$ 頂点作り、同値関係を表すように辺を張る。同じ人に対応する2頂点が同じ連結成分にあれば矛盾。そうでなければ連結成分数割る2だけ自由度がある。

Dは謎。小さい $T$ に対して実験したところ、 $K$ 文字目と異なる文字を左右それぞれで探したとき、どちらかまたは両方で距離が $T$ 以下かつ $T$ と偶奇が等しければ先手勝ち、という結果が得られた。それを実装したら通った。

Eはbitごとにそれが立つような分割方法をdpで数えた。遷移は区間加算になる。遅延評価を行わないように書き換えた双対セグ木を使うと1500msで通った。

午後10時に一旦コンテストを切り上げて祖母の見舞いに行った。昼とは違ってまぶたを開いたり閉じたりしていたが、声掛けへの反応なのかよくわからない。眼球は動いていないようだ。帰る間際に腕が動いたのは、単なる寝返りではないと信じていいだろうか。

木曜日の自分が実家に到着した時間ならまだ言葉を交わせていたらしい。別にECRを優先したつもりはないが、なぜ富山駅に着いてから直接見舞いに行かなかったのだろうと少し後悔している。危機感が不足していた。

帰宅してFを解いた。 $\gcd(A,B)$ で入力の4数を割っておく。 $K$ が割り切れなければその時点で答えは0。また $K\gt A$ のときも答えは0。 $K=A$ のときは $X$ で連続する $A$ の倍数を数えることになって、 $B$ の倍数が連続することはないから $A$ の倍数の数から $B$ の倍数の数を引いてLCMの分など調整することで求められる。

$K\lt A$ のとき、 $X_{i+1}-X_i=K$ なる $X_i$ が $A$ の倍数であるか $B$ の倍数であるかを両方試す。両方が同時に成り立つことはない。 $X_i$ が $A$ の倍数なら $A_i=kA$ と表せて、 $X_{i+1}=kA+K$ が $B$ の倍数になることから $k\equiv -K\times A^{-1}\pmod{B}$ が得られる。これを満たす $1\le k\le(M-K)/A$ を数えるのは簡単。逆も同様である。

6完18位、しかしコンテスト後にDが落とされた。流石に適当すぎたらしい。

しばらく日記を書き、少しハーメルンを読んで就寝。午前1時半過ぎだった。

04/22(土)

午前6時半頃目を覚まし、その後眠れず布団でずっとハーメルンを読んでいた。午前8時頃に一度起きて朝食を摂った。

正午になって身を起こし、昼食を摂って見舞いに行った。自分が見ている間にまぶたが数回開いたり閉じたりしたが、昨日の夜に比べて明らかに動きが少ない。

点滴を打っていないため、金曜日から栄養も水分も摂っていない。よってあと1日保つかどうかということで、今夜は自分も祖母宅に泊まっての寝ずの番に加わることにした。一旦実家に帰り、ABCまで終わったらまた来る。

帰宅して準備を整え午後2時からUniversal Cup 13回目に参加した。今日はIberiaセット。同じセットが使われるMuscatキャンプ6日目はわざわざ回避したのだった。

04/22のUniversal Cup 13回目、Iberiaセットで使われるらしい。回避。
Hello Muscat 2023 参加記 - kotatsugameの日記

Petrozavodsk Winter 2023. Day 6: Um_nik mod 998 244 353 Contest - Dashboard - Contest - QOJ.ac

チームでECDJKを解き5完37位。自分はほとんどの問題の考察に参加し、DとKを実装した。

Eは正しい問題を解けばいいのかバグったチェッカーで通ればいいのかちょっと悩んだが、サンプル1を見ると後者でよいことがわかる。さらに $n$ がある程度大きければ $\lfloor a_{i+1}/a_i\rfloor=1$ となる $i$ がたくさんあると閃いた。それと $O(n^4)$ の全探索を組み合わせれば通る。細かい部分ごと実装をぷらさんに任せた。

次にC。recordである要素を $k$ 個決め打って数え上げることにした。するとその他の要素は「使ってはいけない」か「どちらでもよい」の2種類に分かれる。適当に立式して二項定理を使えば「どちらでもよい」の要素が存在するとき答えへの寄与が0になることがわかる。

つまり $k$ 個を決め打つとき、選んだ要素の後ろにそれ以下の要素が存在しないようにしなければならない。これを言い換えると、選べるのは後ろから見たときの累積MINを更新する要素のみ。それが $t$ 個あるとしたら $k$ 個の選び方が $\binom{t}{k}$ 通りあって、常に $len=k$ なので答えが計算できる。これもぷらさんに実装をお願いした。

Dは初手が見えずかなり苦労した。XORと行列式の多重線形性の間にはなかなか良い性質がなかったが、辛うじて見つけて解けた。まず多重線形性により、元の行列 $A$ を各行1bitずつ取り出した $60^n$ 個の01行列に分解する。すると $n$ がそこそこ大きいときどの行列にも同じ行が存在することが言えて、行列式がすべて0になる。

より精密に述べる。分解した行列の $i$ 行目は、 $b_i$ の取り出されたbitと $c$ の取り出されたbitをXORしたものである。ここでもし同じbitを3行で取り出していた場合、 $b_i$ に必ず被りが発生し、 $c$ が共通であることから行そのものも一致してしまう。これは $n\gt 120$ なら必ず発生する。 $n\le 120$ の場合は直接計算しても間に合う。

Jは $m=1$ のとき自明、 $m\ge 3$ なら有名問題で $P=n$ とできる。 $m=2$ を実験してもらって眺めていたら、 $n\ge 6$ では長さ6の周期を保つ12種類しかないことが分かった。かっつさんが実装。1WAしたので全員でデバッグし、コーナーケースをいくつか見つけて無事2回目で通った。

Kは問題文にリンクがあった別の問題とその解法をまず把握した。与えられるグラフの誘導部分グラフのうち、 $K_4$ つまり辺を6本持っているものの数と0本持っているものの数の差を求めるというもの。解法は包除原理で、差を求めるから上手く項が打ち消し合って計算できるということらしい。

https://codeforces.com/gym/103470/problem/K

https://codeforces.com/blog/entry/97762?#comment-866645

ちなみにこのコメントから見られる $C_4$ を数え上げるライブラリは、自分が知っていた以下のライブラリより空間計算量が良い。 $O(n+m\sqrt m)$ から $O(n+m)$ になっているはず。

https://kopricky.github.io/code/Graph/CountingC4.html

今解こうとしている問題では $K_4$ を数え上げる必要がある。同様に包除を適用しようとしたが上手く行かなかった。それも当然で、先程の問題で打ち消し合っていたのは $K_4$ そのものである。つまりこれを数え上げるのが巧妙に回避されていたのだ。

結局直接数え上げた。1辺を固定しそれを含む $C_3$ を列挙できるので、その3頂点のうち固定した辺に接続しない頂点を、固定した辺の番号でマークしておく。これをすべての辺について行った後、再度辺を舐めて、両端点を同時にマークした辺の数を数えれば $K_4$ の個数になっている。

マークをbitsetでやると計算量的には間に合いそうだが空間が足りない。そこで辺に対しマークする頂点を列挙した後、wordsizeつまり64本ごとにマークを付け直すことにした。これで時間計算量 $O(m\sqrt m+m^2/\mathrm{wordsize})$ のまま空間計算量 $O(m\sqrt m+n)$ にできる。

TL 1secのところ手元でランダムケースを試したら0.85secくらいだったのでかなり怪しかったが、出したら通った。感動。

その後はHやIを考えていた。Iはおそらく操作を前と後ろ交互に行ってよいはずで、シミュレートも前と後ろが交差するタイミングさえ愚直で乗り切れば他はできそうだったが、それが分かった頃には細かいところを詰めて実装するほどの時間は残っていなかった。終了後、感想戦をして解散。

夕食と入浴を済ませ、しばらく日記を書いて、午後9時からABC299に参加した。

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299) - AtCoder

Aは最近よく見る正規表現一発の問題。sedでは|はエスケープしないとORの意味にならないので、inの条件が/|.*\*.*|/と書ける。ただしこれもoutか判定したほうが短くなり、間の文字が全部.となるため/|\.*|/になる。

縮めて再提出しようとしたらしばらくAtCoderが繋がらなかった。先週も同じことがあったのに印刷用問題文を開いていなかったのは失敗だった。提出自体は1分もしないうちに成功していたようだが、結果が見られるまでにはもう少しかかった記憶がある。

Bは結構面倒。 $C=T$ と $C=C_1$ それぞれ集めてソートした。劇的に簡単な方法はなさそう。Cはoが連続する極大な区間を列挙し、左右どちらかに-があるかチェックする。Dは二分探索で、区間の両端の文字が異なる状態を保ちながら縮めていく。

Eはまず頂点 $p$ から距離 $d$ 未満にある頂点を白で塗らなければならない。それ以外の頂点は全部黒で塗って損しないので、そうした後に改めて条件をチェックした。

Fはちょっと難しかった。2回目の $T$ の開始位置 $s$ を決め打つ方針はすぐ出るが、そこから重複なしで数え上げる方法がなかなか出てこなかった。最終的には1回目の $T$ として最後に取った文字の位置が $s-1$ であるようなものを数えた。

Gは貪欲。そこ以降で $M$ 種類の数字が存在するような最も後ろの位置を、 $A$ の頻度配列をデクリメントしながら先頭から探索することで見つけることができる。先頭からそこまでの範囲で数字最小、インデックス最小のものを部分列の先頭に置く。

今度は今使ったもの以外で $M-1$ 種類の数字が存在するような位置を考え、以下同様。こうやって位置を尺取り法っぽく求めるのは、頻度配列を見ているだけなので $O(N)$ 。数字とインデックスが最小のものは優先度付きキューで取得した。

Exは面倒。 $\mathrm{dp}_i$ を「 $X\equiv i\pmod{10^9}$ なる状態から先の期待値」と定義する。 $\mathrm{dp}_R=0$ である。このdpは漸化式 $\mathrm{dp}_i=1+\frac{\mathrm{dp}_{i+1}+\mathrm{dp}_{i+2}+\mathrm{dp}_{i+3}+\mathrm{dp}_{i+4}+\mathrm{dp}_{i+5}+\mathrm{dp}_{i+6}}6$ を持つので、 $\mathrm{dp}_{R+i}$ を $1\le i\le 5$ の範囲で変数で置けば他の値はこの五つの変数で表せる。

遷移を行列累乗で表し一周することで、五つの変数に関する5本の連立方程式が得られる。これは入力 $R$ に依らず、試したら解けることが確認できた。解くことで変数の値がわかり、再度行列で $\mathrm{dp}_0$ を求め代入することで答えが出る。一発で合って感動した。

70分で全完し9位。手早くコードゴルフをした。Aは2回目の提出が最短。CはPerlで書いてbashに負け、DはRubyのbsearchで書いてdcに負けた。他は手つかず。

今日もAtCoderはDDoS攻撃を受けており、その影響で明日のAHC020が延期になった。

コンテストが終わって泊まりの準備も整えたのに迎えが来ない。さてはと思って電話したところ、祖母が亡くなっていたことを知った。午後9時前には息をしていなかったらしい。

臨終直後のあれやこれやが一段落した後で迎えが来て、祖母宅に行きご遺体と対面した。今日の昼と比べると顔色が全く違い、まさに土気色というほかない。また唇の色が一気に抜けていたのも印象的だった。

今日はご遺体と同じ部屋に布団を敷いて寝る。午前1時半就寝。

夜中にトイレに起きて暗い廊下を一人で往復した。「出る」なら今このタイミングだろうなと思ったが特に何もなかった。

04/23(日)

午前7時起床。手早く食事した後、午前中は来客対応でてんてこ舞いだった。自分は主にお茶くみを担当しつつ、合間に日記を書き進めていた。

祖母は生前自分に会うたび自分の幼少期の話を延々していたが、これは他の人に対してもそうだったようで、自分のことを聞き知っておられる方ばかりだった。それでかなり多くの方に声を掛けていただいた。

昼食を摂ってから仮眠に入った。狭いスペースに布団を敷いたため体を伸ばせず、あまり快適ではなく小刻みに起きてしまった。合間にハーメルンから「ガールズバンドが人気な時代ですが、男も頑張ってみます。」を読了。

syosetu.org

金曜日に読んだハーメルンの前作。相変わらず主人公が良かった。バンドリはキャラが多すぎて把握しきれなかったが、オリ主ものということでかなりの数の好意が主人公に向いており、ハーレムの人数が多いという点だけ見て満足していた。

午後3時から2時間程度、仏具受け取りのため駆り出された。帰ってきてまた就寝。今度は環境を整えたので快適に熟睡できた。

午後10時くらいに起きたが眠気が異常なほどある。実家に戻るとすぐ布団に入ってまた寝た。午後11時半だった。