ボタンを押す操作を「仕事」とみなしてスケジューリングの問題を言い換えてみましょう。

仕事の開始時刻の制約がない場合、つまりすべてのボタンが時刻 \(0\) に出現し、時刻 \(T[i]+D+0.5\) に消える場合は、どんな順番でやるのが最適なのか考えてみましょう。

実は、開始時刻の制約がない場合は \(T_i + X_i\) の小さい順でやるのが最適です。この順番でボタン（or 仕事）を並び替えたとき、開始時刻の制約がある場合は、最適な順番（\(1, 2, ..., N\) の順列）はどのような形になっているか考えてみましょう。

Hint 3 の考察を使って DP で解いてみましょう。

\(K = 1\) の場合を考えてみましょう。まず、A を +1、C を -1 としたときのダイヤグラムを考えると、比較的簡単に多項式時間で解くことができます (Difficulty 1200 程度です)。

実は \(K = 1\) の場合、\((l, r)\) のパターン数を \(O(N^2)\) 通りから \(O(N)\) 通りに絞り込むことができます。

実は \(K = 1\) の場合、\(l\) のパターン数を \(\sqrt{N}\) 通り、\(r\) のパターン数を \(\sqrt{N}\) 通りに絞ることができます。

最適な \(l\) の条件について考えてみましょう。まず、A を +1、C を -1 としたときのダイヤグラムを考えた時、\(l\) は高さが更新されるタイミングになるのが最適です。また、高さが更新されるタイミング以外にも、もう一つ「絞り込める条件」があります。何でしょうか。

実は、高さが \(0\) の部分で分かれる区間を「連結成分」とするとき、\(l\) としては同連結成分内で高さが最大になる点しか考えなくても良いです。そして、Hint 4 と合わせると、は \(O(\sqrt{N})\) 通りしかありません。

\(K = 1\) の場合が解けたら、\(l\) が最初から何文字目か、\(r\) を最後から何文字目かを固定したとき、\(k\) に対する swap 回数 \(f(k)\) がどう変化するかについて考えてみましょう。

\(K\) 回のエクササイズで各マスを通る回数を、適当な \(N, K\) に対して出力してみましょう。どんな性質があるでしょうか？

実は、マス \((1, N), (2, N-1), \dots, (N, 1)\) の線を軸として対称になっています。そのため、左上の三角形（\(\frac{1}{2} N(N+1)\) マス）のバージョンの問題の答えが分かれば、元の問題の答えも分かります。

マス \((1, 1)\) から毎回どんな方向に進んでいるかを考えてみましょう。

Hint 3 の答えは、奇数回目に訪れたときは下方向、偶数回目に訪れたときは右方向に進みます。Hint 3 でやったことを他のマスに対してもやってみましょう。

Hint 4 の考察を使って DP で解いてみましょう。

まず、0 を開きカッコ、1 を閉じカッコとするようなカッコ列を考えた時、どのような \((a_i, b_i)\) が来ても最終的な文字列がカッコ列になるようにすることは可能です。

最終的な文字列をカッコ列になるようにするだけでなく、たとえば文字列を「3, 7, 1, 8, 4, 5, 6, 2 文字目の順」など適当に決めた順番で読んだときにカッコ列にすることも可能です。

\(N = 3\) や \(N = 4\) の場合で、各文字が宣言されたときに「どのような順番で読んだときのカッコ列」を目指せばよいか、プログラムで実験してみましょう。

\(N = 4\) の場合、以下のような戦略で AC することができます。この規則性を \(N \neq 4\) にも応用してみましょう。

• 司会者が A を宣言した場合、文字列を 2, 3, 4, 5, 6, 7, 8, 1 文字目の順に読み、正しいカッコ列を目指す
• 司会者が B を宣言した場合、文字列を 4, 5, 6, 7, 8, 1, 3, 2 文字目の順に読み、正しいカッコ列を目指す
• 司会者が C を宣言した場合、文字列を 6, 7, 8, 1, 5, 2, 3, 4 文字目の順に読み、正しいカッコ列を目指す
• 司会者が D を宣言した場合、文字列を 8, 1, 7, 2, 3, 4, 5, 6 文字目の順に読み、正しいカッコ列を目指す

まずはパスグラフの場合を考えます。例として、\(N = 6, F = 10\) で \(1 \to 2 \to 3 \to 4 \to 5 \to 6\) で辺の長さが全部 \(1\) の場合を考えましょう。\(R = (0, 2, 1, 5, 8, 0)\) のケースと \(R = (0, 9, 5, 3, 8, 0)\) のケースそれぞれどんな方法が最適解になるか考えてみましょう。それぞれ最初の所持金 \(28.5\) と \(23.75\) で行けます。

Hint 1 で換金をするときに「どんな換金をするか」を観察してみましょう。

Hint 2 の考察をもとに、所持金が 0 にもならずマイルが 0 からでもない換金が行われるのはどんな時かを考えてみましょう。

実は、Hint 3 で述べた換金が 2 連続で行われることはありません。これをもとに、最初の所持金が決まっているバージョンの判定問題を、パスグラフの場合で DP で解いてみましょう。

Hint 4 の方法を一般グラフに応用してみましょう。

Hint 5 でベルマン・フォード法のような方法を使っている場合は、これをダイクストラ法のような方法に直してみましょう。

最初の所持金を二分探索することを回避する方法を考えてみましょう。