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 というだけで今回のような遷移が引き出せるべきなんだろうか。