【競技プログラミング】AtCoder Beginner Contest 386問題_解法演習

雑記

夏バテからか、AtCoderが全然解けなくなって、やる気も無くなってカナリやばい。
それ以前に、ABC 385もだけど、ABC 386って全体的に難しくないかな・・・？
暑さでバテてやる気が消滅する前に、ABC 150から再復習でもした方が良いかもしれぬ。

ホンっとABC 386のE問題なんて考える気分にすらならない。XOR問題は解ける解けないは別として、考えていて楽しい部類なんだけど、今ではDFSについて考えるのも億劫だ。

こういうときは、過去に解いたことがある問題や、簡単な問題トレースしながらリハビリしますかね。

既存投稿一覧ページへのリンク

一覧ページ

C問題

本問は、F問題の特殊形で、K=1のときは力技で解けそうなので後回し。(F問題はスランプになるから年内は手を出さない・・・)

D問題

本問は、問題文読んでも分かりづらかったので、Yesになるパターンの配置になれば良いプログラムだと理解。
具体的な値で、5,6問試せばTLEする可能性はあるけど、解けそうな気はする。

入力例01(ans: Yes)

13 29
11 2 W
12 6 W
5 5 W
3 12 W
13 10 W
7 12 W
2 6 B
1 6 B
1 4 B
5 6 W
12 7 W
5 12 W
8 4 B
9 3 W
1 12 B
4 10 W
2 8 B
2 2 B
4 6 B
4 12 W
13 2 W
2 11 W
3 6 B
2 10 W
1 2 B
6 13 W
4 7 W
13 1 B
6 4 B

※ 入力例に対して、W: 青、B: 赤で着色 ※

入力例02(ans: Yes)

13 29
3 7 W
11 7 W
11 2 B
8 11 W
13 6 W
4 1 B
5 2 B
6 9 W
9 4 B
7 6 W
4 9 W
5 6 W
5 8 W
12 11 W
7 1 B
2 8 W
8 5 B
10 1 B
9 5 B
10 4 W
9 10 W
6 13 W
11 11 W
7 11 W
9 7 W
1 10 W
12 9 W
1 8 W
6 6 W

入力例03(ans: Yes)

13 29
3 4 B
6 7 B
1 2 B
8 10 W
13 2 W
3 1 B
8 3 B
10 1 B
10 2 B
13 5 W
3 9 B
9 9 W
8 11 W
7 7 B
3 8 B
6 6 B
8 8 B
11 4 B
8 13 W
7 2 B
13 12 W
13 3 W
13 6 W
9 10 W
4 11 W
12 1 W
2 11 W
11 12 W
13 1 W

入力例04(ans: Yes)

13 29
9 9 W
5 8 B
2 3 B
13 4 W
8 12 W
13 9 W
1 2 B
6 11 B
6 10 B
2 6 B
3 4 B
11 2 W
3 13 W
11 13 W
12 11 W
5 7 B
3 12 B
7 6 W
9 11 W
7 8 W
5 10 B
10 12 W
8 9 W
6 9 B
12 6 W
4 12 B
6 5 B
12 9 W
11 7 W