Ccmmutty logo
Commutty IT
0 pv10 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?

問題要約

2121時ちょうどから、KK分後の時刻を、HH:MMの形式で出力して下さい。
(HHは24時間制での時間、MMは分を表す)
時間または分が1桁の時は、先頭に00を追加して22桁の整数として表して下さい。

制約

  • K は00以上100100以下の整数

考察

  • いわゆる「やるだけ」問題
  • 黒ココアさんは完全愚直場合分けルートで4択作りました
    • Kの値が…
      • 10未満:21時 + K分(0埋めが必要)
      • 10以上60未満:21時+K分
      • 60以上70未満:22時+(K-60)分(0埋めが必要
      • 70以上:22時+(K-60)分
  • datetime使って時間計算しても良し
  • formatや、zfillで0埋めしても良し
python
# 入力
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 91~9の数字が書かれたNNN行N列のマスがあります。
このマス目は、上下左右が繋がっているものとします。
高橋くんは、上下左右及び斜めの8方向のうちいずれかを始めに選び、その方向にN1N-1回移動します。 高橋くんが通ったマスにかかれている数字を、左から順に並べた時の整数として最大値を求めてください。

制約

  • 1N101\leq N \leq 10
  • 1Ai,j91 \leq A_{i,j} \leq 9
  • 入力は全て整数

考察

  • いわゆる「全探索」するような問題
  • 制約から、
    • 始点となるマスは最大100マス(N×NN \times N)
    • 方向は8方向
      • 800通りの数字しかできない
  • 800個数字を作って、一番大きいものを出力してあげればOK
  • 実装上の問題として、
    • 盤面がループしている点の表現
    • 方向の指定
      • このあたりが問われている感
      • 正直どっちも典型実装…あ、典型実装まとめとか需要あったりします…?
      • 2種類混ぜてきてるのがC氏の要求の高さ…!!!
  • 盤面のループに関する表現方法については、
    • NNで割った余りで表現する
    • 盤面を拡張しておく
  • このあたりが思いつく
    • 制約が厳しくなってきた時は後者が使えないため、前者を練習しておいたほうが良い気はします
  • 方向の指定については、
    • 高々8パターンなので手で書いてしまえ!(物理で殴るタイプ。黒ココアさんの本番ACはこちら)
    • di,djd_i,d_jで遷移先をループできるとスマートですね
python
# 入力
N = int(input())
L = []
# 1桁ずつ分けるのが面倒だったので、今回は文字列のままの取り扱い
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:「SSの末尾の文字を削除し、先頭に挿入」をxx回連続で行う
  • 2 xSSxx番目の文字を出力する

制約

  • 2N5×1052 \leq N \leq 5\times10^5
  • 1Q5×105 1 \leq Q \leq 5\times10^5
  • 1xN1 \leq x \leq N
  • SSは英数小文字からなる
  • 2 xの形式のクエリが1個以上与えられる
  • N,Q,xN,Q,xは全て整数

考察

  • 愚直にクエリを処理していくと、x=5×105x=5\times10^5のクエリ1が、5×10515\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を引いてあげる…!
python
# 入力
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

問題文

NN個のゲームからなるステージがあります。
i(1iN)i(1 \leq i \leq N)番目のステージは、AiA_i分のストーリー映像と、BiB_i分のゲームプレイによって構成されます。
ii番目のステージをクリアするためには、初回はAi+BiA_i+B_i分の時間がかかります。
2回目以降は、BiB_i分だけでクリアできます。
最初は1番目のステージのみですが、 i(1iN1)i(1 \leq i \leq N-1)番目のステージをクリアすると、i+1i+1番目のステージもプレイできるようになります。
合計XX回ステージをクリアするために、必要な時間の最小値を求めて下さい。
同じステージを周回プレイしても良いものとします。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai,Bi1091 \leq A_i,B_i \leq 10^9
  • 1X109 1 \leq X \leq 10^9
  • 入力は全て整数

考察

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

問題要約

1010010^{100}個のじゃがいもが、1個ずつ流れてきます。
流れてくるじゃがいもの重さは長さNNの数列W=(W0,,WN1)W=(W_0,…,W_{N-1})で表されます。
i(1i10100)i(1\leq i \leq 10^{100})番目に流れてくるじゃがいもの重さはW(i1)modNW_{(i-1)modN}です。
高橋くんは、まず空の箱を容易します。
次のルールに従ってじゃがいもを箱に詰めていきます。
  • じゃがいもを箱に入れる。もし、箱に入っているじゃがいもの重さの総和がXX以上になったら、その箱には蓋をして、新しく空の箱を容易する。
QQ個のクエリが与えられます.i(1iQ)i(1\leq i \leq Q)番目のクエリでは、正整数KiK_iが与えられるので、
KiK_i番目に蓋をされた箱に入ってるじゃがいもの個数を求めて下さい。

制約

  • 1N,Q2×1051 \leq N,Q \leq 2 \times 10^5
  • 1X1091 \leq X \leq 10^9
  • 1Wi1091 \leq W_i \leq 10^9
  • 1Ki10121 \leq K_i \leq 10^12
  • 入力は全て整数

考察

  • とりあえず、じゃがいもの個数が1010010^100なのはちょっともう無限個あるものとして考えて…。
  • じゃがいもの重さはそれぞれW(i1)modNW_{(i-1)modN}
    • WWがループしてる
      • このあたりから周期性を見て…
  • 実際に入力例2のKKWWを使ってどんなふうに高橋君が箱詰めしてるのか確認してみたい
    • 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個
  • ループしてるね…!!!
    • ここのループが判明したので、後は周期性を求めてあげて…とか、ダブリング…とか…(考察を文字に直すための実力不足)
  • 更に、KKがとても大きくて、N=1,W0=1N=1,W_0=1みたいな状態だと、1箱に入るじゃがいもの数がとても大きくなるので…
    • ここ(前処理段階)でも、高速化が必要…!うう…罠が多い…!
python
# 入力
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

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