shu8Creamのブログ

競プロブログ。

AHC026参加記（67位）

競プロ解説

先日、トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）に参加し、67位を獲得しました。

contest_result_ahc026 Contest Result - AtCoder

下図は67位を獲得した提出のseed=0000のビジュアライザ、獲得点数は9354でした。 ahc026_visualize

点数推移と各提出の解法概要

  1. 1,319,800(本番615位相当) 1から順に目的の箱の上の箱を一番低い山に置く貪欲。
  2. 1,329,478(本番574位相当) 番兵として各山の底に9999番の箱があるとした（番兵）。上の箱を運ぶときに、移動する箱の底と移動先の一番上の箱の値が昇順になるようにする。不可能なら差の絶対値を小さくする。
  3. 1,343,061(本番524位相当) 番兵として各山の底に201番の箱があるとする。これまでまとめて移動してきた箱を小分けに移動する。移動する箱は上から昇順に並んでいるならまとめて移動する。移動先は、できるだけ差が小さく昇順にできるような場所に移動する。
  4. （参考）1,356,657 (本番426位相当) 箱はまとめて移動する、移動先は最小値が最大の山にする。（この点数集団が結構多いようです）
  5. 1,375,649(本番273位相当) 3の解法で、昇順に並んだ箱をまとめて移動する部分に制約をつける。昇順でも差が15より大きい場合は分割する。
  6. 1,387,723(本番139位相当) 条件を加える。移動先に箱を置くときに、基本は昇順に並ぶことを優先するが、差が大きくなりすぎる場合は、降順に並ぶことを許容する。
  7. 1,389,848(本番117位相当) 条件を加える。移動先に箱を置くときに、基本は昇順に並ぶことを優先するが、差が大きくなりすぎる場合は、降順に並ぶことを許容する（6で漏れていた部分を改修）。
  8. 1,396,055(本番67位) 序盤で箱の移動をするとき、一時的に高さが低くなる山があれば、すべて取り出して他の山に移動する。空いた山にはできるだけ大きい箱を底に敷く。

考察

序盤

コンテスト中どのような考察をしたのかを解説します。 はじめは、細切れに箱を移動するほうが最終的なコストが大きくなりそうなので、提出1の解法をベースに箱をまとめて移動することを考えました。提出1から提出2にかけて、まとめて箱を移動する効率的な方法を考察しましたが、値の大きい箱は順番に箱を取り出す過程で各山をたらい回しされることになります。そのため、提出2を終えた段階で小分けに箱を動かす手法に切り替えました。まとめて移動する手法では、参考に書いた4の手法がかなり良い点数だと思いますが、これ以上スコアを上げるには一筋縄ではいかなそうです。

中盤

提出3~8にかけては、基本的な考え方は同じで改良を重ねました。箱を小分けに移動しますが、移動先でどうなっていてほしいかを考えます。序盤の提出ではまとめて箱を移動していましたが、これはあまりよくありませんでした。箱の値がバラバラのまま移動しても、値の大きい箱は再び避ける必要があり移動コストがかかってしまいます。特に値の大きい箱が山の上の方にあると何度も山を移動することになります。なのでできるだけ移動先で昇順に並べて箱の移動コストを削減します。この考察に至ると各山をソートしたくなってきますが、この時自分は厳密にソートするとコストが結構かかるのではないかとよく考えずに切り捨ててしまいました*1。

上図は序盤の様子です。箱の移動はできるだけ昇順に並ぶように移動することを考えます。一回目の移動では37の箱を移動していますが、昇順に並べることだけを考えると87の上になるはずですが、箱の値の差がかなり大きいのであまり嬉しくありません。箱の値の差が一定以上*2の場合は、降順に並ぶことも許容すると図のように19の上に移動することになります。降順を許容することで、できるだけ長く昇順に並ぶ可能性が高くなります。昇順に並んでいる箱を移動する必要が出てきたとき、その部分を丸ごと移すことで移動コストが削減できて、対象の箱を運び出す時も上に避けなくてはならない箱がたくさん並んでいる確率を減らすことができます。

この操作を繰り返していくと上図のようになります。これは12個目の箱を取り出そうとしているところを切り出したものになります。この時点ですでに左右の山の上部が綺麗にグラデーションになっており、昇順に並んでいることがわかります。

終盤

今回の解法の一番重要な部分はここまでで後は各パラメータの調整と細かな工夫を入れていきました。その後の考察は、ビジュアライザを観察し続けて試行錯誤しました。例えば、上図を見ていると中央の高い山の上部に200番周辺の最終盤に取り出したい箱が集まっています。その右横には5個しか箱の積まれていない山があります。途中で低くなった山からはすべて取り出してしまって、他の山から大きめの値の箱を持ってくることができれば改善が見込めそうです。後半1時間はこのような感じで、今より1でもスコアが上がれ！と思って実装をしていました。

感想

今回は今まで戦えるスコアになったことがなかった短期のAHCで100位以内に入り、入青することができました。 これまでの傾向からすると、短期長期ともに貪欲解が使えるときに比較的いいパフォーマンスを出している気がします。 まだ長期の方では、黄パフォを取ったことがないのでそこを目指しつつ、当分はレート2000黄色を目指して精進します。

*1:10000 - (山から取り出すコスト40 + 戻すコスト40) × 山の数10 = 9200 実際ここまでコストはかからないのに加えて、ここから工夫するとまだまだ伸びそう

*2:今回は20~30ぐらいの幅で調整

2023年！！

shu8Creamです、2023年になりましたー
今年もよろしくお願いします！！
とりあえず2022年の振り返りパートを書きました。
 2023年の目標を記します。2022年の振り返りはその下に...

2023年の目標

ヒューリスティックやKaggle、Codingameなどやりたいことはたくさんありますが、ふらふらすると目標達成から遠のくので目標はなしにしました。
このブログでAtCoder水~青の人の役に立つようなちゃんとした記事を1本書きたいというのも密かな目標です。今のところは、日本語での情報があまりないアルゴリズムの解説かなー。

レート目標

AtCoder: 入青 1600over
Codeforces: 入紫 2000over

AtCoderは青タッチを当分の目標に、こどふぉは上振れを引くとレート変化がデカいので紫かつ2000overを目標にします。

AC数

AtCoder: 1725 → 2225 (+500)
Codeforces: 338 → 638 (+300)
AOJ: 33 → ?? (+?)
yukicoder: 92 → 292 (+200)
Library Checker: 8 → ?? (+?)
Total: 2196 →3196 (+1000)

AOJとLibrary Checkerは主にライブラリverify用なので特に定めず、その他で1000ACを目指します。

資格取得

プライベート

  • 沖縄旅行
  • サンライズ出雲に乗りたい
  • アウトドアアクティビティをしたい
  • 競プロ界隈でお友達を増やす

2022年の振り返り

レートの変化

AC数

その他（テック系）

資格取得
コンテスト
  • AtCoder Heuristic Rating 水色達成
  • Meta Hacker Cup 2022 Round2進出（上位2000位達成ならず）

その他（プライベート）

  • 石川旅行
  • 日光（栃木）旅行
  • 大阪旅行

CFR #839 (Div. 3) D. Absolute Sorting 解説

競プロ解説

先日開催されたCodeforces Round #839 (Div. 3)のD問題を解説します。
本番中に通せなかったのと、あまりみたことのないタイプの問題だったので記憶に残すためにも書きます。

問題概要

問題文
正の数からなるある数列Aが与えられる。あるxを選び、 A_i = |A_i-x| (1 \leq x \leq n)と置換した時にAがソートされた状態になるようなxを1つ探す。

制約

2 \leq n \leq 2⋅10^{5}
1 \leq a_i \leq 10^{8}
0 \leq x \leq 10^{9}

解説

まずは小さいケースから考えます。
n = 2, A = [3, 4 ]
この場合は、すでにソートされていますが、どんなxを選ぶことができるでしょうか？ x = 0, 1, 2, 3の時条件を満たし、 x \geq 4になると条件を満たしません。

n = 2, A = [5, 4 ]
この場合はどうでしょうか？ x \geq 5になると条件を満たします。

この2ケースを比較すると、連続する2数によってxの上限、下限が決まることに気づくと思います。

サンプルケースの8つ目を実際に試してみます。 n = 6, A = [29613295, 52036613, 75100585, 78027446, 81409090, 73215 ]
初めのxの範囲をbottom = 0, top = 1e9とすると、はじめの2数29613295と52036613では、top = 40824954になります。 以降上限値はずっと変わらず、最後の2数81409090と73215でbottom = 40741153となります。 40741153 \leq x \leq 40824954 の範囲であれば、どこでも条件を満たすことになるため、適当に下限値を出力すれば良いでしょう。 テストケースによっては、bottom>topのようになることがあります。この場合は条件を満たすxが存在しないため、-1を出力します。

回答例（ソースコード）

// 諸々は省略

void solve(){
    ll n; cin >> n;
    vi a(n); cin >> a;
    ll l = 0, r = 1000000000;
    rep(i,n-1){
        if(a[i]>a[i+1]){
            chmax(l,(a[i]+a[i+1]+1)/2);
        }else if(a[i]<a[i+1]){
            chmin(r,(a[i]+a[i+1])/2);
        }
    }
    cout << (l<=r?l:-1) << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int t; cin >> t;
    while(t--) solve();
}

競プロer向け知っておきたい便利なLinuxコマンド

本記事は競プロ Advent Calendar 2022、12/15日分の記事です。
前日14日の記事はこちらから、翌日16日はこちらからどうぞ！

最近、AtCoder以外にも多様なコンテストに出るようになってLinuxコマンドを駆使して色々と調べることが増えてきたのでまとめてみます。 ここでいうLinuxコマンドは、Macでいうところのターミナル、WindowsでいうところのWSLで使用するコマンドを指しています。（Linuxってターミナルだっけ？）

time

時間を計測するコマンドです。実行する時につけておくだけで実行時間がわかるので便利です。 オンラインジャッジがなくて、手元の実行結果を提出するタイプのコンテスト（Meta(Facebook) Hacker Cupなど）だとMAXケースでどれぐらい時間がかかるか測っておくと安心です。 プログラム自体の実行時間は、userを見れば良いです。オンラインジャッジへの提出を考えている場合、ジャッジサーバーと環境が全く違う場合もあるので参考程度と考えておきましょう。

使用例

$ time ./a.out < ./input > ./output

real    0m0.182s
user    0m0.059s
sys     0m0.062s

$ time python A.py < ./input > ./output

real    0m0.451s
user    0m0.057s
sys     0m0.068s

diff

ファイル同士の差分を比較するコマンドです。競プロで使うシチュエーションとしては、愚直解は自明だけど高速化が必要なケースで、愚直解の答えと高速化した解を比較する時に使えたりします。このコマンドはオプション必須だと思っていて、よく使うのはq, yオプションです。

# file1   #file2
1 2 3      1 2 3
4 5 6      4 5 6
4 5 6      7 8 9
1 2 3      2 2 3

使用例

# オプションなし
$ diff ./file1 ./file2
3,4c3,4
< 4 5 6
< 1 2 3
---
> 7 8 9
> 2 2 3

# qオプション
$ diff ./file1 ./file2 -q
Files ./file1 and ./file2 differ  # 違う時はこう出る（差分がなければ何もなし）

# yオプション
$ diff ./file1 ./file2 -y
1 2 3                                       1 2 3
4 5 6                                       4 5 6
4 5 6                                     | 7 8 9      # 差分があるところにパイプが出る
1 2 3                                     | 2 2 3

# yオプション2
$ diff ./file1 ./file2 -y --suppress-common-lines
4 5 6                                     | 7 8 9      # 差分だけ出せる
1 2 3                                     | 2 2 3

tee

ログ出力関連のコマンドです。
ログ出力と聞くと競プロと関係なさそうに感じますが、ファイル書き込みと考えると利用シーンが思いつくのではないでしょうか？
echoなどのコマンドの後ろにパイプで接続するとファイル書き込みができて便利です。

echo hogehoge | tee log.txt

こちらの場合は常に上書きされるので、追記したいときは

echo hogehoge | tee -a log.txt

のように-aオプションをつけます。
競プロでの使い所としては、AHCなどのマラソンコンテストで1テストケースの実行結果を保存して、改善前後で比較したい時などは手っ取り早くコマンドでファイル書き込みができて便利です。
ちなみに、こちらのコマンドは標準出力を書き込むことになるので、標準エラー出力もファイルに書き込みたい場合は

echo hogehoge 2>&1 | tee log.txt

こんな感じにすると良いです！

xargs

標準入力から引数を受け取って実行するコマンドです。実行するだけであれば、普通に実行ファイルを実行すれば良いということになってしまいますが、このコマンドでは並列化処理ができます。ヒューリスティックコンテストでたくさんのテストケースを実行したいけど、1000個のテストケースを実行すると単純計算で1時間くらいかかる...というような時に実行時間を短く収めることができます（PCのスペック次第...）。

# 実行コマンド
seq 0 999 | xargs -P4 -I{} ./exec.sh {} # 0~999の入力ファイルを実行

上記の実行コマンドのように実行します。exec.shファイルに実行したいコマンドをシェルスクリプトで書いています。今回のコマンドはAtCoder Heuristic Contest（AHC）で、C++の./a.outやPythonコードを実行するファイルをexec.shとして実行した例です。実行ファイルは好きなものに置き換えてください。
具体的に中身を解説すると、seqコマンドで0~999までの数値を順に出力し、それはパイプ（| ←この縦棒のこと）で右のコマンドへ渡します。
次にxargsコマンドで./exec.shの実行を行います。-Pオプションがこのコマンドの肝で、このオプションを使うことで自動で並列化して実行することができます。今回は-P4としているので4並列で実行してくれます。
PCスペックによりますが、単純計算で1000ケースを直列実行した時の4分の1の時間で実行が完了します（実際はもう少し時間がかかると思います）。 並列数は任意に指定できますが、スペックが足りないとうまく動作しない可能性もあるので、自分のPCと相談して使用すると良いです。 マラソン系のコードだとうまく計算リソースが使えず、スコアがガクンと落ちる場合もあるので注意です。
最後のオプションですが、-Iオプションで./exec.shの実行コマンドの引数にテストケースの番号（0-999）を渡すことで、合計1000ケースをまとめて実行しようとしています。テストケース番号はコマンド中の{}が置き換えられて順に実行されます。

exec.shファイルに何書けばいいんだー？、ヒューリスティックコンテストで実際どう使うんだー？と思ったあなたは、こちらの記事をご覧ください

おわりに

以上が競プロで使えるLinuxコマンド紹介でした。
ヒューリスティックコンテスト向けが多いですね。僕は、MHCに参加した時に必要性を強く感じたので、普段AtCoderやCodeforcesのアルゴリズムコンテストのみに参加していれば、必要性があまり感じられないかもしれないです...
そんな方も色々なコンテストに参加して、深い競プロ沼へ飛び込みましょう。

Meta Hacker Cup 2022予選参加記

初めてMeta(Facebook) Hacker Cupに参加したので、参加記を書きます。
AtCoder水（アルゴリズム）、Codeforces青ぐらいのレベルです。（参加を考えている方の参考に） 毎年開催されているようで、Round2の上位2000位に入るとTシャツがもらえます。

結果はRound2まで進出し、2100位台というTシャツをもらえない悔しい結果となってしまいました。来年もし参加するならば、Tシャツを絶対に手に入れたいです。。。

Qualification Round

雑解法

A. 各種パーツをカウントして、被らないように分けるだけ。
B1. 細長いフィールドの時は、条件を満たせなくなる。あとは空きマスを木で埋めてしまえばよし。コーナーケースはそもそも木がない時は必ず条件を満たす。
B2. DFSで周囲を見て条件が達成できるかを確認していく。DFSは再帰だとオーバーフローしたのでスタックで書いた。
C1. 与えられる符号の最初の1文字と異なる文字からスタートしてハフマン符号の要領で構築。
C2. 期間中はわからず
D. 期間中に問題をみなかった

コンテスト中の日記

B2の感想 フィールドがMAX(3000*3000)なので、意外と時間がキツそうと思った。実装が終わって確かめるが、validケースが弱い。MAXケースを自作して実行したら、スタックオーバーフローした。DFSを再帰で書いていたが、どうやら再帰だとオーバーフローしやすいらしい。はじめての経験だった。なんとか打開法を調べているとスタックに積む形にDFSを書き換えるといけるかも？はじめて書くので帰りがけの処理とバグに苦労した。再度、自作のMAXケースを実行。エラーもなく出力できた。提出前にMAXケース作ったのが偉すぎる。順位表を見るとB2で6分の制限を切らしている人がちらほら。自分と同じことをしたのだろう。

この段階で19時。夜にABCとえでゅふぉがあるので、今日はここまでMHCはまた明日。C1,C2,Dが残っているが、点数を見る感じDはきつそう。

C1.モールス信号をモチーフにした符号化の問題。一種類の符号が与えられるので一意に復元可能な符号パターンを残りN-1個作る。200文字まで使えるので適当にハフマン符号化するといける。 C2.C1と異なるのは符号化するときに10文字までしか使えないところ。瞬時符号について調べていた。bit全探索の要領でやると容易にN-1パターン生成できることは分かったが、それが一意に復号出来るのか悩んでしまい提出できなかった。解説を読むとできるらしい。瞬時符号とごちゃ混ぜに考察していたのがよくなかったようだ。少し実験して納得した。学びを得られたのでよしとする。

Dは期間中は全くみていなかった。配点的に解けるものだと思っていなかったが、コンテスト終了後に見るとすぐに方針は立った。だが、計算量が怪しい。連想配列をふんだんに使っているのと、深さ2のBFSを対称の頂点に対して全て行なっているので、ブレがあるものの手元の実行時間で2分半ぐらいかかった。本番中のことを考えると6分制限なのでスムーズにいけば通せそうだが、実際にできるかと言われるとかなり怪しい。解説を読むと、辺が多く出ている頂点（BigNode）を別処理して、2stepでやると計算量が改善するらしい。知らない高速化手法が無限にあるんだなあとしみじみ。またどこかで復習しておこう。一応自分の解法も方針としてはいいらしい。Twitter見た感じだと自分と同じ方針でももう少し高速化できるらしい。

Round1

雑解法

A1. コーナーケースに注意して順列をrotateするだけ（コーナーケースがつらい）
A2. B+A+AでZアルゴリズムをする（これもコーナーケースがつらい）
B1. 座標通りに管理して前計算することで計算量を落とす
B2. 求める式を式変形すると座標の和と二乗和を計算すると、O(1)でクエリを処理できる

コンテスト中日記

A1.順列をrotateして正解の並びにできるかを判定する問題。操作回数が0,1,2の時にコーナーケースが散りばめられている。一番配点が低い割に注意が必要でいやらしい（後にやらかしていることに気づく）。最初にk=0,1,2の時を別処理してから、始点を見つけてから愚直に並びが合うかを確かめる。自分がミスったのは、k=1の時にa!=bならYESとしてしまった。初歩的すぎるミス。なんでvalidが通るのか、一問目なのだから弾いてほしい。
A2.この時点の順位表では、A2を飛ばしている人が多かった。おそらくCを除く4問では一番難しいのだろう。自分もかなり時間がかかった。A2はA1の順列制約が無くなったバージョン。方針としては、A1と似た感じで最初にコーナーケースを別処理して、その他を判定する。コーナーケースは、k=0とk=2かつn=2の二つだと思っている。k=1のパターンは、その他の判定のところで分岐を作ってうまく取り込んだ（正直コーナーケースが網羅できているのか相当怪しい）。その他の判定がメインの問題だが、ここはZアルゴリズムをうまく使って線形計算量で判定した。B + -1 + A + Aの配列でZ配列を作る。Z配列の値がNを超えていれば。rotateで並び替えることが可能。k=1の時だけZ配列を見る範囲を絞らなければいけない。

方針は合っていると思うが、コーナーケース…。A2のチェックをしている時に、A1の本番用の入力を使っていたときに、A1が間違えていることに気づいた。かなり萎えた…。前から順に解いていたので、A1,A2が怪しいとなると、配点的にB2が解けないとRound1の突破が怪しくなってくる。Tシャツがなんとしてでも欲しいので、それだけは避けなければ。

B1.二次元平面上にN点が与えられて、さらにQ個の点が与えられる。各Qに対してユークリッド距離の二乗和を計算する問題。B1は点の座標が3000以内なのでヒストグラムを作って前処理してあげると線形時間（modint使ってるので嘘だけど）で解ける。
B2.自分がおバカすぎて2時間も無駄にした。シグマの式を展開して式変形するとX座標Y座標それぞれの和と二乗和が前計算できていれば簡単に処理できる。これもさっきと同じ嘘線形時間。流石にこれは通ったと思うので無事Round1突破（懇願）。

Cは問題をみたが問題文がむずい。制約が以前と変わったと書いてあったが、いつから変わったのか（コンテスト中？）、以前出題された問題なのか、よくわからなかった。 （後で追記する）

Round2

雑解法

A1 文字種が26種類しかないので、各文字が何文字登場したかを累積和の形で保持できる。判定は要らない文字が前後にあるパターンで場合分けすれば良い。

感想

Round2は3時間で日記をつける余裕もないので、感想を書く。A1は簡単だったが、A2が何もわからなかった。ちらっとハッシュは頭によぎったが、経験値不足で解法につなげられなかった。文字列アルゴリズムや動的wavelet matrixでできないか調べていたが、どれもよくわからず。

結果としては2100位台でTシャツにも届かなかった。A1をもうちょっと早く通せていれば、全然可能性があったので余計に悔しい。

以下は、終了後に解いたものについて書く。 A2 どうやらzobrist hashで解けるらしい。通常はXorで持つところを和で計算すると良い。 セグ木などに乗せると配列の更新と区間和を計算量を落として求めることができる。 条件を満たすかの判定は、A1とさほど変わらずに不要文字が前半にあるパターンと後半にあるパターンで場合分けしてあげると良い。

（その他の問題もupsolveしたら追記する）

AtCoderで水色になりました！

色変記事

こんにちは、shu8Creamです。 先日行われた、LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）にて1754パフォーマンスを出して、水色になることができました！ 現在のレートは1247で、レートが一気に+73されたので大成功回でした。 初めて緑になったのが、2021/4/18らしいので2022/8/6で水色になるまで、1年4ヶ月ほどかかりました。

ちなみにCodeforcesは少し前に青色になりました。
ちなみにちなみに最近AtCoder Heuristic Ratingでも水色になりました。

精進記録

各コンテストサイトのAC数
Solved By shu8Cream
Topcoder: 0
Codeforces: 267
AtCoder: 1505
AOJ: 32
yukicoder: 76
library-checker: 7
Sum: 1887

記録はこのような感じです。 長期間停滞している時期もありましたが、就職など生活環境の変化から精進時間が取りづらいという明確な理由があったので、そこまで気を落とすこともなく継続できました。コンテストに出続けることができたのがモチベーションを保てた理由かなと思います。

ABCはほぼ必ず出ていて、ARCには自分の実力を見て早解きできないときつい配点の時はUnratedで参加したりしてました。 個人的にはABCよりもARCの方がじっくり考えなきゃいけない問題が多いので好きです。（もっと実力がつけばもっと好きになれそう）

基本使用している言語はC++で、多倍長整数でズルしたくなったりした時にPython使ってたりします。（ほぼ出番はない） Rustは絶賛練習中です。

学んだアルゴリズム

以前、緑になった時に書いた記事から増えたものと実際に使用したものを中心に紹介します。

実際に使用した

  • 座標圧縮
  • セグメント木
  • BIT
  • 最小全域木(クラスカル法・プリム法)
  • ランレングス圧縮
  • トポロジカルソート(BFS実装)
  • SCC
  • 遅延評価セグメント木
  • Mo's Algorithm
  • ベルマンフォード
  • Zアルゴリズム(ABCで使用、問題は解けず)
  • LIS(ARC)
  • 最大フロー（Ford-Fulkerson）（ARC）
  • XorShift(主にマラソンで活躍)

勉強したが、コンテストでは未使用

  • BinaryTrie(Codeforcesで出題されたので勉強)
  • LCA(オイラーツアー +RmQ)
  • SparseTable
  • LCS
  • レーベンシュタイン距離
  • ZobristHash(ABCで出題されたので勉強)
  • ミラーラビン素数判定法

今後勉強予定

補足

僕の場合、水色になるためには必須でない知識を色々学んでいます。 もし緑で伸び悩んでいたり、現在茶色で水色を目指しているような方は

これをしっかり身につけることが最重要課題だと思います。僕は、DPとDFSがかなり苦手で結構練習しました。 ここ最近は、シンプルDPなら問題見たらすぐにDPだと気づけるようになりましたし、DPだと気づけなかった頃の気持ちを忘れ始めています（これは良くない気がする）。 DFSは、BFSでも解けるものをDFSで解き直したり、慣れてきたら木DPの問題まで手を伸ばして練習したりしました。

競プロ以外

git

ライブラリ類は、基本gitで管理していてgithub上で見られるようにしています。大学時代にプログラミングの演習で使用を強要されたので使えるようになりました。取っ付きづらいツールですが、かなり便利です。

React

後で更新するかも

ここの章で競プロ以外に面白いと思っていることを色々書きたいと思ってましたが、書き始めてから時間が経ちすぎて忘れてしまいました。 思い出したら更新します。

次の目標

AtCoder青を目指して精進していきますが、距離感的にまずはCodeforces紫を中間ポイントとして地道に頑張ります！

反省

だらだら書いていたら、いつまでも公開できなくなっていたのでとりあえず公開することにしました。 気に入らないところは後で更新します。

ヒューリスティックコンテストで大量テストケースを一気に実行したい！

本記事は、競プロ Advent Calendar 2021の12/7の記事です。 （12/18に遅刻投稿しました。）

競プロ Advent Calendar 2021 - Adventar

2022-08-21 更新: シェルスクリプトの実行コマンドを追記
2023-01-28 更新: xargsコマンドの注意点を追記

こんにちは、shu8Creamです。
この記事では、AtCoder Heuristic Contest（以下AHC）に参加したい人・参加し始めた人向けに、大量テストケースの試し方を解説します。
なお、僕がAHCで使用している言語はC++であるため、他言語を使っている場合参考にすることが難しい場合がありますのでご了承ください。

なぜ大量テストケースを実行したいのか

AHCでは、ツールの中に50~100個のテストケースが与えられることが多いです。 スコアの改善度合いは、多くの場合、テストケースを実行して平均を取ってみなければ真に改善されているか判断がつきません。（50個のテストケースでは足りない場合がほとんどかも）
そこで重要なのが大量テストケースの実行です。

入力の受け取り方

まずは入力を受け取りましょう。 AHCは普段のアルゴリズムのコンテストとは違い、入力がとても多いため、コピペでターミナルなどに貼り付けて実行すると、前の実行結果が遥か上に消えていってしまいます。 この状況をファイル入力する方法で改善していきます。

  1. ツールをローカル環境にダウンロード（図１）
  2. ファイルを解凍し、扱いやすい階層に配置する（図２）
  3. tools/in/ ←この階層の下にテストケースがたくさん入っているのでこれを元に実行時に入力を行う（図２）
  4. ./a.out<tools/in/0000.txt のように実行

図１
図２

これだけで大量の入力をわざわざコピペする必要がなくなります。 tools/in/0000.txtの赤字部分を変更すればさまざまなテストケースが試すことができます。 「ツールは使わないし必要ない」と思ってダウンロードしていなかった方もテストケースが入っているのでダウンロードしてみましょう。 Webビジュアライザからテストケースのみをダウンロードすることもできます。

出力の仕方

C++の場合、コンパイル後に実行ファイルが生成され、それを実行します。 実行時に以下のようにするだけで好きなファイルに書き込みができます。

./a.out < ./in/0000.txt > ./out/0000.txt

厳密に言うと、このコマンドでは標準出力をoutディレクトリ配下の0000.txtというファイルに書き込むことができます。

別の方法として、コード上でどのようにファイル出力するかを記載する方法があります。 どのようにするかコードを見ながら解説します。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(n); i++)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// ①僕は元々出力デバッグ用に使っていました。
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int N = 400;
const int M = 1995;

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

// ②ファイル出力のためのお作法
    #ifdef _DEBUG
    FILE *fp;
    fp = fopen("./tools/out/0000.txt", "w");
    #endif

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Input();
    
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//③実際にファイルに書き込むための部分
    #ifdef _DEBUG
    if(isUse[i]){
        fprintf(fp, "%d\n", 1);
        connected[i] = 1;
    }else{
        fprintf(fp, "%d\n", 0);
        connected[i] = 0;
    }
    #else
    if(isUse[i]){
        cout << 1 << endl;
        connected[i] = 1;
    }else{
        cout << 0 << endl;
        connected[i] = 0;
    }
    #endif

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//④これもファイル出力のためのお作法
    #ifdef _DEBUG
    fclose(fp);
    #endif
}

#ifdef ここに好きな名前

上記のような形で宣言して、#else, #endifを駆使して分岐を書くことによってコンパイルするものとしないものを選ぶことができます。 僕の場合、この機能を利用することで、

g++ -std=c++17 -D_DEBUG

赤字部分をつけるかどうかで、ファイル出力するしないを自在に選ぶことができます。 僕は出力先を②のように指定しています。toolsフォルダの中にoutフォルダを作成して、そこにテストケースごとに出力して見やすくしています。

もっと便利にするために

ファイル出力が自由にできるようになりましたが、コンパイルコマンドの記述量が増えてしまいました。 この記述を楽にするために、alias機能を利用します。 ターミナルでは、特定の記述に対して呼び出し方を決めることで独自のショートカットを作ることができます。 僕が使っているものだと、

alias a='./a.out'
alias g='g++ -std=c++17 -O3'
alias gd='g++ -std=c++17 -D_DEBUG'

alias gs='git status'

個人的にはgit系はもっと登録していますが、競プロの用途だと上3つを多く使用しています。 AtCoderのYouTube公式解説放送でsnukeさんが利用していたものを参考にしていたりします。

// 普通はこうしなくちゃいけない
g++ -std=c++17 -D_DEBUG ver1.cpp

// こっちの方が楽チン
gd ver1.cpp

実行がこれで随分と楽になります。

全テストケースの一括実行

ファイル書き込みできるようになったので、いよいよ複数テストケースを一気に実行します。 これを実現するため、僕は下記のようなシェルスクリプトを書いています。

#!/bin/bash
## ファイル名：exec.sh

S=$(printf "%04d\n" "${1}")
## N,Kを入力ファイルから取ってきてスコアファイルの中に記録
awk 'NR==1' in/${S}.txt >&2 > score/${S}.txt
./a.out < in/${S}.txt > out/${S}.txt 2>> score/${S}.txt

# 実行コマンド
seq 0 99 | xargs -P4 -I{} ./exec.sh {} # 0~99の入力ファイルを実行

これはAHC013参加後に作ったもので、参加中も似たようなものをPythonで書いて計測をしていました。 シェルファイルを作って、実行コマンドをターミナルなどで叩くと実行できます。実行コマンドは並列実行できるようにしていますが、並列化することでスコアに影響が出る可能性があるため検証が必要です。 並列化の性能は使用PCの環境に依存するため、確かめてから使用するか、1ケースずつ実行する（-P4を外す）と良いです。 このシェルファイルでは実行結果（実際に採点される出力）は標準出力へ、内部で計算しているスコアや実行時間、焼きなまし時の試行回数などは標準エラーへ出力しています。僕はscoreディレクトリ配下に各テストケースごとの結果ファイルが溜まるようにし、これを入力に平均スコアを算出しています。こうすることで、AHC013のようにN,Kが可変の場合どのケースで点が取れているのか、取れていないのか偏りを見る事ができます。
全テストケースのスコアを一覧で見ると、ある場合でのスコアの悪さに気づくことができ、何がボトルネックになっているか考察の助けになるでしょう。

※注意※
xargsコマンドを使用する場合、Permission deniedの類のエラーが出ることがあり、chmodコマンドでexec.shに実行権限を付与する必要があります。

おわりに

今回はヒューリスティックコンテストで大量テストケースを一気に実行する方法を紹介しました。
僕がAHCに参加し出した時、入出力、改善度合いの評価にとても苦労しまして、多くの初心者が苦労するポイントではないかと思い、今回記事としてまとめてみました。
この記事を参考に、コンテストへの参加者が少しでも増え、強くなる人が増えれば嬉しく思います。
最後まで読んでいただきありがとうございました。