雑記
夏バテからか、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
入力例_A1
縦 13 行、横 13 列のグリッドがあります。
高橋君は以下の条件を満たすように各マスを黒または白のいずれかに塗り分けたいと考えています。
-
すべての行について以下の条件が成り立つ。
- ある整数 i（0 ≤ i ≤ 13）が存在して、その行の左から i 個のマスは黒、それ以外は白で塗られている。
-
すべての列について以下の条件が成り立つ。
- ある整数 j（0 ≤ j ≤ 13）が存在して、その列の上から j 個のマスは黒、それ以外は白で塗られている。
現在、29 個のマスがすでに塗られています。
それぞれのマスの位置と色は以下の通りです（行番号は上から、列番号は左から数える）。
- 5 行 9 列目 → 黒
- 9 行 4 列目 → 黒
- 11 行 10 列目 → 黒
- 4 行 1 列目 → 黒
- 6 行 2 列目 → 黒
- 9 行 3 列目 → 黒
- 13 行 2 列目 → 白
- 11 行 11 列目 → 黒
- 13 行 7 列目 → 白
- 7 行 3 列目 → 黒
- 8 行 2 列目 → 黒
- 6 行 12 列目 → 黒
- 4 行 7 列目 → 黒
- 4 行 13 列目 → 黒
- 8 行 4 列目 → 黒
- 9 行 5 列目 → 黒
- 13 行 5 列目 → 白
- 5 行 2 列目 → 黒
- 11 行 2 列目 → 黒
- 13 行 6 列目 → 白
- 12 行 2 列目 → 白
- 5 行 4 列目 → 黒
- 5 行 12 列目 → 黒
- 8 行 7 列目 → 黒
- 6 行 11 列目 → 黒
- 3 行 5 列目 → 黒
- 12 行 4 列目 → 白
- 11 行 3 列目 → 黒
- 5 行 10 列目 → 黒
? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? B ? ? ? ? ? ? ? ?
B ? ? ? ? ? B ? ? ? ? ? B
? B ? B ? ? ? ? B B ? B ?
? B ? ? ? ? ? ? ? ? B B ?
? ? B ? ? ? ? ? ? ? ? ? ?
? B ? B ? ? B ? ? ? ? ? ?
? ? B B B ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ? ? ? ?
? B B ? ? ? ? ? ? B B ? ?
? W ? W ? ? ? ? ? ? ? ? ?
? W ? ? W W W ? ? ? ? ? ?
高橋君はまだ塗られていない残り 13×13−29 = 140 個のマスの色をうまく決めることで、条件を満たすことができるか判定してください。
input
13 29
5 9 B
9 4 B
11 10 B
4 1 B
6 2 B
9 3 B
13 2 W
11 11 B
13 7 W
7 3 B
8 2 B
6 12 B
4 7 B
4 13 B
8 4 B
9 5 B
13 5 W
5 2 B
11 2 B
13 6 W
12 2 W
5 4 B
5 12 B
8 7 B
6 11 B
3 5 B
12 4 W
11 3 B
5 10 B
input_python
def io_func():
# N, M を取得
n, m = map(int, input().split())
# マス情報を格納するリスト
p = []
for _ in range(m):
x, y, c = input().split() # 1行ずつ取得
x = int(x) # 整数型に変換
y = int(y) # 整数型に変換
# タプル (x, y, c) をリストに追加
p.append((x, y, c))
# N, M, P を戻り値として返す
return n, m, p
output
Yes
E問題
入力例01
長さ 4 の非負整数列 A = (3, 2, 6, 4) および整数 K = 2 が与えられます。
A = (3, 2, 6, 4) から異なる 2 項を選ぶとき、選んだ 2 個の数の総 XOR（排他的論理和: ⊕演算子）としてあり得る最大値を求めてください。
つまり、$\max_{1 \leq i_1 < i_2 \leq 4} (A_{i_1} \oplus A_{i_2})$
を求めてください。
input
4 2
3 2 6 4
input_python
output
7