この記事は、Competitive Programming (1) Advent Calendar 2019 - Adventarの21日目の記事です。
読んでも競技プログラミングの実力は上がりませんので、ご注意ください。
ちなみに過去の分はこちらです。
- Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog
- Advent Calendar 2017 : CPHBを少しだけ和訳してみた(前編) - kmjp's blog
- Advent Calendar 2018 : ブログを書く速度を少しだけ上げる - kmjp's blog
よくわからんが動くものが見たい人は下記YouTubeを参照ください。
AtCoder File System - YouTube
目次
はじめに
競技プログラミングの問題文では、時々変なキャラクターが登場する。
プレゼントに数列を送りあったり、カードを食べたり、勝ち負けが事前にわかるゲームであえて勝負したり。
ではそんなキャラクター達はいったい何問に登場しているのだろうか。
以下、AtCoderの定期コンテスト(ABC, ARC, AGC)を対象に「高橋君」の登場回数をカウントしてみることにする。
とはいえ、Web上にあるリソースを網羅的に探索するのは地味に面倒臭い。
Googleで「site:atcoder.jp 高橋君」と検索しても、提出一覧や解説PDFがヒットしてしまい正確な数は得られない。
テキストから文字列を探す簡単な手段、というと何が思い浮かぶか。
エディタの検索機能だったり、grepコマンドだったり。
残念ながらこれらはファイルシステム上の検索しか対応していない。
どうすればよいか。以下Linux環境を前提とする。
あいにくreminさんの記事とネタ被りしてしまったが、違うアプローチで取り組むことにする。
https://blog.remin.jp/post/atcoder-takahashi-kun-and-aoki-kun/
方式
ファイルシステムじゃないとgrepコマンドが使えないなら、AtCoderの問題文をファイルシステムとして見えるようにしてみよう。
通常ファイルシステムはOS内部で実装されるものである。
しかしOSのプログラミングはちょっと失敗するとOSが固まってリブートする羽目になるので、仮想マシンを使っても面倒臭い*1。
ファイルシステムを通常のユーザー空間のアプリケーションとして構築するためのフレームワークとして、FUSEがある。
今回はFUSEのPython向けバインディングを使おう。
まずAtCoderのデータを取得し、次にそれをファイルシステムとして見せることにする。
データの取得
AtCoderのコンテスト情報と、問題文情報を取得しよう。
コンテスト情報はkenkoooo氏がJSON形式で提供してくれているので、こちらを感謝しつつ利用させていただくこととする。
GitHub - kenkoooo/AtCoderProblems: Extend your AtCoder
各ファイルから以下の情報を取得できる。
- contests.json : コンテストのID、開催日時、コンテストタイトル
- problems.json : 問題のIDとタイトル。
- contest-problem.json : コンテストと問題のIDの対応付け。ABC/ARCで共通の問題を特定するのに使う。
次に問題文の情報を取得してparseしよう。
online-jugde-toolsでは取得できない情報もあるので、今回は自作した。
ここでは問題数分AtCoderにHTTPのリクエストを投げることになる。
request_cache等を使い、短周期でリクエストを送りすぎないよう気を付けよう。
コンテストIDと問題IDがわかれば https://atcoder.jp/contests/abc116/tasks/abc116_d のように容易にURLがわかる。
問題ページから問題文とテストケースを抽出しよう。
これはBeautiful Soupで頑張る。
AtCoderの問題ページは統一感があるようで、実はちょくちょくブレがある。HTMLをベタ書きしているのだろうか…。
- ARC020, ARC026ではテストケースの入出力がpreタグではなくolタグで囲われている。行番号が表示されるメリットがある。
- ARC017Dだけ「問題文」というタイトルの記載がない。
- ARC019D、ARC070D、ARC078Dはインタラクティブなので通常のテストケースの記載はない。
ここまでできたら次はファイルシステムの構築だ。
ディレクトリ構成
実装に入る前に、どんなふうに取得した情報をファイルシステムに対応付けるか考えよう。
今回は参照のみで書き込みはしない単純なものを考える。
ここでは下記の通りコンテスト種類→コンテスト開催数→問題→問題文・テストケース」と階層化していくことにする。
テストケースはinputとoutputをまとめるとか、好みや工夫の入れどころ。
/acfs
|-- abc
| |-- 001
| | |-- A
| | | |-- statement
| | | |-- testcases
| | | | |-- 1
| | | | | |-- input
| | | | | `-- output
| | | | |-- 2
| | | | `-- 3
| | | `-- title
| | |-- B
| | |-- C
| | `-- D
| |-- 002
| |-- 003
| …
|-- agc
| |-- 001
| …
`-- arc
|-- 001
…ABCとARCが同時開催の場合、問題が重複する。
せっかくなので、ファイルシステムらしくシンボリックリンクを張ることにしよう。
/acfs/abc/092 |-- A |-- B |-- C -> ../../arc/093/C |-- D -> ../../arc/093/D |-- id `-- title
ファイルシステムの作成
FUSEを用いて作成されたプログラムをディレクトリを設定して起動すると、そのディレクトリがマウントされた状態となる。
そのディレクトリ内のファイルに対しアクセスが行われると、ファイルのパス名とアクセス時の情報がプログラムに渡される。
今回は読み込みのみなので、アクセスの種類に対応して以下の適切な情報を返してやればよい。
起動時に頑張ってデータをそろえておくと、あとは以下を返すだけである。
getattr: statコマンドやstat関数で参照される、ファイル・ディレクトリの属性情報を問い合わせる関数- stat構造体の中身を埋めて返せばよい。
- ファイルの属性とパーミッション(st_mode)、リンク数(st_nlink)、ファイルサイズ(st_size)、タイムスタンプを埋めて返そう。
readdir: ディレクトリに対し、ディレクトリエントリ一覧を返す- ディレクトリ内にあるファイル・ディレクトリを文字列で適宜yieldする。
- 最初の2つはLinuxの流儀にあわせ
...で固定とすること。
open: ファイルを開く- 今回はopen時のフラグが読み込みのみになっていることを確認するだけで良い。
read: ファイルを読む- ファイルのoffsetとsizeが渡されるので、対応するデータをbinary形式で返そう。
readlink: シンボリックリンク先を返す- 文字列で返すだけ。
実験
動くものが見たい人は下記YouTubeを参照ください。
AtCoder File System - YouTube
コードはGitHubにおいています。
procon/misc/ac_2019 at master · kmjp/procon · GitHub
「高橋君」を含む問題は？
各問題のtitleファイルをgrepしてみる。
/acfs$ grep "高橋君" */*/*/title abc/026/C/title:C. 高橋君の給料 abc/026/D/title:D. 高橋君ボール1号 abc/032/A/title:A. 高橋君と青木君の好きな数 abc/032/B/title:B. 高橋君とパスワード abc/039/B/title:B. エージェント高橋君 abc/039/C/title:C. ピアニスト高橋君 abc/039/D/title:D. 画像処理高橋君 abc/044/A/title:A. 高橋君とホテルイージー / Tak and Hotels (ABC Edit) abc/044/C/title:C. 高橋君とカード / Tak and Cards abc/047/D/title:D. 高橋君と見えざる手 / An Invisible Hand arc/005/A/title:A. 大好き高橋君 arc/005/B/title:B. P-CASカードと高橋君 arc/005/C/title:C. 器物損壊！高橋君 arc/005/D/title:D. 連射王高橋君 arc/007/A/title:A. 帰ってきた器物損壊！高橋君 arc/009/A/title:A. 元気にお使い！高橋君 arc/009/B/title:B. おとぎの国の高橋君 arc/009/C/title:C. 高橋君、24歳 arc/009/D/title:D. 覚醒ノ高橋君 arc/021/C/title:C. 増築王高橋君 arc/029/A/title:A. 高橋君とお肉 arc/029/B/title:B. 高橋君と禁断の書 arc/029/C/title:C. 高橋君と国家 arc/029/D/title:D. 高橋君と木のおもちゃ arc/039/C/title:C. 幼稚園児高橋君 arc/039/D/title:D. 旅行会社高橋君 arc/045/A/title:A. スペース高橋君 arc/045/B/title:B. ドキドキデート大作戦高橋君 arc/045/D/title:D. みんな仲良し高橋君 arc/048/C/title:C. 足の多い高橋君 arc/048/D/title:D. たこ焼き屋とQ人の高橋君 arc/053/C/title:C. 魔法使い高橋君 arc/057/B/title:B. 高橋君ゲーム arc/060/C/title:C. 高橋君とカード / Tak and Cards arc/060/E/title:E. 高橋君とホテル / Tak and Hotels arc/063/D/title:D. 高橋君と見えざる手 / An Invisible Hand
「高橋君」が問題文に登場するのは何問？
- statementファイルをgrepしよう。296問って結構多いですね。
/acfs$ grep -l "高橋君" */*/*/statement abc/004/A/statement abc/004/B/statement abc/004/C/statement (略) arc/094/D/statement arc/094/E/statement arc/097/E/statement arc/099/F/statement /acfs$ grep -l "高橋君" */*/*/statement | wc 296 296 5920
テストケースを試してみる
testcases/*/inputを読んで答えを出力し、testcases/*/outputと比べてみよう。
以下は、ABC001A(2値を読んでその差を答える問題)をPerlのワンライナーで答えるものとする。
誤って絶対値を答えてしまった場合、差がマイナスになるテストケース3でdiffが発生してしまった。
/acfs/abc/001/A/testcases$ for i in *; do echo "test $i:" ; cat $i/input ; perl -e 'print abs(<>-<>),$/' $i/input | diff - $i/output; done test 1: 15 10 test 2: 0 0 test 3: 5 20 1c1 < 15 --- > -15
コンテストを開催日付けで絞る
各コンテストのファイルのタイムスタンプには、コンテストの開催日を設定している。
findコマンドで2017年1月に開催されたコンテストを列挙してみよう。
ファイルを見ると、2017/1/7に開催されたことがわかる。(12時なのはUTC基準のため)
/acfs$ find ./ -maxdepth 3 -name title -newermt '2017/01/01' -and ! -newermt '2017/01/31' | xargs cat AtCoder Beginner Contest 051 AtCoder Beginner Contest 052 AtCoder Beginner Contest 053 AtCoder Grand Contest 009 AtCoder Regular Contest 067 AtCoder Regular Contest 068 /acfs$ stat abc/051/title File: abc/051/title Size: 29 Blocks: 1 IO Block: 4096 regular file Device: 34h/52d Inode: 2474 Links: 1 Access: (0444/-r--r--r--) Uid: ( 0/ root) Gid: ( 0/ root) Access: 2017-01-07 12:00:00.000000000 +0000 Modify: 2017-01-07 12:00:00.000000000 +0000 Change: 2017-01-07 12:00:00.000000000 +0000 Birth: -
エディタで検索してみる
- VSCodeでこのディレクトリを開いたところ、ちゃんと検索もできた。高橋君は借金を倍返ししてくれるそうですね。
まとめ
もともとAtCoder FileSystemは数年前に考えたAC向けのネタの一つでした。
まぁまぁ想像通りに動いてよかったです。HTMLの揺れにはちょっと苦労しましたが…。
興味を持った方は、もっといろんなファイルシステムを作ってみるとか、本格的にファイルシステムを作りたい人はC言語でFUSEを叩いてみるとか、さらにはLinuxカーネルプログラミングかWindowsデバドラプログラミングに取り組んでみましょう。
手持ちのネタが後1回分しかないので、また何か考えないとな。
*1:3年前のACでは、実機検証のためUSBメモリを2台のPCの間で抜き差いしつつ、PCをリブートする作業を数十回行った。とても疲れた。
