韓国最大のオンラインジャッジサイトBOJとは？あと、solved.acとは？

こんにちは。リユナと申します。

今日は韓国の一番大きい競技プログラミング関連サイトであるBOJ(Baekjoon Online Judge)とそれに関しているsolved.acについて説明するポストを書いてみます。

このポストは有料広告が含まれたいです。無料で書くものであり、ステマではありません。

0. BOJとは？

최백준(Choi Baekjoon)という韓国の(元)競プロerが作ったOnline Judgeです。製作者の名前をとってBaekjoon Online Judgeが正式名称であり、BOJは略したイニシャルです。韓国では普通'백준'(ベッジュン)で呼びます。リンクはこちらです。

特徴的なことはまず問題数が３万近くで世界的にもトップクラスの問題数、そして提出可能の言語も本当に多くて、なんと、Brainf**kとかGolfScriptとかWhitespaceとか'아희'(ハングルの特徴を利用した二次元的に作動する難解なプログラミング言語)のように変な言語でも提出ができます。あと、ジョーク的な問題もちょっとあります。こんなことを全部集めたユーザー大会で「구데기컵」(グデギコップ; ウジムシカップという意味です。)のようなこともあります。(実は私、その大会の管理者の一人です。)

以下の写真は全部Chromeの機能で自動翻訳をしたUIです。基本言語はもちろん韓国語です。もし英語ができたら、最下段の右にある言語設定で言語をEngilsh(Beta)にして初めても問題ありません。

1. 始める、登録

右上にある会員登録をクリックして登録ができます。基本的に、登録をしなきゃ提出が不可能です。

じゃあこんなページが現れます。最後のチェックは外しても構いません。

2.問題の提出

このページは問題の初めにあるA+Bという問題です。見えるように解決したらいいです。

１０００番って書かれてあることの右に提出ボタンを押すと、こんなページが出てきます。

じゃあこんなページが現れます。ソースコードの公開設定とかもできますし、言語の目録で言語を選択して色んな言語で提出ができます。私の場合は基本言語をPyhotn3でセットしたのでこう見えてますが、多分初めて作ったアカウントならデフォルトはC++17だったと思います。

言語の右にある「言語設定」を押せばデフォルトの言語などをせっていできます。

じゃあ、問題を解いて提出してみましょう。

例のため、正しいことと間違ってることを一つずつ提出しました。正解の時の翻訳がちょっと変ですが、「正解です！」って思ってください。

AtCoderとかCodeforcesとは違って、何個を間違ってるのか、どのテストケースで間違ってるのかは教えてくれません。進行度何パーセントで間違ってるのだけは教えてますが、それを今のように表せるためにはブラウザの拡張機能が必要です。

これら以外も色んな結果がありますが、よく出てくるいくつかを挙げてみると

タイムアウト：時間制限を超えました。

ランタイムエラー：その通りです。一部の言語は躯体的なランタイムエラーの理由を教えてあげます。

コンパイルエラー：その通りです。コードのコンパイルすらできなかった場合です。

それら以外にもまたいろいろありますが、このくらいなら問題ないと思います。

3.どんな問題がいいですか？

まず、最も重要な点としては、問題の番号は難易度順ではないことです。

始める方へのおすすめはここの段階的に解くを選択することです。あそこに入ると、

こんなに入出力と四則演算から、FFTとかセグ木とかMCMFのような高級アルゴリズムまで(2023年12月基準)57段階で体系的に組まれています。ここで競プロの勉強を始めたらここから始めるのを強くお勧めします。

あとは、大会を準備する上級者のための方法です。 BOJには数多くの出典の問題が採点可能です。

ここの右側のソース(出典)とICPCがあります。ここで好きな大会カテゴリーを選んだ後、その過去の問題を解くことができます。JOIやICPC横浜regionalも充実しています！

例えば、ここは今年の横浜Regionalの問題です。平壌Regional(笑)程度を除けば、世界中のICPCのRegionalや情報オリンピック問題はすべてあるとみても差し支えないでしょう。

4. solved.acとは？

先ほど申し上げたように、BOJには数多くの問題がありますが、これが難易度順に整列されているわけではありません。当たった人の数、正解率などを見てある程度見当をつけることはできますが、それが絶対正確な指標ではなかったため、多くのユーザーが不便を感じていました。これがBOJの最大の弱いところだったんです。その問題を解決するために登場したのがsolved.ac です！リンクはまあ名前のそのままです。

solved.acは2020年、baekjoonさんの大学後輩でもあるshiftpshさんが作った問題の難易度を測定するサイトです。BOJと公式的に連動が可能で、一定レベル以上のユーザーなら解いた問題に限って直接難易度意見を提出することで難易度選定に寄与することができます。難易度はブロンズ５から、シルバー、ゴールド、プラチナ、ダイヤを経てルビー１が最上難易度です。同じティア内では数字が小さいほど高い難易度です。

公式ガイドラインで提供する難易度の比較表です。いつも正確ではないですが、参考にはなれると思います。

ICPCのSeoulや横浜Regionalを基準にしたら、

Bronze：予選の一番易い問題がこのくらいです。四則演算、ただの易い具現くらいがあります。

Silver：本選で一番易い問題が普通このくらいです。易いDPや二分探索くらいが入ります。

Gold：予選の中間難易度、本選の易い方の問題が大体ここからです。ちょっと応用されたDP、グラフ理論の基礎、バックトラッキングなどが入ります。

Platinum：予選の難問、本選の平均的な問題が大体ここです。セグ木などが登場し始める難易度です。

Diamond：予選の最難問、本選の難問が大体ここです。高級のアルゴリズムが必要ですが、本当にいいアイデアが必要です。

Ruby：本選の最難問がたまに入りますし、WFの難問がこのくらいです。最新論文を読まなきゃ解きにくい問題、本当に具現も概念もやばいデータ構造を使う問題、IMO級の数学知識が必要な問題、実装は難しくありませんが、結果を出すためには膨大な量の計算をしなければならない問題などが入ります。

もちろん難易度の高い問題たちを多く解けば自分のレーティングが上がるし、それについてティアも決定されます。ちなみに、私はDiamond1です。

解いた問題のレーティングが高い順番に上位100問がレーティングに入ります。

各々のティア別人口比率は大体こんな感じです。中央がSilver3くらいですね。

あと、段階的に解くの拡張だとも言えるCLASS機能があります。ある意味音ゲーとかのの単位認定とも似ていますが、（ちなみに、solved.ac を作ったshiptpshも音ゲーやってます。）各クラスに指定されている問題のうち、特定の数以上を解決すれば、そのクラスを獲得することができます！この手順に従うだけで基礎を固めて勉強するにはとても良いと思います！

それ以外に、最近は自主的なアリーナ大会(AtcoderやCodeforcesのような)が開催され始めたようですが、私はここにはあまり参加したことがないので、多くの情報を差し上げることは難しいと思います。 (泣) まず初期なので、まだAtcoderやCodeforcesよりは開く頻度が著しく低いです。

5. solved.acに難易度意見提出する

前に説明したティアがBronze５以上なら誰でも難易度の意見を提出できます。Platinum５以上になったらその評価が公式的に反映されます。公式はかなり複雑ですが、大まかに「最近の難易度評価ほどさらに加重値が入り、上/下位のアウライヤは抜ける平均」で評価されます。

こんなに解いた問題があれば、難易度の貢献をクリックしたら次のページに繋がります。

こんなに難易度の意見を出せます。ここは私が既に提出したのでこんなに見えます。例えのためにまだ意見を提出しなかった問題に入ってみます。(もちろん提出した意見を変える事もできます！)

あそこのコメントを残すをクリックしたらこんなことが現れます。

難易度意見とコメントと、タグ(アルゴリズム分類)などを作成できます。最後にあるこのように送信するをクリックすればいいです！

6. おまけ

BOJには本当に変な問題もたくさんありますので、何個紹介します。

まずは、上の例えにも登場したリユナはセーラー服が大好きです。とかあります。気付いたとは思いますが、それ、私が作った問題です。(実際に私はセーラー服が大好きで、これだけで韓国の競プロの人達に知られています。笑)こんなに特定の条件を満たすユーザーの場合、直接問題とテストケースを作って提出すれば創作問題を作ることができます。他にも特定コンセプトの大会があるので、このようなところに出てくる不思議な問題がたくさんあります。