MojaCoderに問題投稿してみた

はじめに

最近知った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できれば、みんなにガンガン解いてもらいましょう。

さいごに

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

パ研合宿2020 第1日「SpeedRun」に参加してみた

はじめに

この前、AtCoderで開催された パ研合宿2020 第1日「SpeedRun」 に参加しました。1時間ちょっとで私用で離脱し、結果は7完1700点でした。

A パ研合宿2020

2021を出力するだけです。

print(2021)

B パ研合宿2403

最初は文字列のリストとして受け取り、それを数値に変換して最大値を得ました。

x = list(input())
x = list(map(int,x))
print(max(x))

C 皆勤賞

連想配列で毎日参加した人数を数えました。

n = int(input())
dic = {}
for i in range(n):
    k = int(input())
    s = list(input().split())
    for j in range(k):
        try:
            dic[s[j]] += 1
        except:
            dic[s[j]] = 1
ans = 0
for i in dic.values():
    if i == n:
        ans += 1
print(ans)

E Amary

解説を見るともっと簡略化できたようです。
両方同じ値だと実現不可能。あとは細かく分岐してごり押ししました。

x,y = map(int,input().split())
if x == 0 and y == 0:
    print(1,1)
    exit(0)
if x == 0:
    print(y*2,y)
    exit(0)
if y == 0:
    print(x,x*2)
    exit(0)
if x == y:
    print(-1)
    exit(0)
if x > y:
    print(x,x+y)
else:
    print(x+y,y)

F Fibonaccyan

与えられる値が 3000 までなので、フィボナッチ数を 3000 まで求めたらいいのかなと思いました。嘘解法な気がします。

p = int(input())
f = [0] * 3000
f[1],f[2] = 1,1
for i in range(3,3000):
    f[i] = f[i-2] + f[i-1]
for i in range(1,3000):
    if f[i] % p == 0:
        print(i)
        break

G 同意書

各メンバーが同意書を出した、出していないで全探索しました。

n,m = map(int,input().split())
l = []
r = []
s = []
for i in range(m):
    x,y,z = map(int,input().split())
    l.append(x)
    r.append(y)
    s.append(z)
ans = -1
for p in range(2**n):
    x = p
    f = [0] * (n+1)
    i = 1
    while x > 0:
        if x & 1:
            f[i] = 1
        x >>= 1
        i += 1
    flg = True
    for i in range(m):
        x = 0
        for j in range(l[i],r[i]+1):
            x += f[j]
        if x != s[i]:
            flg = False
            break
    if flg:
        ans = max(ans,sum(f))
print(ans)

J Output-only

ピタゴラス数になるような数は何？で検索すると解説にもある公式が出てきました。その公式を使って、条件を満たしていたら出力し、10万回出力したら終了させました。

from math import gcd
x = 0
for m in range(1,1000):
    for n in range(1,m):
        a = m**2-n**2
        b = 2*m*n
        c = m**2+n**2
        if a < b < c:
            if gcd(gcd(a,b),c) == 1:
                print(a,b,c)
                x += 1
                if x == 10**5:
                    exit(0)

感想

ABC級の問題が15問、制限時間が2時間と、とても大変でした。
500点、600点問題が全く解けていないので、この点数帯が解けるよう精進していきたいです。

AtCoderで緑になるまで

はじめに

tnodino(@tnodino)です。AtCoderで緑になることができたので、緑になるまでを振り返ろうと思います。

AtCoderを始める前

基本的に不勉強で遊びまくってました。ITの知識も全くなかったのですが、IT業界への就職を志望していました。そして全くプログラミングができない中、パズル感覚でできそうな競プロが面白そうだと思い、始めてみました。

初参加

始めた段階で大会が近頃開催されることを知り、覚えたてのC言語で勢いで出てみました。初参加はABC169で A問題 だけ解けました。C問題 も挑戦したのですが、「小数点の計算だけなのになんで間違うんだ？」と文句を言っていたと思います。

過去問精進

過去問を解くのがいいと聞いたので、ひたすら過去問を解いていました。この時、Pythonについて知りました。全く知らなかったPythonですが、型宣言やinclude宣言がいらず、個人的にはすごく書きやすいと思いました。そのままPythonでの書き方を覚えるために灰問題をひたすら解きまくりました。

その後は、色々な問題を解いてDPやアルゴリズムの使い方を覚えたと思います。Atcoder Problemsで解けていない問題を解いて、緑色で埋まるのが嬉しかったので暇なときは解くようにしていました。

ここまで不勉強でアルゴリズムや数学の知識がなかったので、解説ACが多いです。解けないものは解けないので諦めて解説をみるように妥協していました。解説を見たら、その問題を他人にざっくり説明できるようになるまでは理解するようにしています。すぐに理解できないくらい難しい場合は、いくつもの記事を参考にしたり、計算で検証したり、コードにコメントを書きながら実装しています。

Streakは繋げていません。好きな時に好きなだけやっています。

Twitter

AtCoderを始めてから競プロようのTwitterアカウントを作りました。その時はITリテラシーがなかったのでカモと思われていたのか、DMで怪しい勧誘が多く来てたのであまりTwitterを見ることはしませんでした。

しかし同じように精進したり、分からないところを聞きあえる仲間というのはかなりありがたいものです。難易度が高い問題を解くときややる気がないときにかなりモチベに繋がりました。

コンテストが終わった後には、みんなが浮上して盛り上がるので見てるだけでも楽しいです。頑張って色変したときにはお祝いしてくれるので嬉しいです。

コンテスト中

まずは問題をちゃんと読みます。A問題、B問題辺りは早解きを意識しているので結構ざっくり読みますが、ここでミスをしてペナルティーをくらったことがあるので、ちゃんと出力があっているか確認はしています。

制約にも気を付けます。値が小さかったり大きかったり、何の文字で構成されているかだったり、そこから問題と絡めてどうやって解くかを考えます。

解き方が思いつかない場合、検索を使って公式がないか調べたり、図に書いてみたり、色々なことを試してさらに考えていきます。過去問に似たような問題があった場合、その解き方がこの問題に利用できないか試すこともあります。

あとは時間いっぱいまで諦めないことです。どうしても無理そうな時は諦めますが、解けそうなときはぎりぎりまで粘っています。

さいごに

現在の精進した成果です。

正直、ここまで続いて緑になれると最初のころは思っていませんでした。Pythonも結構書けるようになったり、いろいろなことを知れて、AtCoderをやってよかったなと思います。

人生を変えてくれた競プロ、AtCoderに出会えて本当に感謝しています。