初めてのAtCoder
始めに
今書いているブログの内容がまだまとめることが出来ていないので、雑談で初めてAtCoderをやった感想を書こうと思います。
プログラミングの経歴
大学入学初期
プログラミングを始めたのは大学に入ってからで、それまでは"Hello, World"を表示するプログラムを体験でやってみたり、フローチャートで迷路を脱出するゲームを簡単に遊んだぐらいでした。
大学に入ってからは体験で競技プログラミング部に入って3か月ぐらいやってみたり、C言語を学習を行っていました。
競技プログラミングはやっていてとても楽しかったのですが、個人的にはプログラミングについて知りたい、ゲームを作りたいということで競技プログラミング部に行くことをやめました。
その後
その後は独学でC言語やC++を勉強したり、言語学習をしながらPaizaのプログラミング問題を解いて遊んでいました。 ただ、学部３年からUnity、C#の勉強などをし始めてからはほとんどプログラミング問題を解くことがなくなりました。
PaizaではA問題が半分解ける程度、B問題が８割ぐらいで解けるというぐらいでした。
AtCoderをするきっかけ
AtCoder自体は学部１年のころから知ってはいたものの、やっている人が周りにいなかったのでそこまで興味を持つことはありませんでした。
しかし、twitterでフォローしている方々がAtCoderについてツイートしているのを拝見して少しずつ「やってみようかな」程度になりました。
そんな中、一番モチベーションを上げたことがアルゴリズム検定。twitterで見かけて「持ってたらかっこよさそう」って思い、いずれ受けたいなと思いました。
AtCoderをなかなかできなかった理由
ということを２，３か月前から思っていました。
なんでやらなかったの？ってなりますが、
- 別のことに夢中になっていた（主にUnity）
- 一度過去問を解いて臨みたかった
- ご飯食べていた
- 寝てた
- 友達とスマブラしてた
- 忘れてた等
と以上の理由がありました。Unity以外の理由はほぼ言い訳だなって感じです。
とりあえずやってみる
少し話題がそれるかもしれませんが、基本情報技術者試験や応用情報技術者試験を受けた際に０次審査として受験会場に到着するという話題がありました。
自分の友達も受験会場に到達できなかった人もいました。
実際に調べてみたところ次のサイトを見つけました。
見てみると、結構な割合で応募はしたものの受験していない人が多いです。
自分もAtCoderで考えれば同じ状況だったので、まずはやってみるの第一段階をクリアすることを目標に臨みました。
AtCoder Beginner Contest 154 に出る
今回２月９日に行われたコンテストに出てみました。それぞれの問題の感想を簡単に書いていきます。
A問題
C++でstringを使えば行けるなってことで解きました。
stringをインクルードしなくても通るか不明なのでとりあえずインクルードして使用
B問題
C++を使うのが１０か月振りぐらいだったのでC#とこんがらがってs.lengthと書いてエラーってなり、「C++はプロパティがなくてメソッドだった！」となりました。
C問題
C++にはmapがあるなってことでmapを使って解きました。
mapの探索はlogNだったと思うので行けるかなと思い実装したらACしました。
Youtubeの解説動画をみるとsetでよかったみたいです。
D問題
まず、問題を理解するのに時間が掛かってしまった。特に「期待値」という単語に。
どんな計算をしたらこんな出力がされるんだ！？ってことで期待値について調べてみたり、自分で計算してみると１～ｐまでの和をｐで割った値が期待値となることがわかりました。
そこから、まずは何も考えずにコードを書いてみるとTLEとなりました。初めに提出したプログラムは計算量がO(N2)だったので、制約を見たところ無理だと感じ計算量をO(N)ぐらいに落とすことで解けたはずでした。
が、なぜかACされない！
なぜだ！？アルゴリズムは間違っているはずはない！私は間違ってない！と若干パニックになりました。
ただ、一度Paizaでもアルゴリズムが間違っていないのにACされない経験から小数計算の誤差が間違っていると考え対処に移りました。
結果、C言語に直して提出したらACされました。
「なんでやっ」となって調べてみるとprintfやiomanipなどを使用してちゃんと小数点を表示すると良かったみたいです。
E問題
残った時間に取り組もうと思いましたが、歯が立ちませんでした。
今思えば再起関数を使えば計算できたかもなと思いますが、それでも計算量が少し怪しいです。
F問題
ここまでこれなかった. . .
感想・反省
実際にAtCoderに出て感じたこととして
- 昔やっていたことが通じた
- C++を少し忘れている
- DPが壁
って感じです。
基本的なアルゴリズムはほとんど理解しているつもりではありますが、唯一苦手意識があるのがDPでナップザック問題ぐらいだったら理解しているけど使いこなせていないのが現状です。
今回のパフォーマンスとしては711と緑色には一歩届かずという感じなのでこれからの目標として次のことを上げます。
- C問題、D問題を確実に解けるようにする
- DPを使いこなせるようになる
- AtCoderに出場し続ける
ってことで一番達成すべきはAtCoderに出場し続けることなので、コツコツと頑張っていきたいです。
追記
自分のGithubに解いた問題をまとめていきます。 そしてプロジェクト名少しミスったなって感じてます。