Arc's Laboratory

プログラミングとかの研究室

AtCoder Beginner Contest(ABC) 082 レビュー

今回は12/16のAtCoder Beginner Contest (ABC)についてです。

今回が初参戦となります。

僕のAtCoderのアカウントはこちらです。

問題はAtCoder公式をご参照ください。

A - Round Up the Mean

int型の割り算は小数点以下切り捨てなので、a+bに1足してから2で割れば切り上げた平均値が出てくる。

なぜか僕は(a+b)%2の値を見てから処理していましたが。

B - Two Anagrams

Cしか触ったことのなかった身にとっては、C++の ちからって すげー! と思った問題。

stringコンテナのs,tを用意して文字列を代入し、sort(s.begin(),s.end()); sort(t.begin(),t.end(),greater<char>());を実行する。

すると、sの中身は昇順、tの中身は降順にソートされる。

で、if(s<t)trueならYes、falseならNoを出力。

ソートアルゴリズム書く必要もなし。strcmp使わなくてOK。そう、C++ならね

C - Good Sequence

数字nがm回出現したとき、

-n>mならm個消す

-n<mなら`m-n'個消す

というのを、全てのnに対して確認する。

この時、数字nが何回出てきたかをカウントする配列count[]が必要になってくる。

しかし、count[]の長さは普通に考えると109必要。メモリ足りない。

そこで、数列の長さNが105以下に制限されていることに注目。

105を超える数字nはn回以上出るわけがない。つまり、常にn>mを満たす。

ということで、105を超える数字が出てきたら無条件で消すことにする。

そうすれば、105以上の数字をカウントする必要がなくなるので、count[]の長さは105で十分。計算量はO(N)で解ける。

……模範解答は連想配列使ってましたね。研究が必要そうです。

D- FT Robot

最初は深さ優先探索して、その後メモ化したんですが、向き情報をDPの情報に入れていなかったので撃沈。タイムオーバー。

しかも、この方法ですらTLEになるらしい。O(N3)ならそこそこ速くない……?

x軸方向の移動とy軸方向の動きを分離すればO{N2}で解けるそう。

最初の提出時にデバッグ用のprintfを貼りっぱなしにしていたのは秘密。

まとめ

今回はstringの書式確認やらDPの凡ミスやら、時間の無駄遣いをしすぎました。

次回は変なミスしないようにします。