"AtCoder Beginner Contest 120" で3完でした

Python 競プロ

予定があって先週のABCに参加出来なかった悔しさも込めて、今日はC問題まで頑張るぞという気持ちで2回目のAtCoderにチャレンジしました。

atcoder.jp


初見の感想は

A：chokudaiさん音フェチなんですね(適当)

B：公倍数ってどうやって列挙するんだ？？？

C：ひたすら0と1の境目を探して2箱取った回数を数えればいける...！？(後にTLEで突き返される)

D：(そっ閉じ)

という感じでした。我ながら何の参考にもなりません。

あとのんびりと一旦全問題眺めちゃうの多分ダメですよね。昔から一分一秒を争うような場所が好きじゃないので本当に仕方ないです。コードのきれいさ、ひらめき、アルゴリズム力などを磨いていくことにします。

 A：Favorite Sound

問題設定の突飛さに時間を食われた印象があります...。

・持ってるお金B円で満足するC回まで音を聞ける時

・C回聞くにはお金が足りず(B//A)回の時

の2パターンしかないので、二つの値のうち小さい方を表示します。

  1. a, b, c = map(int, input().split())
  2. print(min(b//a, c))

B：K-th Common Divisor

前回の初競プロ初TLEの反省から、計算量オーダーの記事を少しだけ読んでいました。マジで良かったので載せておきます。Qiitaと先人ホントにありがとう。

参考記事：

qiita.com

qiita.com

そしてAもBも100までというめちゃくちゃ小さいオーダー？だと気づいた瞬間、やり方もコードも汚なくていいから早めに提出しようと判断できました。少し成長でしょうか...？

・小さい方の数字の約数をfor文で(贅沢に)探す

・それらをデカい順に大きい方の数字に対して割ってみて、K番目に割り切れたものをprintする

という流れです。

  1. a, b, k = map(int, input().split())
  2. a, b = min(a, b), max(a, b)
  3.  
  4. lst = []
  5. for i in range(1, a+1):
  6. if a % i == 0:
  7. lst.append(i)
  8. lst.sort(reverse=True)
  9. cnt = 0
  10. for num in lst:
  11. if b % num == 0:
  12. cnt += 1
  13. if cnt == k:
  14. print(num)
  15. break

絶対もっといい書き方ありますね。

C：Unification

最初は

・0と1が両方あることを確認する

・i文字目とi+1文字目が違うとき、カウントして文字列から取る(スライスで新しい文字列にしてしまう)

という操作を繰り返すコードにしました。

  1. s = input()
  2. cnt = 0
  3. while '0' in s and '1' in s:
  4. for i in range(len(s)):
  5. if s[i] != s[i+1]:
  6. cnt += 1
  7. s = s[:i] + s[i+2:]
  8. break
  9.  
  10. print(cnt * 2)

 

(案の定)6つのケースでTLEとなりました。

他人事のように「whileの条件判定がいちいち大変そうだなぁ」とか思いつつ悩んでいたのですが、ふと「どんな並びであろうがどんな順番で取り出そうが、0か1のどちらかの箱が完全に無くなるまで取り出し可能なのでは...？」というひらめきが訪れます。

残り15分までこれに気付かない自分の鈍感さとゆったりジュース飲んでた気の抜けようを反省しつつ、大急ぎで下のコードを書き提出しました。

  1. s = list(input())
  2.  
  3. zerocnt = s.count('0')
  4. onecnt = len(s) - zerocnt
  5. if zerocnt <= onecnt:
  6. print(zerocnt * 2)
  7. else:
  8. print(onecnt * 2)

 

無事AC！

通った時マジで嬉しいのでこれからも一人前の競プロer(？)になるべく精進します。

D：Decayed Bridges

(図を描いてみて)話は分かった、難しそうだ(C問題が通って満足している)(これをもう書き始めている)

感想など

今回のC問題の難易度は置いといて、2回目にして3完を達成できてめちゃくちゃ喜んでいます。ひらめくまでにほぼ無駄な再提出で3回もTLEを出してしまいましたが...。

先日paizaでも(時間かかったけど)Aランクまで上がれたので、ABCでのA問題、B問題は多分解くことはできるんだと思います。ということで前半2問では今後、キレイで無駄のないコードを目指していきたいですね。

またC問題をある程度確実に取れることと、D問題も解けて全完達成することを次の目標にします。少し急ぎすぎでしょうか...。

 

昨日まんまと蟻本を買ったので研究の合間に少しずつ習得していきたいです。欲を言えばC++も...。

もっと全力でやれよって自分でも思いますが、気負わないのを最優先でいきたいのでご了承ください(？)