Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 140

2完、8WA。やりすぎたー。

各問題

A - Right String

ある文字列Uの繰り返しの形にできれば、種類数はUの長さLにすることができます。Uの繰り返しにするためにはL文字間隔で同じ文字が出現すればよいです。 つまりabcabcabcなら、長さ3の文字列abcの繰り返しで、1文字目と1 + 3 = 4文字目と1 + 3 * 2 = 7文字目がa、2文字目と2 + 3 = 5文字目と2 + 3 * 2 = 8文字目がb、という具合です。

Nは2000までなので2重ループは許されます。なので、f(S) = 1から順にNまで調べていけばよいです。ただし、Nの約数でないと答えには当てはまらないので注意です。

B - Shorten ARC

AARCCは、奇数回目からなら ARC -> AC と変換することができます。AAARCCCは、単体では AARCC -> AACC と2回止まりですが、別の場所で偶数回目を消費することで AARCC -> (偶数回目を別の場所で消費) -> ARC -> AC と消費し切ることができます。この偶数回消費は ARC が単体で出ている場所でやれば得できます。

というわけで、A...ARC...C 型と 単体で出現するARC 型を分けて集計して、うまいこと消費回数を数えれば答えがわかります。(雑

C - ABS Permutation (LIS ver.)

適当な貪欲を投げるも、当然通らず。

まとめ

AもBも、考察ははずしてないんだけど詰めが甘くてWAを量産してしまい、水パフォキープにとどまってしまいました。