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

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

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

A - Round decimals

今回のA問題は「やや難」です。
普段のA問題はもっと簡単なので、今回解けなかった人も落ち込まずに競技プログラミングを続けてください。

まずXを文字列として受け取ります。

次に少数第1位の数字を確認しますが、前から何番目にあるかはわかりません。
後ろから数えれば必ず3番目の文字となりますから、後ろから3番目の文字を確認します。
後ろから3番目の文字は
X[-3]
として確認できます。これをsyousu1としましょう。

次にsyousu1を整数へ変換します。文字列のままだと0～4なのか、5~9なのか判定しづらいからです。
整数への変換はint(変数)とします。すなわち
int(syousu1)
とすればsyousu1を整数へ変換できます。

次に整数部分の取り出しです。小数点「.」の手前までの数字を確認するという方法もありますが、少々めんどくさいです。
一旦少数にしてから整数に変換する方法を取りましょう。

まず少数へ変換します。少数への変換はfloat(変数)とします。
float(X)
これでXを文字列から少数へ変換できました。

次に整数へ変換します。少数→整数へ変換すると小数点以下の値は切り捨てられます。
int(X)

最後に小数第1位の数が0~4か、それ以外(5~9)かで条件分岐します。
少数第1位が0~4なら
→Xを出力
それ以外(5~9)なら
→(X+1)を出力

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

【提出】

# 文字列として受け取り
X=input()

# 少数第1位
# 後ろから3つ目の数字
syousu1=X[-3]
# 整数へ変換
syousu1=int(syousu1)

# 整数部分の取り出し
# Xを文字列→少数へ変換
X=float(X)
# intで整数へ変換(小数点以下は切り捨てられる)
seisu=int(X)

# 少数第1位が0～4だったら
if 0<=syousu1<=4:
    # 整数部分を出力
    print(seisu)
# そうでなければ(少数第1位が5～9だったら)
else:
    # 整数部分＋1を出力
    print(seisu+1)

B - Counting Arrays

入力を受け取り、ひとつひとつ重複がないか確認する方法は制約が大きすぎてTLEします。
「リスト」ではなく重複した要素が入らない「セット」を使いましょう。

セットを作るときは
変数=set()
と書きます。

要素を追加するときは
変数.add(要素)
とします。リストは同じ要素が入ることはありません。
すなわち追加しようとした要素がすでにセットへ入っていれば、二重に要素が追加されることはなく無視されます。

この問題では要素として数列を追加していくわけですが、リストはセットへ追加できません。
代わりにタプルならセットへ追加ができます。
タプルはリストに近いですが、リストと違い、要素の変更ができないという特徴があります。
詳しくは以下のページをご覧ください。

タプルへ変換するときは
tuple(リスト)
と書きます。

あとはセットへ追加されたものがいくつあるかを出力すればOKです。

【提出】

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

# 数列格納用セット
# セットは重複したものが入らない
seq=set()

# N回
for i in range(N):
    # 入力の受け取り
    tmp=list(map(int,input().split()))
    # 先頭(0番目の要素)はL
    L=tmp[0]
    # 1番目～の要素はa
    a=tmp[1:]
    # aをタプルへ変換(listはsetへ追加できない)
    a=tuple(a)
    # seqへ追加
    seq.add(a)

# seqの中身の数を出力
print(len(seq))

C - Martial artist

技Nを覚えるために必要な技から、覚えるために必要な技を順にたどって必要な技を確認します。
最後に必要な技全てを覚えるために必要な時間を計算します。

例として以下のような入力を考えましょう。
5
1 0
2 0
3 1 2
4 1 2
5 2 4 3

すなわち以下のようになっています。

N=5
i1 T=1 K=0
i2 T=2 K=0
i3 T=3 K=1 A=2
i4 T=4 K=1 A=2
i5 T=5 K=2 A=4,3

まずキューを用意します。(que)
※キューがわからない人は下部に記載の「dequeについて」を確認してください。
次に習得する技リストを用意します(learn　learn[x]=Trueなら技xを習得する、Falseなら不要)

キューにNを追加します。
Nを習得する技としてリストを更新します。(learn[N]=True)

以下の手順をキューが空になるまで繰り返します。
(1)キューの左端から要素を取り出す。(waza)
(2)取り出した要素を習得するために必要な技を順に確認する。
　・必要な技がまだ習得する技リストに入っていなければ(learn[waza]＝False)
　　習得する技リストを更新(learn[waza]=True)
　　キューへ格納

実際にやってみましょう。

まずはキューを用意します。
que：(空)

習得する技リストを作ります。
waza=[False,False,False,False,False,False]

キューにN=⑤を追加します
que：⑤

習得する技リストを更新します。
waza=[False,False,False,False,False,True]

(1)キューの左端から要素を取り出す。(waza)
que：⑤
なので⑤を取り出します。

(2)取り出した要素を習得するために必要な技を順に確認する。
技⑤を習得するのに必要なのは技③,④です。
learn[3]=False,learn[4]=Falseなので、これらをTrueに更新します。
さらにキューへ③,④を格納します。
que：③,④
learn=[False,False,False,True,True,True]

(1)キューの左端から要素を取り出す。(waza)
que：③,④
なので③を取り出します。

(2)取り出した要素を習得するために必要な技を順に確認する。
技③を習得するのに必要なのは技②です。
learn[2]=Falseなので、これらをTrueに更新します。
さらにキューへ②を格納します。
que：④,②
learn=[False,False,True,True,True,True]

(1)キューの左端から要素を取り出す。(waza)
que：④,②
なので④を取り出します。

(2)取り出した要素を習得するために必要な技を順に確認する。
技④を習得するのに必要なのは技②です。
ですがlearn[2]=Trueなので技②はすでに習得する技として記録されています。
他に必要な技はないのでキューに追加するものはありません。
que：②
learn=[False,False,True,True,True,True]

(1)キューの左端から要素を取り出す。(waza)
que：②
なので②を取り出します。

(2)取り出した要素を習得するために必要な技を順に確認する。
技②を習得するのに必要な技はありません。
que：(空)
learn=[False,False,True,True,True,True]

ここでキューが空になりました。
あとはlearnの要素を順に確認し、Trueになっているものだけ習得に必要な時間を確認して足し算します。
今Trueになっているのは②,③,④,⑤なので、
2+3+4+5=14
答えは14となります。

実装の際は以下のことに気をつけましょう。
・1インデックスで受け取りするため、T,Aの先頭に0などてきとうなものを入れておきます。
・入力はリストで受け取り、0番目の要素をT、1番目の要素をK、2番目以降をAとします。K=0ならAにダミーとして「-1」などてきとうなものをいれましょう。

dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
import：from collections import deque
作成：変数名=deque()
末尾に要素追加 O(1)：変数名.append(要素)
先頭から要素を取り出して削除 O(1)：変数名.popleft()
【使用例】

# インポート
from collections import deque

# 作成：変数名=deque()
que=deque()

# 末尾に要素追加 O(1)：変数名.append(要素)
que.append(1)

# 先頭から要素を取り出して削除 O(1)：変数名.popleft()
x=que.popleft()

詳しく知りたい人は以下のページを見てください。

【提出】

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

# T,Aの受け取りリスト
T=[0]
A=[[0]]

# N回
for i in range(N):
    # リストで受け取り
    tmp=list(map(int,input().split()))
    # 0番目の要素がT
    T.append(tmp[0])
    # 1番目の要素がK
    K=tmp[1]
    # 0<Kならば
    if 0<K:
        # 2番目以降の要素がA
        a_list=tmp[2:]
        # Aに格納
        A.append(a_list)
    # そうでなければ(K=0)
    else:
        # ダミーとして-1を格納
        A.append([-1])

# キューを用意
from collections import deque
que=deque()

# 習得する必要がある技を管理
# Trueなら習得する
learn=[False]*(N+1)

# キューにNを追加
que.append(N)
# Nは習得する→learn[N]
learn[N]=True

# キューが空になるまで→キューの長さが0でなければ
while 0<len(que):
    # キューから取り出す
    waza=que.popleft()
    # wazaを学ぶために必要な技
    for x in A[waza]:
        # ダミーだったら
        if x==-1:
            # ループを抜ける
            break
        # まだ習得する技リストに入っていなければ
        # learn[x]がFalseならば
        if learn[x]==False:
            # キューに追加
            que.append(x)
            # learn[x]をTrueに
            learn[x]=True

# 答えの計算用
ans=0

# 1～Nまで
for i in range(1,N+1):
    # 習得する技なら
    if learn[i]==True:
        # T[i]時間かかる
        # 答えにT[i]を追加
        ans+=T[i]

# 答えを出力
print(ans)

D - Teleportation

座標で考える問題は必ず紙に図を描いて考えましょう。

例として街の座標が以下の4つだった場合で考えましょう。便宜上、A,B,C,Dと名前をつけています。

A(1,1)
B(2,2)
C(-1,2)
D(4,4)

Aからそれぞれの街へ移動するためにいくつ魔法が必要か考えましょう。
例えばA→Bは魔法(1,1)で移動することができます。
これは(Bのx座標-Aのx座標,Bのy座標-Aのy座標)と計算できます。

同様に計算するとA→Cは魔法(-2,1)となります。
A→Dは魔法(3,3)となりますが、A→Bで覚えた魔法(1,1)を繰り返し使えばたどり着くことができますので、この魔法は不要です。

ここまで考えるとAからの方向、つまり傾きが同じであれば同じ魔法でたどり着けるということがわかります。
BとDはAからの方向が同じであるため同じ魔法でいいわけです。

傾きというと「(yの増加量)/(xの増加量)」を思い出しますが割ってしまうと「向きの情報がなくなる」＋「少数なので誤差が出る可能性がある」ため失敗します。
向きの情報とは例えばB'(0,0)のような点があった時、(B'のx座標-Aのx座標,B'のy座標-Aのy座標)=(-1,-1)となりますが-1/-1=1となってしまい、傾きの情報がプラスになってしまうということです。これではBとB'は同じ魔法でいけるとみなされてしまいます。

そういうわけで
魔法(a,b)=(xの増加量,yの増加量)=(「ゴール地点」のx座標-「スタート地点」のx座標,「ゴール地点」のy座標-「スタート地点」のy座標)と計算した情報をそのまま保持
かつ
同じ方向(例えば魔法(1,1)と魔法(3,3))を同じ魔法とみなす
ということが必要です。

これは約分に近い考え方をして、(a,b)の最大公約数dでa,bを割ってあげればよいです。

例えば(3,3)の場合、3と3の最大公約数は「3」なのでa,b=3,3を3で割ります。
(3,3)→(1,1)
確かにBへ移動する魔法と一致しました。

このように最大公約数で割ったものを覚える魔法として記録していきます。
最大公約数を求めるにはmathライブラリのgcdを使います。
from math import gcd
と書いて
gcd(x,y)
とすればx,yの最大公約数が計算できます。

重複した魔法はいらないのでセットへタプルを使って記録していけばよいです。
タプルについて詳しくは以下のページをご覧ください。

あとは全ての街の組をスタート地点とゴール地点として計算し、最後に覚える魔法の数を出力すればよいです。

【提出】

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

# 座標の格納リスト
points=[]

# 覚える魔法のセット
magic=set()

# N回
for i in range(N):
    # 入力の受け取り
    x,y=map(int,input().split())
    # 座標を格納
    points.append([x,y])

# 最大公約数の計算用
from math import gcd

# start=0~N-1
for start in range(N):
    # goal=0~N-1
    for goal in range(N):
        # start=goal(スタートとゴールが同じ街なら)
        if start==goal:
            # 次の点へ
            continue
        
        # スタートのx座標
        x_start=points[start][0]
        # スタートのy座標
        y_start=points[start][1]
        # ゴールのx座標
        x_goal=points[goal][0]
        # ゴールのy座標
        y_goal=points[goal][1]

        # xの増加量
        x_inc=x_goal-x_start
        # yの増加量
        y_inc=y_goal-y_start
        # (xの増加量)と(yの増加量)の最大公約数
        d=gcd(x_inc,y_inc)

        # 最大公約数で割る
        x_inc//=d
        y_inc//=d

        # 魔法に追加
        magic.add(tuple([x_inc,y_inc]))

# 魔法の個数を出力
print(len(magic))

【広告】

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

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

【booth(pdf)】

1～24問目まではサンプルとして無料公開しています

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

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

サンプルを5問分公開しています

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

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

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

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

サンプルとして「準備」～「三目並べ」を無料公開しています。

【kindle】

【booth(pdf】