部内勉強会（１）
概要
競技プログラミング勉強会をしました
勉強会の目標は参加者が半年で緑になること．全員緑というのはそこそこレベルが高いので多分無理そう（？）
コンテスト参加回数を稼げないときついので、緑パフォ出せたらOKとします．
今回は第１回ということで各種コンテストサイトの紹介とAtCoderのアカウント作成，AtCoder Virtual Contestのアカウント作成を行い、実際にバーチャルコンテストをして参加者の能力を測定してみました．
40分７問でABCのA B B C C D E（は？）
もうちょっとレベル低めでもよかったかなと思います
各種コンテストサイトの紹介
日本語のものは
-
毎週コンテストを開催している．日本最大手．講習会の問題は基本的にAtCoderから引用します．
yukicoder
有志で運営されているコンテストサイト．問題数が多いので勉強する際に便利です．
AOJ
同じく日本語のコンテストサイト．教育コンテンツが充実しているなぁという印象．大きなコンテストで使用されることもある
海外のものは
-
世界最大手．競技時間が深夜なのでこどふぉに出ると生活が破綻する
-
世界的に有名．過疎化が進んでいる．上位陣はほんとに強い
LeetCode
企業のコーディング試験問題が無断転載されているサイト．違法．UIはきれい．面接対策に使われる．
などなど
各種サービスの紹介
AtCoder Scores
自分のレートと勉強量を可視化できる．綺麗
AtCoder Virtual Contest
コンテスト形式で練習ができる．今日の勉強会でもしようするのでアカウントを作ってください
AtCoder Ploblems
AtCoderの過去問が整理されているサイト．それぞれの問題の難易度が分かるため、自分に合った問題を解くことができる．
これらの３つのサイトは勉強の際によく使うことになるのでブックマークすることをお勧めします
ACpredictor
コンテストのパフォーマンスとレート変動を予測してくれます．コンテストに出る前に絶対入れましょう．
proxyにはじかれるようです…
コンテストやってみよう
今回取り組む問題はこれ
解説の時間もあるので40分でバチャります
なるべくDifficultyが単調増加になるように選びました
だいぶやりすぎた感がある
解説
Tenki
文字列を比較してあっている数をカウントします
簡単な問題はPythonで実装すると楽です
Kagami-mochi
種類数を見てやりましょう
バケットを使って重複を消すかsetでかんりすると楽です．
Buffet
Bは順番に関係なく得られるのであらかじめ足しておきます
Cを足すかどうか判定して足してあげればいいです
Otoshidama
全探索することを考えます
愚直に実装するとO(N3)なので間に合いませんが最後のループは一意なのでO(N2)にできます
GCD on Blackboard
GCDはユークリッド互除法で得られます．
GCDは順番に関係ないので双方から前計算しておくと求められます．
Digits Parade
全探索するには間に合いません．全探索を効率的に行うためにDPをします
DP[i][j]=i桁目で余りがjとして計算していきましょう
Hopscotch Addict
BFSをしてあげるとよさそうです
各頂点ごとに一回目で到達、二回目で到達、三回目で到達の状態があるので3*n頂点考えてBFSすると解けます．
