はじめに
最近なぜか競プロ系のツイートがタイムラインに流れてくるので、ちょっとその世界の端っこを覗いてみることに。
DISCLAIMER: これは感想文です。競技プログラミングについては、ためになる記事が他にたくさんあるのでそちらをご覧ください
プログラミング系サイト
ざっと調べてみたところ結構あるみたい。
-
AOJ
- 大学系のコンテストサイトっぽい
-
AtCoder
- コンテスト系サイト。日本では一番有名？
-
LeetCode
- グローバルで一番有名か。過去問集みたいな感じ。GAFAなどの実際の面接にだされた問題もあるとかないとか
-
HackerRank
- デベロッパと企業のマッチングサイト。コード書いてアピールするタイプっぽい
-
CodeChef
- ぱっと見、コンテスト系サイト
-
exercism
- 好きな言語選んで、コード提出したらメンターがみてくれる感じの学習サイト
- CodeWars
英語には抵抗ないので、 。LeetCodeやろうとしたのだが、回答をどう書けばいいのかわかりにくくて、結局 Atcoder にする
2019/12/22 - LeetCode やってみたらこっちの方が遥かにUIはいいし、わかりやすい。今後はLeetCode にすると思う。英語に抵抗なければこっちをおすすめ。
自分なりの遊び方
- 全問を
rubyとgoで書き比べてみたら面白いかも。解きやすさや、解答のスコア（メモリ量や速度）をみてみるのは面白いかも。goの勉強にもなるだろう（あとでやってみる） - テストを書きながらやってもいいかも
AtCoder
Atcoderはいろいろと丁寧なガイドがある
- AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
- こんなガイドのようなものまで発見
- 標準入力から値受けとって標準出力から結果をだす形式なので、どう書くかはわかりやすい。
-
Rubyのバージョンは2.3しか選べない
AtCoder Beginners Selection
解答
ここに解答。まだ ruby だけ。
Welcome to AtCoder
特に書くことがない
Product
特に書くことがない
Placing Marbles
特に書くことがない
Shift only
特に書くことがない
Coin
順列組み合わせ的な数学的手法できれいに解こうとするが失敗。単純に三重ループをぶん回すほうがよいというオチ
Some Sums
array.sum が2.3では実装されていないところでちとハマったが、それ以外は簡単
Card Game
文字列を delete で値で消すと、マッチする部分が全て消えるので、delete_at を使う。このためにary.index する。計算回数を無闇に増やさないしないようにしたいところ
Kagami Mochi
uniq 使えば一行でかける。もちの個数 N は使わなくても解ける
Otoshidama
各お札の枚数の組み合わせをつくるのに少し時間かかった。あと「複数の可能性が考えられるときは、そのうちどれを出力してもよい」という条件なのでテストがいままでと書き方変わる。
Daydream
- このあたりから面白くなってくる
-
Sから配列の文字列を消していって、最終的にSがなくなるかどうかかという判定をすることにした -
Tを考えるときに、前方一致でやると S =dreameraserは T =dreamとdreamerに一致してしまう。前者は次にeraserを持ってくることで S = T つまりYESとなるが、後者の場合はNOになってしまう。つまり最初のマッチだけでなく、マッチした全て（dreamとdreamer）をTの候補としてあつかうことになるので、分岐が増えてうまくない -
1≦|S|≦105なので入力する文字はめっちゃ長いことがありえる。下手すると制限時間内（2sec）に終わらない（ここで、解けるのに時間がオーバ... となる） - どうやら、前方一致ではなく、後方一致するといいようだ（後ろからマッチしていくと上記のようなことはなく候補は一意に決まる）
- 後方一致で書いてみるものの、それでも制限時間オーバ
TLE (Time Limit Exceeded)をくらう - 後方一致してその部分を消すときの正規表現が遅い
gsub!(/word$/, '')と気付き、予め文字の長さを整数を渡して、文字を消すときには正規表現を使わずにslice!(x..y)で削除することで、全テストをパス（2s以上が100msへ） - あとで気づくのが、消していく順番さえ間違えなければ
Sに対する全置換gsub!だけで対応でき、3行くらいのコードで書ける。OMG...
Traveling
このあたりになると、まず計算量のオーダが気になるようになる。この問題で正攻法で N 回動いた場合に到達する点を列挙とかやると、N が 10^5 までありえるので、死ぬことがすぐにわかる。
総評
それなりに楽しみながら解くことができました。
スタックしたと思ったら
なんでうまくいかないんだ... となったら
- 提出したコードのジャッジステータスはここ。回答が間違えているのか、時間かかりすぎているのか
- 公式コンテストのテストケースはここ。一部のテストケースだけこける場合もどんなケースでこけるのか確認できそう。
- ググればいっぱい回答が出てくくるのでスタックはしないはず。
参考にさせていただいたサイト
競技プログラミング系のサイトをググるとGoogle入社の話につながっていく法則を発見した。
感想文
- ああ、みんなこんなふうにプログラミングを楽しんでいるのね
- この Beginners Selection、いい感じの問題が揃っている印象
- 🐜本とか、🐅本とか、🌀本とかで基礎をやり直したくなる
- 競プロは数学じゃない。問題を数学的に綺麗に解こうとせず、ループぶん回して解決する方がいいものもある
- アイデアをコードにするのはやっぱり面白い
- やっぱり
rubyの書きやすさは、ぱんぱねぇ - 今回のやつを
goでも書いてみる - 普段はメタレイヤの業務で死んでいるが、プログラミングは今後も暇をみつけてやるぜ
- 開始時間指定のコンテストじゃなくて、空き時間にコツコツ問題といてスコア上げていく系のがやりたい