AtCoder Heuristic Contest 030 参加記

AtCoder Heuristic Contest 030に参加し、275位でした。

FAチャレンジ

なるべく早くサンプルを提出するチャレンジです。（無意味） 負けました。問題を開くのが少なく見積もって3秒は遅れていたのが敗因です。

やったこと

雛型を作る

サンプルと同じことをするコードを今後の修正を加味しながらきれいに書き直します。この中でコストの計算方法の理解が正しいかなどを確認していきます。

https://atcoder.jp/contests/ahc030/submissions/50121556
絶対スコア：12696000000

\sum_{t=1}^{50} {N}^2 = 12696
であることがわかりますね。

ランダムにボーリングする

方針が立たないので適当にq1のクエリを繰り返しながら明らかに確定したタイミングで答えを決める形にします。 答えが確定したかを確認するのを O(N2 d M) かけるとして全部で O(N4 d M) 。間に合います。 答えが確定したかは、0の場所と被らずに油田を置けるかの判定を全ての油田について行います。（かなり簡易な判定）

https://atcoder.jp/contests/ahc030/submissions/50122609
絶対スコア：11981000000

微差ですね。

判定を賢くする

油田の数が多くなるとほとんど判定が効いていないようです。特定のマスについて、そこに被るように置く方法が1通りであるかの判定を追加します。

https://atcoder.jp/contests/ahc030/submissions/50123560
絶対スコア：10678000000

多くのケースにおいて全て埋めきる前に確定させられるようになりました。 実行時間が1.2sだったので、そろそろ気にする必要がありそうです。

順位表を見てみる

(2024-02-10T12:00:00+09:00)

2段になっておりサンプルの上に1段あります。 既にここは超えていますが、見逃している自明解があるようなので、これを探ってみます。

発見しました。サンプルと同じように進めて、見つかっているものの総和を比べると、ここになるようです。

https://atcoder.jp/contests/ahc030/submissions/50127581
絶対スコア：11411000000

組み合わせる

稀に全てのセルを探索しているので、組み合わせると改善するはず。

https://atcoder.jp/contests/ahc030/submissions/50127994
絶対スコア：10220000000

一次元化する

実行時間を改善するためグリッドを一次元化したりいろいろ工夫します。判定をいろいろ賢くして、まだ調べていない部分も確定する部分をちゃんと記録して、調べるときはそれを除くようにします。 かなり掘る回数を削減できました。

この過程で500回に1回くらいの確率でWAになるバグを見つけました。再現性がないとデバッグで困るのでrandom関数は決定的なものにしておいた方がいい気がします。

https://atcoder.jp/contests/ahc030/submissions/50255771
絶対スコア：5415000000

情報量を使う?

掘る場所を改善できる気がします。掘る候補についてそこを掘ったときに得られる情報量を考えて、エントロピーを計算すれば、いい場所を掘るようになりそうです。ただ、実装が面倒だし、TLEになる気もします。

同じ形のときがある

同じ形の油田が２つあるとそのどちらなのかが特定できません。このようなケースがだいたい7.5%ほどあります。２つあるなら２択まで絞れた時点でどちらかに決めるような処理を入れました。

候補が複数あるものを適当に決めて矛盾があれば候補からはずす

やりすぎるとすぐTLEするので候補が多いものに絞った上で、残り時間が少ないと判定を飛ばすようにした。

掘る場所の選び方を工夫する

確定していないものから一様ランダムに選んでいたが、確定している場所の近くは選ばれにくくした。

https://atcoder.jp/contests/ahc030/submissions/50275514
絶対スコア：4957000000

感想

結局占いは使えませんでした...

AtCoder Heuristic Contest 027 参加記

AtCoder Heuristic Contest 027に参加し、273位でした。

時系列

とりあえず

サンプルのdfsと同じものを実装する。 スコアの計算を実装する。

以下、特に明記しない場合はシードが1~100のときの平均
Average = 21991473.54

RDLUの順番を変える

24通りを試し、最良を選択する

Average = 19521742.3

もっとランダム

各マスでランダムに優先順位を決める。 20000回程シミュレーションできた。

Average = 21251525.91

あんまりよくなっていない

現在の解からランダムに派生

ちょっと寄り道したり、省略したりしてみて改善するなら採用を繰り返す。変化が小さいのですぐに局所解になったり、広い盤面だと計算に時間がかかって十分に派生させられないので、いろいろ残念。大きい変化を頑張って採用できるようにする案もあるが、次の手に。

Average = 18365379.48

15000000くらいなら提出する気になるかな...

DFSから変更

DFSは実装が簡単だが、無駄な移動が多い。 なるべく少ない移動ですべてのマスを少なくとも一回通る方法について考える。 これは巡回セールスマン問題（TSP）なので、条件つきでの近似解法について調べる。 三角不等式が成り立つときの問題をMetric TSPというらしい。 この条件下ではDFSのルートから既に行ったことのある場所をとばしてルートを決定していくというのがあるらしい。 クリストフィードのアルゴリズムはよくわからなかった。O(n3)らしいので今回の条件だと使えない？ RDLUの順に評価するDFSを変形する形で実装してみる。

Average = 16936320.88

思ったより改善した

24通り試す

Average = 16144839.97

まだTSPが不完全...。 グリッド上のTSP解法は確実に論文があるはずだが、検索能力がないので見つけられない。 Bing AIにきいてみるとFutureの記事を提案されるがこれは一般的なグラフの解法。 食い下がると、次数5以下の場合の多項式時間アルゴリズムを出してくれる。そんなものが存在するのか...。英語論文を読む気にならない

2-optを使ってみる

Average = 15892483.36

とりあえずTSPは十分と思って、ここから適当に遷移させる。

適当に山登り

Average = 14025677.55

結構改善した

遷移先をいい感じに評価

汚れが大きいところを通るものを選ぶようにする

Average = 13801249.45

局所最適解に陥ることが多い

探索幅を広げる

TSPの後、改善する手順を繰り返す。 改善する段階は重みをつけているので一意だが、TSP解がランダムなのでいろいろな解がえられる。

Average = 13567886.96

TSPがいまいち

そもそもTSPが最適でないし、多様性もない

TSPの最善でないものもいろいろ採用してみる

Average = 13178283.81

遷移先を増やす

Average = 13213827.0

収束の速いケースでは改善したが全体としては悪化

汚れやすい場所を探す

入力生成方法を読むと、1~20の汚れやすいゾーンがある。汚れやすい場所でないところは10以下で汚れやすい場所は最大1000なので、かなり差がある。実際どのくらいかわからないが、汚れやすい場所をそうでない場所の10倍以上通るくらいがよさそう？

10より大きい場所だけでTSPを解けばいいのでは？

間に合わず 悲しい

感想

結構いいアイディアが思いついたと思ったけど、実装しきれず... 参加賞が200人対象なので頑張ったが、さすがに届いてなさそう

AtCoder Heuristic Contest 025 参加記

AtCoder Heuristic Contest 025に参加し、185位でした。

やったこと（時系列）

適当に原型を作る

d[i] = i % D

とする。 https://atcoder.jp/contests/ahc025/submissions/46619584

上の並んでいる部分。みんな考えることは同じやね。

考える

原型を改良する方向で考える。Dが大きいときは、ソートして最小と最大を近づければそれっぽくなりそう。


2 \le D \le 25,


8D \le Q \le 1600D,

Qが最小のときでもギリギリ、ソート出来そう。

ソートの比較

ソートの候補は

要素数25（一致する数字はなし）で、それぞれ106回実行したときの比較回数。

二分挿入ソートは挿入ソートの挿入位置を二分探索で求めるもの。通常、挿入コストが重いので使われないが、比較コストはこの中で最も低いようだ。

最悪でも要素数の4倍未満なので必ずソート出来る。

N = 25
t = 0
for i in range(1, N):
    t += i.bit_length()
print(t) # 94

最悪の比較回数は上のコードで求まる。

大小関係の保存

Qが小さいのでちゃんと最適な質問の仕方をしたい。


x \le y \land y \le z \to x \le z


\operatorname{Weight} \{ a \} \le \operatorname{Weight} \{ b \} \leftrightarrow \operatorname{Weight} \{ a,c \} \le \operatorname{Weight} \{ b,c \}

みたいな性質は使いたい。

ソートしたあと上と下を近づける

大小関係についてきちんと保存して、上記の性質を利用して無駄なクエリを排除するコードを書いてみたものの、うまく動かなかったので、実装コストの軽い方針で進める。 はじめに二分挿入ソートでソートしたあと、要素が2つ以上のなるべく大きいグループからランダムに1つ選び、最も小さいグループに移動させる。これで改善する場合は採用し、新しいグループの挿入位置を二分探索で調べる。

提出 https://atcoder.jp/contests/ahc025/submissions/46724103

結構いいスコア

繰り返す

上の方法では最も大きいグループのどれを移動させても改善しない状態に収束するので、収束が確認できたら初期解をランダムに作成し同じ操作をする。新しく作った解の最大最小のグループを元の解のものと比べて、どちらも改善しているなら採用する

提出 Submission #46742799 - AtCoder Heuristic Contest 025

収束するまでの操作は回しきれないものから30回程のものまである

D=2のときについて考えてみる

シード0~999の1000ケースについて--D=2で実験してみたところスコアの平均は31858.2だった。

解の探索範囲を広げるため、大きい方から小さい方に動かして悪化する場合もそれを採用することにした。スコアの平均は57360.4だった。 悪化する場合は選択せずに選び直すという処理はよかったようだ。

単に2つを比べて近づけていくのはあんまり賢くない気がするが特によい方法が思いつかない。

問題の都合上、少し改善が難しい。力を出し切った感覚はないが、十分なスコアは出ていそうだし、疲れたのでここで終了。結局3回しか提出しなかった。

パソコンを買いました。

競技プログラミング用にパソコンを買ったので、環境構築を全部書きます。

目標はWSL+VSCodeでC++を実行できるようにして、atcoder-cliで提出出来るようにすることです。

パソコン

Lenovo IdeaPad Slim 170 14型 (AMD) 49,830円
プロセッサー: AMD Ryzen™ 5 7520U (2.80 GHz 最大 4.30 GHz)
初期導入OS: Windows 11 Home 64bit
グラフィックカード: AMD Radeon™ 610M グラフィックス
メモリー: 8 GB LPDDR5-5500MHz (オンボード)
ストレージ1: 512 GB SSD, M.2 PCIe-NVMe Gen4 QLC
ディスプレイ: 14" FHD液晶 (1920 x 1080)
重さ: 1.4kg

パソコンに詳しくないので、5万円以下でなるべく性能がいいらしいものを買いました。（参考）
普段使いは生協で買ったLIFEBOOKなので、重さに驚きました。

パソコンのセットアップ

地域を設定したりします。

デバイスの名前はLAPTOP-KP-shogoにしました（後から変更できます）。

Microsoftアカウントは既に持っていますが、新規にメールアドレスを取得してみます。名前を姓名別に入力させるフォーム…。

サインインしてPINを設定出来たらあとは全部スキップして完了。

WSLをインストール

PowerShellを管理者として実行

wsl --install

指示通り再起動する

Restart-Computer

これで再起動できる（手動でいい）。 再起動すると、Ubuntuのターミナルが開かれた状態でusernameを入力するよう指示があるので入力する。次にパスワードを入力するよう指示があるので入力する（入力時、画面に文字が出ない）。もう一回パスワードを入力すると設定完了。 パスワードは簡単にしておいた方がいい。

VS Codeをインストール

Microsoft Storeにもありますが、公式ページからインストーラーをダウンロードしている人が多いのでそっちにします。

https://code.visualstudio.com/download

にアクセスして、WindowsのUser Installerのx64をクリック。 VSCodeUserSetup-x64-1.81.1.exeがダウンロードされるので実行。

使用許諾契約書が出るので同意

インストール先を指定できますが、デフォルトの C:\Users\username\AppData\Local\Programs\Microsoft VS Codeにしておきます。

追加タスクを選択できます。せっかくなので全部チェックしておきます。

インストールを押して完了です。

VS Codeに拡張機能を追加

拡張機能の

をインストール

VSCodeとWSLの連携をとる?

左下の><みたいなのを押して、Connect to WSLを選択

左下が><WSL-Ubuntuになる

これでVSCodeからWSLのファイルを触れるようになる

ターミナルを開いて

shogo314@LAPTOP-KP-shogo:~$

のように表示されている

コンパイラをインストール

ターミナルで

sudo apt-get update
sudo apt install build-essential -y
sudo apt install gdb -y

を実行

g++ --version

で正しく表示されたらOK

VS Codeに拡張機能を追加2

を入れる

試してみる

shogo314@LAPTOP-KP-shogo:~$ mkdir AtCoder/ABC/abc211/a -p
shogo314@LAPTOP-KP-shogo:~$ cd AtCoder/ABC/abc211/a
shogo314@LAPTOP-KP-shogo:~/AtCoder/ABC/abc211/a$

VSCodeで/AtCoder/ABC/abc211/を開いてa/にmain.cppを作る

#include <iostream>
int main()
{
    int A,B;
    std::cin >> A >> B;
    std::cout << (float)(A - B) / 3 + B << std::endl;
}

拡張機能が働いていることがわかる。 ファイルを保存して下を実行

$ g++ a/main.cpp
$ ./a.out
300 50
133.333

g++がちゃんと使えている

atcoder-cliをインストール

Python3をインストール

sudo apt install python3

既にインストールされてる?

$ python3 --version
Python 3.10.12

Pythonをインストールするとpipもついてくるはずだけど、なかったのでインストール。

pip3をインストール

sudo apt install python3-pip -y

Node.jsをインストール

curlは既にインストールされている node.jsはバージョンが結構複雑らしい

Node Version Managerをインストール

https://github.com/nvm-sh/nvm

curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.5/install.sh | bash

Node.jsをインストール

ターミナルを開き直す

nvm install node
npm install -g npm

online-judge-toolsをインストール

pip3 install online-judge-tools

pip listだと表示されるがojが認識されない。 ターミナルを開き直せば使えた。

atcoder-cliをインストール

npm install -g atcoder-cli

試してみる

oj login https://atcoder.jp
acc login

ログイン

$ cd ~/AtCoder/ABC
$ acc new abc210

abc210/aの中にmain.cppを作る

#include <iostream>
int main()
{
    int N, A, X, Y;
    std::cin >> N >> A >> X >> Y;
    std::cout << std::min(N, A) * X + std::max(0, N - A) * Y << std::endl;
}

oj t

が実行できない テストケースのディレクトリがtestsに作られたのにtestを参照している。とりあえずディレクトリ名を変更して実行。 正常に動くことが確認できる。

acc submit main.cpp

提出成功。テストケースのディレクトリ名を変えたせいでテストしてないけど大丈夫?みたいなのが出た。

atcoder-cliの設定

$ acc config default-test-dirname-format test
$ acc config default-task-choice all

テストケースのディレクトリ名を変更する。 コンテストを選んだときすべての問題のディレクトリが作成されるようにする。

$ acc config-dir

で設定用のディレクトリがわかるので、それを開く。 ~/.config/atcoder-cli-nodejs ここにcppディレクトリを作りtemplate.jsonを置く

{
    "task":{
        "program": ["main.cpp"],
        "submit": "main.cpp"
    }
}

main.cppも作る。 テンプレートを適当に作る。

acc config default-template cpp

これで設定したテンプレートが使用できる。

ライブラリを使えるようにする

仮にac-libraryを使ってみる

$ cd ~
$ mkdir library
$ cd library
$ git clone https://github.com/atcoder/ac-library.git
$ cd ~/AtCoder/ABC
$ acc new abc206

abc206を開く d/main.cppを

#include <bits/stdc++.h>
#include "atcoder/dsu"

int main()
{
    using namespace std;
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i; i < N; i++)
        cin >> A[i];
    atcoder::dsu uf(200001);
    int ans = 0;
    for (int i = 0; i < N / 2; i++)
    {
        if (!uf.same(A[i], A[N - i - 1]))
        {
            uf.merge(A[i], A[N - i - 1]);
            ans++;
        }
    }
    cout << ans << endl;
}

にする

$ cd d
$ g++ main.cpp -I ~/library/ac-library
$ oj t

ac-libraryをコンパイル出来ている。

verification-helperをインストール

これだとAtCoderにしか提出出来ないので、インクルードしているものを自動で展開できるようにする。

$ pip3 install online-judge-verify-helper

これでインストールできる。念のためターミナルを開き直して

$ oj-bundle main.cpp -I ~/library/ac-library > a.cpp

展開したものが標準出力に出るので> a.cppを付けて出力先をファイルにする。 展開したいものは<atcoder/dsu>のように<>で囲んでいると駄目で、""で囲む必要がある。

CPLUS_INCLUDE_PATHを設定

これまでだとVSCodeの拡張機能が"atcoder/dsu"を認識できておらずエラーが出ていた。 ホームディレクトリに.bash_profileを作り

export CPLUS_INCLUDE_PATH=~/library/ac-library

と書く。2つ以上設定したい場合は:で区切るらしい。'/home'から書いた方が確実かも。 ここのファイルはbashを起動したときに実行されるのでターミナルを開き直す。

echo $CPLUS_INCLUDE_PATH

で表示されてたら成功。

これでエラーが出なくなった。またg++を実行するときに-I ~/library/ac-libraryを書かずとも動くようになった。 しかし、oj-bundleは書く必要がある。

設定を調整

if(1)
{
}

より

if(1){
}

が好きなのでフォーマッタの設定を変える。 設定を開く。Ctrl+,で開ける。 C_Cpp: Clang_format_fallback StyleがデフォルトだとVisual StudioになっているのでGoogleに変える。

トラブル発生

VSCodeを開き直すと急にojやoj-bundleが使えなくなった。acc check-ojは使えるし、動いているのでPATHの問題っぽい。 home/shogo314/.local/bin/oj --versionが動くのでこれを呼べるようにすればよい。 ~/.bash_profileに

export PATH="~/.local/bin:$PATH"

を追加する。

おわり

結構大変だった。

ライブラリを作る（執筆中）に続く…

AtCoder Heuristic Contest 022 参加記

AtCoder Heuristic Contest 022に参加し、442位でした。

自己紹介

AtCoderはshogo314でやってます。現在のHeuristicレートは1279です。正直アルゴに比べて苦手意識があります。

やったこと（時系列）

環境整備

多くのテストケースで実行してくれるようにする。

サンプル

  • i番目の出口セルの位置についてPの値を10∗iに、出口セルが存在しない位置は0に設定する
  • 各ワームホールについて、y=0,x=0で1回計測し、出口セルの中でPの値が計測値と最も近いものを推定結果として回答する

シードが0~99のときの平均
Score = 61006.45
Number of wrong answers = 70.54
Placement cost = 58216412.0
Measurement cost = 80050.0
Measurement count = 80.05

計測回数を増やす

とりあえず100回にする。

Score = 193196.03
Number of wrong answers = 54.96
Placement cost = 58216412.0
Measurement cost = 8005000.0
Measurement count = 8005.0

測定しないセルを均す

  1. 出口セルがないところについて始め0にする。
  2. その場所と上下左右の5つの平均に変更する。 2の更新を収束するまで繰り返す。高々500回で収束した。
    この方法は結構悩んで思いついた。

Score = 1043108.47
Number of wrong answers = 54.96
Placement cost = 4380140.38
Measurement cost = 8005000.0
Measurement count = 8005.0

シード0

出口セルの温度を並び替え

出口セルははじめ、ソートされているためそこそこ綺麗にならんでいるが、最適ではない。

(0,0)に近いセル程温度が小さくなるようにした。

Score = 1273992.77
Number of wrong answers = 54.87
Placement cost = 2189832.44
Measurement cost = 8005000.0
Measurement count = 8005.0

提出したときの得点が46665734。
https://atcoder.jp/contests/ahc022/submissions/44593554

分散ごとに調整

現在、計測コストの方が配置コストより大きいので、不要な計測を減らす。

S=1のとき

計測回数1回（シード0~99）
Score = 46539724.16
Number of wrong answers = 0.0
Placement cost = 2184762.94
Measurement cost = 80050.0
Measurement count = 80.05

十分余裕がありそうなので出口セルごとの10度の差を狭める

差 4 5 6 7 8 9 10
Score 58501072.9 111642068.92 94756777.73 83280013.78 67687172.44 55751381.55 46539724.16
Number of wrong answers 5.62 0.97 0.52 0.04 0.01 0.0 0.0

5を採用

Score = 111642068.92
Number of wrong answers = 0.97
Placement cost = 606090.1
Measurement cost = 80050.0
Measurement count = 80.05

S=4のとき

計測回数と差で3分探索
計測回数10、差7にする

Score = 46035178.9
Number of wrong answers = 0.69
Placement cost = 1112203.54
Measurement cost = 800500.0
Measurement count = 800.5

S=9のとき

計測回数30、差9にする

Score = 21359258.4
Number of wrong answers = 0.69
Placement cost = 1785155.8
Measurement cost = 2401500.0
Measurement count = 2401.5

S=16のとき

差はなるべく大きくなるよう1000/Nとし、計測回数は差が大きいほど小さくなるよう600/(1000/N)とした

Score = 11425781.84
Number of wrong answers = 1.33
Placement cost = 3018406.44
Measurement cost = 4068960.0
Measurement count = 4068.96

S=25のとき

差はなるべく大きくなるよう1000/Nとし、計測回数はmin(10000 / N, 1280 / (1000 / N))とした。

Score = 5487954.38
Number of wrong answers = 2.92
Placement cost = 3018406.44
Measurement cost = 8099700.0
Measurement count = 8099.7

S>=36のとき

差はなるべく大きくなるよう1000/Nとし、計測回数はなるべく大きくなるよう600/(1000/N)とした。

S = 36
Score = 2139835.28
Number of wrong answers = 9.35
Placement cost = 3018406.44
Measurement cost = 9961740.0
Measurement count = 9961.74

あわせる

シード0~99
Score = 6659829.24
Number of wrong answers = 53.56
Placement cost = 2855445.76
Measurement cost = 8864140.0
Measurement count = 8864.14

シードが大きいときはコストが大きいが正答率が上がり、シードが小さいときは正答率をあまり下げずにコストを大きく減らせた。
提出したときの得点が171125470。ここまで出来たら水perfはありそう。
https://atcoder.jp/contests/ahc022/submissions/44599076

出口セルの右側のセルも計測する

出口セルの部分だけを計測する戦略だとそろそろ限界が近い（SだけでなくLやNで場合わけして調節すれば、おそらくもう少しだけ上げられる）。

S=100にして調べる。
Score = 5161.73
Number of wrong answers = 45.89
Placement cost = 3018406.44
Measurement cost = 9961740.0
Measurement count = 9961.74

これの改善を目標にする。
最大100段階にわけるため、差が10しかなく、標準偏差が100もあると100回計測しても区別できなくなってしまうのが問題である。

出口セルの右側のセルにも意味のある数字を設定することにする。
温度を100段階にわけていたのを右側も含めて10×10段階にする。
右側に出口セルが既にあり設定出来ない場合は無視する。

S=100
シード0
以前

以後
Score = 871116.64
Number of wrong answers = 8.1
Placement cost = 29694576.56
Measurement cost = 8405250.0
Measurement count = 8005.0

よさげ
S>=49のときはこちらを採用することにする。

Score = 6862727.85
Number of wrong answers = 41.5
Placement cost = 23144140.46
Measurement cost = 7641190.0
Measurement count = 7338.94

提出したときの得点が184347800。
https://atcoder.jp/contests/ahc022/submissions/44603614
おそらくSが大きいときは不十分。

スコアの期待値を計算したい

正規分布のあたりの知識が欠落しているので実際に確かめながらやってみる。
正規分布から値をサンプリングする関数はモダンな言語なら大抵用意されている。

正規分布から値をサンプリング

コード

import numpy as np
import matplotlib.pyplot as plt
dataSize = np.int64(1e5)
sigma = np.float64(1)
noise = np.random.normal(0.0, sigma, dataSize)
plt.figure()
plt.hist(noise, bins=100, density=True, color="b")
x = np.arange(-5, 5, 0.01)
gauss = 1/np.sqrt(2*np.pi*sigma**2)*np.exp(-x*x/(2*sigma**2))
plt.plot(x, gauss, "r--")
plt.xlabel('Deviation')
plt.ylabel('Density')
plt.show()

確率密度関数が


\frac{1}{\sqrt{2\pi{\sigma^2}}} \exp{\left(-\frac{x^2}{2{\sigma^2}}\right)}

であることが確認できる。

2個サンプリングして平均をとる

コード

import numpy as np
import matplotlib.pyplot as plt
dataSize = np.int64(1e5)
sigma = np.float64(1)
noise = np.random.normal(0.0, sigma, dataSize)
noise += np.random.normal(0.0, sigma, dataSize)
noise /= 2
plt.figure()
plt.hist(noise, bins=100, density=True, color="b")
x = np.arange(-5, 5, 0.01)
sigma /= np.sqrt(2)
gauss = 1/np.sqrt(2*np.pi*sigma**2)*np.exp(-x*x/(2*sigma**2))
plt.plot(x, gauss, "r--")
plt.xlabel('Deviation')
plt.ylabel('Density')
plt.show()

実は平均をとっても正規分布になる。標準偏差が1/sqrt(2)倍、つまり分散が1/2になっている。
一般化すると、n個の平均をとると、標準偏差は1/sqrt(n)になる。
100回計測して平均をとったとき、精度が上がったのはこれで理解できる。

正規分布の特定の範囲に入る確率

誤差がx以下になる確率を考える。実験してみる。

コード

import numpy as np
import matplotlib.pyplot as plt
import scipy
dataSize = np.int64(1e5)
sigma = np.float64(1)
noise = np.random.normal(0.0, sigma, dataSize)
noise.sort()
y = np.arange(dataSize)/dataSize
plt.figure()
plt.plot(noise, y, "b")
x = np.arange(-5, 5, 0.01)
erf = (1+scipy.special.erf(x/np.sqrt(2*sigma**2)))/2
plt.plot(x, erf, "r--")
plt.xlabel('Deviation')
plt.ylabel('ratio')
plt.show()

誤差がx以下になる確率、累積分布関数は


\frac{1}{2} \left( 1+\operatorname{erf}{\left( \frac{x}{\sqrt{2 \sigma^2}} \right)} \right)

となる。erfは関数が用意されているので、詳しい説明はしない。

特定の確率でおこる事象がk回起こる確率

1%の確率で起こる事象が100回中k回起こる確率密度関数

コード

import numpy as np
import matplotlib.pyplot as plt
from collections import Counter
dataSize = np.int64(1e5)
sampling = [(np.random.rand(100) < 0.01).sum() for i in range(dataSize)]
x, y = zip(*sorted(Counter(sampling).items()))
y = np.array(y)/dataSize
plt.figure()
plt.plot(x, y, 'o-')
plt.xlabel('times')
plt.ylabel('Density')
plt.show()

これはポアソン分布という。

確率pで起こる事象がn回中ちょうどk回起こる確率は、


\binom{n}{k} p^k {(1-p)}^{n-k} = \frac{n!}{k!(n-k)!} p^k {(1-p)}^{n-k}

である。ここでp=λ/nとすると下のようになり、


\frac{n!}{k!(n-k)!} {\frac{\lambda}{n}}^k {\left(1-\frac{\lambda}{n}\right)}^{n-k} = \frac{n!}{k!(n-k)!} \frac{{\lambda}^k {\left(n-\lambda\right)}^{n-k}}{n^n}

n→∞とすると


\frac{\lambda^k}{k!} e^{-\lambda}

となるのだが、これは使わない。

実際n=100、λ=1を入れてみると、


\binom{n}{k} \frac{{\lambda}^k {\left(n-\lambda\right)}^{n-k}}{n^n} = \binom{100}{k} \frac{99^{100-k}}{{100}^{100}}

k=0のとき0.3660
k=1のとき0.3697
k=2のとき0.1849
k=3のとき0.0610
概ね正しそうであることが確認できる。

予測スコアを計算して改善

予測スコアを求めてみる

武器は揃った。 0~1000の範囲に入らない場合、無理矢理この範囲に収めるため正確ではないのだが影響は十分小さいと考え無視する。

出口セルを100回計測するコードでスコアを求めてみる。
使うのは分散で場合わけした直前のコードを少し改善したもの。具体的には温度をi∗10からi∗10+5に変更した。

各シード値でのスコア

seed Score Number of wrong answers Placement cost Measurement cost Measurement count
0 90791 20 3098642 9500000 9500
1 29 58 1593386 6600000 6600
2 1 82 2636568 8900000 8900
3 13740360 0 1077830 6100000 6100
4 1 80 2219656 8100000 8100
5 1 89 3172916 9300000 9300
6 1 88 2420828 8900000 8900
7 306617 16 1980038 7100000 7100
8 1 86 2488344 8700000 8700
9 298 48 1283724 6100000 6100
10 8050058 0 2822272 9500000 9500
11 158 50 1664606 7300000 7300
12 2246726 7 1634262 7600000 7600
13 7878710 0 2992434 9600000 9600
14 281 48 1351002 6500000 6500
15 1 88 2745460 9300000 9300
16 1095 41 1813038 7800000 7800
17 29 56 3217714 9800000 9800
18 2917552 6 1585070 7300000 7300
19 8 64 1623344 6500000 6500
20 75 52 2718534 9400000 9400
21 40 57 1226772 6200000 6200
22 41 57 1171738 6200000 6200
23 6742754 1 2764590 9000000 9000
24 14 62 1048700 6200000 6200
25 8 64 1632254 6500000 6500
26 1 74 1989926 7400000 7400
27 1 86 3446052 9500000 9500
28 1 74 1775136 7600000 7600
29 3339282 5 1812890 7900000 7900
30 8126288 0 2605742 9600000 9600
31 6 65 1536048 7200000 7200
32 9 63 1913126 7000000 7000
33 22 60 1163680 6000000 6000
34 12540522 0 1374150 6500000 6500
35 42 57 1102706 6000000 6000
36 8251728 0 2918674 9100000 9100
37 1 85 3426578 8500000 8500
38 3 68 1874656 7100000 7100
39 1 73 1977426 7900000 7900
40 1 95 3440096 9800000 9800
41 10349996 0 2061840 7500000 7500
42 575523 14 1141832 6400000 6400
43 115872 19 2837540 9500000 9500
44 1 78 2108154 7900000 7900
45 1 86 2969928 8700000 8700
46 1 89 3435172 9200000 9200
47 1 76 2904854 8900000 8900
48 2 68 3488868 9900000 9900
49 1041387 11 1348552 6800000 6800
50 1 77 2191778 8500000 8500
51 27 58 1593368 7400000 7400
52 1 78 2022976 8000000 8000
53 8 64 1462500 7000000 7000
54 22 59 1694966 7100000 7100
55 8946113 0 2678040 8400000 8400
56 1949 39 1628258 6800000 6800
57 1 76 1944562 8200000 8200
58 1 73 1870680 7600000 7600
59 6 65 1481398 6800000 6800
60 1 94 3113594 9600000 9600
61 44507 23 3563216 9600000 9600
62 3 69 1498994 7100000 7100
63 3 67 2926834 9400000 9400
64 1 74 1755430 7500000 7500
65 1 86 2746564 9300000 9300
66 1 79 1990120 7900000 7900
67 2 70 1462828 7300000 7300
68 1 76 2547210 8300000 8300
69 1 80 2101772 8200000 8200
70 2 72 1833956 7600000 7600
71 11 61 2851206 9100000 9100
72 726 43 1779660 7500000 7500
73 1 97 3561452 9800000 9800
74 56591 24 1444866 6800000 6800
75 1 81 2070848 8100000 8100
76 8838478 0 2614166 8600000 8600
77 706 42 3063870 8900000 8900
78 1 80 2284820 8600000 8600
79 9994775 0 2005228 7900000 7900
80 1 76 2241496 8200000 8200
81 3 67 2788358 9500000 9500
82 9729016 0 2078532 8100000 8100
83 11 62 1971160 6900000 6900
84 13 62 1319316 6700000 6700
85 2 69 4028562 9500000 9500
86 2 72 1830988 7400000 7400
87 7 65 1516618 6700000 6700
88 8032289 0 2649752 9700000 9700
89 528062 13 2110828 8200000 8200
90 11 63 1160222 6300000 6300
91 1 74 1975500 7900000 7900
92 1 91 3127390 9500000 9500
93 1 98 2914300 9900000 9900
94 2 70 1673378 7000000 7000
95 1 80 3109064 9400000 9400
96 2 70 1585056 7200000 7200
97 1 83 2347484 8700000 8700
98 1 82 2552252 8400000 8400
99 344038 16 1581520 6500000 6500

Score = 1328337.49
Number of wrong answers = 54.86
Placement cost = 2189842.84
Measurement cost = 8005000.0
Measurement count = 8005.0

予測スコアを計算して出力する

各シード値での期待されるスコアと間違う数

seed Score Number of wrong answers Expected Score Expected Number of wrong answers
0 90791 20 277072 15
1 29 58 46 56
2 1 82 1 78
3 13740360 0 13740360 0
4 1 80 1 74
5 1 89 1 85
6 1 88 1 84
7 306617 16 935719 11
8 1 86 1 82
9 298 48 298 48
10 8050058 0 8050058 0
11 158 50 1833 39
12 2246726 7 5485169 3
13 7878710 0 7878710 0
14 281 48 351 47
15 1 88 1 82
16 1095 41 1095 41
17 29 56 70 52
18 2917552 6 5698342 3
19 8 64 19 60
20 75 52 117 50
21 40 57 50 56
22 41 57 98 53
23 6742754 1 8428442 0
24 14 62 27 59
25 8 64 15 61
26 1 74 2 70
27 1 86 1 78
28 1 74 3 69
29 3339282 5 5217628 3
30 8126288 0 8126288 0
31 6 65 22 59
32 9 63 22 59
33 22 60 42 57
34 12540522 0 12540522 0
35 42 57 65 55
36 8251728 0 8251728 0
37 1 85 1 79
38 3 68 6 65
39 1 73 3 68
40 1 95 1 93
41 10349996 0 10349996 0
42 575523 14 1405085 10
43 115872 19 282889 15
44 1 78 1 75
45 1 86 1 82
46 1 89 1 86
47 1 76 2 71
48 2 68 10 61
49 1041387 11 1041387 11
50 1 77 2 71
51 27 58 42 56
52 1 78 1 75
53 8 64 18 60
54 22 59 18 60
55 8946113 0 8946113 0
56 1949 39 3806 36
57 1 76 2 71
58 1 73 2 72
59 6 65 8 64
60 1 94 1 87
61 44507 23 265278 15
62 3 69 4 67
63 3 67 7 63
64 1 74 3 69
65 1 86 1 81
66 1 79 2 72
67 2 70 3 69
68 1 76 1 75
69 1 80 1 78
70 2 72 2 72
71 11 61 11 61
72 726 43 1418 40
73 1 97 1 92
74 56591 24 138160 20
75 1 81 1 73
76 8838478 0 8838478 0
77 706 42 232 47
78 1 80 1 77
79 9994775 0 9994775 0
80 1 76 4 67
81 3 67 20 58
82 9729016 0 9729016 0
83 11 62 102 52
84 13 62 30 58
85 2 69 2 69
86 2 72 2 70
87 7 65 10 63
88 8032289 0 8032289 0
89 528062 13 528062 13
90 11 63 40 57
91 1 74 2 70
92 1 91 1 87
93 1 98 1 88
94 2 70 5 66
95 1 80 1 77
96 2 70 3 68
97 1 83 1 80
98 1 82 1 79
99 344038 16 1312399 10

Expected Score = 1455039.86
Expected Number of wrong answers = 51.6
Expected Placement cost = 2189842.84
Expected Measurement cost = 8005000.0
Score = 1328337.49
Number of wrong answers = 54.86
Placement cost = 2189842.84
Measurement cost = 8005000.0
Measurement count = 8005.0

配置コストと計測コストは正確に計算できるが、間違う数はランダムである。 今回は間違う数の平均値をもとにスコアを計算したため、正確には期待値ではない。

全体的に間違う数が少なく出てしまっている。 そのわりにはスコアの平均値は1割程しか変わらない。これはスコアへの影響が大きい間違う数が0のときを正確に計算出来ているためだと考えられる。

予測スコアから計測回数などを調整する

計測回数と出口セルごとの温度の差の2つを変え、15パターンで予想スコアを計算し、最もよかったものを採用する。

Score = 6828002.87
Number of wrong answers = 53.9
Placement cost = 1888787.5
Measurement cost = 5612150.0
Measurement count = 5612.15

場合分けを使わずに、分散ごとに場合わけした場合と同じくらいのスコアを得られた。
提出したときの得点が217889721。
https://atcoder.jp/contests/ahc022/submissions/44638443
場合分けを詰め切れていなかっただけだろうが、出口セルを見るだけで、右側も見るようにしたものを超えることが出来た。

分散ごとに場合わけ

分散ごとに、計測回数と差の候補を変える。

Score = 7080872.04
Number of wrong answers = 53.5
Placement cost = 2844973.2
Measurement cost = 8782590.0
Measurement count = 8782.59

提出したときの得点が196923321。
https://atcoder.jp/contests/ahc022/submissions/44646344 むしろ下がってしまった。スコアの予測の精度が低いためだと考えられる。もう少し精度を上げる余地があるが、後回し。

抜本的な解決をはかる。

出口セルの右側のセルも計測するパート2

以前は右側がすでに決まっていた場合、右側の数字をそのままにしていた。しかし、これでは重なる場合があるので、2つのペアが重複なく選ぶようにする。

Score = 7187204.81
Number of wrong answers = 39.81
Placement cost = 15115268.0
Measurement cost = 5302670.0
Measurement count = 5107.82

提出したときの得点が246053584。
https://atcoder.jp/contests/ahc022/submissions/44681182
いい感じ

右側以外のセルも計測する

出口セルだけをみるケースのパターン数を減らし、右も見る、右と左も見る、右と左と下も見る、右と左と下と上も見るケースを追加した。

Score = 7450807.57
Number of wrong answers = 28.47
Placement cost = 26950566.86
Measurement cost = 7085074.0
Measurement count = 6699.85

提出したときの得点が230821137。
https://atcoder.jp/contests/ahc022/submissions/44683982
得点は下がってしまったが、相対スコアは上がった。

相対スコアを考えるために、テストケースごとに実際のスコアの最大値を求める

S=1、シード値0~299で計測回数と差を変えて最もスコアが高くなる物をしらべる LとNによって最適な計測回数と差はある程度決まると思っていたがそうでもない。

予想スコアがうまく働いていないと見て、とりあえず、S=1のとき(計測回数,差)=(2,5)に固定した方がいいか？

上下左右以外も見る

合計11カ所見る
Score = 7405218.39
Number of wrong answers = 24.16
Placement cost = 35002507.7
Measurement cost = 8271817.0
Measurement count = 7705.87
提出したときの得点が249240205。
https://atcoder.jp/contests/ahc022/submissions/44784661
Sが大きいときのスコアは大幅に改善したはずだが相対スコアはあまり上がらず。 たぶん0.00001が0.02になった、みたいな差。 この感じだとこれ以上頑張っても難しそう。時間もないのでここで断念。

感想

結構頑張ったけど、水perfが限界。やれることをやりきったわけではないが、やりきったとしても青perfは出せそうにないなあという気持ち。
ある程度機能する予想スコア計算が書けたのは嬉しい。

長期コンは疲れる。期間中あんまり精進が出来なかった。夏休みはまだまだあるので、精進するつもり。時間を取られすぎたから、AHC023は出ないかな。

ICPC2023 国内予選 参加記

ICPC2023国内予選にチームKSS908111314で参加し、17位で予選通過しました。

チーム

メンバーはhint908、sakasu1、shogo314（自分）。出場時のAtCoderレートはそれぞれ2039、1630、1626。阪大の3軍にあたる。チーム名はメンバーの名前から。

前日以前

チーム練とかは特になかった（エンジョイ勢なので）。jagは出てもいいかと思ったが、私は用事があったので提案せず。

kurehaに圧力をかけておくの図。

当日

12:00～16:30

自分は12時過ぎに会場入り。13時くらいには全員揃っていた。

14時頃、kurehaのパソコンがなぜかWifiに接続出来なかったので、急遽私のパソコンを使うことになる。全員練習問題を提出して実行方法を確認。

誰がどの問題を解くかを事前に簡単に決めておく。とりあえず全員1つずつ通せばいいだろうということで、Aはじゃんけんに勝ったsakasu、Bはshogoが担当することになる。

16:30～16:40

sakasuがAを解く。ちょっと詰まって9:21にAC。

sakasu「ごめーん」

16:40～17:05

shogoがBを解く。交代した時点で問題を読み終わっておらず、少し時間がかかって34:28にAC。

O(nm)で書いたが、O(n^2m^2)で書いた方が速かったかも。

17:05～17:30

kurehaはCをsakasuに投げて、DとEの考察。Dは高々7なので6以下になる場合を考えれば良い。

sakasuがCのコードを書くが出力がおかしい。

shogoはDとEを考えるがいいアイデアは浮かばず。

kurehaがEを書けそうというのでCのコードを印刷して交代。

17:30〜17:55

kurehaがEのコードを書く。

sakasuはCのデバッグ。

kurehaが一旦考察を整理したそうだったので、Cと交代を提案。

17:55〜18:03

sakasuCのコードを修正（添字を一個ミスってた）。1:32:10にCをAC。

18:03〜18:25

kurehaがEのコードの続きを書く。1:54:55にEをAC。

shogoはDを数に大小をつけて、適切に打ち切れば、十分短い時間で6つの数の全通りを試せることを証明。

18:25〜18:49

素直に5重for文を書くことを提案。

kurehaがDのコードをbitsetでいい感じに書く。

2:18:17にDを提出。

18:49〜19:30

3チーム進出条件の25位以内は十分達成しているだろうと思い、順位表を見に行く。15位、阪大内1位で驚く。FとGを解く気にならないので、順位表を眺める。

FとGの問題を見に行く。順位表を見る限り、難易度に差はあまりなさそう。

Fは書く気にならず。

Gはn≦60、m≦60という制約で何が出来るのか全くわからず。

Eの解法をkurehaに教えてもらったり、順位表を眺めたりして、時間を潰す。

shogo「mijingiriが4完だったら煽りに行こう」

時刻ごとの順位

表示してみるとおもしろいかと思ったが、よくある感じかも。

（グラフを表示するコード）

感想

国内予選通過への貢献としてはEを解いたkurehaがかなり偉い。Cを書いたsakasuも偉い。

ライブラリを印刷していなかったが、持ち込んでおけばFを書く気になったかも。

3人とも、国内予選通過は初（自分以外は国内予選自体初）なので不安もあるが楽しみ。