LoginSignup
0
0

More than 1 year has passed since last update.

@sano192

ユニークビジョンプログラミングコンテスト2022 冬(ABC283) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2023-01-09

ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

ユニークビジョン株式会社様について

求人情報

A Dif:8

計算して出力するだけでOKです。
pythonではAのB乗を「A**B」と書きます。
もしコンテスト中に書き方がわからなければググりましょう。

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

【提出】

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

# AのB乗を出力
print(A**B)

B Dif:35

指示通りに操作を行えばOKです。

以下2点に注意しましょう。
・クエリの種類によって受け取る入力の数が違います。一旦リストで受け取ってからリストの0番目、1番目、...という形で割り振りしましょう。
・問題ではリストの先頭が1番目、次が2番目ですが、pythonのリストは先頭が0番目になり番号がずれます。値の更新、出力も番号をずらすようにしましょう。

【提出】

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

# Q回
for i in range(Q):
    # 入力の受け取り
    # リストで受け取る
    query=list(map(int, input().split()))

    # クエリ1
    if query[0]==1:
        # 変数割り振り
        k=query[1]
        x=query[2]
        # xへ値を変更(k番目でなく(k-1)番目になる)
        A[k-1]=x
    
    # クエリ2
    else:
        # 変数割り振り
        k=query[1]
        # 値を出力(k番目でなく(k-1)番目になる)
        print(A[k-1])

C Dif:88

要するに普通の数字は1回ずつ、「00」が来たら2つ分まとめて1回ボタンを押しましょうということです。
0文字目から順に「00」かどうかを確認していきます。
for文でやるとちょっとややこしいのでwhileを使うと良いです。whileは嫌いな人も多いと思いますが、頑張って練習しましょう！

【提出】

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

# 答え
ans=0
# 初期値
i=0
# i<(Sの文字数)である間
while i<len(S):
    # S[i]~S[i+1]=「00」ならば
    if S[i:i+2]=="00":
        # 答えにプラス1
        ans+=1
        # 2つ進める
        i+=2
    # そうでなければ
    else:
        # 答えにプラス1
        ans+=1
        # 一つ進める
        i+=1

# 答えの出力
print(ans)

D Dif:453

まず「良い文字列」はなにかを確認しましょう。
((a))→「良い文字列」
((a))()b(()a)→「良い文字列」
()b)(a)→「良い文字列」でない
)()→「良い文字列」でない
これを見ればわかるように「良い文字列」とは括弧に矛盾がない、開き括弧に対応した閉じ括弧がすべて存在するような文字をいいます。

箱に入れる、取り出す操作はちょっと分かりづらいですが、「)」が来たらそれに対応する「(」まで戻り、その間のすべての文字を箱から取り出すということです。
いくつか例を作ってみましょう。
(abc)→Yes
((a)b)→Yes
(((b)a)b)→Yes
(a(a))→No
((a)a)→Yes

今どれが箱に入っていて、どのタイミングで取り出せばいいのかを管理するわけですが、以下のようにやると上手くいきます。

Sの文字を順に見ていく。最初リストに「""」(空文字列)を追加しておく。
・「(」の場合
リストに「""」(空文字列)を追加。
・アルファベットの場合
リスト末尾の文字にアルファベットをつける。箱に入れたと記録する。
・「)」
リストの一番後ろの要素を取り出し、記録された文字を箱から取り出す。

具体例で見てみましょう。
S：((a)b)c

リスト：""
箱：(空)

・S[0]="("
リストに「""」(空文字列)を追加。
リスト："",""
箱：(空)

・S[1]="("
リストに「""」(空文字列)を追加。
リスト："","",""
箱：(空)

・S[2]="a"
リスト末尾の文字にアルファベットをつける。箱に入れたと記録する。
リスト："","","a"
箱："a"が1個

・S[3]=")"
リストの一番後ろの要素を取り出し、記録された文字を箱から取り出す。
リストの一番後ろは「a」だから「a」を取り出す。
リスト："",""
箱：(空)

・S[4]="b"
リスト末尾の文字にアルファベットをつける。箱に入れたと記録する。
リスト："","","b"
箱："b"が1個

・S[5]=")"
リストの一番後ろの要素を取り出し、記録された文字を箱から取り出す。
リストの一番後ろは「b」だから「b」を取り出す。
リスト："",""
箱：(空)

・S[6]="c"
リスト末尾の文字にアルファベットをつける。箱に入れたと記録する。
リスト："","","c"
箱："c"が1個

最後まで箱の中のボールが被りませんでしたので、Yesとなります。

このように最後に入れたデータが最初に取り出されるデータ構造をスタックと言います。
この問題は「(」が来たタイミングでスタックに新しい要素を追加し、「)」が来たタイミングでスタックから取り出しを行うことで、どの文字を取り出せばいいのか管理ができています。

箱の中身の管理は連想配列を使うと楽にできます。

defaultdict(連想配列)について
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造です。
pythonでは標準で搭載されており、dict()と書くことで使えます。
しかし標準のものはデフォルトの値(初期値)が設定できず、存在しない「キー」にアクセスする可能性があるときの処理が面倒です。
defaultdictは標準の連想配列と同様に使えて、さらに初期値を設定できます。
値の割当が行われていない「キー」には自動的に初期値が割り振られます。
「使い方」
・インポート：from collections import defaultdict
・作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
・キー、値の登録【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]

使用例
# インポート：from collections import defaultdict
from collections import defaultdict

# 作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
AsArray=defaultdict(int)

# キー、値の登録【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["Men"]="Taro"
AsArray[(1,2)]=[3,4,5]
 
# 値の参照【O(1)】：変数名[キー]
print(AsArray[1])
print(AsArray["Men"])
print(AsArray[(1,2)])

# 値が割当されていないキーも参照可能(値はデフォルト値)
print(AsArray[99])

【提出】

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

# スタックを用意
Stack=[""]

# defaultdictのインポート
from collections import defaultdict

# 箱(各文字が入っている個数を記録する)
Box=defaultdict(int)

# i=0~(Sの文字数-1)
for i in range(len(S)):
    # 「(」の場合
    if S[i]=="(":
        # スタックに空文字列を追加
        Stack.append("")
    # 「)」の場合
    elif S[i]==")":
        # スタックの末尾(最後に入れた要素)を取り出し
        Mozi=Stack.pop()
        # x：Moziの各要素
        for x in Mozi:
            # xを取り出し(要素数をマイナス1)
            Box[x]-=1
    # アルファベットの場合
    else:
        # 箱に入れる(個数をプラス1)
        Box[S[i]]+=1
        # もし個数が2個になったら
        if Box[S[i]]==2:
            # 「No」を出力
            print("No")
            # 終了
            exit()
        # スタック最後の要素末尾に追加
        Stack[-1]+=S[i]

# 「Yes」を出力
print("Yes")

【広告】

『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 灰・茶・緑問題 超詳細解説』

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

『AtCoder ABC251～275 ARC140～151 灰・茶・緑問題 超詳細解説』

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

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

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

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

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

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

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

『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

0
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
0
0