ABC387

ABDEFの5完。Cを12分ほど考えて飛ばして戻ってこなかったが、これが（珍しく）奏功してFがギリギリ間に合った（間に合わなかったとしても、面白いEFに時間を使ったほうがよい）。あと2分遅れていたらこんな穏やかな気分ではいられなかったはずでね。ごめんCを解かずに黄パフォ取るの気持ちいい。

A - Happy New Year 2025

A問題はこのくらいがいいんだよ。

B - 9x9 Sum

B問題はこのくらいがいいんだよ。積を求めて変数に入れておく。

C - Snake Numbers

N以下のヘビ数の個数を求める関数を作ればいい。例えば3で始まる8桁のヘビ数が何個あるかは簡単にわかる。あとは、Nと桁数が同じで最上位桁も同じヘビ数の個数がわかればいいが、これは桁毎にやる必要がありかなり面倒だ。C問題だし何か楽な方法があるのではないかと考えるが、わからない。桁DPで殴れないかと思ってテンプレを貼ってみたが、何をしていいかわからない。ABCの時間を使い切れば最初の方針で通せるだろうが、こんなつまらないことに時間を使ってもしょうがないので飛ばした。

D - Snaky Walk

初手を縦横で2回やるのめんどくさそうだなあと思いながら考えていた。頂点数を2倍にするやつを使えば典型に落とし込めそうなのでそうした。運良くスムーズにACできた。

あとから考えると解説のやり方みたく余計なメモリを使わずにできるなあ。

E - Digit Sum Divisible 2

全然わからんので実験してみる。実験コードを使った愚直でNが小さい（10^6未満）ときは解ける。Nが大きいときは常にできるんだろうなあと当たりをつけて考えていく。「良い整数」はかなり多い。「双子の良い整数」も多く、この一部にいい性質があったとしても見つけるのが難しそう。しばらくにらめっこして、(2000, 2001)のような組があると気づいた。これは桁数が増えても「双子の良い整数」だ。しかし、4000とかだと1を足しても3の倍数にならないし1を引いたら桁和が増えてしまう。範囲が[N, N*2)なのでねえ。これが[N, N*10)だったら楽なんだけど。他のアイデアとしては、桁和をとってもmod 9は変化しない、8で割り切れるかの判定は下3桁でできる、2倍の範囲で桁和を小さくすることはできる（N=2345のとき3000は桁和が小さい）、など。10^9くらいの大きい数でも実験した。桁和が8と9の組をよく見かけたのでそれ固定で探索してみると、やっときれいな法則性が見えた。桁和が8で下3桁が0なら「良い整数」だし、それに1を足せば桁和が9で9の倍数だから「良い整数」だ（希望が見えてからも実験を繰り返しこのことを少しずつ理解していった）。あとは実装だが、桁数が6以下なら愚直。そうでないとき、上3桁を取り出してTとし、T+1からT*2-1までを全探索する。桁和が8になるものが見つかったら元のNの桁数-3個の0にくっつけて出力する（まあ最低でも100個くらいあるからどれかは桁和が8になるでしょ（全探索で証明できるとは思ったがやらなかった））。桁数が増えるケースがずっと怖かったが、この方法なら自然に対処できている。

F - Count Arrays

頑張って具体例を追って問題の意味を追うと、グラフの気分になってくる。自分はこいつ以下だという矢印が出ている。これが「以上」でも「以下」でも答えは変わらないので、特に区別せず（そのときどきでやりやすいように）考えていった。DAGにならない場合を調べるが、よく考えると頂点と辺の数が同じなのでサイクルにひげが付いたやつにしかならない。つまり、サイクルを発見してそこを根とした木でDPなりして問題を解けばいい。ここはかなり悩んだが、atcoder::scc_graphを使った。強連結成分に複数の頂点が含まれる場合は適当に最初の頂点に代表させ新たにグラフ（森）を構築する。構築するとき同じ強連結成分の頂点からの辺は無視しなければならないと気づいてstd::setを使った（時間がないので重い処理も迷いなく入れる）。入次数が0の頂点を根とみなし、DP。ここで、DPが実はそこまで簡単ではないことに気づく。その頂点が例えば3になるのが何通りか求めるとき、子が3の通り数だけでなく2や1や0（0-indexedでやっている）の情報も必要だ。二乗の木DPとも違うしちょっと困ったけど、これは累積和をとれば対応できる。子の累積和を使って「jである通り数」をそれぞれ求めたら、累積和をとって「j以下の通り数」にする。残り時間の少ない中でサンプルが通らず絶望感が出てくるが、落ち着いて内部の数値を（どれを出せばいいかわからんけどとにかく）出力してみてそれを見た自分が何か感じるのを待つ（ちゃんとこのムーブができるのはえらい）。どうも正しそうなので全体を見直すと、各根からDFSするはずが代表となった頂点以外も全部対象になっていたと気づく。代表だけの入次数をチェックするようにしてサンプルが通ったので提出してAC。頂点数1の木をDFSしても1を掛けるだけで問題ないはずなのになんでこれで出力が変わったんだと疑問だったが、あとから考えると、累積和によってMが掛かってくる（そりゃそうだ最初のイメージをひきずっていた）（サイクル内の頂点は全部同じ数でないといけないからね）。あと、最初のころから、グラフの向きを逆にしても行けそうだけどそれはおかしくないかみたいな不安があって、それは、出次数が1だから入次数のほうをチェックするみたいにちゃんと対称性が（あった/崩れていた）（よくわかってないからどっちでもしっくりきて困る）。

年末恒例、アニメBEST3

少しずつ基準を変えていく。キャラのところにキャラじゃないものを入れるとか以前入れたことがある声優をまた入れるとかもあり。ランキングの健全性よりも見た目のきれいさを重視。緩くしたというよりは、好きなものをちゃんと入れようという方向性。見るアニメが減ってるから相変わらず3つ埋めるのが大変という状況。記憶力も落ちているので、抜けがありそう。

作品

1. この素晴らしい世界に祝福を！3
2. ラブライブ！スーパースター！！3期
3. 魔法少女にあこがれて

このすばは本当に強かった。スタッフも変わってどうなるのかと思ったけど、出てきたのはこのすばで毎回面白かった。終盤の盛り上がりもよかった。その後の一挙放送で見返したときも、このすばってすげえわと思った。

スーパースター2期が変な終わり方だった気するけど、そこからこんな面白い展開になるとは。2期はかのんがスーパースターだと思ったけど、3期は一人ひとりがスーパースターだと感じた。

まほあこはずっと前に漫画を少し見たことがあり、アニメの話を聞いて「まほあこってあの漫画の！？」となった。この時期はあんまアニメ見てなくて、3月と4月に分けて一挙放送かなんかで全部見た。漫画と同じ話をやっているようで、けっこう違う空気を作っている。

サブタイトル

1. ラブライブ！スーパースター！！3期 #8
2. Re:ゼロから始める休憩時間 #55
3. （不明）

姉妹のシーンは泣いた。オニナッツの体型が好き。最後はあまりにも予想通りすぎて笑った。俺ですらわかる。リエラがそうなる理由はここ数話で既に描かれていたんだよというネタばらしが美しい。

リゼロはミニアニメで重要回。2回目でベア子が違和感持ってスバルを見る描写が丁寧。

キャラ

1. 柊うてな（魔法少女にあこがれて）
2. トマカノーテ（ラブライブ！スーパースター！！3期）
3. 新島麻衣（妻、小学生になる。）

うてなちゃんは名前がいいよね。自分はウテナ見てないんだけど、魔法少女系の名前として格がある。性格も好きだし、声もいい。私服のセンスも好き。そりゃキウィちゃんも好きになるよ（これはさすがに雑な言い方）。

トマカノーテはキャラじゃないけど響きがかわいいので。リエラとの距離感がいい。キャラ配置が素晴らしい。マルガレーテが、EDのマルガレーテの位置へきれいに収まるまでの物語。

麻衣は妻の娘。大人でかわいいキャラは貴重。OPのロングスカートが好き（本編でも着てるけど）。

歌

1. 天体のメソッド ED
2. Lv2からチートだった元勇者候補のまったり異世界ライフ ED
3. しかのこのこのここしたんたん OP

天体のメソッドのED曲は有名なので当然知ってたけど、11月に初めてアニメ本編を見たので。これで、知ってるアニメのEDになった。特に見え方が変わるというわけではないけど、女の子のスカートの動きや男の子の重心移動を知ってるキャラで見られる良さがある。

ゼロ魔みたいなED。このモブみたいな4人がメインのEDでいいのかと最初は思ったけど、本編でめっちゃ活躍していいキャラになっていいEDになった。キャラの魅力がだんだん解放されてそれをEDで楽しめるのがいい。

しかのこは、ニコニコ動画が死んでたので9月終わりのニコ生一挙で見た。安心感のあるOP。重すぎず、いっぱい詰め込んで。こういうのももはや古典の部類か。ほんとに作品を象徴するいいOPだと思う。

声優

1. 赤尾ひかる
2. 悠木碧
3. 篠原侑

赤尾ひかるは、ブルアカのコハルで認識して、ユメステの本巣叶羽もこの声で、こみっくがーるずも去年ちょっと見て、という感じだった。えんどろのユーシャの時点では認識していなかった。今年になって本巣叶羽が好きになってそこに声がなじんできて信頼できるようになった。

悠木碧は「妻、小学生になる。」の第一声が原作の声ですごかった。さすがに次からは悠木碧だったけど。

篠原侑はぷにるの声としてよく合っていた。

ABC386

1ペナ6完。Cまでに22分かかっててゴミ。本来、自分にとって簡単な問題を解くのはつまらないけど簡単なら瞬殺できるからまあOKということのはずが、自分の頭の回転が遅すぎてつまらないうえに時間がかかるという惨状になっている。FのDPをちゃんと書き切ったのはえらい。開始時にGitHub Copilotがオンになっていて、まあ使ってもいいんだけど不慣れなのでさすがにオフった（時間のロス）。これ何が問題って、Copilotを試すために何か競プロの問題を解こうとして面倒で1問も解かないまま今日を迎えたんだよね。競プロに対するやる気がめちゃくちゃ落ちている。飽きたと言ってもいい。緑から青diffの問題は面白いけど、そこから外れた問題に魅力を感じなくなっている。難しい問題については、2時間あって自力ACできない問題は解説を見ても自分の能力を超越していて断絶を感じて無理になる（楽に勉強できる典型はほとんど勉強してあるから）。

A - Full House 2

カードを1枚ずつ追加していくとき、カードの枚数が3,2になるためには3,1か2,2を経由する必要があると思う（未証明）（A問題でここまで高い考察難度やめろ（嫌なら全探索すればよかっただろ））。枚数をカウントしてソートしてそれを確認するコードを書く。ソートを降順にするのを忘れてサンプル合わなかった。カード追加を13通り全探索というのもあるが、はっきりしないのでスルーした。今見ると、0が書かれたカードを追加するのも許されそうで、問題文がやや難しい。

解説のおまけのところ、サンプルをよく見てなくて気づかなかった。こういうのいいね。

B - Calculator

AtCoderでこういうのを見ると「DPか！？」って思ってしまうが、よく見ると貪欲でいい。ループ回数が|S|-1でいいのかなり意外で動揺した。

C - Operate 1

Fを読んだが、すぐには解けなそうなのでまずはCを倒す。文字数の差で場合分けする。変更は簡単。挿入は、同じ位置で違う文字があったらそこにその相手の文字を挿入してあとは愚直比較。削除は挿入の文字列を入れ替えればいい。cin >> s, t; を久々にやらかして時間を消費した。

提出してWA。Sの文字数をNとして、挿入できる場所はN個ではなくN+1個だった。N文字一致したら末尾にTの最後の文字を追加するようにしてAC。解説にあるように、前後から一致する文字数の最大を求めるのが明快だった。

D - Diagonal Separation

全ての（すでに塗られた）黒マスについて、自分を含む左上の長方形領域に白マスがなければ、Yes（その長方形の和集合だけを黒に塗ればいい）、一つでもあればNo（その白マスから右と下に動いて黒マスに行ける）。縦位置でソートしてBITかなあと思い貼ってしまったけど、よく考えると（白マスの）横位置の最小値だけでいい（最初最大値で実装しててサンプル合わなかった）。ソートは、同じ行なら白マスを優先する（列はどうでもいい）。ソートした順に見て、白マスなら最小値を更新、黒マスなら自分と同じか左に白マスがないかチェック（自分と同じか上の白マスだけ見ていることに注意）。

E - Maximize XOR

最初は嫌だなあという印象だった。上位ビットから決めようとすると、その位置で何個の1を選ぶかが色々ありえる。制約の意図がわからん。next_permutationの計算量を調べるが、だめかなあという感じ。じゃあDFSは？ワンチャンO(comb(N, K)+N)とかで行けたりしない？と思ってとりあえず実装してみる。Kが大きいときはN-Kに置き換えてあとでA全体の総xorとxorをとる。ラムダ式による再帰も慣れたもんだ。選ぶ回数が残っているときだけ選ぶのは当然だが、選ぶ回数と残り深さが同じときは「選ばない」という選択ができないことにも注意。サンプルは通ったが、計算量がわからない。DFS木が、最後に枝分かれしてからも長く続いているとよくない（極端な話、深さ1とか2とかで全部分かれてしまったら全体にNが掛かってしまう）。実験すればいいと気づきやってみると、Nが小さいときは大丈夫そうだ。N=200000, K=1みたいのがやばい。一方、N=1500, K=2はなんとかいける（制約はギリギリ満たしていない）。長い一本道を次の枝分かれまでスキップするようなことも考えたが、K=1（K=N-1も含む）だけ場合分けすれば行けそうなのでそうした。K=1はN通り試すだけなので簡単。サンプルが通らなかったとき、2024が正解のところ2025と出力していて、芸術点が高かった。279msでAC。

スキップする方法でAC。何回連続で「選ばない」をしてから「選ぶ」かでforを回す。長い一本道はなくなり、どの葉から見ても探索深さがO(K)なのでOK（アクシデンタルダジャレ）。何回連続で「選ばない」ができるかの計算が難しく、1WAを出した。更に解説を見ると、元の自分のコード（K=1を場合分けしないとTLEすると思われる）に1個条件を足すだけで、スキップする方法と同じくらいの実行時間でAC。単に残り回数が0になったらそこで最大値更新してreturnすればよかった。途中の長い一本道はいいのか気になったが、よく考えるとそこは毎回分岐していてforと同じような処理になっている。分岐しないのは残りを全部選ぶときだけで、Kが小さければ問題ないし、Kが大きければ元のコードですら速い。毎回（2個以上に）分岐するなら、そもそも分岐は葉より少ないのでDFSの呼び出し回数もその程度で済む。

F - Operate K

Cをやってたときは解像度が低かったけど、改めて見るとまんま編集距離なんだよな。DPテーブルを横に見て（Yesの場合は）値がO(K)回しか切り替わらないとかそういうのだろと思って、まずは計算量を考えないただの編集距離を書く。このDPを思い出してくると、そういうんじゃなくて編集距離がK以下の部分だけやるみたいなのだとわかる。もう少し考えると、文字数の差がKより大きい場合はNoなので、単に文字数の差がK以下の領域だけをやればいいとわかる。DPテーブルは2行分持ってswap（これはO(1)でできる）しながら使う。問題は、前の行で文字数の差がK以下でない領域を参照して遷移する場合もあるということ。場合分けは面倒なので、有効な領域の前後1個ずつをK+1で埋めることにした。s[i]を追加してi+1文字になる（DPの状態にはi+1を使う）というややこしさがあり、K+1で埋める処理を間違えて時間がかかった。編集距離のDPが、dp[i][j]でSの先頭i文字とTの先頭j文字の編集距離を表しているとわかっているなら、あとは必要な部分だけ更新すればいいという簡単な問題。が、その実装がけっこう難しくて、そこが面白かった。

PAST17-OPEN

2ペナ全完。

A - BMI

式変形して整数で。

B - フルコンボ/Full Combo

普通の音ゲーでわかりやすい。変数名はapとagにした。&&じゃなくて||と書いてサンプルが合わなかった。思考の解像度が低すぎる。

C - 換金/Turn into Money

やるだけだが、A_iから1を引き忘れたのとintでオーバーフローするのをサンプルに教えてもらった。ひどい。

D - Webサービス/Web Service

なんで月毎に与えられるのかわかんなくて最初全部足してたけど、無料分が年毎じゃなくて月毎にリセットなのね。無料分を（0未満にならないように）引くだけ。シンプルな処理でそこそこ難易度高い。

E - 連長圧縮/Run Length Encoding

ランレングスを貼る。

F - 構文木/Parse Tree

グラフを構築すればできるとは思ったけど、細かい方針で迷いまくって時間をかけた。頂点は番号でトポロジカルソート済みという制約に気づいたのは実装がかなり進んでからだった。終了後にやり直して、演算子と値を別の変数に持って、頂点番号の大きい順に値を確定させていけばいい。

G - 蛇行する文字列 / Find the Snaky

DFSで全探索。足跡も管理する。

H - 履修登録/Course Registration

見るからにDP。時間毎に処理する（最近のABCであった気がする）。「ちょうどj単位」を「j単位以上」にできないぞって混乱してた（大きいほどいいか小さいほどいいかが逆だったから？DP苦手だなあ）。結局、M単位以上の状態をまとめることで対応できた。

I - 部分列ペア/Subsequence Pair

5文字の文字列が10^7個くらいだし、部分列としてありえるのも高々2^5個。グラフ構築すらできそうだと思ったけど、配列で持つのはけっこう面倒なのでunordered_mapにした。サンプルが通らず、実際の答えより大きい出力も小さい出力もある。選び方が違っても部分列として同じになることがあるのに気づかなかったのと、個数を使い忘れていたのと。面倒なのでvectorにつっこんでsortしてuniqueした。490msもかかった。

いや解説通りかよ。

J - カフェ/Cafe

どの人が来たかという情報は必要ない。カフェの人数が1人増えた時刻と1人減った時刻とクエリの時刻をソートして時間順に処理すればいいが、端点を含むことから同じ時刻なら増える・クエリ・減るの順にソートする。64bit整数に全部入れたけど、クエリ番号を持つ必要があるのを忘れていて迷走。

K - 正しいチェックディジット / Correct Check Digit

簡単そうだが、構築はけっこう厄介そう。問題名のわりにゴミみたいなチェックディジットだ。DPもあるかと思ったけど、考察で殴ることにした。10=2*5なので、素因数の有無で4通りに場合分けできる。iが10の倍数なら影響を与えない。そうでないとき、5の倍数なら5で割ったあまりにしか影響を与えない、2の倍数なら2で割ったあまりにしか影響を与えない。そうでないとき、好きな値にできる。特に、'0'はどの位置でも値に影響を与えないので、'?'以外のものを先に計算していくつかの'?'で値を0 mod 10にできたら、あとは全部'0'にすればいい。つーことで、5の倍数のときは2の倍数にして、2の倍数のときは5の倍数にすればいい。もちろん3とかの10と互いに素なやつが来たらそこでちゃんと合わせる（10通り全探索）。'?'を数で埋めたとき値を更新してなくてWA。

解説はDPか。確かに思考停止で書けるな。なんでやりたくなかったんだろう。ところでなんでTL3秒だった？

L - 割引券/Discount Ticket

ワーシャルフロイドっぽいけど、さすがに辺（割引を使う場所）の全探索は間に合わない。とりあえず割引券を使わないときの最小を求めておく。これを使うと経路の最後で1回割引券を使うときの最小もわかる。そして、割引券を1回使ってから割引券を使わずにというのもわかり、解けた。4乗になると思ったら2回に分ければ3乗だけでいけた。

解説見たら草。そりゃそうだ。

M - 長方形/Rectangle

なぜかやりたくねえ。落ち着いて考えると、縦横独立にできる。相対速度で考えればいいから場合分けは速度の符号だけ。長方形Bが速度-u（uは正の数）で動いていたら、長方形Aが速度uで動いているとしても結果は同じなので、AB入れ替えればいい。あと相対速度ゼロのときもあったわ。これは区間が重なってるか見て長さ0の区間か全てを覆う区間を返す（制約から全てを覆ったままになることはない）。あとは縦横の区間の共通部分の長さを求めるが、時刻0以降しかカウントしないことに注意する。

N - ソフトウェアアップデート/Software Update

これが一番時間かかった。「Tをソートするだけでよくね」から「やっぱだめかも」になり、見積もりの式を見てそこから「そのときやってるアップデートの真ん中で確認したら誤差は0になる」と勘違いしてしまった。そのアップデートの途中に確認したら必ず誤差が出るというケースもある。グラフ描くと三角形なので平均取るだけ。頑張って計算して提出してWA。コードを整理しながら考えて、だいぶ経ってから「そっちもabs必要だったわ」になってAC。

なぜかFastestを取っていた。

O - 整地クエリ/Flatten Query

Aが変化しないなら、ソートしてxより大きいやつの合計を求めるだけ。実際は変化するけど、1ずつなのでインデックス付きでソートしてそれを小さい計算量で維持できそうだ。インデックスだけでソートしようかとも思ったけど、まあわかりやすくpairで。また、A_iが今どこにあるかを管理するvectorのBも用意する。合計はatcoder::fenwick_treeで。それらを更新できるかが主題となるが、そもそもの話としてAの要素が相異なるならそのまま順番を変えずに更新できる。更新対象の要素と同じ値が大量にあるときどうするか。1増やすとき、同じ値の中で一番右にあればそのまま更新できる。ということでそうなるようにswapする。丁寧な二分探索でその位置を見つける。