(ABC303)A-C問題のpythonでの解法

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC303のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム

組み合わせ(combinations) 　　　　　　　・・・　問題B

今回の参加コンテスト(ABC303)
感想

今回の参加コンテスト(ABC303)

AtCoder Beginner Contest 303

A問題：Similar String

A – Similar String

問題(要約)

2つの文字列S, Tが与えられ、各文字全てが下記条件に当てはまるか判断する

xとyは同じ文字
xとyの片方が 1 で、もう片方が l
xとyの片方が 0 で、もう片方が o

解答

# 番号1
n=int(input())
S=input()
T=input()

# 番号2
    # 番号2-1
    if S[i] != T[i]:
        # 番号2-2
        if (S[i] == "1" and T[i] == "l") or (S[i] == "l" and T[i] == "1"):
            continue
        # 番号2-3
        elif (S[i] == "0" and T[i] == "o") or (S[i] == "o" and T[i] == "0"):
            continue
        # 番号2-4
        else:
            exit(print("No"))
# 番号3
print("Yes")

考え方 (下の番号は、コード内のコメント番号と連携している)

解答の方針は、if 文を用いて問題文の条件を確認する

n, S, Tの入力を受け取る
for文を用いて文字列から単語を一つ取り出す
1. 取り出した文字が違うかどうかを確認。同じ場合は次の文字を調べる
2. 1 と l の似た文字に当てはまるかを確認する。SとTの入れ替えがあることに注意
3. 1 と o の似た文字に当てはまるかを確認する
4. 番号2-2, 2-3に当てはまらない場合は、似た文字ではないのでNGとする
最後の文字まで確認ができたため”Yes”を出力する

B問題：Discord

B – Discord

問題(要約)

N人の人が並んでM回写真と撮る。一度も隣同士にならなかった二人組が不仲である可能性があり、不仲である可能性の組みの数を求める

解答

# 番号1
import itertools

# 番号2
n,m=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(m)]

# 番号3
comb = set(itertools.combinations((x for x in range(1,n+1)),2))

# 番号4
for k in range(m):
    for i in range(1,n):
        # 番号4-1
        if A[k][i-1] < A[k][i]:
            a,b=A[k][i-1],A[k][i]
        else:
            a,b=A[k][i],A[k][i-1]
        
        # 番号4-2
        if (a,b) in comb:
            comb.remove((a,b))
# 番号5
print(len(comb))

考え方(下の番号は、コード内のコメント番号と連携している)

N人のうち二人ペアの組み合わせを列挙し、隣同士の組み合わせを列挙したものから削除する。残った組み合わせの数を数える

組み合わせを列挙するためにイテレータのitertoolsをインポートする
入力 n, m, A を受け取る
- 入力 A は、内包表記を用いて、2次元配列で受け取る
itertoolsのcombinationsを用いて想定される組み合わせパターンを全て列挙する。また、配列でなく、集合(set)にすることにより、後のif文の検索スピードを向上させている
- 第1引数：配列。内包表記にて1からNまでの配列を入力
- 第2引数：取り出した組み合わせ。今回はペアなので、２
- combinationsで作成したペアの組み合わせは、左側の数字の方が小さくなっている。
  つまり、組み(a, b)は、 a < b が成り立つ
配列Aを順番に調べていく。カウンタ変数 k は、撮影回数順。i は並びを示す
1. combinationsの配列は、左側の方が小さくなっているため、組み合わせの順番を調整する。つまり、隣同士の二つを取り出し、小さい方をa, 大きい方をbとする
2. 組み合わせ列挙したcomb配列の中に(a,b)があるかどうかを確認し、存在していれば、removeでcomb配列から削除する
残ったcomb配列の数を数える

C問題：Dash

C – Dash

問題(要約)

二次元平面の点(0,0)に体力Hの高橋君がいる。M個の回復アイテムが二次元平面上に配置してある。倒れることも無く、N回移動できるかを判断する

体力1を消費し、Sの文字列に従って順番に移動する R, L, U, D、それぞれ右、左、上、下にひとマスづつ移動
体力が負になった場合に倒れてしまう。移動した点にアイテムがあり、かつ高橋君の体力がK未満ならば、移動した点のアイテムを消費し、体力がKとなる
- アイテムは一度使うと消費されてなくなる
- 体力がK以上の場合はアイテムが消費されない

解答

# 番号1
n,m,h,k=map(int,input().split())
S=input()

# 番号2
items = set()
for _ in range(m):
    x,y = map(int,input().split())
    items.add((x,y))

# 番号3
wayDic = {"R":(1,0),"L":(-1,0),"U":(0,1),"D":(0,-1)}
x,y=0,0

# 番号4
for s in S:
    # 番号4-1
    if h<=0: exit(print("No"))

    # 番号4-2
    x+=wayDic[s][0]
    y+=wayDic[s][1]
    h-=1

    # 番号4-3
    if h < k:
        if (x,y) in items:
            # 番号4-4
            h=k
            items.remove((x,y))
# 番号5
print("Yes")

考え方(下の番号は、コード内のコメント番号と連携している)

問題文の記載の通りにx,yを動かしていく。アイテムが消費されて行くところに注意が必要

入力n,m,h,k,Sを受け取る
アイテムの位置は集合型で受け取る。空の辞書型itemsを宣言し、それぞれの位置を追加していく。
定数と初期値の設定
- 移動向きと距離を辞書型で登録する
- 位置の初期値x, yを設定する
配列Sから文字列を順番に取り出す
1. 現状の体力 h が0以下なら、次の動きで倒れてしまう。そのため、”No”を出力してプログラムを終了させる
2. 位置 x, y を辞書型wayDicから呼び出し、それぞれ加算する。体力 h は 1減らす
3. 体力hが、k 未満かを判断する。k 未満の時、現行位置にアイテムがあるかを確かめる。
4. 体力が k 未満、かつ、現行位置にアイテムがある場合にアイテムを消費して、h = k にする。また、アイテムが消費されるため、itemsから位置(x,y)を取り除く
  ＊同じ所を通る場合に重複してアイテムが使われないようにする
途中で倒れた場合はプログラムが終了するため、ここでは倒れずに到着したため”Yes”と出力

補足：辞書型と集合の削除

辞書型と集合の削除の仕方でつまづいてしまったため、下記にChatGPTでまとめてもらいました

メソッド	動作	返り値	エラーの発生
辞書型
`pop()`	指定したキーに対応する値を取得し、辞書から削除	削除された値	`KeyError`
`clear()`	辞書のすべての要素を削除し、空の辞書とする	なし	なし
`del`	指定したキーに対応するキーと値を辞書から削除	なし	なし（キーが存在しない場合にエラー）
集合
`remove()`	指定した要素を集合から削除	なし	`KeyError`
`pop()`	集合からランダムな要素を削除し、その要素を返す	削除された要素	`KeyError`
`clear()`	集合のすべての要素を削除し、空の集合とする	なし	なし