21か月前公開・21か月前更新・10 min read

緑コーダーがABC258のA~Eまで

https://cdn.magicode.io/media/notebox/blob_KfIwTBw

AtCoder Beginner Contest 258

ABC258のA~Eに関する解説(という名の自分用メモ書き）です。

今回！も！4完止まり…！！！
Eは、時間があっても多分、今の僕には理解できない状態だったので、実力相応ではあったかな、と…。
E問題、パッと見簡単そうに見えて、今の実力では見抜けなかった罠があちこちにあったり…しっかり水色上位の難しさを出してきた感じです…。

次こそ！5完！したい！

A - When?

問題要約

21

時ちょうどから、

K

分後の時刻を、HH:MMの形式で出力して下さい。
(HHは24時間制での時間、MMは分を表す）
時間または分が1桁の時は、先頭に

0

を追加して

2

桁の整数として表して下さい。

制約

K は $0$ 以上 $100$ 以下の整数

考察

いわゆる「やるだけ」問題
黒ココアさんは完全愚直場合分けルートで4択作りました
- Kの値が…
  - 10未満：21時 + K分(0埋めが必要)
  - 10以上60未満：21時+K分
  - 60以上70未満:22時+(K-60)分(0埋めが必要
  - 70以上:22時+(K-60)分
datetime使って時間計算しても良し
formatや、zfillで0埋めしても良し

# 入力
K = int(input())

if K < 10: # 0分~9分
    print("21:0" + str(K))

elif K < 60: # 10分~59分
    print("21:" + str(K))

elif K < 70: # 60分~69分
    print("22:0" + str(K - 60))

else: # 70~分
    print("22:" + str(K - 60))

B - Number Box

問題要約

1~9

の数字が書かれた

N行N列

のマスがあります。
このマス目は、上下左右が繋がっているものとします。
高橋くんは、上下左右及び斜めの8方向のうちいずれかを始めに選び、その方向に

N-1

回移動します。高橋くんが通ったマスにかかれている数字を、左から順に並べた時の整数として最大値を求めてください。

制約

$1\leq N \leq 10$
$1 \leq A_{i,j} \leq 9$
入力は全て整数

考察

いわゆる「全探索」するような問題
制約から、
- 始点となるマスは最大100マス( $N \times N$ )
- 方向は8方向
  - 800通りの数字しかできない
８００個数字を作って、一番大きいものを出力してあげればOK
実装上の問題として、
- 盤面がループしている点の表現
- 方向の指定
  - このあたりが問われている感
  - 正直どっちも典型実装…あ、典型実装まとめとか需要あったりします…？
  - 2種類混ぜてきてるのがC氏の要求の高さ…！！！
盤面のループに関する表現方法については、
- $N$ で割った余りで表現する
- 盤面を拡張しておく
このあたりが思いつく
- 制約が厳しくなってきた時は後者が使えないため、前者を練習しておいたほうが良い気はします
方向の指定については、
- 高々８パターンなので手で書いてしまえ！(物理で殴るタイプ。黒ココアさんの本番ACはこちら）
- $d_i,d_j$ で遷移先をループできるとスマートですね

# 入力
N = int(input())
L = []
# １桁ずつ分けるのが面倒だったので、今回は文字列のままの取り扱い
for i in range(N):
    L.append(input())

# ありえるパターンを全部突っ込んで、最終的にソートすればいいかなスタイル
ans_L = []

# 二重ループで始点全探索！
for i in range(N):
    for j in range(N):

        # 移動パラメータ1
        for dx in [-1, 0, 1]:
            # 移動パラメータ2
            for dy in [-1, 0, 1]:

                # 移動パラメータ1と移動パラメータがともに0＝移動しない足踏みパターンは無し！
                if dx == dy == 0:
                    continue

                tmp = []
                # 1歩ずつ歩くよ
                # 盤面出ちゃったら反対から出てくる挙動を、Nで割った余りで表現
                for k in range(N):
                    tmp.append(L[(i + (dx * k)) % N][(j + (dy * k)) % N])
                # 文字列として結合してあげて…
                ans_L.append(''.join(tmp))

# ソートして、一番大きい＝一番後ろにあるもの！
ans_L.sort()
print(ans_L[-1])

C - Rotation

問題要約

長さNの英小文字からなる文字列Sが与えられます。
2種類のクエリを合わせてQ個処理してください。

1 x：「 $S$ の末尾の文字を削除し、先頭に挿入」を $x$ 回連続で行う
2 x： $S$ の $x$ 番目の文字を出力する

制約

$2 \leq N \leq 5\times10^5$
$1 \leq Q \leq 5\times10^5$
$1 \leq x \leq N$
$S$ は英数小文字からなる
2 xの形式のクエリが1個以上与えられる
$N,Q,x$ は全て整数

考察

愚直にクエリを処理していくと、 $x=5\times10^5$ のクエリ1が、 $5\times10^5-1$ 回飛んできて死ぬ
文字列の切ったり貼ったりもあんまりしたくないなぁ…
クエリ1のローテーション操作を、どうにかして簡略化できないかなぁ…
このあたりが発想の出発点
実際に操作は行わずに、操作の回数だけを記録して出力時に調整する、という典型手法
「末尾の文字を先頭に移動」を行った回数をtop_idxとして記録
- 最初は0。1回も操作してないからね
- 文字数が増えるわけではないので、Nで割った余りで毎回調整するのを忘れずに…。
- 出力のときに余りを取るでも大丈夫
後は出力のときに調整
x=3：3文字目を出力したい時、top_idxが、動いていた場合の実際の先頭の位置なので
出力時に調整を忘れずに…！
- 1 2を行った後の2 1は、
- 実際の文字列Sの中で、後ろから2番目のもの
  - 先頭の位置が増えれば増える程、後ろから前に文字が回ってきてるので、
  - top_idxのカウント＝クエリ1の操作を行った回数分、先頭に文字が挿入されてる…！
  - だから、0-indexに直した上で、top_idxを引いてあげる…！

# 入力
N, Q = map(int, input().split())
S = input()

# 先頭の位置
top_idx = 0

# クエリ処理
for i in range(Q):
    # クエリ入力
    query_type, x = map(int, input().split())

    # 
    if query_type == 1:
        top_idx += x

    else:
        top_idx %= N
        output_idx = (x - 1) - top_idx
        print(S[output_idx])

D - Trophy

問題文

N

個のゲームからなるステージがあります。

i(1 \leq i \leq N)

番目のステージは、

A_i

分のストーリー映像と、

B_i

分のゲームプレイによって構成されます。

i

番目のステージをクリアするためには、初回は

A_i+B_i

分の時間がかかります。
2回目以降は、

B_i

分だけでクリアできます。
最初は1番目のステージのみですが、　

i(1 \leq i \leq N-1)

番目のステージをクリアすると、

i+1

番目のステージもプレイできるようになります。
合計

X

回ステージをクリアするために、必要な時間の最小値を求めて下さい。
同じステージを周回プレイしても良いものとします。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i,B_i \leq 10^9$
$1 \leq X \leq 10^9$
入力は全て整数

考察

ソシャゲで周回に慣れてる人は多分割と簡単にイメージできたのでは問題
A,B,Xはちょっと制約が大きすぎるので、制約の小さいNで考えて…
どのステージを周回プレイするのが良いかなー？と。
例えば3ステージ目を周回プレイするのであれば、 $B_3$ をいっぱい重ねる事になりますね
- 3ステージ目を周回するのに、4ステージ目を1回だけプレイする必要は無いですね
  - X=10の時に1ステージ目クリア、2ステージ目クリアで合計2回クリア。
  - 3ステージ目を残り8回回る。 $B_3 \times 8$ 分の時間がかかる。
  - もし1回でも4ステージ目を回ったほうが良いのであれば、 $(A_4 + B_4) < B_3$ になっちゃう
  - この時点で $B_4 < B_3$ も確定しちゃうので、だったら $B_4$ 回ったほうが良くない？？？っていう話に…
1ステージ目を周回プレイするために必要な時間、2ステージ目を周回プレイするために必要な時間…で、最小値を求めれば良いね
nステージ目を周回プレイするためには、 $1~(n-1)$ ステージ目を1回ずつクリアしてなきゃいけない。
累積和でサクッと前処理しておいたら後々簡単に出てきますね。

# 入力
N, X = map(int, input().split())
L = []
accum_L = []
for i in range(N):
    A, B = map(int, input().split())
    L.append([A + B, B])

    # 累積和もここで一緒に作っちゃう
    if i == 0:
        accum_L.append(A + B)
    else:
        accum_L.append(accum_L[-1] + A + B)

# 答えの上限。10^18じゃ足りない点に注意
ans = 10 ** 20

# 何ステージ目を周回プレイするか全探索！
for i in range(N):

    # 周回プレイする回数
    loop_cnt = X - (i + 1)

    # もしこのステージ以降で周回プレイできない＝ステージ数に対してXが小さい場合はそこで打ち切ってOK
    if loop_cnt <= 0:
        break

    # iステージを周回プレイする場合に必要な時間＝(i-1)までの初回クリアに掛かる時間＋周回プレイする分の時間
    tmp_ans = accum_L[i] + L[i][1] * loop_cnt

    # 小さいなら更新して
    ans = min(ans, tmp_ans)

# 出力！
print(ans)

E - Packing Potatoes

問題要約

10^{100}

個のじゃがいもが、1個ずつ流れてきます。
流れてくるじゃがいもの重さは長さ

N

の数列

W=(W_0,…,W_{N-1})

で表されます。

i(1\leq i \leq 10^{100})

番目に流れてくるじゃがいもの重さは

W_{(i-1)modN}

です。

高橋くんは、まず空の箱を容易します。
次のルールに従ってじゃがいもを箱に詰めていきます。

じゃがいもを箱に入れる。もし、箱に入っているじゃがいもの重さの総和が $X$ 以上になったら、その箱には蓋をして、新しく空の箱を容易する。

Q

個のクエリが与えられます.

i(1\leq i \leq Q)

番目のクエリでは、正整数

K_i

が与えられるので、

K_i

番目に蓋をされた箱に入ってるじゃがいもの個数を求めて下さい。

制約

$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq X \leq 10^9$
$1 \leq W_i \leq 10^9$
$1 \leq K_i \leq 10^12$
入力は全て整数

考察

とりあえず、じゃがいもの個数が $10^100$ なのはちょっともう無限個あるものとして考えて…。
じゃがいもの重さはそれぞれ $W_{(i-1)modN}$
- $W$ がループしてる
  - このあたりから周期性を見て…
実際に入力例2の $K$ と $W$ を使ってどんなふうに高橋君が箱詰めしてるのか確認してみたい
- 1箱目 :[5, 8, 5, 9]→4個
- 2箱目 :[8, 7, 4, 4]→4個
- 3箱目 :[8, 2, 5, 8]→4個
- 4箱目 :[5, 9, 8]→3個
- 5箱目 :[7, 4, 4, 8]→4個
- 6箱目 :[2, 5, 8, 5]→4個
- 7箱目 :[9, 8, 7]→3個
- 8箱目 :[4, 4, 8, 2, 5]→5個
- 9箱目 :[8, 5, 9]→3個
- 10箱目:[8, 7, 4, 4]→4個
- 11箱目:[8, 2, 5, 8]→4個
- 12箱目:[5, 9, 8]→3個
ループしてるね…！！！
- ここのループが判明したので、後は周期性を求めてあげて…とか、ダブリング…とか…（考察を文字に直すための実力不足）
更に、 $K$ がとても大きくて、 $N=1,W_0=1$ みたいな状態だと、1箱に入るじゃがいもの数がとても大きくなるので…
- ここ（前処理段階）でも、高速化が必要…！うう…罠が多い…！

# 入力
N, Q, X = map(int, input().split())
W_L = list(map(int, input().split()))

# W_iを全部合わせたもの（じゃがいも1サイクルの合計重さ）
S = sum(W_L)

rd = X // S  # Xが大きすぎた場合に、何周セットで箱詰めするのが確定する？
rem = X % S  # Xが大きすぎた場合に、セットで足りない分の計算

# しゃくとり法のイメージで、「i番目のじゃがいもを最初に箱に入れた時、その箱にじゃがいもが何個入る？」を前計算
a = [0] * N
na = rd * N
for i in range(N):
    while rem >= 1:
        rem -= W_L[(i + na) % N]
        na += 1
    a[i] = na
    rem += W_L[i]
    na -= 1

# ダブリング前計算部分
D_num = 41
d = [[0 for i in range(N)] for j in range(D_num)]
for i in range(N):
    d[0][i] = (i + a[i]) % N

# ダブリング部分
for i in range(D_num - 1):
    for j in range(N):
        d[i + 1][j] = d[i][d[i][j]]

# クエリ処理部分
for i in range(Q):
    k = int(input())
    k -= 1

    si = 0
    for i in range(D_num - 1, -1, -1):
        if (k >> i) & 1:
            si = d[i][si]
    print(a[si])

Discussion

コメントにはログインが必要です。

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？