NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

AtCoderでの競技プログラミングがもっと楽しくなるサイトまとめ

この記事は情報系を勉強する女子大生 Advent Calender 2017の16日目の記事です.

qiita.com

16日目担当のNoiminです.

情報系学科の学部4年で,自然言語処理の研究室に所属しています(自然言語処理は本アドベントカレンダーでもasai0304さんが取り上げてくださっていますね). 去年から趣味として競技プログラミングをかじっています.実力はまだまだですが楽しくやっています.

今日はその競技プログラミングを話題にしたいと思います.

競技プログラミング/AtCoderとは

一言で言うと競技プログラミング(略して競プロ)とは,与えられた問題に対するプログラムを早く正確に書くことを競うものです.プログラミング自体の知識はもちろん,アルゴリズムやデータ構造,数学の知識技能などを活用して問題を解きます.

例えば,こんな問題が出題されます.

問題文(AtCoder Beginner Contest 080 A - Parking)

駐車場があり、以下の二種類のプランのどちらかを選んで駐車できます。

プラン 1: T 時間駐車した場合、A×T円が駐車料金となる。 プラン 2: 駐車した時間に関わらず B円が駐車料金となる。

N時間駐車するとき、駐車料金は最小でいくらになるか求めてください。

制約

"{

"{

"{

入力

入力は以下の形式で標準入力から与えられる。

N A B(半角スペース区切り)

出力

駐車料金が最小で x 円のとき、x を出力せよ。

この要件を満たすアルゴリズムを考えて,プログラムを作成します.例えばPython3なら,以下のように書けるかと思います.

n,a,b = map(int, input().split())
print(min([a*n, b]))

この問題は初心者向けコンテストの1番最初の問題ですが,徐々に難しい問題が解けるようになっていくのがとても楽しいです.

競技プログラミングのコンテストはオンライン上でもオフライン上でも開催されていますが,最も手軽に参加できるのはAtCoder社の主催するオンラインコンテストAtCoder Beginner Contestだと思います.AtCoder Beginner Contest(略してABC)は初心者向けのコンテストで,毎週土曜日(たまに日曜日)21:00から開催されています.また,競技プログラミングのコンテストが開催されるサイトはTopCoderCodeforcesなど英語のサイトも多く,当然問題文も英語ですが,AtCoderは日本語で問題文を読むことができるので日本人がとても参加しやすいです.

この辺りの話はku-muさんのブログ記事がとても詳しく説明しているので,気になる方はku-muさんのブログ記事も読んでみてください. (補足: 競技プログラミングというと普通はku-muさんの以下の記事でいう「アルゴリズムのコンテスト」で出題されるようなものを指します) cocodrips.hateblo.jp

さて,AtCoderのコンテストに出てみると,こんな気持ちになってきます.

  • もっと難しい問題が解けるようになりたい
  • もっとレーティング(その人の実力を表す数値.レートと言うことも.これまでに参加したコンテストの結果から計算される)を上げたい
  • もっとたくさんの問題を楽しみたい!

そうなると,AtCoderや他のコンテストの過去問などなどたくさんの問題を解きつつ週末はコンテストに出る,という競プロer(※競技プログラミングをやる人)としての生活が始まるわけです🎉

この記事を読んでいる方の中には,もうとっくに競プロライフを送っている人や,最近競プロにはまった人もいるかもしれませんね.

AtCoderやその他コンテストサイトには,それらのサイトで競技プログラミングを楽しんでいる有志が作った,精進(※競プロerは競プロの上達に務めることをこう言う)に役立つサイトがたくさんあります.

それらのサイトを,AtCoderの過去問やデータを使ったものを中心に紹介していこうというのが今回の記事の趣旨です.

前置きが長くなりましたが,早速紹介します!

各サイト紹介

AtCoder Problems

http://kenkoooo.com/atcoder/

AtCoder Problems(β版)

作者: @kenkooooさん

AtCoderの過去問を解きたい時にはこれ! と言われるくらいの定番サイト.

AtCoderで開催されたコンテストの問題を一覧することができます.

上部のフォームに自分のAtCoder IDを入れるとすでに正解した問題と提出はしたけど不正解だった問題が色分けされて便利です. ユーザページでは,AtCoderの問題の連続正解日数や今までに解いた問題の数などが表示され,モチベーションの維持にもなります.

さらに,最近公開されたβ版には様々な機能が追加されています.

f:id:noimin:20171216004859p:plain

AtCoder Scores

AtCoder Scores

作者: @Yazatenさん(原案), @rsk0315_h4xさん(大枠の作成), @_TTJR_さん(デザイン)

こちらはAtCoderの重み付き配点ありのコンテストの問題を配点順に並べたサイトです.

私は現在このサイトを利用して400〜600点の問題を解いて青コーダー(レート1600以上)を目指しています. 初心者の方はこちらのサイトで各問題の配点を調べて100点の問題から順に解いていくのもいいかも.

こちらのサイトも正解済みの問題の色分けがありますが,使用されているAPIの仕様変更に対応するため,現在改修中とのこと. (配点による問題の並べ替えや指定の配点の問題の表示等には影響ありません) (12/25追記: 新APIに対応し,正解済みの問題の色分けが復活したようです!(改修ありがとうございます!) さらに便利な新機能も……?)

f:id:noimin:20171216030014p:plain

AtCoder Rating Estimator

AtCoder Rating Estimator

作者: @kobae964さん

改良版: AtCoder Rating Estimator

作者: @beet_aizuさん

現在のレーティング,これまでの参加回数と目標レーティングから,自分が次のコンテストで取るべきパフォーマンス(1回1回のコンテストでどれだけ良い成績を取れたかを示す値.これまで参加したコンテスト全ての結果から計算されるレーティングとは区別される)の値がわかります.

私はよくコンテスト直前に自分に必要なパフォーマンス値をこのサイトで確認して士気を高めています.

f:id:noimin:20171216031020p:plain

2018/07/16追記 作者の@kobae964さんから@beet_aizuさん作の改良版の存在を教えていただきました! 改良版ではAtCoder IDと目標レーティングの入力だけでより気軽に必要パフォーマンスの確認・ツイートができます (スクリーンショット参照).

f:id:noimin:20180716225954p:plain

AtCoderRatingGraphComparison

AtCoderRatingGraphComparison

作者: @koyumeishi_さん

2人のユーザの間でのレーティングの遷移やコンテストの戦歴の比較ができます.

私は近いレーティングの人と自分の成績を比較して「負けないぞ!」とか「お互い頑張りましょう!」とか一人で叫んでいます.

画像ではAtCoder社社長のchokudaiさんとの比較です笑

f:id:noimin:20171216031810p:plain

AtCoder Stats

AtCoder Stats

作者: @koyumeishi_さん

AtCoderのコンテスト,問題,ユーザに関する様々な統計情報が閲覧できます.この記事を書くために上記サイトのことを調べている過程で知ったサイトですが,とても便利で驚きました.

スクリーンショットを掲載した日本の,レーティング変化のあるコンテストに10回以上参加したユーザの中でのNoiminの位置なんてものは,AtCoder Statsで見られる情報のごくごく一部にすぎません.「ある問題について,どのレート帯の人がどれくらいの時間で正解しているのか?」など,痒い所に手が届きまくっています.

f:id:noimin:20171216032404p:plain

Rating History

Rating History

作者: @beet_aizuさん

TopCoderCodeforcesAtCoder,AOJ,yukicoderのレーティング遷移及び今までに解いた問題数がわかります.特に,この5つのサイトの中で複数のサイトのコンテストに参加している方には便利なサイトだと思います.

競プロerは「〇〇までにn問解く!」というモチベーションを持っていることも多いので,複数のサイトで解いた問題の合計数がわかるのは嬉しいです.

2019/02/16追記: 移転されていたようです.移転先のURLに更新しました.

f:id:noimin:20180324184546p:plain

AtCoder Finder

http://atcoder-finder.com/

作者: @Ymgch_Kさん

AtCoderの問題を,問題分類のタグごとに探せるサイトです.なんとタグ付けは自動で行なっている模様. 特定の種類の問題について集中的に精進して得意分野を作りたいときや,特定のアルゴリズムを勉強した後に演習用の問題を探す際に便利です.

f:id:noimin:20180324184618p:plain

AtCoder Rating Comparison

AtCoder Rating Comparison

作者: @wk1080idさん

指定したユーザ間でAtCoderのレーティング遷移や最新のレーティグを比較できるサイトです. 似た実力のライバル間や学校などでの友人間の比較をしてみると面白いと思います. 画像ではchokudaiさんと私の比較になっていますが,3人以上のユーザの比較も可能なのが便利です.

f:id:noimin:20180610162656p:plain

f:id:noimin:20180610162703p:plain

ac-predictor

webページ版: ac-predictor

ブラウザ拡張機能版: ac-predictor

作者: @kymn_さん

AtCoderのコンテストにおける順位,パフォーマンス,レート変化の相互変換がサイト / ブラウザ拡張機能です. 私含むレート更新が待ちきれないみなさんにお勧めです.

なんとwebページ版とブラウザ拡張機能版の両方が提供されています. webページ版は順位表式にパフォーマンスやレート変化が見られるので,いろいろな参加者の成績を眺めるのに良いです. ブラウザ拡張機能版はコンテストの順位表からすぐにパフォーマンスやレート変化が確認でき,さらにtwitterへの投稿も可能なので,コンテスト後にtwitterでワイワイするのに便利です.

webページ版 f:id:noimin:20180716230411p:plain

ブラウザ拡張機能f:id:noimin:20180716230807p:plain

AtCoder Performances

旧バージョン AtCoder Performances

新バージョン AtCoder Performances

作者: @noisy_noimin, fuurin

最後の最後で手前味噌ですが,AtCoderのレーティングではなくパフォーマンスをグラフ化するサイトを作りました.

パフォーマンスはコンテスト1回1回の成績に対応する値なので,グラフが比較的過激に上下します.パフォーマンスの平均値,最大・最小値などをTwitterでつぶやくこともできます.

動作がとても重い&ソースコードがひどいので,春休みあたり改修できたらいいなぁと思っています.

2018/07/19追記: 新バージョンが完成しました! fuurinくんの力を借りまくって旧Ver. にはない機能を色々と追加したので新バージョンもよろしくお願いします!

新機能例

  • グラフ画像付きツイート
  • グラフ・表にする対象コンテストの期間の範囲の指定
  • 4人までのライバルとの比較

f:id:noimin:20180719164047p:plain

まとめ

みなさん,楽しい競プロライフを!

明日のICPCアジアつくば大会に出場される方,応援してます!

情報系を勉強する女子大生 Advent Calender 2017,明日はasai0304さんの「Word2Vecモデルを作る② 基本のNeural Networkを式からpythonで実装してみる」です.自然言語処理を専門としながらもNeural Networkに苦手意識を持っている身としても楽しみです!

サイト作者の皆様へ: お手数ですが,情報に誤りがあるor自分のサイトが掲載されてない!or自分のサイトは掲載しないでくれなどありましたら@noisy_noiminまでご一報ください.