Study

PythonでAtCorder258 (A,B,C)

  /

先週末のAtCorder258も、所用で参加できませんでした。257に引き続き、2週連続で参加できていないです。

で、やってみたのですが、もし参戦していたら、Aしかできていなかったと思います。一応、Cも解けはしたのですが、本番だったらBに時間を使っていてCをやる時間がなかったと思います。

Contents
  1. 【A】 When?
  2. 【B】Number Box
  3. 【C】Rotation
  4. 【D】 Trophy
  5. まとめ

【A】 When?

K = int(input())

h = 21
m = K
if K >= 60:
    h = 22
    m = K - 60

print(f"{str(h).zfill(2)}:{str(m).zfill(2)}")

Aにしては少し凝った問題だった気がします。ゼロ埋めの所は、ググりました。

【B】Number Box

解けませんでした。まさか、Bが解けないことがあるとは・・・

サンプル問題の1も解けず、提出すらできない状態でした。全探索でやれば何とかなるだろうと思って実装していったんですが、場合分けで操作回数のループの中に8パターンの経路を入れて分けがわからない状態に。

諦めて回答を見てなるほどと思いました。

現在値を持っておいて毎回更新していき、8方向のループの中にN-1開操作のループを入れれば良かったんですね。解説をみてコードに落とし込んだものはこちら。

N = int(input())
a_list = [(input()) for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(N):
        masu: str = a_list[i][j]  # 通ってきたマスの数値を格納
        for p, q in zip(
            (1, 1, 1, 0, 0, -1, -1, -1), (1, 0, -1, 1, -1, 1, 0, -1)
        ):  # 8方向の座標
            # 現在値
            cur_i = i
            cur_j = j

            for _ in range(N - 1):  # N-1回操作
                # マス移動
                cur_i += p
                cur_j += q
                cur_i = N - 1 if cur_i < 0 else cur_i
                cur_i = 0 if cur_i > N - 1 else cur_i
                cur_j = N - 1 if cur_j < 0 else cur_j
                cur_j = 0 if cur_j > N - 1 else cur_j

                # add score
                masu += a_list[cur_i][cur_j]

            # N-1回操作終了、masuを数値化して、ans更新
            masu_int = 0
            for idx, v in enumerate(masu):
                masu_int += int(v) * 10 ** (N - idx - 1)
            ans = max(ans, masu_int)

            masu = a_list[i][j]  # score初期化
print(ans)

【C】Rotation

問題を見て、dequeの問題だと思い、「わーい。これ知っている♪」と喜び勇んでコードをかくも、TLEに。よくよく考えると計算量がO(NQ)で、あ、これ無理だと気づきました。

紙で考え方を書いていって、ずれる回数をカウントしていけばいいとわかり、無事、正解にたどりつくことができました。

N, Q = map(int, input().split())
S = input()
querys = [input() for _ in range(Q)]

total_rotate = 0
for query in querys:
    t = int(query.split()[0])
    x = int(query.split())
    if t == 1:
        total_rotate += x
        if total_rotate > N:
            total_rotate -= N
    if t == 2:
        idx = x - total_rotate
        print(S[idx - 1])

【D】 Trophy

問題を見て、動的計画法だと思ってコードを書いてみたものの、正解にたどりつけず断念。

解説をみると動的計画法ではなく考え方の問題でした。発想系？、工夫系？とでも言うのでしょうか。

まとめ

AtCorder258は参加できなかったのですが、もし参加していたらAだけしか解けていないという散々な結果になっていたでしょう。

逃げるわけではないのですが、今週末も飲みに行く予定があるので、参加できそうにありません。週末の予定はどうしてもAtCorderより優先したくなるので、参加するのは中々難しいですね。

継続して参加している人、すごいと思います。参加はできませんが、問題を解くことだけは続けていきたいと思います。

RELATED POST