見出し画像

【ABC354】緑コーダーの競プロ参加記録 #18

igasu_7

今回はAtCoder Beginner Contest 354。使用言語はPythonです。


A問題 - Exponential Plant

コンテスト中の提出
https://atcoder.jp/contests/abc354/submissions/53582657

  • 高橋くんの身長が$${H}$$。

  • 発芽日を$${0}$$日目として、植物は$${i}$$日目の夜に高さが$${2^i}$$伸びる。

  • 高橋くんの身長を超えるのは何日目の朝か出力してね。

難しいです。

$${1 \le H \le 10^9}$$なので、$${2^i > 10^9}$$となる$${i}$$がどれくらいになるかというと、$${2^{10} = 1024 \ge 10^3}$$より、だいたい$${i = 30}$$程度になります。

1日の流れをforループとみなして、朝（前半）に身長チェック、夜（後半）に植物が成長するようなコードを書きます。

先に述べたように、ループ数は$${30}$$より大きくしておきます。
（正確には、30日分の成長をした植物に対して身長チェックを行えるようなループ回数を設定します。）

""" AC コード """
H = int(input())
res = 0
for i in range(31):
    if H < res:
        print(i)
        exit()
    res += pow(2, i)

「$${i}$$日目の夜に$${2^i}$$伸びる$${(0 \le i)}$$」を「$${i}$$日目の朝に$${2^{i-1}}$$伸びる$${(1 \le i)}$$」と言い換えてもよいです。

""" ACコード """
H = int(input())
res = 0
for i in range(1, 100000):
    res += pow(2, i - 1)
    if H < res:
        print(i)
        exit()

$${H \le 2^i}$$となる$${i}$$を厳密に計算する必要はなく、それなりに大きい数を設定しておけば問題ありません。


B問題 - AtCoder Janken 2

コンテスト中の提出
https://atcoder.jp/contests/abc354/submissions/53589602

  • $${N}$$人のユーザーがいる。

  • $${i}$$番目のユーザーは名前が$${S_i}$$で、レートが$${C_i}$$。

  • ユーザー名$${S_i}$$の辞書順に$${0}$$から$${N - 1}$$の番号を割り当てる。

  • レートの総和$${T}$$に対して、$${T  \mathrm{mod}  N}$$の番号のユーザーを出力してね。

入力が [文字列, 整数] の形式で、やや面倒です。
一旦すべて文字列として受け取って$${C_i}$$のみ整数に変換します。

""" 入力を受け取る """
N = int(input())
S = []
T = 0
for i in range(N):
    s, c = input().split()
    S.append(s)
    T += int(c)

ユーザー名の辞書順は、ユーザー名のリストをソートすればよいです。

ソート後のリストにおける$${i}$$番目のユーザーは、番号$${i}$$を割り当てられています。
よって、$${S[T \% N]}$$が答えになります。

""" ユーザー名をソートして T % N 番目 を出力 """
S.sort()
ans = S[T % N]
print(ans)


C問題 - AtCoder Magics

コンテスト中の提出
https://atcoder.jp/contests/abc354/submissions/53605558

  • カードが$${N}$$枚ある。

  • $${i}$$番目のカードは強さ$${A_i}$$、コスト$${C_i}$$。

  • $${A_x > A_y}$$かつ$${C_x < C_y}$$であるカード$${y}$$があれば捨てる。

  • 残ったカードを昇順で出力してね。

必ず残るカードについて考えてみます。
たとえば、「強さが最大のカード」か「コストが最小のカード」は必ず残ります。

「強さが最大のカード」をカード$${x}$$として考えたとき、他のすべてのカードはこれより強さが小さいため、捨てるかどうかは「カード$${y}$$のコストが$${C_x}$$より大きいか？」を判定すればよいです。

「コストが最小のカード」をカード$${x}$$としたときも同様です。「カード$${y}$$の強さが$${A_x}$$未満か？」を判定することになります。
（今回はこちらを採用してみます。）

上記の戦略を、「$${N}$$枚のカードの中で最小」ではなく「捨てるかどうかまだ確定していないカードの中で最小」と考えます。

現在の最小コストのカードを$${x}$$として固定したとき、強さ$${A_y}$$の小さい順に$${C_x < C_y}$$となるカード$${y}$$を捨ててよいです。
ソートと合わせて尺取り法のような探索法をとることができ、全体で$${O(N)}$$になります。

$${A, C}$$を分けてソートしたいので、その「強さ」「コスト」をもっているのが何番目のカードか分かるようにします。

""" 強さ と コスト をそれぞれ分けてソート """
N = int(input())
A, C = [], []
for i in range(N):
    a, c = map(int, input().split())
    A.append((a, i))
    C.append((c, a, i))
A.sort()
C.sort()

「捨てるかどうか」を管理するリストも用意します。

コストの小さい順にカード$${x}$$を選択し、強さの小さい順にカード$${y}$$を選択します。

""" keep[x]: x 番目のカードを残す """
keep = [True] * N
j = 0
ans = []
for c, a, x in C:
    if not keep[x]:
        continue
    ans.append(x + 1)
    while j < N and A[j][0] < a:
        y = A[j][1]
        keep[y] = False
        j += 1

残すカードの番号を昇順にソートしてから出力することに注意してください。

""" 答えを出力 """
ans.sort()
print(len(ans))
print(*ans)

公式解説では、より簡潔にこれを行っています。


D問題 - AtCoder Wallpaper

upsolve
https://atcoder.jp/contests/abc354/submissions/53749704

（2024/05/22 追記）
こういう座標をコネコネする問題は苦手で頭がパニックになってしまいますが、解きます。

壁紙の模様は$${1 \times 1}$$の大きさの8種類の異なるパネルで構成されていると考えます。
各パネルについて以下のように番号を振ってみます。

「黒い領域の面積の2倍」の値は、番号の昇順に$${[2, 1, 0, 1, 1, 2, 1, 0]}$$となります。

$${A, B, C, D}$$で与えられる領域の中にそれぞれのパネルが何個ずつ含まれているかを個別に計算できればよいですが、これが難しいところです。

まず、簡単なことから考えます。
$${(A, B) = (0,0)}$$であるときの、パネル$${0}$$の個数がいくつあるかを考えます。

少し実験してみると、その個数は、長方形領域の高さ$${H}$$、幅$${W}$$として$${\lceil\frac{H}{2}\rceil \times \lceil\frac{W}{4}\rceil}$$になることが分かります。

$${\lceil x \rceil}$$は「$${x}$$を切り上げした整数」を表します。

$${(A, B) = (0,0)}$$であるときのパネル$${0}$$の個数がカウントできました。
もっと言うと、大きさ$${H \times W}$$の長方形領域の最も左下にあるパネル$${k}$$の個数をカウントできました。

ここで各パネル$${k}$$のマスの左下の座標を見てみると、以下の図のようになります。

これを一般化すると、与えられる$${(A,B)}$$に対して、長方形領域の最も左下にあるパネル$${k}$$は、$${A}$$を$${4}$$で割った余りを$${X}$$、$${B}$$を$${2}$$で割った余りを$${Y}$$として、$${k = X + 4Y}$$となります。

パネル$${k}$$の個数を数えたあと、次のパネル$${k'}$$について数えます。
パネル$${k'}$$が長方形領域の左下になるよう、長方形領域を縮小します。

以上をもとに、コードを書いていきます。
まず入力を受け取り、長方形領域の高さ$${H}$$、幅$${W}$$、パネル$${k}$$の面積を表すリスト$${S}$$を用意します。

また、大きさ$${H \times W}$$の長方形領域の最も左下にあるパネル$${k}$$も求めます。

""" H: 高さ, W: 幅, S[i]: パネル i の面積の2倍 """
A, B, C, D = map(int, input().split())
H = D - B
W = C - A
S = [2, 1, 0, 1, 1, 2, 1, 0]

k = (A % 4) + (B % 2) * 4

パネル$${0}$$を左下にした場合、パネル$${i}$$について考えるときの長方形領域の高さ、幅の縮小量$${Dh[i], Dw[i]}$$はそれぞれ次のようになり、パネル$${i}$$の個数は以下のように求まります。

""" パネル 0 を左下にした場合の、i 番目のパネルの個数 """
def cnt(i):
    height = H + Dh[i]
    width = W + Dw[i]
    if height <= 0 or width <= 0:
        return 0
    return ((height + 1) // 2) * ((width + 3) // 4)    # 切り上げ処理

""" パネル 0 を左下にした場合の、i 番目の幅・高さの縮小量 """
Dw = [0, -1, -2, -3, 0, -1, -2, -3]
Dh = [0, 0, 0, 0, -1, -1, -1, -1]

ここで、上記コードの$${S}$$と$${Dw, Dh}$$のインデックスが必ずしも一致しないことに注意が必要です。
たとえば、パネル$${7}$$が左下であった場合、幅を$${-1}$$縮小した長方形領域の左下はパネル$${4}$$になります。

ムリヤリ突破するとこうなります。

""" 
P[k][i]: パネル k が左下であるときの、i 番目のパネル番号
"""
P = [
    [0,1,2,3,4,5,6,7],
    [1,2,3,0,5,6,7,4],
    [2,3,0,1,6,7,4,5],
    [3,0,1,2,7,4,5,6],
    [4,5,6,7,0,1,2,3],
    [5,6,7,4,1,2,3,0],
    [6,7,4,5,2,3,0,1],
    [7,4,5,6,3,0,1,2]
]
ans = 0
for i in range(8):
    ans += S[P[k][i]] * cnt(i)
print(ans)

いろいろ実装の仕方はあると思うので試してみてください。
私はこういうのを上手く実装できません…。

""" パターン 2 """
P  = [(k >= 4) * 4 + ((k + i) % 4) for i in range(4)]
P += [(not k >= 4) * 4 + ((k + i) % 4) for i in range(4)]


E問題 - Remove Pairs

upsolve
https://atcoder.jp/contests/abc354/submissions/53640721

  • $${N}$$枚のカードで高橋くんと青木くんがゲームをする。

  • $${i}$$番目のカードは表に$${A_i}$$、裏に$${B_i}$$が書かれている。

  • 操作: それぞれの手番に$${A_i = A_j}$$または$${B_i = B_j}$$であるカード$${(i, j)}$$を取り除く。

  • 先に操作を行えなくなったら負け。

  • どちらが勝つか出力してね。

ゲーム理論はメモ化再帰！！

$${N \le 18}$$なので$${2^N}$$でも許されそうで、どのカードが残っているかをビットマスクで管理できそうです。

ある盤面の状態$${\mathrm{mask}}$$から手番をスタートして、そのプレイヤーが勝てるかどうかをメモ化再帰で記録します。

相手が勝つとき自分は負けるため、再帰呼び出しの戻り値を反転することに注意が必要です。
将来的に勝てる手が1手でもあれば勝ちなので OR 演算をします。

""" upsolve """
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(100100100)

""" メモ化再帰 """
def dfs(mask):
    if mask in D:
        return D[mask]
    res = False
    for i in range(N):
        if (mask >> i) & 1 == 1:
            continue
        for j in range(i + 1, N):
            if (mask >> j) & 1 == 1:
                continue
            if A[i] == A[j] or B[i] == B[j]:
                res |= not dfs(mask | (1 << i) | (1 << j))
    D[mask] = res
    return D[mask]

N = int(input())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
D = defaultdict(bool)
takahashi_win = dfs(0)
if takahashi_win:
    print('Takahashi')
else:
    print('Aoki')


あとがき

今回は 3完 25分 で 3709位、915 perf でした。

久々の 3完。まぁそういう日もあります。
前回の ARC177 でなぜかレートが増えているので傷が浅い。

それよりもA問題でサンプルが全然通らなくてかなり焦りました。

ではまた～。


【更新履歴】
2024/05/19 (1時頃)：記事投稿。
2024/05/22 (23時頃)：D問題を追加。

この記事が気に入ったらサポートをしてみませんか？