ABC 377

ABC 377

ABC 377 に参加しました。

A 問題

与えられた文字列が ABC の順列であるかを求めよ。ソートして ABC と比較します。

import Data.List;main=getLine>>=y.sort;y"ABC"="Yes";y _="No"

B 問題

小さなグリッドにルークを複数置いたとき、ルークの移動範囲外のセルの数を数えよ。愚直にグリッドを塗って解けます。

C 問題

巨大なグリッドにナイトを複数置いたとき、ナイトの移動範囲外のセルを数えよ。すべてのセルの数から移動範囲内のセルの数を引くことで効率的に解答できます。

D 問題

区間の列 $\{[L_i, R_i]\}_i$ が与えられとき、 $[1, N]$ 内の区間であってどの $[L, R] \in \{[L_i, R_i]\}_i$ も包含しない区間の数を求めよ。

区間の左端を $N, N - 1, .., 1$ の順で走査します。区間の右端として設定可能な値は単調減少していくことが分かります。

E 問題

順列 $P^1$ を結合し $P^1 \diamond P^1 := P^2$ を作成する、 $P^2 \diamond P^2 := P^4$ を作成する、……という操作を繰り返し $P^{2^k}$ を求めよ。順列は functional graph であるため、強連結成分毎にループします。

解法は合っているはずなのに、どうしてもサンプルが合いません。後日考えると、 SCC の頂点が逆トポロジカル順になっていたことが原因でした。

やはり盆栽不足の範囲では、曖昧な理解が弱みになります。もしも ac-library の写経で高速な SCC を作っていれば、問題無く解けていたでしょう。盆栽が足りませんでした。