NoiminのNoise

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

はじめての Codeforces 前編 (参加登録〜コンテスト本番)

最近 Codeforces (通称: こどふぉ) に初めて参加する方が AtCoder との違いや参加の仕方に戸惑っているのをよく見たので,少しでも日本人競プロer から見たこどふぉの敷居を下げられるように本記事を書くことにしました.Codeforces に興味がない人に興味を持たせるというより,すでに興味持っている人を後押しする狙いの記事です.主に,Twitter のタイムラインで見かけたこどふぉについての疑問を元に構成しています.

もし,本記事に記載していないことでわからない・わかりにくい点がありましたらご質問ください.また,すでに何回かコンテストに参加している方にとっては当たり前のことばかりかと思います.もし間違い等を発見しましたらご指摘いただければ幸いです.

予想外に長くなってしまったので,前編と後編に分けることにしました.

前編となる今回はコンテストへの参加登録からコンテスト本番での動きについて紹介したいと思います.コンテスト種別,Hack,プレテストとシステムテストといった話題について扱います.後編では,復習の仕方やユーザページの使い方,おまけとして CF-predictor という有名なツールについて紹介する予定です.

(2019/10/20 Hack の説明で,不要なネタバレ要素や同じ Room の人のユーザネームが隠れていない画像が含まれていたので画像の差し替えを行いました)

(2020/2/4 コンテスト開始時の挙動の説明をより正確に・コード長制限に言及)

目次

0. Codeforces とは

f:id:noimin:20191014142238p:plain
Codeforces のトップページ (ログイン前)

ロシア発祥のプログラミングコンテストサイト.ロシア語版と英語版があります.

2時間〜2時間半くらいのコンテストを週に何度かやっています.開催頻度高め.

開始時間は日によって違いますが,日本時間でいうと 23:35〜や 0:35〜が多め.多くの日本人には少し厳しい時間帯です.このことから,18:35〜や 22:35〜といった日本人に優しい時間に開催されるコンテストは「人権こどふぉ」と呼ばれることも.

問題の難易度は if 文・for文が書ければ解けるような易しいものから上位の人たちが凌ぎを削るような難しいものまで様々.出題傾向が異なるので一概には言えませんが,Codeforces のコンテストの1問目は AtCoder Beginner Contest の1問目に比べたらちょっと難しいくらいだと思います.

その他,次のような特徴があります.思いつくだけ列挙しましたが,このあたりは先日ぴーよさんが公開された記事を読むとわかりやすいです.

ywmt.hatenablog.com

  • コンテスト中はプレテストと呼ばれる小規模なテストに通れば仮の点数が得られる.コンテスト終了後にあるシステムテストに通って初めて AC となり,正式な点数が得られる.
  • Hack と呼ばれる,他人のソースコードが正しい解を出力できないようなテストケースを考えて与えることで,自分が点数を得ることができる仕組みがある
  • 1つの問題で得られる点数は,その問題自体の点数に加えて提出時間や再提出回数にも依存する.
  • 点数のつき方はコンテストの種類によって違う
  • writer の資格は (AtCoder に比べると) 緩めで,問題の質にばらつきがある
  • 参加者がめちゃめちゃ多い *1
  • (AtCoder と比べると) 実装の重い問題や幾何問題がやや多め,ガチガチの数学問題はやや少なめ
    • 個人的な感覚としては ICPC などに出る実装重め問題の重さほどではない
    • ただし問題傾向も writer によって大きく異なる
  • 新規ユーザの初期レートは 1500 として扱われる

特に AtCoder競技プログラミングを始めた人 (含 Noimin) にとっては色々と勝手が違いますが,重要そうな部分を本記事で解説したいと思います.

以下,ユーザ登録を済ませてあることを前提とします.Codeforces に興味あるけどユーザ登録はまだ……という方は,右上の「Register」からユーザ登録を済ませ,「Enter」でログインしましょう.

1. コンテストに参加登録をする

上部にあるメニューバーの「CONTESTS」から,コンテストの一覧に飛べます.

f:id:noimin:20191014155757p:plain
コンテスト一覧

画像に出ているのは今後予定されている or 今実施されているコンテストのみですが,下にスクロールすると終了したコンテストの一覧もあります.終了したコンテストの一覧は過去のコンテストの結果を確認したり問題を解き直したりしたい時に便利です.

Register » が出ているコンテストは参加登録ができます.コンテスト一覧表の Register » か,直近のコンテストであれば右側の Pay Attention の中にある「Register now »」というリンクをクリックしましょう.リンク先のページで出てきた合意事項を確認して「Register」ボタンを押せば登録完了です.

f:id:noimin:20191014155544p:plain
Codeforces Global Round 5 への参加登録が完了

コンテスト一覧表でも,登録が完了したコンテストは Registration completed と出るはずです.

普段はコンテスト5分前に Registration が閉じられるので,参加したいコンテストへの参加登録はお早めに

コンテスト種別

とりあえず以下のコンテスト種別を押さえておけばいいと思います.

Codeforces Round #XXX

  • 最も開催頻度の高いコンテスト.
  • Div. 1, Div. 2,Div. 3に分かれている.
  • レート変化の対象になるのは Div. 1 は紫以上 (Rating: 1900〜) ,Div. 2 は青以下 (Rating: 〜1899) ,Div. 3 は水色以下 (Rating: 〜1599).
    • ただし Div. 2 のみ開催の回は紫もレート変化対象.
  • 順位のつき方は Div. 1/2 と Div. 3 で異なる.
    • Div. 1/2 は問題ごとに固有の得点を持っており,時間経過・誤答提出ごとにその点数が減衰していく.得点が高い方が上位.
    • Div. 3 は ICPC に似たルールで,正解数が同じなら (解答時間の合計 + 誤答ペナルティ) が少ない方が上位.
  • Hack のルールも Div. 1/2 と Div. 3 で異なる.
    • Div. 1/2 は Hack をコンテスト時間中に行う.Hack によって得点が上下する.
    • Div. 3 はコンテスト終了後に Hack をするための時間がある (12時間) .コンテスト自体に参加していないユーザも Hack ができる.Hack されたユーザは Hack された問題が不正解ということになるが, Hack したユーザのスコアや正解数には特に影響はない.

Educational Codeforces Round XX

  • ↑ほどではないがそこそこの頻度で開催されている.
  • レート変化の対象は紫以下
  • 順位のつき方・Hack については Div. 3 と同じルール.
  • 競技よりも教育が目的 (らしい)

Codeforces Global Round X

  • 最近開催されるようになった.
  • みんなレート変化の対象.
  • 順位のつき方・Hack については Div. 1/2 と同じルール.
  • 上位は Tシャツなどがもらえる.

個人的には年末年始に開かれる「Goodbye 2018」「Hello 2019」のようなコンテストがお祭り感あって好きです.

2. コンテストに参加する

f:id:noimin:20191018005030p:plain
コンテスト開催中はコンテスト一覧が開催中のコンテストだけになる

コンテストが始まりました.早速 Enter » で問題一覧に飛びましょう.コンテスト開始時間になったときに CONTESTS を開いている場合には,モーダルウィンドウが出てくるので OK を押すと A 問題に飛ばされます.A 問題以外を見たい場合は問題の上にある "PROBLEMS" から問題一覧に飛べますが,大抵の場合は A 問題から見ると思います. (ちなみに,ルール的にも解ける問題は早い時間帯に解いておいた方がポイントは高くなります.)

他のコンテストサイトと同様に,まずは問題を解いていきます.

問題を解く

f:id:noimin:20191018005503p:plain
問題ページ

問題一覧から問題名をクリックすると問題ページに飛びます.問題文の英語は読みやすい回と読みにくい回がありますが,自力で解読するのを頑張ったり機械翻訳に頼って頑張ったりしましょう.ちなみに私は初手機械翻訳して訳をざっと眺めることで概要をつかんだ後,英語を読んで細かいところを詰めています.

提出は上のメニューから「SUBMIT CODE」を選択しても良いのですが,右側の「Submit?」でファイルを丸ごと提出する方が便利です.提出すると即座に MY SUBMISSIONS のページに飛び,プレテストが始まります.

ちなみに,コード長は 64KB 以下に抑えなければならないというルールがあります (Codeforces Contest Rules).個人用に長いテンプレを使っている方や,自作の高機能なスニペットを貼り付けたときには注意.私のスニペットが全体的に短めであるということもありますが,3年以上こどふぉをやっていてごく最近までコード長制限に気づいていなかったぐらいですし,これは気づきにくいルールかもしれません.

プレテスト

f:id:noimin:20191018010332p:plain
Pretests Passed

プレテストに通ると,問題のステータスが Pretests Passed になります.Accepted ではないのがミソです.プレテストは少ないテストケースによる簡易的なテストなので,このままでシステムテストに通るかもしれませんが,Pretests Passed となったコードでも他の人に Hack されて不正解になる可能性もあります (Hack については次の節を参照).ただ,Hack されたり自力でミスに気づくとかしない限りはとりあえず次の問題に取り組むことになるかと思います.

プレテストが終わって Pretests Passed 以外のステータスになったら,それはプレテストに通らなかったことを意味します.プレテストに通るようにまた考え直してみましょう.

プレテストに通った場合,仮の点数・順位が変化します.点数・順位の基準はコンテストごとに異なります.

Div. 1/2 または Codeforces Global Round の場合

f:id:noimin:20191018150839p:plain
とあるコンテストの開始から42分経過後の点数表

  • 点数の高い人が上位.
  • 問題は難易度に応じて固有の点数 (500〜) を持つ.Div. 1 と Div. 2 で同じ問題が出題されても,その点数は Div によって異なる.
  • コンテスト開始からの時間経過に応じて,各問題を正解することによって得られる点数は減衰していく.つまり,同じ問題でも早く解けた人のほうが点数が上.
  • プレテストに失敗したコードを修正して再提出したり,プレテストに通した後に自力で間違いに気づいて再提出したりすると,再提出1回につき50ずつ点数が引かれる.
  • 上記のような計算方法の性質から,少数の難しめの問題を早く・ミスせず通した人が,ミスは多いものの問題をたくさん通した人よりも上位に来ることもよくある.
  • Hack も得点計算に使用される (画像参照) .

Div. 3 または Educational Codeforces の場合

  • ペナルティの少ない人が上位.
  • 各問題の価値は難易度を問わず同等.コンテスト開始から何分で問題を解けたかが問題ごとのペナルティとなる.
  • 再提出のペナルティは 1 回につき 20 分.
  • 再提出のペナルティは 1 回につき Div. 3 は 10 分, Educational Codeforces は 20分. (Div. 3 のペナルティが 10分になっていたので修正しました.
  • 再提出ペナルティは 1 回につき 10 分 (Educational Codeforces も 10 分でした).

例: Educational Codeforces のあるラウンドに参加し,開始8分でA問題を1発で通した.その後,開始12分後,15分後にB問題を提出するもいずれもプレテストに通らず,開始22分後の提出でB問題を通した. →ペナルティは (A問題のペナルティ8分) + (B問題のペナルティ22分) + (再提出2回のペナルティ20分) = 70分

Hack

Codeforces を始めた人が一番わかりづらく感じると思われる機能がこの Hack です.私の Twitter アカウントで行なったアンケートの結果もそれを物語っています.

ここでは, Div. 1/2 のコンテストを例に Hack のやり方を見ていきます.

Hack をする前に,Hack したい問題のロックが必要です.

f:id:noimin:20191018153628p:plain
A,B,C問題がプレテスト通過済み

星マークの隣に開いている鍵のマークが出現し,背景が緑色になっている問題がすでにプレテストを通過した問題です.

ロックとは,すでにプレテストを通過した問題 X について,

  • Hack されようと間違いに気づこうと,X 問題にコンテスト終了までそれ以上の提出ができなくなる代わりに
  • 同じ Room の人の X 問題のソースコードを見て Hack できるようにする

というものです.Div. 3 / Educational Codeforces の場合はロックはなしで,Hack の時間になったら好きな問題の任意の参加者のソースコードを見て Hack できます.

問題をロックするには,ロックしたい問題の行にある鍵マークをクリックします.確認画面が出てくるので,「Lock Problem」を押したらロック完了です.ロックが完了すると当該行の鍵マークが締まった鍵マークに変化するはずです.

f:id:noimin:20191020215314p:plain
ロック確認画面

f:id:noimin:20191018154409p:plain
C 問題のロックが完了

さて,Hack の準備ができました.早速上のメニューの「ROOM」で同じ Room に割り当てられている人々のソースコードを見にいきましょう.ちなみに Div. 3 / Educational Codeforces の場合は Room という概念がないので「STANDINGS」で全体の順位表にいきましょう.

f:id:noimin:20191018154904p:plain
Room 内順位表

Room 内の順位表で,点数が太字になっている部分は,その行のユーザが当該問題をロックしていることを意味します.また,Hack をしているとセルの背景が緑や赤になることがありますが,これは赤→「直前に見たソースコード」緑→「それ以前に見たソースコード」ぐらいの意味しかないようなので気にしなくて良いです.

ここで他のユーザの問題ごとの点数 ( 496 とか 972 とか) をクリックダブルクリックすることで,そのユーザの提出したソースコードを見ることができます (自分がロックしている問題に関してのみ) .

f:id:noimin:20191020215045p:plain
他のユーザのソースコードの閲覧画面

他のユーザのソースコードを閲覧する際にはコピーができないようになっているので,どうしても手元で試したいときは写経をする必要があります.バグを見つけたら「Hack!」ボタンを押して Hack しましょう.画面のスクショを撮り忘れたので後日追加しますが,「Hack!」ボタンを押すと相手を撃墜するためのテストケース・またはそのテストケースを生成するプログラムを入力する画面に行けます.ケースを入力したら上のメニューの「HACKS」から自分がした Hack の結果一覧を見ることができます. Div. 3 / Educational Codeforces の場合は「HACKS」で自分も自分以外も含むすべての Hack の結果一覧を見ることができます.

Hack は成功したら +100,失敗したら -50 の得点の変化があります.リスクがあるので Hack は慎重にやりましょう.また, Div. 1/2 は問題を解く時間中に Hack もしないといけないことにも注意しましょう.

一方,Div. 3 / Educational Codeforces では Hack による得点 (ペナルティ) の変化はありません*2 問題を解く時間に Hack ができず,問題を解く時間が終わった後に12時間好きなだけ Hack できます.

システムテスト

f:id:noimin:20191018161152p:plain
コーディング終了

時間が来るとコンテスト (のコーディングの時間) が終了します.お疲れさまでした.

Div. 3 / Educational Codeforces ではここから Hack の時間になりますが,そうでなければあとはシステムテストを見守るだけです.

システムテストはプレテストよりも大規模なテストで,writer さんが用意したケースに加えてコンテスト時間中に行われた Hack のケースも含めた最後のテストです.システムテストに通って初めてその問題を AC したことになります.

しばらく (数分〜数十分) すると,システムテストが始まります.自分の提出がシステムテストのキューに入ると,正解が確定していないということで未提出/不正解であるかのような表示になり,順位も一時的に下がるので心臓に悪いですが,焦ってはいけませんシステムテストに通ればちゃんとまた正解として表示されます.

f:id:noimin:20191018161439p:plain
システムテストの最中.不正解・未提出であるかのように表示されているが焦ってはいけない.

システムテストの進捗は右側のボックスの中に出てきます.ちなみにシステムテスト前は「System Testing」ではなく「Pending System Test」となっています.参考までに.

システムテストが終わると,上のメニューの「ROOM」から Room 内の結果を,「STANDINGS」から全体の結果を見ることができます.

f:id:noimin:20191018162057p:plain
Final Standings (Room 内)

ちなみに,画像の中にある赤い数字「-3」は残念ながらシステムテストに落ちてしまったことを意味します.緑色の文字で点数が書いてあればシステムテストを通過して AC したという意味です.おめでとうございます!

後編に続く

以上,コンテストへの参加登録から参加までの流れでした.

後編では,コンテスト結果やレート変化を確認したり,コンテストの復習をしたりします.おまけで多くのこどふぉユーザが使っているツールである CF-predictor も紹介したいと思います.コンテストの復習も,戸惑う方が多いようです.私もこどふぉを始めてしばらくはわからないままでした.

後編は1週間以内には公開できるかと思います.後編もよろしくお願いいたします.

後編を公開しました.プロフィールページ・コンテスト後の復習・CF-predictor の話をしています.

noimin.hatenablog.com

*1:参加者1万人以上もざら

*2:もちろん, Hack された側はその問題が不正解になりますが