devgenjin77’s blog

AtCoder Beginner Contest 179 参加記

AtCoder 競プロ ABC

2020/9/19に開催されたAtCoder Beginner Contest 179に参加しました。

前回は2完を喰らってしまったので、今回はそのリベンジとばかりに気合を入れて臨みました。

AtCoder Beginner Contest 179 - AtCoder https://t.co/hZZp2jTxFG
参加します。前回2完だったんで今回は少なくとも3完以上目指します。
— devgenjin77 (@devgenjin77) 2020年9月19日

今回の結果

で、肝心の結果ですが、今回も2完終了となりました。ヽ(`Д´)ﾉｳﾜｰﾝ

ABC179結果

灰色パフォーマンスでレーティングは大幅下げ。灰色落ちの危機を向かえそうです。

devgenjin77さんのAtCoder Beginner Contest 179での成績：6367位
パフォーマンス：271相当
レーティング：570→537 (-33) :(#AtCoder #ABC179 https://t.co/559EiRyUf4
2完終了で大幅マイナスを喰らいました😭
灰色落ちしないよう頑張ります。
— devgenjin77 (@devgenjin77) 2020年9月19日

振り返り

ABC179提出結果

A問題

A - Plural Form

文字列の末尾で処理を分岐する問題。Javaだとs.endsWith("s")で分岐すればよい。

問題なくAC。

B問題

ループ処理だが、言われたとおり実装するだけ。問題なくAC。

C問題

この問題でやらかしてしまった。。

$A \times B + C = N$ を満たす正整数の組 $(A,B,C)$ の数を求める問題。

$A \times B \lt N$ となる $A,B$ を決めれば、 $C$ は一意に求まる。なので、 $1$ から $N - 1$ までの $X$ について、それぞれ何通りの $A \times B$ で表すことができるかの組み合わせの数を足し合わせればいいやと考えました。

しかし、ここからが結構厄介で、 $X$ が素数の場合とか、平方数の場合とか、素因数分解したときに同じ素数が複数入ってる場合など色々考えしまい、混乱してしまいました。

で、結局いろいろライブラリなどを使ってこねくり回したものの、結局サンプルすら通らないので退散。。

この問題、後日よくよく考えたら、 $A$ を $1$ から $N - 1$ のそれぞれについて、

$A \times B \lt N$ となる $B$ の数、すなわち $floor((N - 1)/A)$ の値を足し合わせれば答えになることに気付きました。

これだと、この問題が灰色diffなのも納得がいきますね。

D問題

D - Leaping Tak

早々にC問題を諦めて、Dに取り組むことに。

この問題、色々考察するも、結局愚直に各区間のDPを行うやり方しか思いつかない。

なので、とりあえずサンプルが通る実装を行い、多分ダメかなーとおもいつつも提出したら、やはりダメ。結局TLEを喰らってしまいました。

解説をみると、DP高速化が必要とのことで、まだ色々勉強が足らないと思いました。

これを機会に覚えることにします。

E問題

E - Sequence Sum

C,Dが散々な出来なので、コンテスト中はチラッとしかみれませんでした。

コンテスト後のTLで周期性なるキーワードが出て解法がわかったので、後日ACしておきました。

F問題

F - Simplified Reversi

これもコンテスト中はチラッとしかみてませんでした。

ま、後日解説ACでもすることにします。

これまでの実績

うかうかしてると、冗談抜きで灰色落ちしそうです。。

コンテスト実績

総括

実力不足を思い知らされる結果が続きますが、これを乗り越えるには日々精進をつづけていくしかないですね。

次回も懲りずに頑張ります。