ABC152の解説です。
自分は39:11全完で世界28位。もうちょっとすらすらできてもよかったかな、とは思います。
では、解説に移りましょう。
A問題
$N=M$ かどうか判定しましょう。おわり。
B問題
これは、$a$ と$b$ の大小を考えるだけで解けるのですが、少し知識的な面で補足を。
C++のstd::stringでは、コンストラクタに長さと何らかの文字を与えると、その文字を長さ分だけ連結した文字列を生成してくれます。
これを利用して解いた自分のコードはコレです。覚えておくと便利なときがたまにあります。
C問題
300点にしては難しめだったかもしれません。
愚直な大小比較をすると、時間制限に引っかかります。
端の方から累積して最小値を取ると、判定が一発でできるので、最初に累積最小値を取っておきましょう。
D問題
結構めんどくさいですが整理して解きましょう。
Aと、Bの長さを全列挙します。
Bの長さがNの長さより短い場合は、最初と最後の2文字以外自由なので、$2^{length(B)-2}$ 通りあります。
Bの長さがNの長さより長い場合は、ひとつも作れません。
あとは、等しい場合です。
Aの最後の文字がNの最初の文字より大きい場合は、作れません。
Aの最後の文字がNの最初の文字より小さい場合は、最初と最後の2文字以外自由なので、$2^{length(B)-2}$ 通りあります。
等しい場合だけまた場合分けがあります。
Aの最初の文字がNの最後の文字以下の小さい場合は、Nの最初と最後の文字を除いて見た数+1通りあります。
そうでない場合は、Nの最初と最後の文字を除いて見た数と同じ通り数あります。
こうして全列挙を行い、値を足せばよいです。
一応計算量は理論上 $O(N\log N)$ ですが、まあ $O(N)$ だと思っていいです。
E問題
$A_iB_i$ の値として考えられるのは、$A$ の最小公倍数にするのが明らかに最適です。
最小公倍数をmodつきで求めたいところですが、ユークリッドの互除法を使って最大公約数を通じて求めてしまうと、modが崩れて破滅します。
そこで、最小公倍数の定義を考えて、$A$ の各要素を素因数分解し、各素因数について最大値を求め、最小公倍数を直接求めに行きます。
$A$ の各要素は今回小さめなので、素因数分解をしても間に合います。
計算量は $O(N\sqrt{A})$ です。
F問題
今回は、ABCのFとしては非常にちょうどいい難易度だったと感じます。
制約を眺めると、$M$ が最大でも $20$ であることに気づきます。これを利用して解きます。
まず、すべての $u_i,v_i$ について、DFSなどでパス上の辺を列挙し、どの辺を通るかがすぐわかるようにしておきます。この判定を $O(1)$ でできるようにしておくとあとが楽です。（しなくても解ける気はしますが、しない意味がないのでしましょう。）
そのあとは、bitDPをします。
${\rm dp}[i][S]=i$ 番目までの辺を使って、集合 $S$ に含まれる $u$ と $v$ の組み合わせについて、パス上に黒い辺を含ませる通り数
とします。
答えは ${\rm dp}[N-1][U]$ ($U$ は全体集合）となります。
先に行ったDFSでの列挙を利用して遷移の計算量を抑えられ、全体での計算量は、$O(NM2^M)$ となります。
おわりに
今回のABCでレートが久しぶりに上がりました。
さっさと黄色に復帰したい…