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

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

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

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

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

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

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

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

累積和(accumulate) 　　　　　　　　　　　　・・・　別解
数字化 (Unicode )　　　　　　　　　　　　　　・・・　別解

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

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

AtCoder Beginner Contest 305

A問題：Water Station

A – Water Station

問題(要約)

100kmのマラソンコースがあり、スタートとゴール地点を含む5km毎に給水所が設置してある。現在地点が与えられるので、最も近い給水所を出力する

解答

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

# 番号2
if n%5<3:
    print(n-n%5)
else:
    print(n+(5-n%5))

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

給水所は5km毎であるため、現在距離を5で割った余りを用いて近くの給水所を出力する

以下、プログラム内容詳細

入力nを受け取り、整数型に変換する
if文を用いて、Nを5で割った余りが3未満(0, 1, 2の場合)とそれ以外(3, 4の場合)で分別する
- 余りが0, 1, 2の場合：余り分を現在距離から引くことにより最も近い給水所を探せる
- 余りが3, 4の場合：次の給水所までの距離は、5 – 余りで求められる。現在の距離にその距離(5-n%5)を足すことにより最も近い給水所を求める

B問題：ABCDEFG

B – ABCDEFG

問題(要約)

直線上に7個の点 A, B, C, D, E, F, G が並んでいる。隣り合う距離は下記で与えらる。

点 A と点 B の距離は 3
点 B と点 C の距離は 1
点 C と点 D の距離は 4
点 D と点 E の距離は 1
点 E と点 F の距離は 5
点 F と点 G の距離は 9

2点の英大文字 p, q (7点のうちいずれか, p≠q）が与えられるので、点pと点qの距離を求める

解答

# 番号1
p,q=input().split()

# 番号2
point_dict = {"A":0, "B":3, "C":4, "D":8, "E":9, "F":14, "G": 23}

# 番号3
print(abs(point_dict[p]-point_dict[q]))

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

与えられている点に対して、事前に累積和を求める。各点と累積和を紐付けて、距離を求める

入力 p,q を受け取る
各点に対して、A点からの距離(累積和)を求め、各点とA点からの距離を辞書登録する
point_dictには、A点からの距離が登録されているから、引き算をすることで求めたい距離がもとまる。ただし、p, q の順番は決まっていないため、絶対値(abs)をとる

補足：別解

上記では自身で累積和を求め辞書登録しました。累積和自身を自分でやるのは、手間！間違える人もいる！(私… ) そういう場合も考え、累積和もやってもらうバージョンが下記です。

考え方

arrayに隣同士の距離を入力 (問題の転記だけなので、間違えが少ない)
＊初期位置の 0 は追加が必要です
itertoolsのaccumulate関数を使うことにより簡単に累積和を求められる（ラクです）
ord関数を用いることにより、英文字→数字可能。ただし、A: 65 になるため65を引いている

import itertools
p,q=input().split()

array = [0,3,1,4,1,5,9]
cumulative = list(itertools.accumulate(array))

print(abs(cumulative[ord(p)-65]-cumulative[ord(q)-65]))

C問題：Snuke the Cookie Picker

C – Snuke the Cookie Picker

問題(要約)

縦Hマス、横Wマスのグリッドがある。グリッド上のある縦横2マス以上の部分長方形の内部にクッキーが置かれている。すぬけ君がグリッド上のクッキーをどれか1枚を食べてしまった。すぬけ君が食べたクッキーの座標を出力する

解答

# 番号1
h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

# 番号2
hasCookie=False
lineIdentified=False

# 番号3
for i in range(h):
    cnt=0
    for j in range(w):
        if S[i][j]=="#":
            cnt+=1
    # 番号3-1
    if cnt != 0:
        if hasCookie==False:
            line=i
            countHashtags=cnt
            hasCookie=True
        # 番号3-2
        else:
            if countHashtags < cnt:
                lineIdentified=True
                break
            elif countHashtags > cnt:
                line=i
                lineIdentified=True
                break
    # 番号3-3
    if lineIdentified:
        break

# 番号4
for j in range(w):
    if line == 0:
        if (S[line+1][j]=="#" and S[line][j]=="."):
            exit(print(line+1,j+1))
    elif line == h-1:
        if (S[line-1][j]=="#" and S[line][j]=="."):
            exit(print(line+1,j+1))
    else:
        if (S[line+1][j]=="#" and S[line][j]==".") or (S[line-1][j]=="#" and S[line][j]=="."):
            exit(print(line+1,j+1))

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

行を特定してから、列を特定する探し方を採用する。

（行の特定）行毎の # の数を数え、0でなく、他の行より数が少ない列を探す。
（列の特定）その特定した行において上、または、下の行が # となっている箇所を探す

以下詳細

入力 h, w, S を受け取る。Sは内包表記を使い2次元配列で受け取る
二つの変数を定義する
- hasCookie: クッキーが存在する塊の行に到達したかどうかを確認する
- lineIdentified: ラインの特定ができたかどうか
Sの行列を一つずつ確認していき、行毎に # の数を数えcntに格納していく
1. cntの数が0でなく、hasCookieがFalseの時はクッキーの塊の初めの行になるため、下記の変数を登録する
  - クッキーのラインを登録する(line)
  - クッキーの数を登録する(countHashtags)
  - クッキーのラインに到達したため、hasCookieをTrueにする
2. 上記で登録したcountHashtagsとcntの数を都度比較する
  - countHashtags < cnt 時は、lineに登録されている行がクッキーが食べられた行
  - countHashtags > cnt 時は、現在確認している行がクッキーが食べられた行
  - クッキーの行が特定できた上記二つの条件のときは、lineIdentified=Trueとする
3. lineIdentifiedがTrueの時は、クッキーを食べられた行が特定できたため、breakでfor文を抜ける
行は特定できたため、列を検索する。1行目と最終行と他の行でサーチの仕方を変える
- 1行目の場合：2行目が # で1行目が . の場所を探す
- 最終行の場合：最終行 – 1 の行が # で、最終行が . の場所を探す
- 上記のどちらにも当てはらない場合は、自分の行の上、または、下の行が # で、特定した行が . の場所を探す
ansで足し合わせたものを出力する

補足：別解

AtCoderの解説をベースにpythonで解いてみました。

非常にスッキリしていますので、こちらをお薦めです。
（自分の解き方は苦労したのに、複雑・・・。センス必要ですね）

< 考え方 >

クッキーの塊の上下左右の位置を求める。求めた位置を再度スキャンし、 . の位置を探す。

ポイントA：上下左右の位置を格納する変数を用意。最小値 or 最大値で初期値を変えている
ポイントB：全検索する。# がある位置の最小値 or 最大値を上下左右の変数に代入する
ポイントC：求めた上下左右の位置を再度スキャンし、. がある位置を出力する

h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

# ポイントA
u,b = 501,-1
l,r = 501,-1

# ポイントB
for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            u,b=min(u,i),max(b,i)
            l,r=min(l,j),max(r,j)

# ポイントC
for i in range(u,b+1):
    for j in range(l,r+1):
        if S[i][j]==".":
            exit(print(i+1,j+1))