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

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

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

A - Tires

文字列の末尾が「r」ならば「er」、「t」ならば「ist」を出力します。
末尾はS[-1](後ろから1番目の文字)とすることで確認できます。
あとはif文で条件を確認すればOKです。

「Yes」「No」は文字列なので出力の際、"Yes","No"とダブルクオーテーションをつけてください。

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

【提出】

# 入力を受け取る
S=input()

# 末尾の文字が「r」ならば
# 末尾はS[-1]で確認できる
if S[-1]=="r":
    # 「er」を出力
    print("er")
# そうでなければ(末尾の文字が「t」ならば)
else:
    # 「ist」を出力
    print("ist")

B - Mongeness

(i1,i2,j1,j2)の全ての組について条件を満たしているか確認します。

すべての組を確認する解法でよいか？の判断は制約をみて行います。
2≤H,W≤50ですから、仮にH,Wが最大サイズの50でも組み合わせの数は50^4=6250000組(=だいたい10^6)より小さいことがわかります。
※実際には1500625組です。

pythonは実行制限時間である2sec(2秒)の間にだいたい10^6回くらいの計算ならできるため間に合います。

次にどうやって全ての組を確認するか考えましょう。
以下のように実装すればOKです。

# i1=1~H-1まで
for i1 in range(H):
    # i2=i1+1~H-1まで
    for i2 in range(i1+1,H):
        # j1=1~W-1まで
        for j1 in range(W):
            # j2=j1+1~W-1まで
            for j2 in range(j1+1,W):

これで(i1,i2,j1,j2)の全ての組を順に処理することができます。
処理内容を具体的に説明します。
まずi1=0,1,2,...H-1が入ります。
※問題文ではi1=1,2,3,...,Hですが、0インデックスで受け取るため、番号が一つずれています。すなわち一番上から0行目、1行目、...という数え方をしています。
次にi2です。
i2は
for i2 in range(i1+1,H):
なのでi1+1から始まります。
i1=0 → i2=1,2,3,...H-1
i1=1 → i2=2,3,4,...H-1
...
i1=H-2 → i2=H-1
となります。
i1=H-1のとき、i2にはなにも入らず、処理されません。(スルーします)

j1,j2も同様の処理がなされ、結果として全ての組が確認できます。
試しにprintで(i1,i2,j1,j2)を出力して確認してみましょう。(例としてH,W=3としています)

H=3
W=3
for i1 in range(H):
    for i2 in range(i1+1,H):
        for j1 in range(W):
            for j2 in range(j1+1,W):
                print(i1,i2,j1,j2)

「出力結果」(i1,i2,j1,j2)
0 1 0 1
0 1 0 2
0 1 1 2
0 2 0 1
0 2 0 2
0 2 1 2
1 2 0 1
1 2 0 2
1 2 1 2

たしかにいい感じに9組作れています。

あとはそれぞれの組について条件を満たしているか確認します。
一つでも条件を満たさないものがあれば「No」を出力します。

条件を満たさないとは
A[i1][j1]+A[i2][j2]>A[i2][j1]+A[i1][j2]
となっている組があるということです。

この場合は「No」を出力→途中終了という処理にしておきます。
途中で終了するにはexit()と書きます。

【提出】

# 入力を受け取る
H,W=map(int, input().split())

# Aを受け取るリスト
A=[]

# H回受け取り
for i in range(H):
    # i行目の受け取り
    h=list(map(int, input().split()))
    # リストへ格納
    A.append(h)

# i1=0~H-1まで
for i1 in range(H):
    # i2=i1+1~H-1まで
    for i2 in range(i1+1,H):
        # j1=0~W-1まで
        for j1 in range(W):
            # j2=j1+1~W-1まで
            for j2 in range(j1+1,W):
                # 条件を満たさないならば
                if A[i1][j1]+A[i2][j2]>A[i2][j1]+A[i1][j2]:
                    # 「No」を出力
                    print("No")
                    # 終了
                    exit()

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

C - Triangle?

この問題は
ABC181 C：https://atcoder.jp/contests/abc181/tasks/abc181_c
の類題です。
この問題が解けなかった人は解説を読んでACできたら、ABC181 Cも解いてみて
・きちんと理解できているか
・自力で実装ができるか
試してみることをおすすめします。
なお、ABC181 Cの解説は「AtCoder　凡人が『緑』になるための精選50問詳細解説」でかなり丁寧に記載しています。
サンプルとして解説内容を無料公開しておりますので、そちらもぜひご覧ください。
https://qiita.com/sano192/items/d4aba1192a81cf736eae

「正の面積をもつ」ということは「三角形ができている」ということです。
逆に「正の面積をもたない」場合は「三角形ができていない」すなわち「3点が同一直線上にある」ということを意味します。

ゆえに3点の組み合わせ全てについて
「三角形ができている」⇔「3点が同一直線上にない」
ものがいくつあるかを確認します。

3点を(x1,y1),(x2,y2),(x3,y3)としたとき、「同一直線上にない」という条件は以下です。
(y3-y1)(x2-x1)≠(y2-y1)(x3-x1)

なぜ上記の式で判断できるか簡単に説明します。
3点(x1,y1),(x2,y2),(x3,y3)が「同一直線上にある」場合はどうなるか考えましょう。
まず2点(x1,y1),(x2,y2)を通る直線は以下の方程式で表されます。

これを変形します。

この直線の上に(x3,y3)があれば「同一直線上にある」と言えます。
つまり(x,y)=(x3,y3)として等号が成り立つということです。

これが3点が「同一直線上にある」条件なので、逆に等号が成り立たない場合は「3点が同一直線上にない」と判断できます。
※厳密に言うと最初の式で0除算が発生する可能性があるのでこの変形は完璧に正しいわけではないですが、最後の式は「同一直線上にある」という条件としては正しいものになっています。

あとは3重ループで全組確認すればOKです。

pythonだと間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 入力を受け取る
N=int(input())

# 座標の受け取りリスト
points=[]

# N回受け取り
for i in range(N):
    # X,Yを受け取り
    X,Y=map(int, input().split())
    # 座標をリストへ追加
    points.append([X,Y])

# 点の組を数える変数
count=0

# i=0~N-1まで
for i in range(N):
    # j=i+1~N-1まで
    for j in range(i+1,N):
        # k=j+1~N-1まで
        for k in range(j+1,N):
            # 座標を変数へ
            x1,y1=points[i][0],points[i][1]
            x2,y2=points[j][0],points[j][1]
            x3,y3=points[k][0],points[k][1]

            # 同一直線上になければ
            if (y3-y1)*(x2-x1)!=(y2-y1)*(x3-x1):
                # カウントする
                count+=1

# 答えの出力
print(count)

【広告】

『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】