トップ > AtCoder > AtCoder Beginner Contest 175 振り返り

AtCoder Beginner Contest 175 振り返り

AtCoder

結果

TLEに怯える日々を過ごしています。3完でパフォ1308。

お気持ち的には大爆死ながらレートは-1でほぼ変動なし。

とはいえ青を目指すには低いパフォを続けるわけには行かないので上げていきたい。

A B C D E F
1:32 4:54 10:03 (4) (1) -

問題

A - Rainy Season(1:32)

3文字与えられる。Rがいくつ連続しているか数えよ。

from itertools import groupby
S = input()
if 'RRR' in S:
    print(3)
elif 'RR' in S:
    print(2)
elif 'R' in S:
    print(1)
else:
    print(0)

最初RLEを使おうとしてgroupbyを読み込んだが面倒くさくなった。

A問題は方針を2秒で立てられるかの勝負だと思っているので今回は敗北(?)

B - Making Triangle(4:54)

棒が最大100本与えられる。長さが異なるものを3本選んで三角形を作れる組み合わせは何通りあるか？

一瞬 D - Triangles が頭をよぎったが今回はNが小さいので全探索で大丈夫。

ソートしてから条件を書き並べた。

N = int(input())
*L, = map(int, input().split())
L.sort()
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[k] < L[i] + L[j] and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
                cnt += 1
print(cnt)

C - Walking Takahashi(10:03)

座標Xからなるべく原点に近づきたい。1ステップで±Dだけ動ける。Kステップ後の時点で原点との最短距離を求めよ。

ちょうどKステップであるというのを読み飛ばしていてclarに助けられた。

X, K, D = map(int, input().split())
 
if abs(X) >= D*K:
    print(abs(X)-D*K)
else:
    q, r = divmod(X, D)
    if q & 1 == K & 1:
        print(r)
    else:
        print(D-r)

Kステップかけて原点付近まで到達できない場合はなるべく原点に向かって進む。

そうでない場合は原点を超える直前までに何回移動するかを求め、その回数とKの偶奇が一致しているかどうかで場合分け。

pythonだと負数の剰余もいい感じに計算してくれるので簡潔に書ける。

D - Moving Piece

順列に従って移動+スコア獲得をする。K回以下( %%K \leq 10 ^9%% )の移動で達成できるスコアの最大値を求めよ。

最初にダブリングを書いて、そこでK回以下に気づく（実装する前によく見よう）。

方針転換：移動先を与えるリストは順列なので複数のサイクルができる。各サイクルについて獲得スコアの総和が正なら、最大回数ループを続ける(嘘解法)。そうでないなら区間和が最大となるように選ぶ。

これは嘘で、例えば獲得スコアが10 → 10 → -15 のようなループで7回移動するとき、

  • 10 → 10 → -15 → 10 → 10 → -15 → 10
  • 10 → 10 → -15 → 10 → 10

この2つを比較すると、前者の2回ループ+1回移動よりも後者の1回ループ+2回移動のほうがスコアが高い。結局最後までこれに気づかず。

それ以前の問題として、区間和の最大を求める段階で%%O(N ^2) \simeq 10 ^7%%オーダーの計算が必要なのだが、Pythonがこなせる計算量に対して悲観的すぎるため、何か計算量を改善する方法があるかとググったりしていた。

強いPythonistaならPyPyの力を信じたりNumPy+NumbaやCythonを使って何とでもなるのかしら。

E - Picking Goods

かなり典型的なDPに見えた。

%%dp[i][j][k] = (i, j)%%の地点で、その行で拾ったアイテムの個数が%%k%%個であるときの価値の総和の最大値

とすれば、遷移をうまく書くことができる。

しかし、制約から最大で%%3000 \times 3000 \times 4 \simeq 10 ^7%%オーダーの計算。PyPyで提出したもののTLE。

NumPyを使って書き直したものの手元で全く速くなっていない…(Numbaを試してみるべきだったか)

コンテスト後に配列使い回しで通ることが判明。あと、dpテーブルをdp[k][i][j]の順に持つだけでも通るらしい。ぐぬぬ。

import sys
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r, c)] = v
 
dp = [[0]*(W+1) for _ in range(4)]
 
for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = max(dp[1][j-1], dp[0][j]+v)
            dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v)
            dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v)
        else:
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = dp[1][j-1]
            dp[2][j] = dp[2][j-1]
            dp[3][j] = dp[3][j-1]
 
print(max(dp[i][-1] for i in range(4)))

総評

パフォーマンスだけ見れば現状の実力どおりの結果なので仕方なし。

Eはもう少し高速化を粘れば通せていたかもしれない。とはいえDも通せていない状況で定数倍高速化を頑張る気にはなれなかった。

次に向けて実力を付けていきたい。