86. 今日解いた問題（2022.03.21）

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

問題一覧

E - King Bombee (Diff: 1125)
082 - Counting Numbers（★3） (競プロ典型: ★3)
084 - There are two types of characters（★3） (競プロ典型: ★3)
C - Next Letter (Diff: 1077)
E - Rook Path (Diff: 1380)
B - Sum AND Subarrays (Diff: 1381)

自分の解法など

E - King Bombee

昨日のABC-E問題。昨日解説を読んで理解したので、今日起きてからサッと書いてみました。ほぼ解説の通りなので、自分で考えた解法とかではないです。

次出てきたときに解けるといいですね。

082 - Counting Numbers（★3）

桁数ごとに総和計算を行えばよいので、 $O(\log_{10} R)$ です。桁数が L または R と同じときの計算式に注意します。

この問題で厄介だったのは mod の取り回しでした。減算・除算が出てきますが、これをそのまま当てはめるのは少し怖いので、加算・乗算の逆元を使うことにしました。

084 - There are two types of characters（★3）

$l$ を固定して考えると、 $S_r \ne S_l$ となる最小の $r \gt l$ について、 $i \ge r$ なる $i$ は全て採用できると分かります。

つまり、各 $S_i$ について $S_j \ne S_i$ （ $j \gt i$ ）となる $j$ をあらかじめ計算しておけば、そこから $O(N)$ で答えを求められます。この事前計算はしゃくとり法によって $O(N)$ で求められます。結局、全体として $O(N)$ で解けます。

解説を見たらぜんぜん違う方法で書かれていました。計算量は $O(N)$ で同じなので、まぁいいかな、と思います。

C - Next Letter

なるべく前方の文字を a にするのが最適戦略なので、前方から順に見て

最後の文字でない、かつ、a にできるなら a にして残り操作回数を適切に減らす
最後の文字であるなら、残り操作を全て行う

が最善手です。最初の条件は、a にできないなら今の文字より大きな文字にしかできないので、何もせず次のループへ進むのがよいです。

最後の操作は剰余を取って、どの文字にたどり着くか $O(1)$ で求めます。全体として $O(|s|)$ で解けます。

E - Rook Path

ゴールから考えてみます。 $K$ 手目でルークが $(x_2, y_2)$ にいるためには、 $(K-1)$ 手目でこのマスと同じ行または同じ列にいる必要があります。ただし、全く同じマスにいる場合はダメです。

…と、このように考察すると、この問題で重要なのは「ルークがどのマスにいるか」ではなく、「ルークが $(x_2, y_2)$ と同じ行または列にいるか」ということだと分かります。つまり、個々のマスを考える必要はなく、以下の 4 状態を考えればよいです。

0: $(x_2, y_2)$ と異なる行、異なる列にいる
1: $(x_2, y_2)$ と同じ行、異なる列にいる
2: $(x_2, y_2)$ と異なる行、同じ列にいる
3: $(x_2, y_2)$ と同じ行、同じ列にいる

これで、 $dp(操作回数, 状態) := (動かし方の通り数)$ として DP を行い、答えは $dp(K, 3)$ になります。

遷移はやや複雑になりますが、以下のとおりです（行列で示します）。

$A = \begin{pmatrix} (H-2) + (W-2) & H - 1 & W - 1 & 0 \\ 1 & W - 2 & 0 & W - 1 \\ 1 & 0 & H - 2 & H - 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$

$dp(i)$ を列ベクトルとして、 $dp(i) = A \times dp(i-1)$ です。計算量は $O(K)$ ですが、遷移行列を定義できるので繰り返し二乗法を使えば $O(\log K)$ まで落とせますね（この問題ではそこまで要求されてませんが）。

B - Sum AND Subarrays

問題に書かれている通り、「美しさ」のリストは $O(N^2)$ で全列挙できます。

この中から $K$ 個選んで AND が最大値になるようにするには、上位ビットから順にループして「そのビットについて 1 である「美しさ」を抽出する」操作を繰り返せばよいです。この操作で $K$ 個以上取れた場合は抽出後のリストを次に回し、取れなかった場合は前回のリストを次に回します。最終的にリストに残ったものから任意の $K$ 個を選んで AND を取ると答えになります。

全体として、 $O(N^2 \log(\max a_i))$ で解けるので間に合います。

考え方は合っていたのですが、2 のべき乗計算で凡ミスしていて謎に時間がかかってしまいました。

C# の話。2 のべき乗計算で

long a = 1 << i;

という感じで書いていて、どうも WA が取れないので色々試していたら、この計算が 4byte 計算になっててオーバーフローしていた。

long a = 1L << i;

が正しかった…。
— イバコ (@ibako_piyo) 2022年3月21日

イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。