AtCoderでLanguage Ownerになりたい！
この記事は ISer Advent Calendar 2019 7日目の記事です。昨日の記事はhutoshikawaさんによる 今年みたアニメなど[後編] でした。
AtCoderは競技プログラミングのコンテストを行っているサービスですが、コンテストに参加する以外の楽しみ方もいろいろあります！ この記事ではLanguage Owner（以下LOとします）を狙うという楽しみ方の紹介と、僕が二か月前にSchemeでLOになったとき1の記録を書いていこうと思います。まじめな記事ではないので、気楽に読んでくだされば幸いです。
必要な前提知識
- AtCoderの存在を知っている
LOとは？
AtCoderでは、解答を提出するのに様々な言語を使用することができます。使用可能な言語は、C++やPythonといった有名な言語から、Brainf*ckやUnlambda2といった難解プログラミング言語まで多種多様です。
そして、それぞれの言語の中で最もACした問題数が多いユーザーに与えられる称号がLanguage Ownerです！かっこいいですね。 各言語のAC数ランキングはAtCoder Problemsから見ることができます。
LOになるまで
ここからはSchemeでLOを取ったときの記録を書いていこうと思います。
言語を書けるようになる
LOを取るためには、まず言語を書けるようになる必要があります。当たり前ですね。
AtCoderで問題を解く前の段階では、Schemeの文法は講義である程度知っていた状態でしたが、入出力を行う方法を知らない状態でした。そこで、AtCoder Beginners Selectionで他の人の提出を見て、簡単な問題をACできるようになりました。3 他の人のコードを見ても分からない部分は、処理系のリファレンスマニュアルを読んで勉強しました。
いっぱい問題を解く
問題を解き始めた2019年の10月21日当時、SchemeのLOだったユーザーのAC数は177でした。つまり、LOになるためには最低でも178問解く必要があります。なんとかACできるような言語で178ACを目指すのは辛いので、まずはAC数ランキング3位に入れる136ACを目指すことにしました。解き始めたのは10月21日の昼頃だったと思います。
ABC (AtCoder Beginners Contest)
ABCは競技プログラミング初心者向けに開催されているコンテストで、4問/6問ある問題セットの中ではA問題が一番簡単です。10月21日時点でABCは143回開催されていたので、A問題をすべて解くと3位には食い込めることがわかります。とりあえず、簡単に解けるA問題と、ぱっと見で簡単そうなB問題を潰しました。これでおよそAC数が140、順位は3位になりました。（ここまで、10月22日朝）
10月22日は「即位礼正殿の儀の行われる日」で休日なので、ありがたく休日を問題埋めに使うことにしました。
その他の問題
LOを狙うとわかるのですが、ABCのA問題とB問題は難易度が雲泥の差です。なのでABCのB問題を埋めるのは後々やることにして、簡単に解けそうな問題を探すことにしました。目指すAC数が400-600なら、B問題を（場合によってはC問題も）埋める必要が出てきますが、この当時は必要なかったためやりませんでした。
まず、AtCoder Problemsを見るとRatedなコンテストで出された問題のdifficultyがほぼ全て載っているので（本当に便利です、これが…！）difficultyが低そうな問題を片っ端から見ていって、簡単に解けそうな問題なら解きました。Schemeの文字列処理をする関数を使いこなせなかったため、文字列処理系の問題はだいたい飛ばしました。ここまででおよそ165ACです。
次に、Unratedなコンテストを見ていきます。A問題や、その他のACできそうな問題（例）を解きました。
「その他」と大雑把に説明しましたが、実はUnratedなコンテストでは意外なところに簡単にACできる問題があります。それはマラソンマッチの問題です。マラソンマッチとは、厳密な最適解を求めるのが難しいような問題でどれだけよいスコアを出せるかを競う大会なのです。逆に言えば、与えられる入力に対して出力のフォーマットが正しければ、どれだけスコアが悪くてもACを得ることができます。これを利用すると、たとえば出力に「○○の行数を1行目に出力して、2行目以降は～」のような制約があれば「0」と出力するだけでACがもらえる可能性があります。そこまでしてLOの称号を得ても虚しくないか、など考えるのはやめにして、Unratedなコンテストの問題を適当に埋めると、AC数が170を超えました。（ここまで、22日夕方）
最後に、ほかにも解けそうな問題を探すために、AC数ランキング上位の人がほかに解いている問題を見ることにしました。AtCoder Scores を使って検索で絞り込むと、「他の人がSchemeでACしているが、自分はしていない問題」のみを表示することができ、これも非常に便利なのでこれを使います。そうすると10問くらい解ける問題が見つかったので、これを解いてAC数が180を超えました。
こうして、22日の夜に、無事SchemeのLOになることができました。だいたい20時間くらいかかったと思います。
LOになりたい方へ向けて
SchemeのLOを取る過程で得た、少ない知見を書いていこうと思います。
現在のLOのAC数が少ない言語（～300ACくらい）を狙う方へ
LOのAC数が少ないのは、大きく分けて4タイプの原因があります。「なんでもいいからLOになりたい」という方は、この原因を見極めるとよいでしょう。
1つ目は、単にほかの言語でコードを書いたほうが楽とかいう理由でAtCoderではあまり使われない言語であること。COBOLや、今回LOを取ったSchemeはこれに当たると思います。言語の仕様さえわかれば、比較的容易にLOを狙えると思います。
2つ目は、難解プログラミング言語であること。これにはUnlambdaなどが含まれます。Unlambdaは入出力すら苦痛（筆者の主観ですが）なので、解ける（解こうと思える）問題が相当限られてきます。それなのにLOは109ACしていて4訳が分かりません。Brainf*ckは564ACです。LOを目指す方は頑張ってください。
3つ目は、ACできない問題がある言語であること。これにはText(cat)があたります。どんな入力に対しても同じ出力でACを得られる問題か、入力がない問題しか解けないため、LOを目指すためには解ける問題探しが重要になります。
4つ目は、コード提出に使える問題が少ない言語であること。これにはIOI-Style C++などが含まれます。IOI-Style C++は IOIer Japan Programming Contestでしか提出に用いることができません。
メジャーな言語でLOを目指す方へ
たとえばC++でLOになるためには、2638ACが必要です5。がんばってください。
おわり
ここまで読んでくださってありがとうございました。AtCoderは近々言語のアップデートがあるかもしれないので、LOを目指すための選択肢が増えるかもしれないですね。明日はMisterさんの記事です。
-
Unlambdaは意図的に難解になるように設計された言語ではないですが、公式ホームページ（2019年12月7日確認）に言語の性質として"Obfuscated programming languages"といった記述があることから難解プログラミング言語のくくりに入れています。↩
-
他の人の提出は「提出結果」→「すべての提出」で、言語を見たい言語に、結果をACに絞り込むことで見られます。↩
-
AtCoder Scoresで、2019年12月7日確認。↩
-
AtCoder Scoresで、2019年12月7日確認。↩
