34. AtCoderに初参加した

先日から苦戦していたリモートデスクトップ設定ですが、結局VPNサーバを立てるのは諦めて、普通にリモートデスクトップできるようにしました。ただ、ポート番号そのままは流石に怖いので、最低限のセキュリティとして適当なものに変えておきました。これで様子を見てみます。

さて、今日は AtCoder に初参加しました。

競技プログラミングは高校時代以来で、あの頃と比べると界隈のレベルもとんでもなく上がっています。とりあえず練習ページで提出までの流れは確認しましたが、どのような問題が出るのかロクに確認もせず、ほぼ大会初見という感じで挑んでみました。

ビギナー向けの ABC (AtCode Beginner Contest) というものでしたが、普通に難しかったですね。ABCE完答、Dは一部テストケースで時間切れになる不正解、FGExは問題を見る時間が無かった、という結果でした。

各問題の感想です。

A

書かれている通りに実装すれば良いだけの問題でした。
何故か綺麗なコードを書こうとして、無駄に時間を取ってしまいました。あんまり慎重すぎるのも良くないですね。

B

計算量削減がいるかな？と思いましたが、制約的に行けそうだったので愚直な実装で通しました。全然問題なかったです。

C

少し考えると、2進数に書き換えて1を2に変換するだけの問題だと気付きました。似たような問題を高校時代に解いた覚えが…。

D

計算量が問題になる系かな…と思っていましたが案の定そうでした。
最初の提出は普通に非効率だったので、もう少し考えて、「新しく得られた数が小さければ前回の結果から変わらない」「大きければ、前回まででソート済みの配列から入れるべき場所を見つけて、一番小さいやつを追い出して突っ込む」みたいな処理にしたのですが、（少し改善しましたが）これでも時間切れでした。うーん？まぁ解説を読んで勉強します。

と、解説を読むと考え方は合っていて、最後の一手が足りていませんでした。「前回までソート済みの配列から入れるべき場所を見つける」という処理が線形探索だったのですが、ここを改善すれば良かったようです。

実はこの改善点は気付いていた（二分探索すればもっと速くなると気付いていた）のですが、実装の重さと残り時間を考えて試すまでに至りませんでした。解説的には「優先度付きキュー」を利用すれば良かったようです。ああ、そんなデータ構造もあったな…。

E

各位の数にバラして1桁目と2桁目であるべき差を見ます。先頭桁から順番にスキャンして、非等差な箇所があればその桁を +1 して以降は 0 にします。+1 した結果その桁の数が 10 になったら、繰り上げ計算のような処理を入れます。

…という感じの実装にしました。もっと良い方法がありそうな気もしますが、時間が無かったので思いついたものを愚直に実装しました。運良くバグらず通せました。

F, G, Ex

時間無くて見てないです。

反省点としては、「簡単な問題に時間を掛けすぎない」「綺麗なコードを書こうとしすぎない」「沼ってる問題を引きずらない」というところでしょうか。

しかし、上位勢のタイムを見るととても同じ人間とは思えなかったですね…。純粋にすごい。