😺

AtCoder Regular Contest 157 Aのメモ

2023/02/26に公開

AtCoder

競プロ

tech

AtCoder Regular Contest 157に参加したので記録を残します。
今回は0完爆死です。
https://atcoder.jp/contests/arc157

A - XXYYX

0完なので解けなかったわけですが…
順位表で解かれている数を確認して、実はAよりBのほうが簡単みたいなことはなさそうだったのでひたすらAについて考えていました。

コンテスト中の考察（ダメな例）

あり得る文字列を全部試すのは一瞬考えたけどまあもちろん制約的に無理です。
しかし、どのように考えたらいいのか正直全然わからず。文字列の生成を試行してみる発想でいましたが、どうやらそうではなく入力値の整合性を計算で求めればいいのではと気づくまでに1時間くらいかかっていました。

とりあえず、一旦文字列の長さを考えずに入力の条件を満たす文字列を生成したらどうなるかを考えてみました。（実際に生成するわけではなく、考え方として）

たとえば入力例1だと、たとえば XXXYYXYY のようになります。 $A$ から $D$ までどれも2文字なので、この場合の文字列の長さは $(N - 1) \times 2$ の8文字になります。しかし、実際には $N$ 文字である必要があるので、3文字減らす必要があります。
共通部分があれば減らすことができます。 XX と XY は X が共通するので、 XXXY は XXY にできる、みたいな感じで。それをやっていって、最終的に $N$ 文字まで減らせればOKという発想です。

しかし、それをどう実装すればいいのかわからず。終了間際になって、とりあえずなんか提出しようと思って無理やり書いたのを提出したけど当然WA…

解説を見て

まず、連続して同じ文字が現れることを一旦考えないことにし（連続している文字の重複を除去して考える）、かつ同じ文字しかないケースも考えないことにすると、 X と Y は交互に現れます。X と Y のみから構成される文字列なので。
そう考えると、 XY と YX の出現回数の差（ $|B - C|$ ）は1以下になると。
たとえば XYX はそれぞれ1回ずつの出現になるので $|B - C|$ は0。 XYXY だと $B$ が2で $C$ が1なので差は1。XYXYX だとどちらも2で差は0。XYXYXY だと $B$ は3、 $C$ は2で差は1……と、ここからどんなに増やしても循環しそうです。

YX から始まる文字列で、 YXY だとどうなるか、YXYXではどうか？など考えていくと、上記の $B$ と $C$ が入れ替わるだけで、差が1以下になることは変わりません。
実例を見た限り、たしかに $|B - C| ≦ 1$ は成り立ちそうです。なので、まずこれが成り立たなかったら答えはNoです。
逆に、これが成り立つのであれば基本的には答えはYesになります。 $A$ や $D$ についてはいくらでも増やせると。最初に連続している文字の重複を除去して考え始めましたが、 $A$ や $D$ の個数はその除去された文字数に等しいです。
$A$ や $D$ の分を足し込むと考えると、YXYに加えて $A$ が3だとすると、 YXXXXY のように増やせます。さらに $D$ が4だとすると、 YYYYYXXXXY のようにできます。これは $A$ や $D$ がいくら多くても変わりません。
$A$ や $D$ が増えると全体の文字数も増えますが、 $A+B+C+D=N-1$ が保証されているので、そのせいで条件を満たさなくなることはありません。

逆になんで $A$ や $D$ の分を除去して考えてもいいんだっけ？と思いましたが、上記とは逆に $A$ や $D$ の分を除去した分だけ全体の文字数（ $N$ ）も減ると考えられるので、 $A+B+C+D=N-1$ は成り立ち続けると考えればいいんですかねぇ。（ちょっと怪しい）

なお、 $B$ も $C$ も0の場合がコーナーケースになるということでした。X と Y の両方を含む文字列だと必ず XY か YX のどちらかは出現するので、 $B$ も $C$ も0というのが成り立つためにはX か Yのどちらかだけで成り立つ文字列でないといけない、つまり $A$ か $D$ のどちらかは0である必要があるということになります。

なので実装としてはまず上記コーナーケースのチェックを行い、それに適合しない場合は $|B - C| ≦ 1$ が成り立つかどうかを判定するということになります。

import kotlin.math.abs

fun main() {
    val (n, a, b, c, d) = readLine()!!.split(" ").map { it.toInt() }

    if(b == 0 && c == 0 && (a != 0 && d != 0)) {
        println("No")
        return
    }

    if(abs(b - c) <= 1) {
        println("Yes")
    } else {
        println("No")
    }
}

感想

わかったような気にはなりましたが、やはり自力で導き出すのは難しそうだなという感じです。
ただ、同じ文字列が連続するケースは一旦考えないなど、面倒なケースは一旦除外して単純なケースから考え始めて、面倒なケースは後付で考えるというのが有効なのかなという気がしました。
まあ今までもそういう考え方を無意識にしていて解くことができた問題もあるのですが、ちゃんと意識してはこなかったというか。汎用的に使えそうなので、今後はそのように意識的に考えてみようかなと思いました。

それにしても、この問題をすぐに解けるような人とは絶望的な差を感じますね。解ける人はいちいち考えなくても直感的にわかってしまうのでしょうかね…？

（執筆時間: 1時間17分28秒）

A - XXYYX

コンテスト中の考察（ダメな例）

解説を見て

感想

Discussion