自己紹介
(ほとんどの人が)初めまして
uetaと申します。
電気機械系の大学院2年で研究はなぜか統計系統のことをやっています。
競技プログラミングとは
一般に競技プログラミングは略して競プロと呼ばれるのですが
競プロと呼ぶと大半はアルゴリズムのほうをさしますが、今回はアルゴリズムではなく、ヒューリスティック(マラソン)のほうについて書こうと思います。
ヒューリスティックとは最適な解を算出することが難しい問題について
制限時間内に算出可能なより良い解を求めるというものである。
もっと詳しく知りたい方は以下を参考にしてください。
今回は、マラソン系特にAHC用ツール(入力ジェネレータ・ビジュアライザ・ローカルテスタ)の使い方を説明したいと思います。
(できる人はみんな当たり前のようにつかってしまうので、初めてやった時ここの説明がなくて正直困った。。。。)
間違っていた場合は連絡ください。
よろしくお願いいたします。
今回の目的
競技プログラミング特にAtcoderというサイトで提供されるツールの使用方法を説明します。
本サイトではマラソン系のコンテストはAtcoder heuristic Contest、通称AHCと呼ばれています。
今回はこちらで提供されるツールを使うときの使用方法です。
割と新しいコンテストだと
以下のようにツールが与えられます。
これです。
構成
第一回 ビジュアライザについて ←今回
第二回 Windowsでの実行方法
第三回 Ubuntu, WSLでの実行方法
これは何?
コンテストで使った入力値に対する結果を図示するのに用います。
グラフであったり、マップであったり図描写を可能にします。
これらを使うと自分のPC、ローカル環境で実行できるようになり結果を確かめられます。
今回はビジュアライザの概要ついて説明します。(入力ジェネレータ・ローカルテスタはこちら)
ビジュアライザとは
回によってはローカル環境でビジュアライズする機能が与えられることがありますが、
ここではサイト上で図示が可能なweb版について説明します。
web版 というところを押すとサイトにつながります。
これはローカルでビジュアライザするよりも高機能なものが与えられることがあり、頻繁使うことをお勧めします。
コンテストで使う、グラフであったり、マップであったり図描写を可能にします。
これは基本的には結果の確認に使います。
なぜ、ビジュアライザが必要か?
ビジュアライザは結果を表示するために使います。
例えば: AHC17において、出力で以下のようなものを出力したとします
10 8 4 8 10 11 3 5 9 7 11 10 10 5 11 2 10 9 7 2 11 4 7 8 6 3 1 ...
これではどのような結果になっているかがわかりません。
これをweb版ビジュアライザを利用すると以下のように結果を直感的に確認できます。
以下の画像はAHC17より。
ヒューリスティックコンテストは図示して初めて結果が理解出るものが非常に多いです。
また、得点の算出もしてくれ、エラーの時は「Invalid」等で表示されるのもよい点です。
また、それにコメントをつけて毎回の出力に対してほかのデータに誤りがないかを確認することも可能な回もあります。
このように、メリットが数多くあります。
これを有効的に使うことでかなり有利に進めることが可能です。
実際の使い方
これはHTTF本戦を復習したときのビジュアライザの結果です。
seed値のところに数字(0以上の整数)を入力するか、「Input」の部分に直接コピペします。
入力値に対応する「Output」の部分に結果を張り付けると表示されます。
使い方はビジュアライザの「詳細」より確認してください。
コンテストによって細かい使い方が異なります。
seedとは?
回によって細かい手法は異なります。 基本的に入力値はseedを基に乱数を用いて作成されます。 seedとは乱数を生成するのに使う値のことを指します。 これを指定することで、乱数値を固定することができます。例えば、pythonなら
import random
print(random.randint(0,10000000000))
以下のように完全ランダムな数字が出力されます。
しかし、シード値を固定すると
import random
random.seed(314)
print(random.randint(0,10000000000))
このように乱数を固定することができ、固定の乱数にすることができます。
よって、シード値を与えると乱数にもかかわらず、同じ環境を用いれば誰でもどこでも必ず同じ入力値を得ることが可能になります。
最後に
ビジュアライザを使い、プログラムがどのように作用しているかを何回も確認しましょう。
ビジュアライザをいかにうまく使うかで、コードの修正時間やコンテストの出来が大きく変わります。
ぜひ有効活用しましょう。
次回
次はWindowsでの実行ファイル、実行コマンドについて次回にまとめたいと思います。