10/10(月)

午後11時起床。30分ほど日記を書いていたが完成するはずもなく、未完成のままメモ書きだけ削除して投稿した。

メモ書きとは時間帯とその時やっていたことを大まかに記録したもの。普段日記を書くときは、まずブラウザの閲覧履歴やTwitterからこれを復元した後、記憶に残っている行動・思考・事物で肉付けしている。このとき日記に書かないことも決めているため、そのフィルターを通さない状態のまま公開する気にはなれないのだ。

午後11時半からCF #825 div.2。

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

Aからちょっと考える必要があった。並べ替えの操作をするかしないか両方試すことにして、並べ替える場合は0の出現回数または1の出現回数を揃える。片方を揃えればもう片方も揃う。

Bは、 $a_{i-1}\mid b_i$ かつ $a_i\mid b_i$ より $b_i={\rm lcm}(a_{i-1},a_i)$ とするのがギリギリで、条件を満たしやすそう。ここから再度 $a$ を復元して一致するかチェックすればよい。

C1は $(l,r)$ がgoodなら $(l+1,r)$ もgoodなので、尺取りで解ける。配列サイズをミスして1WA。ただしこの考察はC2ではあまり意味がない。div.2のCだからシンプルに解けるだろうと思っていたのに全く見えず、何か見落としているのかと不安になった。順位表を確認したら全然通されていなかったので、安心して腰を据えて考えることができた。

$(l,r)$ がgoodであることと、 $l\le\forall i\le r$ について $a_i\ge i-l+1$ となるのは同値。ところで $i\lt l$ のとき、 $i-l+1\le 0\lt a_i$ よりこの条件を必ず満たす。よって $l$ に対して $(l,r)$ がgoodとなる $r$ の数は、 $a_r\lt r-l+1$ となる最小の $r$ （存在しなければ $n+1$ ）を取ったときの $r-l$ と等しい。

$l\lt r+1-a_r$ と書き直すと見通しがよい。各 $r$ は $1\le l\lt r+1-a_r$ を邪魔すると言えて、 $l$ に対してそれを邪魔する $r$ の最小値は単調増加。今、クエリごとに $a$ の値が一つだけ変わる。もし $r+1-a_r$ が大きくなるならば、対応する $r$ がどこまで新たな最小値となるか二分探索で求まる。

小さくなる場合は、もともとその $r$ がどの範囲の $l$ に対して最小値となっていたかを、こちらも二分探索で求め、削除することになる。削除後の最小値が知りたいので、最初に計算しておく $r$ を小さいほうから二つ持っておくとよい。

Dのほうが多く通されていたので簡単なんだと思ったのに、初手すらわからなくてびっくり。ただ比較的すぐに解法が「降って」きた。 $s$ の $2i-1$ 番目と $2i$ 番目をペアにし、高々1回のrotate操作ですべてのペアについて文字を揃える方針。最初の状態で文字が異なるペアを列挙したとき、これが奇数個だとそもそも0と1の文字数が異なるため不可能。偶数個の場合、先頭のペアから順に0と1を交互に取って $b$ とすることで、rotate後に見事文字が揃う。

Eは $O(n^3)$ のdp。ターンごとにスコアに加えられた値は、同じ値が連続するいくつかの区間に分けられて、それを長さ1に圧縮すると元の列 $a$ の部分列になっている。よって、次にどの値の区間を作るか、直前にどのターンまで使ったか、余っている操作回数はいくらか、の3次元で表現できる。

区間はまず長さ $1$ とし、後から追加で $1$ ずつ伸ばすことにすれば、状態ごとに遷移が定数時間で書ける。途中で余っている操作回数が負になるケースも計算に含めてしまい1WA。

システスも全部通って全完4位。C2をちゃんと通せたのも、Dで素早く天啓を得られたのも偉かった。

週記に戻ってほとんどの部分を書き上げた。読了したなろうについての感想部分を開けた状態で一旦更新。もう一度編集ページを開き、そのまま書き続けて完成させようとしたが、睡眠時間と明日の予定を鑑みて早々に切り上げた。午前5時就寝。

10/11(火)

正午起床。木曜日のチュウニズムのアプデでトンデモワンダーズが収録されるらしい。かなり好きな曲なので最高。

【10/13(木) 楽曲追加情報！】
本日も、13日(木)より稼働開始の『CHUNITHM SUN』に収録される楽曲を紹介！
niconicoからは「神っぽいな」など大人気楽曲が、ほかにも東方ProjectやVARIETYに話題の楽曲が追加されるよ！イロドリミドリからも新曲が登場！ pic.twitter.com/f96fiJP94K
— チュウニズム公式@10/13(木) CHUNITHM SUN稼働開始！ (@chunithm) 2022年10月11日

今週からセミナーが火曜開催になる。準備して山に向けて出発した。セミナー開始前に購買で昼食を買うのと、履修登録について教務課で行うべきことを一通りやっておきたい。後者は先週やろうと思っていたのに家から出られなくてできなかったこと。

他研究科の集中講義で面白そうなものがあった。ぜひ受講したいが、調べても日程が出てこない。そもそも履修登録の方法についても教務課に問い合わせる必要がありそうなので、早めに一回話を聞きに行く必要がある。
週記（2022/09/26-2022/10/02） - kotatsugameの日記

購買は12時45分までだから先にそちらに、と思ったら、教務課も12時45分から昼休みだった。ダッシュでパンと飲み物を買った後、教務課に滑りこんでとりあえず必要な書類を受け取った。セミナーの合間に記入して、あわよくば提出したい。

とりあえず教室に向かって午後1時からセミナー。最初は同級生の発表。集合とその上の二項演算の組 $(M,\mu)$ 、いわゆるマグマについて、 $K,S\in M$ であって $\mu(\mu(K,x),y)=x$ と $\mu(\mu(\mu(S,x),y),z)=\mu(\mu(x,z),\mu(y,z))$ を満たすものが存在すれば、ラムダ計算っぽいことができるというのが面白かった。

ラムダ計算っぽいことというのは、変数 $x_1,\dots,x_n$ と定数が入り混じるどんな式に対しても、 $f\in M$ が存在して、その式と $\mu(\dots\mu(f,x_1),\dots x_n)$ が一致するということ。 $\mu$ を関数適用だと思えばそれはそうなのだが、これまでと見方が違うように感じられて新鮮だった。

2時間半ほどで終了。ちょっと休憩をお願いして教務課に駆け込み、いくつかの質問と書類提出をした。他研究科の集中講義の履修について、結論から言えば、可能だが日程はわからないので文学部のページを定期的に確認せよとのこと。以下にURLを記録しておく。日程がわからないのはちょっと怖いものの、困ったら落とせばよいしと履修認定願いを出した。

講義・履修 | 東北大学大学院文学研究科・文学部

この履修認定について、単位を卒業要件に含められるか否かはまた別の問題らしい。例えば僕が前期で取った講義のうち工学研究科で開講されていたハードウエア基礎は、学務情報システムから確認した限り卒業要件に含められないタイプの履修となっていた。認定願いでは含めてくれと言っておいたのにこの仕打ちは聞いてないんだけど……と遠回しに尋ねたら、システムのほうが間違っている可能性があるので成績証明書を見ると確実と言われた。どれくらい単位数が必要なのか計算が狂ってしまうので、近く確認しておきたい。

教室に戻って、今度は博士課程の方の発表。 $n\times n$ の対称行列 $S$ に対し、 $n\times 1$ の列ベクトル $u$ を $u^{\rm T}u=1$ のもと動かして $u^{\rm T}Su$ を最大化するという話が出てきた。 $S$ の最大固有値が最大値になるらしい。なんとなく見覚えがあるだけで詳細がわからないため、そこまで踏み込んだ解説をしていただいた。ラグランジュの未定乗数法を用いるのだが、それすら忘却の彼方にあり、今日はここの説明だけで時間を使い切ることに。申し訳なさがある。

午後6時過ぎ終了。山の下の学食で食事して帰宅。

実は今日はインターン先の定例会があった。月曜日が祝日だったためずれてきて、セミナーと被ってしまったのだ。会議を覗いてみるとまだ勉強会の途中だったので、そこから30分ばかり参加した。チームマネジメントの話。メンバーにより多く意見を述べてもらう方法論は、自分の卑近な体験とも通じるところがあったので、そこに注目しながら聞いていた。具体的な質問を投げかけると良いらしい。

勉強会を終え、再度外出。ゲーセンに行く。今日は新しく解禁した曲を詰めるだけの日で、そのうち三つについては手元動画を撮った。またチュウニズムデュエルを終わらせた。かなりギリギリになってしまったが、今週木曜日に迫ったアプデ前にやり残したことはもうない。

蒼穹舞楽 14-0-0 手元 pic.twitter.com/ugZKJra3RN
— こたつがめ (@kotatsugame_t) 2022年10月11日

午後11時過ぎにゲーセンを離脱。帰宅してシャワーを浴び、午後11時半からCF #826 div.3。

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

Aは文字列を数字に変換するのがよさそう。Mは $0$ にし、他は文字列の長さを絶対値としてSとLで符号を切り替えるとうまく比較できる。Bは $n\ge 4$ なら2だけrotateすることで常に達成可能。 $n=2,3$ はサンプルにある。Cはsegmentごとの和として $\sum_i a_i$ の約数を全探索。調べるべき数が十分少ないので、判定には毎回 $O(n)$ かけてよい。

Dはボトムアップに計算するのが楽。ノードごとに操作するかしないか、どうしようもないかは一意に定まる。Eはdp。長さが前に来ている場合は配る遷移、後ろに来ている場合は貰う遷移で対処する。

Fはちょっと時間がかかった。色に対して値を持つ区間MAXのセグ木を使う。ここは上位2種類だけ管理することで線形時間に落とせるはずだが、面倒だった。区間 $(l,r,c)$ に対し、 $l'\le r$ かつ $c'\ne c$ なる区間 $(l',r',c')$ であって $r'$ が最大のものを求めると、 $\max(l-r',0)$ が答えの候補になる。 $l$ と $r$ の役目を入れ替えてもう一度同様の計算をし、小さいほうを出力すればよい。

Gは大変時間がかかった。解法はbitDPだが手数が多いし変数の扱いもややこしい。各 $h$ に対して $1\rightarrow h$ の最短経路が $p$ たちのどんな部分集合を巻き込めるか調べる。これは $1$ と各 $h_p$ から全点に対する距離を求めておけば計算できて、巻き込みたい $p$ を $1\rightarrow h_p$ の距離順にソートして順に辿るときの距離と、 $1$ からストレートに $h$ に向かうときの距離が等しくなればよい。bitDPの遷移を行う前にこの判定を計算すれば $O(f(2^kk+3^k))$ が達成できるが、自分は判定しながら遷移する $O(f3^kk)$ で解いた。

全完8位。FGでの失速が痛い。Cは一つ目の区間の長さを全探索してもよかった。

上にツイートを貼った手元動画はコンテスト後に投稿したもの。その後コードゴルフしたりハーメルンの更新をチェックしたりした後、先週の週記の昨日書き残した部分を完成させた。なろうの印象に残っている部分をリストアップするためとはいえ、ページを開いたのにサッとチェックするだけで終わるわけもなく、かなりじっくり読み返してしまったため午前8時くらいまでかかった。その後就寝。

10/12(水)

午後5時起床。なろうを読むのとチュウニズムのアプデ前公式生放送を見るのを繰り返していた。午後9時過ぎに寝落ちし、日付が変わったあたりで再度目覚めた。

www.youtube.com

自分がTAをしている講義は、先生が用意したpdf資料を分担して発表するセミナー形式で行われる。発表に用いる原稿あるいはスライドについて、講義前日までにClassroomに投稿されれば先生とTAでコメントをつけるということになっていた。初回の発表は明日なので、いつ投稿されてもいいようにメールや通知には気を配っていたが、結局寝ている間にも来ていない。

ところがClassroomを開いたらちゃんと午後5時くらいに投稿されていた。通知を見るだけではなく、しっかりページを確認しに行かなければならなかったようだ。確かに前日までに投稿されているので、コメントをつける必要がある。しばらくその作業をしていた。本当はこんな時間にTAに関する作業をしてはいけないらしい。

その後はなろうを読みふけっていた。午前6時に1作読了。「設定鍵インベントリア：シャンフロの諸々」。

https://ncode.syosetu.com/n6458eg/

先週読了した「シャングリラ・フロンティア〜クソゲーハンター、神ゲーに挑まんとす〜」の番外編や設定を集めたもの。掲示板回が読めてよかった。本来は投稿日を確認して本編と並行して読んでいくべきだったかもしれないが、しかし一度最新話まで読んでからこちらに触れる利点もあって、設定で伏せ字にされている部分がところどころ理解できるのが面白い体験だった。こんな昔から練られていた設定なんだなあと感動することが多い。

本編の2回目にプロゲーマーと対決する場面、509部分に「ヴィランが律義にエレベーターでビルを昇る」というギャグがある。これ単体でも面白かったのだが、実は1回目の対決中のシーンを下敷きにした天丼ネタだったということを知った。当時の本編には描写がなく、掲示板にのみ言及があった。

履修登録を済ませた後、指導教員の先生から依頼された、講義で使用するスライドのチェックを行った。チェックといっても誤植を見つけるだけ。ただ70ページ弱あってそれなりに時間がかかった。

午前10時半に布団に入り、ハーメルンを開いた。原作カテゴリに「シャングリラ・フロンティア」が存在するのを見つけ、試しに検索してみると、253件もあってひっくり返った。一つ選んで読み始め、2時間くらい経ったところで就寝。

原作：シャングリラ・フロンティア - ハーメルン

10/13(木)

午後3時半起床。TAのため大学に向けて出発。

まず成績証明書を発行した。火曜日に言っていた確認作業のため。結局学務情報システムから見るのと同じ状態、つまり工学研究科で開講された講義は卒業要件に含められない状態になっていた。せっかく頑張ったのにという気持ちはあるものの、まあ数学専攻なのにハードウエア基礎の単位で卒業するというのもよくわからないから、理解はできる。内容も自分の興味に近く、無駄になった気はしていない。今期取った講義もいくつかはこういう扱いになるのだろう。2年次ではちゃんと専門科目から単位を集めるようにしたい。

5限、TA。スライドを映すために自分のノートPCを貸したら、Ubuntuに入っているPowerPoint互換ソフトでは数式がうまく表示されないらしくて、結局先生のMacを使うことになってしまった。この切り替え作業で少し時間を食ってしまったのが申し訳ない。

発表は細部が丁寧だし堂に入っておりびっくりした。90分まるまるやりきるというのも含め、昨日スライドをチェックした時に感じた以上に、非常によく準備されていた。1年生ということで正直ちょっと舐めていたかもしれない。

残った5分で、先生に言われて途中の定理の別証明をサッと紹介し、終了。このとき発表の内容に関する補足も無理やり差し込んだ。本当はポジティブなフィードバックも含めたかったが、TAがどれくらい出しゃばってよいのかわからない。

学食で食事して帰宅。しばらくコードゴルフして、午後7時半に布団に入った。昨日読み始めたハーメルンを読了。「シャンフロ掲示板シリーズ」。

syosetu.org

主人公のスキルや挙動が外野にすぐ解説されてしまうのはちょっとモヤっとするが、それがなければただすごいすごい言うだけになってしまうので仕方ないのだろう。バランスはなかなか難しそうで、本家に比べて違和感があるのも当然か。それらを加味しても、掲示板回がたくさん読めるというだけで十分にうれしかった。

本編512部分、プロゲーマーとの対決2回目の決着は、意表をついて現れた子供NPCを見てプロゲーマー側が硬直するというものだった。いくら驚いたからといってそんなに動きが止まるか？と思っていたが、そもそも操作キャラの設定に子供NPCの泣き声で硬直するというものがあったのを、掲示板の言及で思い出した。その設定は182部分の後書きに書いてあったもので、本編を読んでいるときは忘れてしまっていた。

同じ原作の別の作品を開いて少し読んでみたが、恋愛をピックアップしたものなので気分に合わず、投げ出した。

午後8時半から3時間ほど仮眠していた。起きてすぐCF #827 div.4。

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

ABはよい。Cは横線がR、縦線がBと決まっていることが重要。横一直線のRがあるかどうかで場合分けする。Dは毎回 $O((\max a)^2)$ かけて計算する。このあたりですでにジャッジが詰まり始めていた。

Eは左から累積MAXを計算してその上で二分探索。Fは $t$ にa以外の文字があるか、 $s$ にa以外の文字がなく、 $s$ が $t$ より短い場合のみYESとなる。a以外の文字を含むかどうかと文字列の長さをそれぞれ管理した。

Fを提出したときにDがサンプルで落ちているのに気付いた。 $a_i\lt a_j$ のケースだけ考えていたが、 $a_i=a_j=1$ もOKであるのを見落としていた。再度提出。

Gは累積ORが増えるタイミングが高々30回しかない。よって、累積ORが数列全体のORと等しくなるまで、残っている要素を全探索して最大にできるものを先頭に置くのを繰り返しても間に合う。

全完5位。Dのリサブで+9分となり残念。ただサンプルで落ちてくれたため、ペナがつかなかったのだけはラッキーだった。

結構長い間TLを見て時間をドブに捨てていた。MHC Tシャツを注文したというツイートが流れてきたのでメールを確認すると、自分のことろにも商品に関するメールが届いていた。ただしソーシャルのタブに入っていたので、ツイートが目に入らなかったらそのまま気づかなかった可能性もある。危ないところだった。

午前4時から日記を書き始めた。朝方になって一瞬だけインターン関連のコーディングを行い、午前10時に布団に入った。しばらくラノベを読んで正午ちょっと前に就寝。

10/14(金)

午後3時の直前に起床。すぐさま1on1。

昨日寝る前の一瞬で実装したものについては、その時に出力が期待通りであることまで確かめてあったので、今日はそれをお見せして新しいタスクの話をするだけだと思っていた。しかし改めてコードを確認すると盛大に書き間違えている。慌てて修正して実行すると、なんと出力が変化してしまった。これまで期待通りの出力をしていたのにそこから変化したというのは、今のコードが正しくないということに他ならない。

原因に全く心当たりがないので自分は早々に絶望してしまったが、今は大本となるコードを実装された方と1on1している。無事問題のある部分を見抜いてくださった。幸い修正も簡単で、すぐに正しい出力が得られるようになった。あとは来週のタスクについて話し合って終了。ペアプログラミングすることになったので、ちゃんと睡眠を取ってはっきりした意識で臨みたい。今日は寝起きだったので最初口が回っていなかったような感覚がある。

サークルに参加するため外出。大学の教室に着いてすぐバチャに参加した。6問目までは特に言うことがない。7問目はそれなりに苦労して30分程度でAC。ちゃんと参加したはずの、しかもそれほど古くないコンテストの問題なのに、どうやって解いたか全く記憶になかったが、実はこれは新規ACだったらしい。AGC045-C。当時はBと心中したようだ。

https://kenkoooo.com/atcoder/#/contest/show/9b2231e9-0635-4e29-a602-81cd00cac55d

Submission #35638627 - AtCoder Grand Contest 045

$A\ge B$ となるようswapしてよい。ある01文字列が操作後としてvalidであることと、1が $B$ 文字以上連続する箇所を全部0に揃えた上で0が $A$ 文字以上連続する箇所があることは同値。0が連続する箇所を固定することで重複を取り除く方針が思い浮かぶが、かなり大変そうなので、条件をチェックしながら文字列を先頭から構築することにした。

現在0が何文字連続しているかを状態に持つ。その次に0を置くのは簡単。1を置くときが問題だが、連続する1をまとめて置くことで対処できる。それが $B$ 文字未満ならこれまで連続していた0の文字数はリセットされる一方、 $B$ 文字以上ならリセットされず、さらに今置いた1の文字数が追加されるのだ。

どこかのタイミングで0が $A$ 文字以上連続したことがあるかのフラグと、直前に置いた文字が0か1かのフラグを持って、状態数 $O(N^2)$ で遷移が $O(N)$ のdpが書けた。この段階で一度サンプルを試すと合っていたので、いよいよ遷移を高速化する。といってもこの部分は簡単だった。dp配列に対して横や斜めの区間加算になったので、imos法を使えばよい。

しばらく感想戦を行った後、学食に寄らず帰宅。木曜日に仕送りの冷凍食品が届いて冷凍庫が満杯になったため、土曜日の冷凍弁当配達までに少しでも消費しておく必要がある。食事して午後8時から仮眠。

ちゃんと目覚ましは午後9時過ぎにかけてあって、一度意識を取り戻したことは覚えているが、yukicoderに出ようというモチベーションが足りず起きられなかった。次に目を覚ますと日付が変わっていた。幸い今日のコンテストは4時間もあるので、遅ればせながら参加。マラソンのA問題以外は時間内に解けた。

yukicoder contest 364 (Do you know Cherry Contest?) - yukicoder

Bは単にcinで受け取ったため最初の単語しか読めていなかったが、判定を先頭1文字で行ったため難を逃れた。

Cはちょっと難しい。 $A$ 日後に行く回数を決め打つ。 $A$ 日後に $B$ 回行くのと $B$ 日後に $A$ 回行くのは相殺できるため、 $T\lt 0$ の場合は $B$ 回以上、 $T\ge 0$ の場合は $B+\lceil T/A\rceil$ 回以上のケースを考えなくてよい。よって全探索可能で、この範囲ならオーバーフローも起こさない。 $T\ge 0$ の場合上限が大きくなることに気づかず1WA。

Dはよい。Eは $L\le i\le R$ について $D\lt T_i$ なら $A_i$ 、 $T_i\le D\lt T_i+A_i$ なら $A_i+T_i-D-1$ 、 $T_i+A_i\le D$ なら $0$ を足し合わせればよい。クエリを $D$ の昇順に答えることにすれば、セグ木に値をセットしたり削除したりすることで計算できる。Fはローリングハッシュ。法が一つだと落ちたので三つ使った。このあたりいつも適当に増やしている。

コンテスト終了後に解説を確認した。Fの法は二つあればよいらしい。

snuke.hatenablog.com

しばらく日記を書いた後、ラノベを読み始めた。1冊読了。「最凶の魔王に鍛えられた勇者、異世界帰還者たちの学園で無双する」3巻。

面白かった。開幕早々大勢の前で主人公が自分の実力を見せつけるシーンがあり、一気にテンションが高まる。その結果で周囲から噂されるような描写こそなかったものの、その後も自重せずに能力を振りかざすバトルシーンが多く、大変楽しかった。ただ外面の順調さとは裏腹に、主人公の考えは良くない方向に先鋭化している。そのうち致命的に破綻しそうで少し怖い。やられ役のセリフにもそういう状態を揶揄するものがあり、そこだけは単純に主人公の無双を楽しむ気持ちにはなれなかった。これまで自分が思っていた敵味方の区別がラストの展開であいまいとなり、意表を突かれた。これからも楽しみ。

また日記に戻る。午前10時半ごろ、今日の終わりまでほとんど書き上げた段階で布団に入った。そこから少しハーメルンを読んで、午前11時過ぎに寝落ち。

10/15(土)

午後3時起床。冷凍弁当を受け取った。かなり苦労したが何とか冷凍庫に押し込むことに成功。1時間ほどハーメルンを読んでからまた寝た。

午後8時半起床。食事して午後9時からABC273に出た。

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

Aは $N!$ を出力する。Rakuで書いた。 $1\dots N$ を演算子*でfoldする……のだが、 $N=0$ のとき空集合をfoldすることになると気づいていなかった。幸いそのようなケースは単位元として $1$ を返してくれるらしい。

Bは $i=0\dots K-1$ の順に $10^i$ の位の値を取得して四捨五入する。Cは $A$ を昇順にソートして、各 $i$ に対して $i\le j$ であって $A_j\lt A_{j+1}$ となる $j$ を数え、それを $K$ とした場合の答えをインクリメントした。

Dは面倒。mapとvectorで行・列に対してそこにある壁を順に並んだ状態で持つと、その上で二分探索することで、移動先にある最も近い壁を十分高速に求められる。

Eは永続化データ構造をあまり知らないので身構えたが、末尾の要素に注目することを思いついたらかなり簡潔に解けた。ADDクエリで追加された要素について、その直前の要素がなんであったかというのは以降絶対に変わらない。また直前の要素さえわかればDELETEクエリに対応できる。これら2種類のクエリは数列の末尾の要素だけ管理しておけば対応できるし、出力も行える。このことから、SAVEとLOADは末尾の要素が何かという情報だけ扱えばよいこともわかる。

Fは座標を全部まとめてソートし、区間dpをすればよい。状態数 $O(N^2)$ 、遷移は左右に1広げるだけなので定数時間で行える。原点にゴールや壁、ハンマーがある場合について少し考えたが、制約から座標の絶対値が $1$ 以上なので気にしなくてよい。

G。 $R_i=1$ なる $i$ の個数を $r_1$ とおく。同様に $r_2,c_1,c_2$ も定める。 $r_1+2r_2\ne c_1+2c_2$ なるケースは先に弾いておく。

$C_i=2$ なる列に置かれた値の和は $2c_2$ となるが、それだけで和が $R_i$ になるという条件を満たした行が、 $R_i=1$ について $x$ 行、 $R_i=2$ について $y$ 行あったとする。二つの変数が満たすべき条件は $0\le x,y$ 、 $x+2y\le 2c_2$ 、 $x\le r_1$ 、 $y\le r_2$ に加え、残った $z=2c_2-x-2y$ を $r_2-y$ 行に割り振るため $z\le r_2-y$ も必要となる。

まず $x,y,z$ 行の決め方が $\binom{r_1}{x}\binom{r_2}{y}\binom{r_2-y}{z}$ 通りある。次に、先に $c_1$ の割り振り方を決める。 $2c_2$ を割り振った後、 $r_1-x+z$ 行が残り1、 $r_2-y-z$ 行が残り2を必要としている。ここを $c_1$ 列の1で満たす必要がある。残り2の行を二つに分け、一旦割り振り方を $c_1!$ 通りとした後、改めて $2^{r_2-y-z}$ で割れば場合の数が求まる。

本題の $2c_2$ の割り振り方についてはdpで求めた。割り振りたい値が $2i$ あって、そのうち $2j$ を $j$ 行に2ずつ、残り $2i-2j$ を $2i-2j$ 行に1ずつ割り振る方法を数え上げる。 $(i,j)$ を状態とすれば遷移は2の行と1の行のどちらにどれだけ置くか決めるだけなので定数時間で行える。必要なのは $(i,j)=(c_2,y)$ であった。以上を全部掛け合わせたものを、すべての $x,y$ に対して足し合わせれば答えとなる。

ExはStern-Brocot treeなど検索してみたものの手も足も出ず、終盤20分くらいはコードゴルフをしていた。7完8位。

コードゴルフ。Aはdcだと上手く書けなかった。今のところ最初に提出したRakuが最短となっている。Bは後述。CはRubyで書いたものの、Perlからbashを呼び出すほうが短くなるらしい。朝方になって、bashからPerlを呼び出すことでさらに1B縮んでいた。EはAWKで縮めたが改善点がいくつかあって負け。他は手付かず。

Bについて。コンテスト中の方針は10のべき乗を使って $X$ を操作する方針だったが、dcだと $X$ を10でどんどん割っていくほうが短い。dcでループを書こうとすると再帰を使うことになるので、行きがけに10で割った分帰りがけに10を掛けるというのが簡単に行えるから。ところがもっと短い方法が見つかった。 $X$ に5を $K$ 個並べた数を足し、 $10^K$ の倍数になるよう切り捨てても答えが求まるようだ。そのコードを弄ってみたら1B縮んだので、今は自分が最短となっている。

午後11時半からCGR23に出た。

Dashboard - Codeforces Global Round 23 - Codeforces

Aは1がどこかにあればよい。数列の長さが $k$ になるまでその位置を避けつつ1番目の操作ができて、最後に2番目の操作をすれば達成される。

Bはほとんどの要素が0か1のままになりそう。操作後の数列における0と1の境界を、操作によるずれも加味しつつ元の数列の境界として戻してみると、そこより左の1はすべて操作によって削除され、右の0はすべて操作によって1以上になるか削除されている。この境界を全探索する。

左の1を $x$ 個、右の0を $y$ 個とする。まず $x$ 回の操作で左の1を削除し、できるだけ多く右の0を1にする。 $x\ge y$ のときは余った $x-y$ を右端の要素に押し付け、 $x\lt y$ のときは残った $y-x$ 個の0をさらなる操作によって削除することで、いずれにしても $\max(x,y)$ 回の操作で広義単調増加にできる。全部0か全部1の場合は押し付けたり削除したりできないことがあるが、境界を全探索しているので問題ない。

Cは転倒数を0にできるはず。すべての $i$ について、 $a_i-a_{i+1}$ 以上の値を $i+1$ から始まるsuffixに足すことができればよい。 $N\dots 1$ の順に、 $a_i-a_{i+1}$ が大きな $i$ に当てはめていけばできそうだったので、証明せずに提出した。

Dはメモ化再帰。葉でない頂点 $u$ に対しそこを $i$ 回通る時の答えを求めるには、 $u$ の子の数を $c$ として、 $u$ の子すべてについて $i\leftarrow\lfloor i/c\rfloor,\lceil i/c\rceil$ としたときの値が求まればよい。 $i$ の変化から、各頂点について $i$ は $k$ を何かで割って切り捨てたものと切り上げたものの高々2種類しか考えなくてよい。ここでうっかり $\lceil i/c\rceil$ ではなく $\lfloor i/c\rfloor+1$ を使うと、パスグラフのときに2乗オーダーになってしまうらしい。まったく意識していなかったので、引っかからなかったのはただ運がいいだけ。

ここまで順調に解いて20分。しかしなんと、残り全部の2時間かけてもE1が解けなかった。別の問題に目を通したわけでもなく、4完303位で2949→2827(-122)。その後E1をupsolveした。

二分探索したいが、2分割すると全然情報が得られない。よって3分割することを考えていた。何回か聞くことで $1/3$ または $2/3$ にできればよい。前者なら8回、後者は2回が使える上限となる。嘘をつかれるタイミングを全探索して必死に実験していたのに、ここに致命的なミスがあった。

そもそもこういう問題は、直前までのクエリの結果を見て何を聞くか決めるべきなのである。なので固定した8セットあるいは2セットを探索していては見つかるものも見つからない。苦し紛れに5回のクエリで $2/3$ にする方法を発見し、手で場合分けすることで最短2回で確定させるものを実装したが、ジャッジがadaptiveのため通るわけもなかった。このあたりでようやく、聞くものを動的に決めるべきだと思い至ったはず。

解法1。そうやってうまく聞けば2回か3回で $2/3$ にできるらしい。常に3回かかった場合クエリが2回ほど多いように見えるが、通っている。

[E1] 3 回で 2/3 に減らす。a, b, c の 3 分割して。
a → o → b → o → ab が残る
a → o → b → x → ac が残る
a → x → a → x → bc が残る
a → x → a → o → b → x → ac が残る
a → x → a → o → b → o → ab が残る
— maspy (@maspy_stars) 2022年10月15日

10/17追記：3回聞いた場合は集合のサイズが必ず $\min(|B|,|C|)$ だけ減るので、 $n=|A|+|B|+|C|$ が3で割って2余る数だった場合、 $|A|=\lfloor n/3\rfloor$ 、 $|B|=|C|=\lfloor n/3\rfloor+1$ と分割することで普段より少し多く減らせる。実際に実験してみると見事に81回となった。

これは、a<=b<=c としておけば N <= 138254 で 81 回です。（x ← ceil(1.5x)） pic.twitter.com/xa189E2C9b
— maspy (@maspy_stars) 2022年10月17日

解法2。実は2回で $2/3$ ではなく $3/4$ にするのでもよい。 $A,B,C,D$ と4分割して $A\cup B$ と $A\cup C$ を聞くことで見事に分離できる。最後に残った3個の候補を2個にするには、先ほど述べた5回で $2/3$ にする方法を使ってもクエリが足りる。こちらを実装して通した。

つまり4分割することさえ思いつくことができていれば、固定した2セットを毎回聞くので十分に対応できたのだ。候補が2個になるまで減らすには3分割だよなあとばかり考えていて、最後微妙なところだけ別で処理しようという気にならなかった。それに、 $2/3$ にするにしてはクエリ回数2回が合計82回に比べてかなり余裕ある値だとも意識できていなかった。ダメダメ。

布団に突っ伏してラノベを読んでいたら寝落ちしてしまった。午前5時前のはず。

10/16(日)

午前9時前に起床。二度寝するかしないか迷いながらもラノベを開き、そのまま夕方までずっと読書を続けていた。3冊読了。

「アストラル・オンライン」。微妙。ストーリーがあまり面白く感じられず、主人公の設定が「シャングリラ・フロンティア」と似ていることにばかり目が向いてしまった。これはその2作を連続して読んでしまったのも運が悪かった。

「凶乱令嬢ニア・リストン」。面白かった。普通にバトルする話だと思っていたら、主人公がテレビっぽいものに出演し始めてびっくり。そういう展開があることはイラストやあらすじを見ているだけでは全然わからなかった。好みの展開なのでこのサプライズは嬉しい。

「君と紡ぐソネット」。面白かった。受験数学に焦点を絞るため、数学教育が偏重された世界という設定を加えるのがアクロバティック。登場人物の名前に数学用語が含まれていてニヤニヤしていたが、よくよく見ると日本人数学者の名前も使われていた。普通の苗字なのでしばらく気づかなかった。主人公は数学で点は取れないものの、考えるのが好きだから理系に進んだらしい。その進路の決め方はかなり勇気があると思った。

主人公たちが取り組んでいる問題の一部は実際に本文中に登場する。1行2行で記述できる問題ということで、ほとんど整数論の問題だった。競プロで鍛えた典型力を使うとホイホイ解けてしまうので、それに苦戦しているキャラを見るとじれったい気持ちになったが、その分成長して解けるようになってくれると開放感があった。以下のツイートにある説には同意できる。一問、解けると言っても結構頑張って計算する必要があった答えが、見方を変えると一瞬で求まったのにはしてやられた気持ちになった。

自分東大数学レベルとか数学オリンピックレベルの数学はあんまり出来なかったはずなので、ラノベ形式で採用しやすい問題が競プロ勢とめちゃめちゃ相性が良い説が自分の中で有力。
— chokudai(高橋直大)🍆@AtCoder社長 (@chokudai) 2022年10月8日

作中に競技プログラミングへの言及があってびっくりした。受験数学と競プロがそれほど関係しているとは思っていなかったが、今どきはOMCもあってかなり界隈が近くなっているのかもしれない。

うわーこれはすごい……！

拙作の中でも競技プログラミングに少しだけ触れてはいるのだけど（東大受験の数学バトルを描く過程で無視できませんでした）、ついにストレートで青春小説に。 https://t.co/yud6dOtD6e
— 暁社夕帆@数学ラノベ『君と紡ぐソネット』発売中！ (@y_akiyashiro) 2022年10月3日

その後3時間ほど日記を書き、午後9時からARC151に出た。

AtCoder Regular Contest 151 - AtCoder

Aは $S_i=T_i$ なる箇所はなんでもよいため0を入れておくのが最適。 $S_i\ne T_i$ なる箇所はどう決めても $S$ との距離が1増えるか $T$ との距離が1増えるだけなので、そのような位置が奇数個ある場合は $U$ を作れない。偶数個の場合どう決めるか迷ったが、後ろから貪欲にするのがよい。あらかじめ全部0を入れておいて、後ろから見て $S$ との距離と $T$ との距離の差が縮まるときだけ1に置き換える。

Bは辞書順で大小関係が定まるインデックス $i$ を固定して考える。 $A_i\lt A_{P_i}$ かつすべての $j\lt i$ について $A_j=A_{P_j}$ となる場合の数を求めたい。等しいとされた要素の関係をUFで管理し、 $A_i=A_{P_i}$ となってしまう場合は除いておく。UFの連結成分数を $c$ とすれば $c\ge 2$ であり、 $A_i$ と $A_{P_i}$ の決め方は $M(M-1)/2$ 通り、残りは $M^{c-2}$ 通りとなる。掛けて $1\le i\le N$ で足し合わせれば答えが出る。

毎回powを使って $M^{c-2}$ を求めるのが重いかなと考え、 $M^N$ に適宜 $1/M$ を掛けていく実装にした。しかし $M=998244353$ のケースでRE。なぜ $M\lt 998244353$ という制約になっていないのか……。

Cは実験。両端に書かれた値が等しい場合、異なる場合、片方の端がマス目の端である場合、両端がマス目の端である場合と4通りの状態が考えられるので、それぞれ間にある空きマスの数に対応したGrundy数を求めてみた。ほとんど0か1になってちょっとビビるも、自分の実験コードが正しいことを信じて提出したら通った。ちなみに最初は前二つの状態だけ実験していて、その時は本当に0と1しか出現しなかったのでかなりの割合で自分のミスを疑っていた。

D。とりあえず一つのクエリにおける操作がゼータ変換っぽい形式になることは分かった。何かしらの変換を施した状態で列を管理すれば更新すべき要素が少なくなったりしないかと考えるも、うまくいかない。サンプル1を手で試していたら、クエリの順番を入れ替えても答えが同じになりそうだと気づいた。 $(X,Y)$ が同じクエリをまとめて遷移するのはできるので、実装。サンプル2も合ったもののWAだった。

そんな感じで1時間くらい使ったが解けなかったため、Eに移った。こちらはそれなりに素早く解けた。 $X$ から $Y$ に移ったとき、元の $X$ で残っている部分があるかないかで場合分け。残っている部分がある場合は、その部分を $Z$ と置くと、 $X$ から要素を削除して $Z$ 、 $Z$ に要素を追加して $Y$ と遷移するのが最適。操作回数は $P+Q-2|Z|$ となる。このような $Z$ としては最長共通連続部分列を取るべきで、SAとLCPを使って求められる。

残っている部分がない場合は必ず $P+Q$ 回以上かかっているので、 $X$ と $Y$ に共通する要素があるならそれを残して操作するべき。よって後は $X$ と $Y$ で要素が一切共通しない場合を考えることになる。このとき、 $X$ としてはできるだけ短い状態でいたほうが自由に動けて嬉しいはず。空列は許されていないので、長さ1の状態と長さ2の状態を交互に取ることになると考えた。

つまり、初手で $X$ から1要素選んでそれ以外を削除した後、長さ2の状態と長さ1の状態を交互に取って $Y$ に含まれる1要素だけの列となり、最後に $Y$ を復元するのが最適。長さ1の状態から別の長さ1の状態に遷移できる条件は、使った2要素が $A$ の中で隣接していることである。よって $A$ を用いてグラフを作り、 $X$ に含まれる要素から $Y$ に含まれる要素までたどり着くまでの最短経路問題を解けばよい。

Dに戻ってきた。よく見ると $X$ が同じで $Y$ が異なるクエリの順番を入れ替えているのはまずそう。そこで、 $X$ が同じクエリだけまとめて遷移することにした。 $Y$ に応じて値がどのように変化するかは、一組の $(j,j')$ に関して係数を前計算しておけばわかる。それを $2^{N-1}$ ペアに適用すればよい。出したら通った。

20分余ったがFのsolved数が絶望的。すぐ縮みそうな問題もないし、特に何をするでもなく時間を過ごしてコンテスト終了。5完38位。

午後11時半からCF #828 div.3に出た。

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

Aは同じ数に対応する文字が同じかチェック。Bはちょっとややこしかった。「最初偶数だった項」と「最初奇数だった項」でそれぞれ足された値を管理すれば、クエリのたびに今の偶奇がわかる。あとはそのような項の数と掛け合わせ、 $\sum_i a_i$ と足して答えになる。Cは $s$ における $c$ と同じ文字に対し、それより先にあって最も近いgまでの距離を求め、最大値を出力する。gを一つ探し、そこから逆向きにぐるっと一周すればよい。

Dは最初の状態でどれだけ2べきが足りないか求め、2べきを多く含む $i$ から順番に使っていく。Eは $a,b$ の約数 $a_x,b_x$ を全探索し、 $x$ として $c$ 以下で最大の $a_xb_x$ の倍数、 $y$ として $d$ 以下で最大の $a/a_x\times b/b_x$ の倍数を使うことにして範囲の条件を満たすことを確認。 $a_x$ としてありうる数、 $b_x$ としてありうる数はE2の制約でもそれぞれ最大1344個なので、2乗で十分間に合う。

FはMEXを $k=1\dots N$ で固定。 $l_l\le l\le l_r$ かつ $r_l\le r\le r_r$ なる $(l,r)$ について $p_l,\dots,p_r$ のMEXが $k$ となる、という情報が得られる。中央値が $k$ 未満となるのは、 $k$ 未満の数の個数が $k$ 以上の数の個数以上となる場合のみ。前者は $k$ 個、後者は $(r-l+1)-k$ 個なので、 $k\ge(r-l+1)-k$ を満たす $(l,r)$ の個数を求めればよい。丁寧に考えると定数時間で数え上げられる。かなり時間がかかった。

全完8位。Fに20分かけたのが気になる。今考えれば $l$ と $r$ の範囲は $p_i=k$ となる位置を含まないように決めているのだから、 $[l_l,l_r]$ と $[r_l,r_r]$ のうちどちらかは、より大きなMEXを考えるとき常に $[l_r,r_l]$ に含まれるようになる。つまり短いほうの範囲を全探索しても線形時間となるため、そこまで苦しい式変形は必要なかった。

日記を書いて午前3時半就寝。