AtCoder ABC389 振り返り感想戦(緑コーダーがPythonでABCD問題)

ABC 389感想まとめ

トヨタ自動車プログラミングコンテスト2025（AtCoder Beginner Contest 389） - AtCoder

ABCD 4問解答でした。今回は、D問題まではわりとスムースに解けました。

1時間ほど時間があったのでE問題にチャレンジしたのですけども、答えを出力するところまでプログラムを書けずに終わりました。Eは、SegTreeを使う方針でいたのですが、先週に引き続き SegTreeの使い方に慣れておらず、それで時間を消費してしまった感じです。

Eの解説を読むと、そもそも問題の意味を誤解していたので、どっちにしてもコンテスト中には正解にたどり着けなさそうでした。これまでコンテスト中にE問題を解けたことはないので、今年の目標ですかね。

A - 9x9

入力文字列 S の1文字目と3文字目を int に変換して、掛け算しました。

S = input()
a = int(S[0])
b = int(S[2])
print(a*b)

B - tcaF

1*2*3*4 ... の掛け算の結果を for ループで計算し、それが X と一致したらその時の値を出力します。

INF = 10 ** 18
X = int(input())

count = 1
for i in range(1, INF):
    count *= i
    if count == X:
        print(i)
        break

C - Snake Queue

素直に、ヘビの先頭位置と長さをデータ構造に貯めていきます。回答例では、 (先頭位置, 長さ) の tupleにしました。

データ構造としては Deque を使用することにしました(問題文にも Queue と書いてありますし)。

操作2のとき、先頭ヘビを取り除き、後続のヘビを左に詰める作業が発生します。まともに後続のヘビを詰めていくと実行時間がかかるので、詰めた分を offset 変数に保持しました。

from queue import deque

Q = int(input())

dq = deque()
offset = 0 # 操作3でヘビを詰めた分のoffset
for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        # ヘビを最後尾に追加する.tupleで記録(先頭位置, 長さ)
        length = query[1]
        if len(dq) == 0:
            dq.append((0, length))
            continue
        else:
            last = dq[-1]
            dq.append((last[0] + last[1], length))

    elif query[0] == 2:
        # 先頭ヘビを取り除く。取り除いたヘビの長さの合計を offset で記録
        left = dq.popleft()
        offset += left[1]
    else:
        # k 番目のヘビの頭の位置を求める。取り除かれたヘビの分だけ、座標を引く。
        k = query[1]
        target = dq[k-1][0] - offset
        print(target)

D - Squares in Circle

円の中心を 原点 (0,0) として考えます。

とりあえず、原点から右上方向の1/4の円だけを考えます。この範囲に入っている正方形の数が分かれば、それをだいたい4倍すれば円全体の正方形が求まりそう...という方針でいきました。

R = int(input())

# 座標(x,y) を中心とする正方形が、円の中に入っているか判定する
def is_inside(x, y):
    xx = x + 0.5 # 正方形の右上の座標
    yy = y + 0.5 # 正方形の右上の座標
    distance = xx ** 2 + yy ** 2
    inside = distance <= R ** 2
    return inside

count = 0 # 円の 1/4 分の中に入っている正方形の数
count_line_zero = 0 # y==0 のときに、何個の正方形が入っているか

# 右上半円の各 y について、その行に何個の正方形が入っているかを求める
for y in range(R+1):
    # 二分探索で、行に含まれる正方形の右端の位置を求める
    left = -1
    right = R + 1
    while right - left > 1:
        mid = (left + right) // 2
        if is_inside(mid, y):
            left = mid
        else:
            right = mid
    count += left + 1

    if y == 0:
        count_line_zero = count

# 右上半円 * 4 すると、円全体の中の正方形の個数になる
# 重複部分を4回引いている
# +1 しているのは、原点を4回引いちゃうと引きすぎなので、+1戻している。
answer = count * 4 - count_line_zero * 4 + 1
print(answer)