はじめに

最近知ったMojaCoderに問題を投稿してみることにしました。この記事で作っている問題はPark walkです。ぜひチャレンジしてみてください。

問題文を作る

まず、使いたいアルゴリズムから問題文を考えることにしました。使いたいアルゴリズムは「dowble sweep」という2点間の最大距離(木の直径)を求めるものです。そこから、このアルゴリズムを使うようにストーリーを考えて、誰が見ても問題を解釈できるように微調整しました。

制約

「dowble sweep」は適当な頂点から一番遠い頂点を求め、その頂点から一番遠い頂点を求めると木の直径(その木の最大距離)が求まるというものです。なので、一番使われていると思われる「10⁵」が間に合うので、これを「N」にしました。頂点を結ぶ線の情報を与えるときに、「A > B」となる入力があると(多分)めんどくさいと思うので、与える情報を「A < B」に限定することにしました。さらに「C」が大きすぎると時間がかかると思ったので、最大でも「100」と小さめにしておきました。ここまでの制約は全て整数なので、「入力は全て整数である」という文も追加しておきます。

入力、出力

入力は木の問題なので頂点数を先に与え、順に結ぶ線の情報を与えていくことにしました。出力する解は問題文でも書きましたが、さらに簡潔に書いておきます。

入力、出力例

サンプルケースは小さいので手作業で作りました。まず、問題の意味が伝わっているか不安だったので、例1でどういう操作をすることでこの解を得られるかを補足することにしました。そして、例2に簡単なケースを、例3に少し大きめのケースを用意することで、書いたコードが合っているかの確認ができるようにしました。

テストケース

テストケースを作るのに何万行となる値を手作業で打ちこむのは厳しいので、テストケースを作ってtxtファイルとして出力するコードをPythonで書きました。まずは、txtファイルの出力先であるinputとoutputフォルダを下のディレクトリのように作りました。(「main.py」はテストケースを作るコードを書くファイル)

├── input
├── output
└── main.py

そして、テストケースをrandrangeやshuffleを使ったランダムケース、連番や一つの値だけを与え続けるなどのコーナーケースを作り、それをinputに出力します。その後、readline()などで先ほど出力したファイルから入力を受け取り、想定解のコードで答えを求め、outputに答えを出力します。自分は変数にテストファイルの名前を入れ、formatでテストケース名の入力、出力を簡単にできるようにしています。こうすることでinputとoutputでファイル名が違うという事故も防げます。下のコードは「N(1 <= N <= 100) mod 2」の答えを出力させる問題をランダムで作れるように書いています。

from random import randrange
# テストケースの名前を入れる
name = '01_sample'

# -----------------
# テストケースを作る
N = randrange(1,101)
# -----------------

# -----------------
# inputに出力
path  = 'input/{}.txt'.format(name)
with open(path, mode='w') as f:
    f.write('{}\n'.format(N)
# -----------------

# -----------------
# 想定解のコードで答えを求める
# inputから読み込む
path  = 'input/{}.txt'.format(name)
with open(path, mode='r') as f:
    # readline()で値を一行ずつ受け取る
    N = int(f.readline())
ans = N % 2
# -----------------

# -----------------
# outputに出力
path  = 'output/{}.txt'.format(name)
with open(path, mode='w') as f:
    f.write('{}\n'.format(ans)
# -----------------

実際にテストケースを作った後はこうなります。inputとoutputに同じ名前のtxtファイルを出力していく感じです。

├── input
│   ├── 01_sample.txt
│   └── 02_sample.txt
├── output
│   ├── 01_sample.txt
│   └── 02_sample.txt
└── main.py

作ったら、テキストファイルが入力形式に沿っているか確認します。入力が複雑になるとミスをしている可能性があるので注意します。

投稿

ここまで考えたら、あとは問題を投稿するだけです。問題文はMarkdownとMathjaxを使って書くことができます。書き方は検索すれば出てくるので、調べながら書いていきます。

テストケースの方は、作成したtxtファイルが入ったinputとoutputのファイルをそのままドロップすることで反映されます。作成したテストケースをクリックすると入力出力が見れるので確認しておきます。

テスト

実際に想定解のコードを提出し、ACができるか確認します。MojaCoderはジャッジサーバーの影響で少し制約を小さくしないと想定解が通らないことがあります。10⁵で解けると思っていても、TLEになることもあります。その場合は制約を小さくして、テストケースも作り直す必要があります。実際、このPark walkも制約を10⁴に減らしています。この段階でACできれば、みんなにガンガン解いてもらいましょう。

さいごに

問題を作るということはとても大変ですが、自分が作った問題を解いてもらえるというのは楽しいもので、引き続き作問にチャレンジしてみたいと思います。

tnodino のログ

MojaCoderに問題投稿してみた