「「AtCoder Beginner Contest 118」で初競プロ」で初はてぶ

Python 競プロ

初記事、初競プロです。おめでとう自分、これから頑張っていこう自分。

誰かの役に立てる記事を書いていきたいです。

高橋直大さんをフォローしたら、さっそく初心者がなんとも参加しやすそうなコンペ？が開催されるアナウンスを発見。

形式すら何も知らないがとにかくやってみるのが一番良い、と突如として初の競技プログラミングです。

atcoder.jp

それぞれ見た時は

A：これは多分いけるからイキって短く書こう

B：2つのsetオブジェクトに積集合が使えたことをぼんやり思い出す

C：出来れば偉いぞ俺、ぐらいの気持ち(汚くなりそうという直感)

D：「ちょうどN本」でヤバいと察する

みたいな第一印象でした。

A問題「-B +/- A」

  1. a, b = map(int, input().split())
  2. print(a + b if b % a == 0 else b -a)

イキって1行にif/elseのやつ書きました。全部通った時ほんとに嬉しかった。皆さんにもそんな時期があったでしょうか。

B問題「Foods Loved by Everyone」 

メモリとか速さとかはおいおい理解して磨けばいい、という気持ちで全ケース通すことを念頭に置いてました。

  • 全食べ物IDのsetを用意
  • 一人ずつ順に積集合をとっては比較元foodsを減らす更新
  • foodsの中身が無くなっちゃったらbreak
  • 最後まで残ればfoodsの長さを出力
  1. n, m = map(int, input().split())
  2. foods = set(range(1, m+1))
  3. for i in range(n):
  4. opinion = set(list(map(int, input().split()))[1:])
  5. match = foods & opinion
  6. if match:
  7. foods = match
  8. else:
  9. foods = set()
  10. break
  11. print(len(foods))

という感じです。もっと良いやり方の人を探すのも楽しみ。

のんびりやってて後で順位覗いて気づいたんですけど、出来るだけ早く出した方が良いですね。どんだけノープランで着手してるんだという気持ちになりました。

C問題「Monsters Battle Royale」

  • 同じ体力のヤツは何体いても同じなのでは？と思いまたset化を使用して重複している数値に消えてもらう
  • リストに戻して体力が小さい順にソート
  • 最大体力のヤツを2番目に大きい体力のヤツが攻撃し続けて死ぬ直前まで削れば「新しい体力値のモンスター」と見なせる
  • 要するに最大公約数か(終了後に友達の解法を聞いて気付く)
  1. num_monster = int(input())
  2. hplist = sorted(list(set(map(int, input().split()))))
  3. if not hplist:
  4. print(0)
  5. while len(hplist) != 1:
  6. new_hp = hplist[-1] % hplist[-2]
  7. del hplist[-1]
  8. if new_hp != 0:
  9. hplist.append(new_hp)
  10. hplist = list(set(hplist))
  11. hplist.sort()
  12. print(hplist[0])

TLEって何？

→時間オーバー！？

→制限2秒！？

→どこがどのくらいかかってるの？？？

という無知初心者丸出しムーブをしました。6つのケースで引っかかってるのを発見ついでに評価のされ方、見方を知りました。事前準備のしてなさが出ました。

今後は良いアルゴリズムと関数の動作速度とかを勉強しないといけませんね。動作してる速度感が全くイメージできずうーんと他のアプローチを考えてたら終了しました。

D問題「Match Matching」

良い問題(タイトルが)。

  • 桁数バカバカ増やすのがいい？
  • 使い切る組み合わせを探索する？
  • そもそも設定をよく読んでない(反省)

こういうときってとりあえずいくつかなら通りそうなコードを何か書いて送っといた方がいいのでしょうか...？

感想

競プロめちゃくちゃ楽しい。