LoginSignup
TrendQuestionOfficial EventOfficial ColumnOpportunitiesOrganization
3
1
@sano192

posted at

updated at

東京海上日動プログラミングコンテスト2022(ABC256) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Python,AtCoder,競技プログラミング,競プロ

東京海上日動プログラミングコンテスト2022(ABC256)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

東京海上日動様について

本コンテストは東京海上日動様が主催されています。
興味のある方はHPを御覧ください。

A - 2^N　Dif:7

単純にNを受け取って2のN乗を出力すればOKです。
2のN乗は
2**N
と書けば計算できます。

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

【提出】

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

# 2のN乗を出力
print(2**N)

B - Batters　Dif:83

マス目と駒を用意して実際にシュミレーションしてみましょう。
まず各操作の最初にマス0へ駒を一つおきます。
次にマス目上にある全ての駒についてA[i]マス先へ移動させます。
・(今いるマス目＋A[i])<4ならば
　(今いるマス目＋A[i])へ駒を移動させます。
・それ以外(4≤(今いるマス目＋A[i])ならば
　Pにプラス1します。駒はなくなります。

駒のあるマス目をKomaというリストへ記録していきましょう。
例えば駒がマス0,マス2,マス3にあるなら
Koma=[0,2.3]
となります。

for x in Koma:
と書くことでKomaの値をxへ順に入力しながら処理できます。
これで(x＋A[i])と書くことでA[i]分だけ駒を進めることができます。
新しく進んだマス目の情報はNewKomaというリストへ記録し、操作の最後にKoma=NewKomaと更新しましょう。

【提出】

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

# Pに初期値0を入れる
P=0

# 駒があるマス目
# 最初はマス0に1個
Koma=[0]

# i=0~(N-1)
for i in range(N):
    # 新しい駒の場所
    NewKoma=[0]

    # Komaの値を順にxへ入力して処理
    for x in Koma:
        # (x+A[i])<4⇔マス目の範囲内なら
        if x+A[i]<4:
            # 新しいマス目を記録
            NewKoma.append(x+A[i])
        # そうでないなら(マス目の範囲を超えたら)
        else:
            # Pにプラス1
            P+=1

    # KomaをNewKomaで更新
    Koma=NewKoma

# 答えの出力
print(P)

C - Filling 3x3 array　Dif:541

マス目に名前をつけましょう。Mは「マス目」のMです。(名前はなんでもいいですが・・・)
ABC256_C_1.png

式を立てると以下のようになります。
M11+M12+M13=h1
M21+M22+M23=h2
M31+M32+M33=h3
M11+M21+M31=w1
M12+M22+M33=w2
M13+M23+M33=w3

重要なのはh,wがすでに決まっているので、左上4マス(M11,M12,M21,M22)が決まれば他のマス目(M13,M23,M31,M32,M33)も自動的に値が決定されるということです。
具体的には式変形して以下のようになります。
M13=h1-(M11+M12)
M23=h2-(M21+M22)
M31=w1-(M11+M21)
M32=w2-(M12+M22)
M33=h3-(M31+M32)

h,wともに最大値は30なので一つのマス目に入りうる数は最大でも28までです。
M11,M12,M21,M22の4通りについて1~28を試すなら28^4=614656≒10^5なので全パターン試しても実行制限時間に間に合います。
残り5マス(M13,M23,M31,M32,M33)について上記式で計算した時、それらが満たすべき条件は以下の2つです。
・全て正の整数(0より大きい)
・M13+M23+M33=w3も成り立つ
これらを満たすなら答えとしてカウントします。

【提出】

# 入力の受け取り
h1,h2,h3,w1,w2,w3=map(int,input().split())

# 答えのカウント
ans=0

# M11=1~28
for M11 in range(1,29):
    # M12=1~28
    for M12 in range(1,29):
        # M21=1~28
        for M21 in range(1,29):
            # M22=1~28
            for M22 in range(1,29):
                # それぞれの値を計算
                M13=h1-(M11+M12)
                M23=h2-(M21+M22)
                M31=w1-(M11+M21)
                M32=w2-(M12+M22)
                M33=h3-(M31+M32)
                
                # ・全て正の整数(0より大きい)
                if 0<M13 and 0<M23 and 0<M31 and 0<M32 and 0<M33:              
                    # ・M13+M23+M33==w3も成り立つ
                    if M13+M23+M33==w3:
                        # 答えにカウント
                        ans+=1

# 答えの出力
print(ans)

D - Union of Interval　Dif:546

まず区間を左側が小さい順に並び替えます。
各区間ごとにそこまでで作っている区間でカバーできるかを確認していきます。

例を見ましょう。
入力が以下の場合を考えます。
4
1 10
20 30
25 29
25 35

まずひとつ目の区間を今の区間、[NowL,NowR)とします。
[NowL,NowR)=[1,10)となります。

(1)[20 30)
区間の左側20は「今の区間」右側NowR=10より大きいです。「今の区間」はどう頑張っても[20 30)をカバーできません。
この時点で[1,10)は絶対に必要なことがわかるので「1 10」を出力します。
「今の区間」を更新し、[NowL,NowR)=[20,30)とします

(2)[25,29)
まず区間の左側25は25≤30⇔25≤NowRとなっています。
であれば左側25は「今の区間」=[20,30)でカバーできることがわかります。
一方右側29も29<30⇔29≤NowRです。同様に「今の区間」=[20,30)でカバーできます。
[25,29)は[20,30)の範囲内にいるのでわざわざ区間を増やす必要はないということです。
この場合はNowL,NowRともに更新しません。

(3)[25,35)
区間の左側25は25≤30⇔25≤NowRですからさきほど同様に左はカバーできています。
右側35は30<35⇔NowR<35なのでカバーできていません。ですから区間の右端だけ更新します。つまりNowR=35とし、「今の区間」=[20,35)となります。

最後に[NowL,NowR)(=[20,35))を出力します。

以上を一般化すると以下の手順になります。
(1)1つ目の区間を[NowL,NowR)とする
(2)次の区間について
　・「今の区間の右側」<「次の区間の左側」の場合(「今の区間」が「次の区間」をカバーできていない場合)
　　「今の区間」は絶対に必要なので出力
　　「今の区間」を「次の区間」で更新
　・「次の区間の左側」≤「今の区間の右側」の場合(左がカバーできている場合)
　　・「今の区間の右側」<「次の区間の右側」の場合(右がカバーできていない場合)
　　　「今の区間の右側」を「次の区間の右側」で更新(右側を広げる)
(3)最後に「今の区間」を出力
　
【提出】

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

# 区間の情報を格納するリスト
LR=[]

# N回
for i in range(N):
    # 入力の受け取り
    L,R=map(int,input().split())
    # 区間の情報を格納
    LR.append([L,R])

# 左側の小さい順にソート
LR.sort()

# 今の区間左側
NowL=LR[0][0]
# 今の区間右側
NowR=LR[0][1]

# i=1~(N-1)
for i in range(1,N):
    # 次の(i番目の)区間左側
    NextL=LR[i][0]
    # 次の(i番目の)区間右側
    NextR=LR[i][1]

    # 「今の右側」<「次の左側」
    if NowR<NextL:
        # [NowL,NowR)は絶対に必要な区間
        print(NowL,NowR)
        # 今の区間を更新
        NowL=NextL
        NowR=NextR

    # それ以外(「次の左側」≤「今の右側」)
    else:
        # 「今の右側」<「次の右側」
        if NowR<NextR:
            # 区間を更新(右側を広げる)
            NowR=NextR

# 最後に区間を出力
print(NowL,NowR)

【広告】

『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

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
What you can do with signing up
Sign upLogin
3
1