【AtCoder】AtCoder Beginner Contest 214 (A~C) 参戦記

AtCoder Beginer Contest 214に出場した

3ヶ月ぶりに復活して初めてのコンテスト

知らない間に問題数が8問になってるし,とうとう200超えたんだね

結果

順位:8405人中2621位

得点:600点

ペナルティ付き最終解答時間:33:11

パフォーマンス:931

※()内の数字はWAの回数

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 1:16
B 200点 0 4:24
C 300点 0 33:11
D 400点 - -
E 500点 - -
F 600点 - -

レート変化

916→917 (+1)

もうすぐ1000だ

f:id:monhime:20210815083131j:plain:w400

f:id:monhime:20210815083128j:plain:w400

解答

A Repeat ACL

A - New Generation ABC

問題要約

ABCコンテストは1回目から125回目までは4問,126回目から211回目までは6問,212回目から214回目までは8問だった。N回目のABCコンテストにおいて出題された問題数を答えよ。

解答

やるだけ

コードを見る(クリックして下さい)

ABC214_A

 

Submission #25016903 - AtCoder Beginner Contest 214

B Integer Preference

B - How many?

問題要約

$ a + b + c \leq S $ かつ $ a * b * c \leq T $ を満たす非負整数の組 $ (a, b, c) $ はいくつあるか

制約

$ 0 \leq S \leq 100$

$ 0 \leq T \leq 10000$

$S, T $は整数

解答

$S, T$ の制約から,$ 0 \leq a, b, c \leq 100$で全探索しても,軽い処理の$ 10^6 $ループなのでギリ間に合う。

ちょっと不安なので,bとcはこれ以上増やしても意味がないところでbreakした

コードを見る(クリックして下さい)

ABC214_B

 

Submission #25023556 - AtCoder Beginner Contest 214

C Connect Cities

C - Distribution

問題要約

$ N$ 人のすぬけ君が円周上に並んでおり,反時計回りに$ 1,\,2,\,...,\,N $の番号がついている。$ i\,(1\leq i \leq N)$ 番目のすぬけ君は時刻$ t$ に宝石をもらうと$ S_i $ 単位時間後,すなわち$ t + S_i $ にその宝石を$ (i +1) $ 番目のすぬけ君にわたす。ただし,$ (N +1) $ 番目のすぬけ君とは1番目のすぬけ君を指す。また,高橋君は時刻$ T_i $に$ i$ 番目のすぬけ君に宝石を渡す。全ての$ i\,(1\leq i \leq N) $ について,$ i $番目のすぬけ君が初めて宝石をもらう時刻を求めよ。

制約

$ 1 \leq N \leq 200000$

$ 1 \leq S_i,\,T_i \leq 10^9 $

入力は全て整数

解法

$ N $が大きい。$ O(n) $ or $ O(n\log n) $ 解法を考える。

初めて宝石をもらう時,それが「高橋くんからもらう石」か「$ i - 1 $番目のすぬけ君からもらう石」かの2通りがある。

1番目のすぬけ君がもらう石からスタートし,仮の解答$X_i$ を,$ X_{i + 1} = \min\{X_i + S_i,\,T_i\}$と記録していく。

この記録は2周すれば十分である。

最小要素からスタートすれば一周が必要十分となるが,最小要素を探すのに$ O(n) $かかるし,愚直に2周してもたいして変わらないんじゃないかな。

解答

コードを見る(クリックして下さい)

ABC214_C

 

Submission #25023556 - AtCoder Beginner Contest 214

感想

復帰戦となったが,レーティングは保てたし悪くはなかった。

今回のコンテストのD問題は水diffで,解けなくても大丈夫な問題だったので運が良かったかな?

ここで緑diffが来たら解けたか怪しかった。


難しい問題を解けるかどうかの前に,解ける問題を確実に素早く解く力が必要

しばらくの間はAtCoder ProblemsのVirtual Contestのあさかつ/くじかつに毎回参加しよう

今まで変に水diffに挑戦して解けなくて,実戦力が落ちてパフォ下がって辞めている

今度こそは継続したいなぁ