Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@sano192

ABC258 A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2022-07-03

ABC258(AtCoder Beginner Contest 258)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

A - When?　Dif:10

Nが60未満なら21時台、60以上なら22時台になります。
22時台ならNから60を引くことで分がわかります。例えばN=86なら86-60=26分です。

出力のときに分が一桁なら、すなわち0~9分なら前に「0」を一つつけなければなりません。
時間を出力するときはNを文字列にして"21:"か"22:"にくっつけます。

数字を文字列にするには
str(数字)
と書きます。

文字列同士をくっつけるときは「+」を使います。"21:"とNをくっつけるなら
"21:"+str(N)
となります。ここで+str(N)ではなく+Nとすると、pythonは数字を足し算しなければならないと解釈してエラーになってしまいます。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
N=int(input())

# Nが60未満なら
if N<60:
    # N=0~9なら(0~9分なら)
    if 0<=N<=9:
        # 「21：」+「0」+(Nを文字に変換)　を出力
        print("21:"+"0"+str(N))
    # それ以外なら(11~59分なら)
    else:
        # 「21：」+(Nを文字に変換)　を出力
        print("21:"+str(N))
# それ以外なら(Nが60以上)
else:
    # 60マイナスする
    N-=60

    # N=0~9なら(0~9分なら)
    if 0<=N<=9:
        # 「22：」+「0」+(Nを文字に変換)　を出力
        print("22:"+"0"+str(N))
    # それ以外なら(11~59分なら)
    else:
        # 「22：」+(Nを文字に変換)　を出力
        print("22:"+str(N))

B - Number Box　Dif:511

入力例1を図にしてみましょう。
ABC258_B_1.png
実装に合わせて0インデックス、すなわち最初の行、列の番号は0としています。
例えば(0,2)から右下に進むときの座標の変化を見てみましょう。
ABC258_B_2.png
(0,2)
(1,3)
(2,0)
(3,1)
行、列ともに1ずつ増えていき、4になったら0へ戻るという挙動になっています。
これはN=4で割った余りを使うと以下のように書けます。
((0+0)%4,(2+0)%4)→(0%4,2%4)→(0,2)
((0+1)%4,(2+1)%4)→(1%4,3%4)→(1,3)
((0+2)%4,(2+2)%4)→(2%4,4%4)→(2,0)
((0+3)%4,(2+3)%4)→(3%4,5%4)→(3,1)
つまり右下にi移動したマスというのは
((スタート行+i)%N,(スタート列+i)%N)
と表せるということです。

左上ならマイナスになります。
((スタート行-i)%N,(スタート列-i)%N)

右なら列だけ増えます。
(スタート行,(スタート列+i)%N)

i移動したマスの座標をより一般に考えましょう。
上方向(-1,0)：((スタート行+(-1)*i)%N,(スタート列+0*i)%N)
右上方向(-1,1)：((スタート行+(-1)*i)%N,(スタート列+1*i)%N)
右方向(0,1)：((スタート行+0*i)%N,(スタート列+1*i)%N)
右下方向(1,1)：((スタート行+1*i)%N,(スタート列+1*i)%N)
下方向(1,0)：((スタート行+1*i)%N,(スタート列+0*i)%N)
左下方向(1,-1)：((スタート行+1*i)%N,(スタート列+(-1)*i)%N)
左方向(0,-1)：((スタート行+0*i)%N,(スタート列+(-1)*i)%N)
左上方向(-1,-1)：((スタート行+(-1)*i)%N,(スタート列+(-1)*i)%N)

(スタート行,スタート列,行方向,列方向)を引数とする関数を作ります。
各マスを通りながら数字を記録していく関数です。
行方向、列方向には-1,0,1のいずれかが入ります。

# 引数：(スタート行,スタート列,行方向,列方向)　→　マス目の数字を確認して値を返す
def Calc(G,R,GD,RD):
    # 結果
    result=""
    # i=0~(N-1)
    for i in range(N):
        # ((G+GD*i)%N,(R+RD*i)%N)マスの数字を記録
        result+=Grid[(G+GD*i)%N][(R+RD*i)%N]
    # 整数へ変換
    result=int(result)
    # 返す
    return result

Nは最大10とかなり小さいので、全てのマス、全ての方向について愚直に値を確認し、最も大きいものを出力して終わりです。

【提出】

# 入力の受け取り
N=int(input())

# マス目
Grid=[]

# N回
for i in range(N):
    # 入力の受け取り
    A=input()
    # 一文字ずつのリストへ展開
    A=list(A)
    # Gridへ記録
    Grid.append(A)

# 引数：(スタート行,スタート列,行方向,列方向)　→　マス目の数字を確認して値を返す
def Calc(G,R,GD,RD):
    # 結果
    result=""
    # i=0~(N-1)
    for i in range(N):
        # ((G+GD*i)%N,(R+RD*i)%N)マスの数字を記録
        result+=Grid[(G+GD*i)%N][(R+RD*i)%N]
    # 整数へ変換
    result=int(result)
    # 返す
    return result

# 答え
ans=0

# 行：G=0~(N-1)
for G in range(N):
    # 列：R=0~(N-1)
    for R in range(N):
        # (G,R)がスタートマス
        # 計算結果が今までの答えより大きければ更新
        # 上方向(-1,0)
        ans=max(ans,Calc(G,R,-1,0))
        # 右上方向(-1,1)
        ans=max(ans,Calc(G,R,-1,1))
        # 右方向(0,1)
        ans=max(ans,Calc(G,R,0,1))
        # 右下方向(1,1)
        ans=max(ans,Calc(G,R,1,1))
        # 下方向(1,0)
        ans=max(ans,Calc(G,R,1,0))
        # 左下方向(1,-1)
        ans=max(ans,Calc(G,R,1,-1))
        # 左方向(0,-1)
        ans=max(ans,Calc(G,R,0,-1))
        # 左上方向(-1,-1)
        ans=max(ans,Calc(G,R,-1,-1))

# 答えの出力
print(ans)

C - Rotation　Dif:419

t=1のクエリをクエリ1
t=2のクエリをクエリ2
と呼びます

クエリ1のたび問題文の指示通りに操作を行うと間に合いません。
例えばS=abcdefのとき、クエリ1でx=3だとどうなるか考えましょう。
S：abcdef
1回目：fabcde
2回目：efabcd
3回目：defabc
よってSの最初の文字(0文字目)が3文字目「d」に移ったということがわかります。
このスタートの文字位置だけ管理することを考えましょう。赤い矢印がスタート位置です。

ABC258_C_1.png

より一般にはスタート位置は以下のように変化します。
(新しいスタート位置)=(前のスタート位置-x)%N

Nで割った余りを取っているのはマイナスになった時0へ戻すためです。
例えばS=abcdef(N=6)の時、前のスタート位置が0でx=4ならば
(新しいスタート位置)=(前のスタート位置-x)%N
⇔(新しいスタート位置)=(0-4)%6
⇔(新しいスタート位置)=(-4)%6
⇔(新しいスタート位置)=2
と計算できるわけです。

次はクエリ2について考えます。
こちらは簡単で、(スタート位置+(x-1))%N)番目の文字を出力するだけです。
※pythonは0インデックスのため(x-1)と一個ずれることに注意してください

例としてx=2の時を考えましょう。同じようにS=abcdefで、スタート位置は3番目になっているとします。
(スタート位置+(x-1))%6)=(3+(2-1))%6=4%6=4ですから、4番目の文字「e」を出力すればよいです。
(実際にはSは3番目の文字「d」から始まる、すなわちS=defabcになっているためです)

Nで余りを取っているのはNを超えたときに0に戻すためです。
例えばx=5なら
(スタート位置+(x-1))%6
=(3+(5-1))%6
=7%6
=1
となって1番目の文字「b」を出力します。

【提出】

# 入力の受け取り
N,Q=map(int,input().split())
S=input()

# スタート位置
Start=0

# Q回
for i in range(Q):
    # 入力の受け取り
    t,x=map(int,input().split())

    # クエリ1
    if t==1:
        # (新しいスタート位置)=(前のスタート位置-x)%N
        Start=(Start-x)%N
    # クエリ2
    else:
        # (スタート位置+(x-1))%N)番目の文字を出力
        print(S[(Start+(x-1))%N])

D - Trophy　Dif:687

基本的にはできるだけプレイ時間(=B)が少ないゲームをやり続けたほうが良いです。
プレイ時間が少ないステージができるところまでクリアしたら、その前のステージをもう一度クリアする必要はありません。
よって
ステージ1までクリアし、ステージ1をクリアし続ける
ステージ2までクリアし、ステージ2をクリアし続ける
ステージ3までクリアし、ステージ3をクリアし続ける
...
と全パターンを試し、一番時間が短いものを探します。

例えば以下の例で考えましょう。
N X：3 10
A1 B1：7 8
A1 B1：10 3
A1 B1：9 4

「ステージ1までクリアし、ステージ1をクリアし続ける」
ステージ1のクリアにかかる時間はA1+B1=7+8=15分です。
この時点で1回クリアしているので残り必要な回数はX-1=10-1=9回です。
9*B1=9*8=72分なので合計15+72=87分かかります。

「ステージ2までクリアし、ステージ2をクリアし続ける」
ステージ2に到達するまでにステージ1を1回クリアしなければなりません。
ステージ1のクリアには先程計算した通り15分かかります。
ステージ2のクリアにかかる時間はA2+B2=10+3=13分です。
すなわちステージ1,2両方のクリアに15+13＝28分かかります。
この時点でステージ1,2合わせて2回クリアしているので残り必要な回数はX-2=10-2=8回です。
8*B2=8*3=24分なので合計28+24=52分かかります。

「ステージ3までクリアし、ステージ3をクリアし続ける」
ステージ3に到達するまでにステージ1,2を1回クリアしなければなりません。
ステージ1,2のクリアには先程計算した通り28分かかります。
ステージ3のクリアにかかる時間はA3+B3=9+4=13分です。
すなわちステージ1,2,3全てのクリアに28+13＝41分かかります。
この時点でステージ1,2,3合わせて3回クリアしているので残り必要な回数はX-3=10-3=7回です。
7*B3=7*4=28分なので合計41+28=69分かかります。

最も短いのは「ステージ2までクリアし、ステージ2をクリアし続ける」パターンで、52分となります。

X<Nの場合、(X+1)~N番目のステージは使えないということに注意してください。

【提出】

# 入力の受け取り
N,X=map(int,input().split())

# 答え
ans=10**20
# ステージiまでをクリアするのにかかる時間
time=0
# i=1~(X,Nのうち小さい方)
for i in range(1,min(X,N)+1):
    # 入力の受け取り
    A,B=map(int,input().split())
    # 「ステージiまでクリアし、ステージiをクリアし続ける」のにかかる時間
    tmpans=0

    # ステージiまでをクリアするのにかかる時間
    # (i-1)番目までをクリアするのにかかる時間+ステージiをクリアするのにかかる時間
    time+=A+B
    # (ステージiまでをクリアするのにかかる時間)を足す
    tmpans+=time

    # ステージiまではクリアしている
    # ⇔i回はクリアしているので残り(X-i)回ステージiをクリアする
    tmpans+=(X-i)*B

    # 答えが小さければ更新
    ans=min(ans,tmpans)

# 答えの出力
print(ans)

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?