AtCoder Beginner Contest 177 参加ログ・感想

ABまでできた。Bが案外難しかった。Cは勘違いしてた。Cは単純に累積和を別リストにもって頭から順番に足していけばいいだけだったのに過去問にひきづられて困惑。DはUnion-Find（実装したことなく、無理だった）。本番弱いなぁ。

---

内容

• Python3でやっている。
• 参加ログ。
• 所感。
• コンテスト中に何を考えたか。
• コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
• 問題の詳細で細かく書こうと思うものは別記事とする。
• E以上はとりあえず現状自力では無理なのでDまで。解けるようになってきたら更新するかも

---

結果

Aは割り算の値の大小比較。Bは検索対象側を検索ワードの幅で固定して、スライディングウィンドウしていくイメージ。ここに気づくのにめちゃ時間をかけてしまった。Cは愚直にやると無理なので先に計算しておくべき和を計算するんだけど問題を勘違いして終了。DはUnion-Findっていうのを使うんだろうなーとおもいつつ、実装したことなくて手をつけられず。BFSでもできそう。

---

どう考えたか + α

A - Don't be late

問題タイプ：条件分岐

をで割って、t以下かどうかでif文で分岐すればいい。

d, t, s = map(int, input().split())
if d / s <= t:
    print('Yes')
else:
    print('No')

---

B - B - Substring

問題タイプ：部分文字列探索

結構難しい。Pythonでは文字列がitereableなので、文字列として読み込む。をでスキャンしていくイメージ。の頭から、の長さ分文字列をとって、それがのそれぞれの文字列と異なる箇所があったら、カウントする。というのをのなかで、と同じ長さ取得できるところまでチェックして、最小のカウントが答え。

B - Substring：Sの頭からTをスキャンしていくイメージ

S = input()
T = input()
minv = len(T)
cnt = 0
if T in S:
    print(0)
    exit()
else:
    for i in range(len(S)-len(T)+1):
        for s, t in zip(S[i:len(T)+i], T):
            if s != t:
                cnt += 1
        minv = min(minv, cnt)
        cnt = 0
print(minv)

---

C - Sum of product of pairs

問題タイプ：mod・累積和

パターンの掛け算の和のmodを計算する。愚直に全て計算すればでTLEなので、累積和を使って工夫する。これは別記事にする。

追記：

blacktanktop.hatenablog.com

---

D - Friends

問題タイプ：グラフ・BFS（幅優先探索）・Union-Find

グラフの問題。パッと見るとUnion-Findらしいが、実装はしたことなかったので、これを機会に実装をチャレンジした。また、おわってからBFSならスムーズにできる事がわかった。別記事にする。

追記

blacktanktop.hatenablog.com

E - Coprime

問題タイプ：素数・素因数分解 当然ここまで行ってないが、素数の列挙さえ高速にできれば、できそうな問題。挑戦してみたい。

---

おわりに

当面の目標は、ABC完答できればDまでということで、ABで終了。Cは先週と同じく線形探索（順番に見ていくだけ）と累積和に気づけず。あとから悶絶。Cはこのパターンが多い。一度しかなめないでやるにはどういう工夫が必要かを落ち着いて考えればさっといけるようになるはず。

---