Ai と等しい要素が i の直前に出現した位置を Bi とする」とあったが、等しい要素を A 数列から探すのか B 数列から探すのかわからなくてフリーズしてしまった。サンプルで理解したけども、読み飛ばして「
より正確には」以下を読むのでも理解できた。だけどそこまでたどりつかずにぐるぐるとスタックしてしまった。わかれば値の範囲を見て Hash でメモ。■D 問題 Count Simple Paths。計算量で難しさを出してくるのが D 問題というイメージなので、愚直 DFS が通るのは甘々です。だけど BFS は書けるけど DFS はなんか苦手という時期が自分にもありました。■E 問題 Mod Sigma Problem。解けてないよ。６問解く実力がなくて F 問題が 25 点だけ上なら F 問題を先に解かない理由がないよ。■F 問題 Add One Edge 2。単純グラフというのは自己辺なし多重辺なし。単純グラフというのは自己辺なし多重辺なし(２回目)。問題文を読んでるときにこの通りに補完しているが、ABC なんだからそこまで書いてもいいと思うんだよね。知らなきゃ解けないという問題は門前払いされたようで面白くないよ。それが概念でなく単なる言い替えレベルの用語がどう定義されているかというだけのことであればなおさらしょうもなくて面白くない。次数２の頂点同士を結んでその LCA までのパスがすべて次数３であるか、LCA が次数２の頂点の一方であるかという場合を数える。とにかく実装が下手だった。WA (隣接している次数２の頂点を結んでしまっていた。それは多重辺)、WA (葉を刈り取る DP をしているのに処理順が LIFO だった。20241019と同じミス。手癖で書いてるんじゃないのよ。pop かな shift かな pop でいいよねと考えた結果なのが救われない)、WAWAWA (葉を刈り取る DP をしているのだから、１を仮の根としたときの親に処理を流すのは間違いなのよね。この場合の根とは最後まで残った１ノードのことなのだから。一番深いところから積み上げる DP なら間違いではなかったし、脳内イメージではそうしていたんだけど、実際にやってることがちぐはぐだった)、AC (再帰関数で再実装したら AC だった。だって何度問題を読み直してももう考えることが残っていなかったので、原因がわからなくても実装が悪いことが明らかだった)。■レートは横ばい。デバッグとペナルティで失った 50 分が痛い。■■■精進。E 問題。累積和とか転倒数とか BIT とかのワードを見かけてもいまいちピンときていなかったが、ある動画でエスアールヒクエスエルが負と聞いてやっとやるべきことがわかった。それを正しくやるのにも散々迷走して凡ミスをして苦しむんだけど。提出 #59430244 (AC)。■■■精進。水 diff ながら抜けていた ABC221-E LEQ。さっきの E 問題を解いたあとだと普通に解ける気がして、普通に解けた。提出 #59440817 (AC)。ABC378-E とは類題ってことでいいのでは？ 自分は感覚とかイメージとかのふわっとしたもので問題を解いているので(○○の△△は二分探索(を疑う)みたいなトリガーを記憶しておくことも適切に引き出すこともできなくて、二分探索の雰囲気がするから二分探索をしている。例「二分探索っぽさがあるよね」)、式を操作したり式を見て糸口を見つけるということが苦手というか、まったくアプローチができていない。そういう苦手を突くという点で類題だと思った。この問題では２の冪乗というものについて、足し合わせてみたり、足し合わせたものをまとめて割ったりするとどうなるかな、何の問題もなく個別に計算したのと同じ結果が手に入るなということを確認するだけで解答が書けた。昨日まではそれができなかった。ある範囲の連続部分列の和が Sr-Sl であると、それが mod を取ったあとだとどうなるか、それをどうするかと考えてみることができなかった。そういうアプローチが存在していなかった。
N 個のマスすべてに石がちょうど 1 個ずつ入っている」)。石が余る場合に間違えていた。修正に５分。N マスすべてに石が配れるかは確認済みなので、石の総数が N であることをチェックするだけ。ペナルティ込みで 23 分かけた計算。難しいよー。■D 問題「Home Garden」。一転して簡単な問題。配列(生配列とポインタペアで十分)に植えた日を記録していく。収穫は先頭から順番に。４分半。■E 問題「Sum of All Substrings」。かつての ABC-D 緑 diff って感じの問題。まず、余りを取る問題でないことに驚いた。えっ。64 ビットに収まるんですか？ (サンプルを見て)収まらないね。１の位から考える。S の各桁の数字は１の位として何回活用されるか。10 の位、100 の位としては……。繰り上がりも考慮して決めていく。提出までおよそ 30 分。書く量は 252 バイトでもすらすらとは書けない。■F 問題「Buildings 2」。よみがえる ABC372-D「Buildings」の悪夢 (「脳みそがスポンジ化している」「番狂わせの D 問題」「提出するまでほぼ１時間ぐだぐだやっていた」「問題が全然頭に入ってこない」「いったい何を数えるんだよー」「"ビル i とビル j の間にビル j より高いビルが存在しない" という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ」「理解したら実装は５分」)。慎重に問題とサンプルを読んで理解に努めた。基本的には自分自身を起点とする増加列を数えておけば良さそう。自分より低いビルも見ることができるんだけど、r より低いビルを l から見ることはできないので、それは数えても意味がない。l と r の高低にかかわらず r から見える r より高いビルの数が答えの候補になる。あと考えることは、l から r が見えない場合。答えはゼロではなく、あいだにある最も高いビルから見えるそれより高いビルの数が答えになる(この条件は r が最も高いビルである場合もカバーするので場合分けが消える)。ランダム入力と愚直解法からこのケースを見つけた。ABC372-D の記憶によって数えるべきものがはっきりわかっていたから、見つけたケースの解釈で迷うことがなかった。あとは増加列を数えるのに LIS をやるポカをした。スタックを１本持って長さを数えるだけでいいのはさっき挙げた Buildings と同じはずなんだけど、なんで同じにできなかったんだろうなあ。最初の提出 #59612302 (WA) を書くのに 20 分かけて、デバッグに 20 分かけた。提出 #59621904 (AC)。■G 問題「Count Grid 3-coloring」。10 分も残っていないので問題を読むだけ。左の数字と上の数字を参照して１,２,３の場合の数を数える DP かなと思ったけど、制約が３乗を許容しているし制限時間も長めの３秒なので、何かが抜けているか全てが間違っているかのどちらか。■コンテスト成績証。青パフォ 1763。■あっ、F 問題の問題名が Buildings 2 だ！ そうか、問題名で自己言及していたのか。■■■C 問題。左にある石の山から処理をしようとするといろいろ保留することになって面倒そうと書いたけど、実際には左からやった方がシンプルになった。提出 #59709275 (左から / 204 Byte)。提出 #59582960 (右から / 280 Byte)。
1*/2* を拾い出してからスラッシュの位置を探して計算した。なんでか 10 分かかっている。■D 問題 1122 Substring。やることが多いよね。まずペアの列を複数切り出したんだけど、同じ値が３つ以上連続している場合に注意が必要。その部分でペアの列を切って新しい列を始めるのだけど、どちらの列にもペアを登録することになる。たとえば 1 1 2 2 2 3 3 が与えられたとき、得られるペアの列２つは 1 2 と 2 3 になる(同じ数字の繰り返しは省略)。2 と 2 のペアが前後のどちらの列にも属している。その次にペアの列に対して同じ値を含まない最長の範囲を求める。現在の値を右端とするとき左端がどこまで伸ばせるかを考えた。最初は値ごとに直前の位置を記憶しておくだけでいいかと思ったけど、そうではないのだな。たとえばペアの列が 1 2 3 2 1 だったとき、右側の 1 から左側の 1 の直前までを切り出すと 2 3 2 1 になって違法。値ごとに直前の位置を記録するだけでなく、その最大値を１つメモしておく必要があった。RE/WA を１回出しつつ 26 分かけた。難しいし妥当だと思う。■E 問題 11/22 Subsequence。25 点だけ配点が上の F 問題に先に取り組んだけど追い返されてきた。スラッシュの位置にそのスラッシュを中心とする 11/22 文字列の長さを記録しておけば、(区間の両端に近いスラッシュだけちょいちょいと調整すれば)セグメント木の区間クエリで答えが出せると思ってしばらく無駄な時間を費やしていた。何を勘違いしていたか。「(連続とは限らない) 部分列」で 11/22 文字列を構成するということは、スラッシュとスラッシュで 11/22 文字列が区切られるわけではない、ということがわかっていなかった。スラッシュを飛ばしてその向こうまで 1 なり 2 なりの文字を拾い出して構わない。ということを理解すると、スラッシュの位置ごとに左に１がいくつあって、右に２がいくつあるかということだけが重要。クエリで範囲が与えられたとき、どのスラッシュにとっても同じ数だけ１と２の利用が制限される。範囲内のスラッシュに対して二分探索で左右の１と２の均衡点を探る。こういう二分探索は少し前に初めてやった(ABC364-D「K-th Nearest」、20240727)。２つの均衡点(m0, m1)を取り違えるタイポで WA を１回出しつつほぼ１時間かけた。終了５分前に WA が出たときは目の前が真っ暗になる思いがしたけど、上から読み直して運良く見つけられた。F 問題を考えていた時間とセグメント木を使っていた時間が無駄になった。3、40 分で解きたかったね。■F 問題 1122 Subsequence。A の値域が 20 以下という制約からどういう DP がやれるか考えてしまって考えが深まらなかった。D 問題でやった DP と、E 問題で気がついた「都合の悪い要素を飛ばして伸ばせる」という点がヒントになると思うんだけど、未だまとまらず。現在の要素を右端として直前の同値の要素からどれだけ左に伸ばせるかを考えたいんだけど、それをするのに何をキーにして状態を記録するのかが不明。■値が 20 種類しかないということは、最長でも 20 までしか伸ばせないということだ。ということは？ 何ができる？ 長さが問題にならないなら幅が 1<<20 でも問題ないということで、bit DP か？■五線譜ならぬ 20 線譜があって、隣接する同値の２要素を繋いだ区間が線上に乗っていて、20 本の線からオーバーラップのない区間を選んで繋ぐ。同じ線からは１つの区間だけ。■■■精進。F 問題。O(AN) の方針に行き詰まって O((2^A)A) の ビット DP に方針を定めたとして、遷移がわからなかった。ところで、状態のキーがこれまで使用した値ペアだとして、何を記録するのか。これは N 要素のどこまでを使用してその状態に至ったかの最小値。ということを整理しているうちに TSP が降ってきた。巡回セールスマン問題と同じ遷移で解ける。提出 #60111625 (TLE) のち 提出 #60113392 (AC / 612 Byte / 1405 ms)。やっぱり今日の１問レベルの歯ごたえがあった。Crystal での提出を見てると E 問題の AC から７分半でこの F を通している人がいるけども(#60070912)、それは頭がおかしい。自分はこの問題を反射では解けないし、指を動かすだけでもそれ以上の時間がかかるのは間違いない。TSP 問題は３問ほど解いたことがある(だけど未だに苦しむんだよ)。たとえば ABC180-E「Traveling Salesman among Aerial Cities」(20201018p01.02)。これ水 diff 下位の難易度しかないことに驚く。この F 問題は青 diff 下位だったけど、目くらましが目くらましとして機能しないレベルの人にとっては、青も水も変わらず典型パターンを当てはめるだけの問題になってしまうのか。それも難なくやってのける。■■■A 問題。ややこしいし効率が悪いしやる意味はないんだけど、あえての正規表現。提出 #60163766。パターンは ^(1\g<1>2|/)$。Ruby ならできます。同じパターンを C 問題でも使おうとしたけど、N≦200000 では TLE が不可避だった(提出はしていない)。■■■F 問題。それとさっき挙げた ABC180-E Traveling Salesman among Aerial Cities。遷移まで含めて bit DP と呼ばれてるみたい？ 「集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。この実装方法から bit dp とも呼ばれることの多い手法です。」([AtCoder 参加感想] 2020/10/17:ABC 180 | maspyのHP)。自分が bit DP と認識しているものはメモ化再帰とよく結びつくもので、状態をビットフラグで表すことで順序に関する情報を落として再計算を省くというもの。遷移はそのつど再帰関数を書くときに考えている。だけど bit DP というだけで今回のような遷移が引き出せるべきなんだろうか。