もふふろぐ

AtCoderにおける高橋君と青木君の関係 AtCoderの問題文を取得する

本記事は、Competitive Programming (1) Advent Calendar 2019の10日目です。 JavaScript (Node.js)でAtCoderの問題文を収集する方法を紹介します。 ネタ記事ですのであしからず。

概要

この記事を読むと次のことがわかります。

  • AtCoderの問題文を収集する方法 (JavaScript)
  • AtCoderの問題文に登場する高橋君と青木君の関係

背景

ひと月ほど前、競技プログラマーの間でAtCoderの次の問題が話題になりました。

F - Fork in the Road

AtCoderの問題文に登場する高橋君青木君は、経験上、対立関係にあると考えられてきました。 しかし、この問題では青木君が高橋君を助ける行動をとります。

通説に疑問を感じた私は、高橋君と青木君の関係を洗いなおすために、AtCoderの過去の問題を収集することにしました。

準備

何かしらのスクリプトを書いて問題ページをGETすることになります。 今回は筆者が常用しているJavaScript (Node.js)を使用しました。 無論、他の言語でも同様の手順をとれます。

スクリプト全体はGitHubのrdrgn/script-atcoder-takahashi-kunにて公開しました。 実行するにはNode.jsが必要です。

問題文の収集

それでは、AtCoderの問題文を収集し、高橋君と青木君が登場する問題を抽出していきましょう。 手順は次の通りです。

  1. AtCoder 非公式 APIから問題一覧を取得する
  2. AtCoderから問題ページを取得する
  3. 高橋"と"青木"を両方含む問題を抽出する

問題一覧取得

AtCoder公式のAPIは機能が充実していないため、問題一覧の取得にはkenkooooさんが運用しているAPIを使用します。

https://kenkoooo.com/atcoder/resources/problems.json

上記のURLをブラウザで開けばjsonを表示できます。 ただし、スクリプトからGETする際にはヘッダでAccept-Encoding: gzipの明示的な指定が必要になります。 npmのrequestパッケージならオプションでgzip: trueを設定しましょう。

// request-promise-native パッケージを読み込みます。
const request = require('request-promise-native');

// 指定したURLからデータをGETします。
const problems = await request.get({
  url: 'https://kenkoooo.com/atcoder/resources/problems.json',
  json: true,
  gzip: true,
});

ちなみにcurlコマンドであれば--compressedオプションが有用です。

curl --compressed https://kenkoooo.com/atcoder/resource

popen()で呼び出せば、競プロで書き慣れたC++でも、手軽に実装できます。

FILE *f = popen(("curl -sk --compressed https://kenkoooo.com/atcoder/resource").c_str(), "r");

問題ページ取得

前項で取得したjsonのidcontest_idから各問題のURLがわかるので、これもGETします。

// あるコンテストIDと問題IDを使用して問題ページをGETします。
const problemHtml = await request.get(`https://atcoder.jp/contests/${contest_id}/tasks/${id}`);

この際、一部の問題はログインなしでアクセスできないらしく、404が返されるので、適当にcatchしておきましょう。

高橋・青木検索

適当に文字列を検索します。

const containsTakahashiKun = /高橋/.test(problemHtml);
const containsAokiKun = /青木/.test(problemHtml);

/高橋(君|くん)/などとしてもよいですが、今回は"高橋"や"青木"を冠する事象には高橋君・青木君が関与しているものと見なして進めます。

結果、現在(2019年12月9日)高橋君と青木君の共演が見られる問題は71問あることがわかりました。

問題数
すべての問題3208
高橋"を含む問題578
青木"を含む問題77
高橋"と"青木"を含む問題71

URLは次の通りです。

[
  "https://atcoder.jp/contests/abc027/tasks/abc027_c",
  "https://atcoder.jp/contests/abc030/tasks/abc030_a",
  "https://atcoder.jp/contests/abc031/tasks/abc031_b",
  "https://atcoder.jp/contests/abc031/tasks/abc031_c",
  "https://atcoder.jp/contests/abc032/tasks/abc032_a",
  "https://atcoder.jp/contests/abc039/tasks/abc039_b",
  "https://atcoder.jp/contests/abc039/tasks/abc039_c",
  "https://atcoder.jp/contests/abc047/tasks/arc063_b",
  "https://atcoder.jp/contests/abc048/tasks/arc064_b",
  "https://atcoder.jp/contests/abc112/tasks/abc112_c",
  "https://atcoder.jp/contests/abc144/tasks/abc144_f",
  "https://atcoder.jp/contests/abc147/tasks/abc147_f",
  "https://atcoder.jp/contests/agc002/tasks/agc002_e",
  "https://atcoder.jp/contests/agc004/tasks/agc004_c",
  "https://atcoder.jp/contests/agc005/tasks/agc005_c",
  "https://atcoder.jp/contests/agc005/tasks/agc005_f",
  "https://atcoder.jp/contests/agc010/tasks/agc010_d",
  "https://atcoder.jp/contests/agc010/tasks/agc010_e",
  "https://atcoder.jp/contests/agc010/tasks/agc010_f",
  "https://atcoder.jp/contests/agc014/tasks/agc014_a",
  "https://atcoder.jp/contests/agc014/tasks/agc014_b",
  "https://atcoder.jp/contests/agc014/tasks/agc014_d",
  "https://atcoder.jp/contests/agc015/tasks/agc015_e",
  "https://atcoder.jp/contests/agc016/tasks/agc016_f",
  "https://atcoder.jp/contests/agc025/tasks/agc025_c",
  "https://atcoder.jp/contests/agc025/tasks/agc025_f",
  "https://atcoder.jp/contests/agc029/tasks/agc029_d",
  "https://atcoder.jp/contests/agc033/tasks/agc033_b",
  "https://atcoder.jp/contests/agc033/tasks/agc033_c",
  "https://atcoder.jp/contests/agc034/tasks/agc034_c",
  "https://atcoder.jp/contests/aising2019/tasks/aising2019_d",
  "https://atcoder.jp/contests/arc012/tasks/arc012_3",
  "https://atcoder.jp/contests/arc013/tasks/arc013_3",
  "https://atcoder.jp/contests/arc013/tasks/arc013_4",
  "https://atcoder.jp/contests/arc021/tasks/arc021_3",
  "https://atcoder.jp/contests/arc027/tasks/arc027_4",
  "https://atcoder.jp/contests/arc040/tasks/arc040_a",
  "https://atcoder.jp/contests/arc045/tasks/arc045_a",
  "https://atcoder.jp/contests/arc046/tasks/arc046_b",
  "https://atcoder.jp/contests/arc046/tasks/arc046_c",
  "https://atcoder.jp/contests/arc057/tasks/arc057_b",
  "https://atcoder.jp/contests/arc062/tasks/arc062_a",
  "https://atcoder.jp/contests/arc063/tasks/arc063_c",
  "https://atcoder.jp/contests/arc064/tasks/arc064_d",
  "https://atcoder.jp/contests/arc076/tasks/arc076_d",
  "https://atcoder.jp/contests/arc090/tasks/arc090_c",
  "https://atcoder.jp/contests/arc091/tasks/arc091_d",
  "https://atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_e",
  "https://atcoder.jp/contests/code-festival-2015-exhibition/tasks/codefestival_2015_ex_a",
  "https://atcoder.jp/contests/code-festival-2015-quala/tasks/codefestival_2015_qualA_c",
  "https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_d",
  "https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c",
  "https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c",
  "https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_e",
  "https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_d",
  "https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a",
  "https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_j",
  "https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_b",
  "https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_e",
  "https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c",
  "https://atcoder.jp/contests/kupc2015/tasks/kupc2015_g",
  "https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_c",
  "https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_h",
  "https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c",
  "https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_f",
  "https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_g",
  "https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_b",
  "https://atcoder.jp/contests/tricky/tasks/tricky_4",
  "https://atcoder.jp/contests/yahoo-procon2017-final/tasks/yahoo_procon2017_final_b",
  "https://atcoder.jp/contests/yahoo-procon2017-qual/tasks/yahoo_procon2017_qual_a",
  "https://atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_c"
]

まとめ

いかがでしたか?

AtCoderから高橋君と青木君が登場する問題を検索した結果、高橋君と青木君がゲームなどで戦う問題が多いことがわかりました。 他にも、青木君が高橋君にいたずらをしたり、高橋君が居眠りしている間に木やマス目に整数を書き込んでしまう問題もありました。 しかし、青木君が迷子の高橋君を探したり、贈り物をしたりするなど、温和な関係が見られる問題もありました。

結局のところ高橋君と青木君の関係はわかりません。 今後開催されるコンテストからも目が離せませんね。