mery's Notes

めりーがプログラミングしたりします。

MENU

AtCoder Beginner Contest (ABC) 224 Pythonで参戦しました。 A,B,C三完 解説あり

前回参加したやつ

mery-kirokudayo.hateblo.jp

f:id:mery_poke:20211101224140p:plain

こんにちは。めりーです。

本日のAtCoder Beginner Contest (ABC) 224に参加しました。
A、B、C問題を30分ちょっとで解けたので十分では無いでしょうか。

今回は数学的な問題が多かった印象がありました。
とくにB問題は問題を理解するのに特に時間がかかってしまいました。
iとjの選び方に何かの規則性があるのか?と探してしまいましたが、特に何も規則性がなさそうだったという落ちに・・・。

というわけで解説もしていきます。

言語はPython、提出はPyPyです。

目次

A問題

問題文

A - Tires

与えられた文字列の末尾が「er」か「ist」かを判別する問題。
また、与えられる文字列の末尾は「er」もしくは「ist」のどちらかである。
という問題。

こういう問題がA問題っぽいなーって思いながら解いてました。
コンテストに参戦するのが久しぶりなのと、過去問はC問題しかやってなかったので、A問題を見るのも久しぶり。
このサクッと解ける加減がA問題の魅力だなぁと実感。

というわけで方針を。
1. インプットする
2. 末尾がrかtかをチェック
3. 出力する

以上である。

というわけで、実際のコードがこちら。

s = input()

if s[-1] == "r":
    print("er")
else:
    print("ist")

input関数で入力を受け付ける。
入力の末尾をs[-1]で引き出す。
末尾がrとtの場合で場合分け。
それぞれで出力して終了。

今回は末尾がerとlistしかないので他の条件はチェックしなくて良いので楽ですね。

B問題

問題文

B - Mongeness

個人的に1番手こずった問題。

マス目が与えられて各マスには1つの数字が入っている。
マス目が条件を満たすかどうか判別せよ、との問題。

何が手こずったかって、条件の規則性。
何かしらショートカットできそうな規則性があったせいで、全探索ではなくショートカットを追ってしまった。無念。
その数字より下の数字とか右の数字とかと比較したら計算量抑えられるかなーって思ったけど、そんなことをわざわざしなくても、B問題なんだし、愚直に全探索すれば問題無いことを思い出す。
別に隠された規則性とか探らなくていいもんね。

問題の解き方としては、B問題らしく、計算量とか考えず、全探索で問題なし。

それでは方針を。
1. i1を決める。
2. それに伴い、i2の範囲が決まるので、範囲内でi2を決める。
3. j1を決める。
4. それに伴い、j1の範囲が決まるので、範囲内でj1を決める。
5. 各場合において、条件を満たすかチェック。
6. 条件が全て満たされているかによって出力を変化。

実装はこちら。

h,w = map(int,input().split())
a = []
for i in range(h):
    A = list(map(int,input().split()))
    a.append(A)

flg = True

for i1 in range(h-1):
    for i2 in range(i1,h):
        for j1 in range(w-1):
            for j2 in range(j1,w):
                if a[i1][j1] + a[i2][j2] > a[i2][j1] + a[i1][j2]:
                    flg = False
                    break
            if flg == False:
                break
        if flg == False:
            break
    if flg == False:
        break

if flg:
    print("Yes")
else:
    print("No")

このコードを見てキモいと思っただろうか。
安心してほしい。僕もキモいと思う。
アルゴリズムの問題で4重ループって・・・。

ポイントだけ解説を。

i1の範囲の上限がh-1なのは、

  • 1 <= i 1 < i2 <= h

という条件があるため。
i1がhと同じ値を取ると、i2がh+1を取ることになって上限突破しちゃうからね。
これはj1の範囲の上限も同様。

変数flgで条件が満たされているかどうかをチェックしている。
条件が満たされなかった場合はflgをFalseにし、ループを終了
している。
計算時間の節約だね。

C問題

問題文

C - Triangle?

点を3つ選んで直線で結ぶ。
それが三角形になる組み合わせは全部で何通り?という問題。

入力例1がめっちゃ親切に画像まで用意してくれててありがたいね。
めっちゃいいヒントになったね。

Nの範囲が300までと狭いので、全探索が余裕で間に合いそうですね。

また、逆に三角形にならないパターンがどのようなパターンかを考えると全探索して、そのパターンのみ弾けるので楽だね。

三角形にならないパターンは入力例1の点「1、2、4」を見て貰えれば分かる通り、3点が1直線上にある時
あれ、高校数学の軌跡の問題で似たようなことをやった覚えが・・・

というわけで方針を。
1. 全探索する。
2. ループ回数を記録。
3. ただし、三角形じゃない時 = 1直線上にある時は記録しない。
4. 記録した回数を出力

というわけで実際のコードを。

n = int(input())
x = []
y = []
for i in range(n):
    X,Y = map(int,input().split())
    x.append(X)
    y.append(Y)

ans = 0

for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if (y[k] - y[i])*(x[j]-x[i]) != (y[j]-y[i])*(x[k]-x[i]):
                ans += 1

print(ans)

このコードを見てキモいと思っただろうか。
安心し(ry

再び現れました。多重ループ君。今度は三重です。

同じ点を2回数えないように、i < j < kという条件をつけました
これがないと、「1,2,4」と「1,4,2」を別々に数えてしまうのです

そして、問題はおそらく1直線上にあるかどうか判別するためのif文
if (y[k] - y[i])*(x[j]-x[i]) != (y[j]-y[i])*(x[k]-x[i]):
これでやっていることは、高校数学。
ただの2点を通る直線の方程式の変形である。
公式を覚えてない人は調べてね。僕も調べた
ただ、元の公式では割り算があるため、割り算の無い形に変形したのである。
※割り算で小数が出ると予期しない計算結果になる可能性があるのでエラーの源。

という感じで3問正解しました。
目標のC問題まで正解できたため、とりあえずは上々かな、と。
D問題チラッと見たけどエグかったです。

それでは。