Contents
概要
どうも、只今転職活動中のれいです。
とある企業でコーディング試験を受けたところ、「お前プログラミング出来ないから無理〜ｗ」と落とされました。(※丁重にお祈りされました)
は？プログラミングできるしｗｗふざけんなしｗｗｗ
とりあえず間近にあるAtCoder Beginner Contest受けて証明したるしｗｗｗｗ
🙄 🙄 🙄 🙄 🙄 🙄 🙄 🙄
プログラミングできましぇ〜〜〜ん
ということで、真面目にプログラミングとアルゴリズムの勉強をはじめました。
反省
まず、初回ABCでやって悪かったなって思ったことを書いておきます。
ええ、つまり言いワケしておきます。
慣れない言語を使った
競プロといったらC++といった安直な発想でC++を使いました。
が、ROSや組み込みでC++を触った程度なので、クラスに関する理解は多少あってもSTLに対する知識が圧倒的に不足してました。
そもそも、C++だからって意味もなくvectorを使ったりしてのも馬鹿ですね…はい。
ブランク
ABCを受けてみて気付いたのですが、そもそも腕が鈍っていました。
新卒で現職に就いて2年間、まともにコーディングできる業務についていなかったですからね…(2年で4桁行くらいしか書いてないのでは…)
3年前の学生時代にARC, AGCに興味本位で出た事があったのですが、その際はアルゴリズムについてノー勉でもマシな結果を残していました。
(人口が少なかったので今より高いレートが出やすかっただけかもしれませんし、そもそもアルゴリズムを知らない時点で結果については信用出来ないですが…)
2年間プログラミングする機会が極端に減っただけで、ここまで書けなくなるとは…
Keep programmingは正しかった！
開発環境が不十分だった
- Mac + Eclipse + GCCで受験したけどコンテナの中身が見れない！デバッグできない！！
- デバッグうまく開始できなくてEclipse何度も再起動しないといけない
試験受けながらキレてました(ちゃんと準備してから受験しましょう)
知識不足
これについてはもう言い訳のしようもないですね。
(試験内容については触れられないのでこれ以上何も書けません)
その後、やったこと
ムカついたんでとりあえず「青コーダー」なるものになってみようと思いました。
開発環境構築
デバッグできないのはあまりに問題が大きすぎるので、デバッグ環境を整えました。
やったことは↓の別記事を参照。
C++に慣れる
とりあえず初めはC++に慣れるために、ABC過去問をA問題から解きました。
分からないところは、解説や他人のacceptされた提出を見ることによってC++(というかSTL)の機能を知りました。
最近のABCの解説pdfは初心者に対してはやや丁寧さに欠けるので、ABC125以前の問題を解くことをオススメします。
はじめに最低限使えるべき内容
- long long (intじゃ足りないことも多々あるので、64bit型を使いましょう)
- cin / cout
- vector (sortとか探索、2重のvectorを満足に扱えること)
sortはラムダ式等で任意にソートできるようになりましょう。
茶・緑色になるのに要る内容
- map
- pair : Ai, Biの順序を保ったままソートするときに必要
- tuple : Ai, Bi, Ciの…(略)
水色？
- priority_queue
- queue
- stack
その他(優先度は低め)
- multimap
- unordered_map
後はbinary_search, lower_boundとかでしょうか。
上記内容を知っていれば、とりあえずなんとかなります。
ググりながら過去問を解いて、各機能を知りましょう。
理論・アルゴリズムを知る
「1000000007 で割ったあまり」系の問題
過去問を解いていたら、「nCkを求めたいけど割り算が必要になるけど剰余演算した後の値に割り算できないよなぁ…」って絶対なります。
この手の問題は解放を知らないと絶対解けません。覚えましょう。
(ちなみに逆元を用いれば解けます。)
ついでにnCkの演算用ライブラリについても見ておきましょう。
組み合わせ問題も頻出ですし、必ず必要になります。
ただライブラリをコピペするだけじゃなく、内部の実装を知っておきましょう。
素因数分解
最大公約数や素因数分解、約数の個数等を用いる問題がよく出ます。
動的計画法
D, E問題では最頻出ではないでしょうか。
一般的な動的計画法と桁DPについて覚えておきましょう。
桁DPについては以下ページがとてもわかり易いです。
また、Almost Everywhere Zero (ABC154)のサンプルコードを別途載せておきました。
コメントを多めに記述しているので、理解しやすいかと思います。
https://spiralray.sakura.ne.jp/blog/cp/dp/digit-dp
その他アルゴリズム
よく使うのはこれくらいでしょうか。
- 尺取 (しゃくとり)法
- Segment Tree
- Union-Find木
- 二分探索
ABCのD問題まででは、グラフの問題はなかなか出てこない気がします。
ワーシャルフロイドやダイクストラについては最近勉強し始めました。
青コーダーになるには必須知識ですね。
結果
とりあえず水色コーダーになれました。
勉強した成果がパフォーマンスに現れて、気持ちいいですね…！
初のF完や黄色相当のパフォーマンスを出せたりで興奮も…！
青コーダーになるために…
コーディングに慣れるため、ひたすら過去問解いてます。
AtCoder Problemsで大体の難易度を確認しながら、A問題から順番に解いて行くことでタイピング・早解き力の練習をしています。
配列のカッコとか、普通のタイピング練習アプリでは使わない箇所の練習ってどうやればいいんですかね？
アルゴリズムについては、今は「蟻本」購入し勉強中です。
最後に
コーディング試験に落ちたという割とネガティブな理由からですが、競技プログラミングの世界の楽しみ方を少し知ることが出来た気がします。
私はロボット(特に組み込み)のプログラミングしかしてこなかった為、アルゴリズムに対する学習モチベーションは今まで高くなかったのが正直なところでした。
ですが、知らないと高速化のアイデア自体が出てこないから必要ないと思いこんでいただけ。勉強した内容を使える機会はいくらでもあったのかもしれないなって思いました。
引き続き青コーダーを目指して頑張って行きたいと思います！
え、えーーーっと…とりあえず転職先募集中です！！！
ロボットと電子工作とプログラミング！
女の子は甘いもので出来てる?