プログラミング初心者がAtCoderに挑戦してみたお話。【その7】

スポンサーリンク
あ プログラミング

こんにちは。じんせーです。

今回は11/9(土)に行われた、第二回全国統一プログラミング王決定戦予選参加記となります。

いつものABC(AtCoder Beginner Contest)とは違って、今回は企業主催のコンテストみたいです。
形式としてはARC(AtCoder Regular Contest)に相当する難易度の模様。
僕はARC出たことないので、ARC級コンテストとしては初参加です。

ちなみに前回の記事はこちら。↓


気になった方は見てみて下さい

さて、果たして今回の結果は…!?

スポンサーリンク

結果

にっけい

順位:1499位/3477人中
パフォーマンス:1082(緑色)
レート:677

うーん、なんとも言えない結果に。。
緑パフォなので大事故にはならずに済んで良かったです。

A問題(100点)とB問題(300点)の2完だったんですが、
B問題3回TLEを食らったために、ペナルティ+15分と余計な思考時間を+15分ほど上乗せする羽目になりました。

この問題は大まかに

「距離ごとに要素数を記録する(距離1のものがa個、距離2のものがb個…)」

「『距離iの要素数を距離i+1の要素数乗』したものを「1≦i≦最大距離-1」について求め、全てかけ合わせる」

という感じの解法になります。

このうち前者のプロセスについて、
僕は「for文を最大距離数回分だけ回し、それぞれの距離で該当する要素がいくつあるか数えるためにcountメソッドを使う」という方法をとってしまいました。

この方法をとると計算量がO(N^2)となってしまい、
10^10個すなわち最大100億個のデータを計算しなければならず制限時間内に間に合いません。

3回TLE提出をした後にそれに気づき、
慌てて「取りうる距離数の配列を作り、n個の要素それぞれについて距離を調べ、先程作った配列のうち該当する距離を+=1する」方法に変えてなんとかACしました。。

そんな感じで、今回の最大の反省点は
「日頃問題を解く時、計算量について無頓着だった」
ために、コードを書いている途中で良くない解法をとっている事に気づかなかった点です。。

スポンサーリンク

次への抱負

特に何も変わらず、過去問の水色レベルの問題をちょくちょく解いていこうと思います。

…という無味乾燥な感想になってしまいましたが、
来週以降もブログを見に来て頂けたら幸いです。。m(_ _)m

【追記】
続きの記事を書きました!

プログラミング初心者がAtCoderに挑戦してみたお話。【その8】
こんにちは。じんせーです。 最近寒くなってきましたね。新しい暖房が欲しいです。 今回は11/16(土)に行われた...

こちらも是非ご覧ください。

コメント

  1. […] […]

  2. […] こんにちは!じんせーです。 前回のAtCoder記事からだいぶ時間が空いてしまいましたが、 … プログラミング初心者がAtCoderに挑戦してみたお話。【その7】 […]

タイトルとURLをコピーしました