codingame:SPRING CHALLENGE 2023WOODリーグ ルール翻訳
こちらは年２回開催される、botプログラミングバトルCodinGameの「SPRING CHALLENGE 2023」のルールを翻訳したものです。 www.codingame.com
ツカモさん（tsukammoの収穫記）がルールを要約してくださるのが恒例となっていましたが、今回お忙しそうだったので、僭越ながら簡単に訳しました。
ツカモさんのようなわかりやすい要約ではなく、DEEPLにつっこんだものを簡単に修正したものです。記載内容の保証はできません。すみません。
5/26 18時ツカモさんのブログが更新されました。codingame:SPRING CHALLENGE 2023 ルール要約 - tsukammoの収穫記
目標
対戦相手よりも多くのクリスタルを獲得した状態でゲームを終了すること。
ただし、アリを直接コントロールすることはできない。アリはビーコンの存在に反応する。
ルール
ゲームはターン制で行われる。 各ターンでは、両プレイヤーは同時に任意の数のアクションを実行する。
マップ
マップはランダムに生成され、六角形のセルで構成される。
各セルはインデックスを持ち、最大6つのセルと隣接する。各方向には0から5のラベルが貼られている。
タイプがあり、そのセルが何を含んでいるかを示す。
0リソースが含まれていない場合。1卵が含まれている場合。(Level2 WOOD2)2クリスタル資源が含まれている場合。
また、各セルに含まれるresources（資源）の量も入力で与えられ、ゲーム中にアリがセルを収穫することで変化することがある。
また、セルに拠点がある場合もあり、プレイヤーのアリはここからゲームを開始することになる。
アリとビーコン
両プレイヤーとも、自分の拠点に数匹のアリが配置された状態でスタートする。プレイヤーはアリを直接動かすことはできないが、ビーコンを置くことでアリを動かすことができる。
プレイヤーは1ターンに何個でもビーコンを置くことができるが、各マスに1個ずつしか置くことができない。
ビーコンを置くとき、プレイヤーはそのビーコンにstrength（強度）を設定する必要がある。ビーコンの強度は重みのようなもので、それぞれのビーコンに送られるアリの割合を決定する。
つまり、ビーコンのstrengthが強ければ強いほど、自分のアリがそのビーコンに送られる割合が高くなる。
例
次の例では、strengthが2,1,2の3つのビーコンが存在する。
アリは1ターンに1セルの速度で移動し、指定されたビーコンへの最短経路を通るように最善を尽くす。
ターン終了後、次のターンが開始するまでの間に、既存のビーコンはパワーダウンし、プレイから取り除かれる。
ビーコンを使ってアリを配置し、自分の拠点と資源との間に収穫チェインを張ろう。
収穫チェイン
クリスタルを収穫して得点を得るには、資源と自分の拠点の間に、アリを含むマスが途切れることなく連なっている必要がある。
1ターンに収穫できるクリスタルの量は、チェインの中で最も弱いリンクと同じ、つまり連鎖を構成するセルのアリの数のうち、最も少ない数である。
収穫チェインは卵に対しても同様に機能する。 卵を収穫すると、資源と同じ数のアリが次のターンの開始時に自軍の拠点にスポーンする。 (Level2 WOOD2)
収穫量は各資源ごとに別々に計算され、それぞれの資源について、そのマスから自分の拠点までの最適な収穫チェインがゲームによって自動的に選択される。
行動
各ターンにおいて、プレイヤーは以下の行動を任意の数だけ行うことができる。
BEACONindexstrength：strengthの強度をもつビーコンをindexのセルに配置する。LINEindex1index2strength：index1からindex2までの道筋にあるセルすべてに、strengthの強度をもつビーコンを配置する。最短経路は自動的に計算される。WAIT：何もしない。MESSAGEtext: HUDの自分側にtextを表示する。
各ターンの行動順
LINEのアクションが実行される。BEACONのアクションが実行される。- アリが移動する。
- クリスタルが収穫され、得点となる。
- 卵が収穫され、新しいアリが拠点にスポーンする。(Level2 WOOD2)
勝利条件
マップ上のクリスタル総量の半分以上を獲得する。
100ターン後に相手より多くのクリスタルを獲得している。
敗北条件
プログラムが決められた時間内にコマンドを出力しない、または認識できないコマンドを出力した。
デバッグのためのヒント
タイルにカーソルを合わせると、ビーコンのstrengthなど、そのタイルに関する追加情報が表示される。
MESSAGE コマンドを使用して、HUDにテキストを表示できる。
ビューアの歯車アイコンを押して、表示オプションを追加する。
キーボードでアクションを操作する：スペースで再生/一時停止、矢印で1フレームずつステップする。
ゲームプロトコル
初期入力
最初の行: numberOfCells マップ内のセルの数を表す整数。
次のnumberOfCells行: セルをインデックスで並べたもの 各セルはスペースで区切られた8個の整数で表される
- タイプ:
1: 卵2: クリスタル0:それ以外 initialResources: ここにあるクリスタル/卵の量。- 6つの
neigh変数： 6つそれぞれが各方向に対応し、隣接セルのインデックスを含む。隣接セルがない場合-1(Level2 WOOD2)
次の行: numberOfBases このリーグでは1が与えられる。
次の行: numberOfBases 自軍の拠点が存在するセルのインデックスを表す整数。
次の行: numberOfBases 対戦相手の拠点が存在するセルのインデックスを表す整数。
毎ターンの入力
次のnumberOfCells行: 1つのセルにつき1行、セルのインデックスの順に並ぶ。1つのセルにつき3つの整数が入力として与えられる。
resources: そのセルにあるクリスタル/卵の量。myAnts: そのセルにいる自軍のアリの数。oppAnts: そのセルにいる対戦相手のアリの数。
出力
あなたの行うすべての行動を;で区切って1行で出力する。
BEACONindexstrength: 1ターン持続するビーコンを設置。LINEindex1index2strength: 2つのセル間の道筋に沿ってビーコンを配置する。WAIT: 何もしない。MESSAGE: 自軍のHUDにテキストを表示します。
制約
numberOfBases = 1
各ターンの応答時間 ≦ 100ms
1ターン目の応答時間 ≦ 1000ms
5/26 17時ごろ ainemがWOOD1リーグに昇格し、LEVEL2のルールが開放されたので、追記しました（緑帯の文）
これであなたもでぶ間違いなし！レシピ集
こちらはでぶ Advent Calendar 2022の17日目の記事となっております。 競プロの話は出てきません、悪しからず。
タイトルから、コスパ良くカロリーを摂るレシピがたくさん載っていると思ったそこの貴方！！！ 甘いっ！！ *1 もっと心のカロリーを燃やせよ！！！
この企画の主であるshojin_proさんはみんなより少しだけ世界に占める割合が多いことで知られていますが*2 もしかしてでぶは怠惰だと勘違いしていませんか？？ 身体に金をかけるのがモデルとボディビルダーだけだと思っていませんか？違うだろっ！！この身体に幾らかけたと思ってるんだ！！ そう、でぶとはたゆまぬ精進を積み重ねた先に辿り着ける一等賞、飽くなき食への探究心の結晶、誇れるボディ人生の勲章であるっ！！！！
小腹ばっか空かせてないで、大腹空かせよ！！！！
ということで、でぶ界のお口担当こと私あいねむがみなさんに食べて欲しい、おいしいレシピを紹介します。
フランゴピリピリ
鶏肉をスパイスに漬けて焼く料理で、フランゴ(鳥)ピリピリ(辛い)の意。
ファイナルカレー
カレースターと名高い水野仁輔氏が、欧風カレーとインドカレーのいいとこ取り、カレーの究極系を目指したレシピ、それがファイナルカレー。
本当のレシピは本を買って手に入れてほしいところではありますが、ググると出てきます。
このレシピは本当に美味しくて、絶対失敗しないので、我が家が人んちに持っていくカレーの定番だったりします。肉を漬けておかなければいけないのがちょっとネックでミキサーも必要なのでハードル高めですが、味は保証します！！！
無心に玉ねぎを炒める、その時間が何より尊い
完成写真は撮り忘れてた。
ステーキライス
最後に簡単なものを。 冷凍のチャーハンを炒めます。
冷凍のサイコロステーキを炒めます。
フライパンに残った油で目玉焼きを焼きます。
ワインと合わせて最高！！！
最後に…あー、えーともっと心のカロリーを燃やせよ！！！*3
*1:カロリー/価格の高い食べ物としてオールドファッションハニーやブラックサンダーが知られているぞい
*2:出典を探したけど体重記録ツリーが消えていた…
*3:私も意味はわかっていません。どんな意味?
M1 MacにPyPyをインストールした記録
PyPyのM1Mac向けバージョンがリリースされ、インストールにむちゃくちゃ苦戦したので、記録。
PyPy 7.3.10 is out! https://t.co/Y6whfKLmnJ
— The PyPy Project (@pypyproject) 2022年12月6日
It's a huge collection of tiny features, including a number of small performance improvements, representing about night months of work.
Thanks to all contributors and our release manager Matti Picus for all the hard work!
PyPyの入手
ここから躓く。 https://www.pypy.org/download.html ここからダウンロードしろって書いてあるけど
「おめーのPyPyねーから！」と言われ、心がくじける。PyPy出鼻くじかれる pic.twitter.com/hawxyQkzEH
— ainem (@ainemixion) 2022年12月7日
http://downloads.python.org/pypy/
からダウンロードできそうなことを知る。
pypyのインストール
どうやらhttps://doc.pypy.org/en/latest/build.html を見ながら自分でビルドしなければないっぽい。 このドキュメントに沿って行っていくので、詰まったところまで飛ばして読んでください。
Clone the repository
hg cloneが出てきて、そんなコマンドこのマックには存在しないよと言われて調べる。
ググラビティが低い、いや、私の検索能力が低い。
If you prefer to compile your own PyPy, or if you want to modify it, you will need to obtain a copy of the sources. This can be done either by downloading them from the download page or by checking them out from the repository using mercurial. We suggest using mercurial if you want to access the current development. mercurialをインストールしよう。
mercurialのインストール
どうやらmercurialというツールで、リポジトリのクローンなどが行えるらしい。
brew install mercurialする。
hg clone https://foss.heptapod.net/pypy/pypy pypyどんだけpypy言わすのよ！ｗ
Install build-time dependencies
On Mac OS X: Currently PyPy supports both building on both Apple Silicon (M1, Arm64) and X86_64. You must use an appropriate toolchain for building: either arm64 or x86_64. “Fat” universal2 builds are not supported. Currently tcl/tk is not supported, set export PYPY_PACKAGE_WITHOUTTK=1 when packaging to avoid attempting to build the _tkinter extension library. Most of the build-time dependencies are installed alongside the Developer Tools. openssl still need to be installed for tests, and a brew-provided pypy will speed up translation:
xcode-select --install /usr/local/bin/brew install openssl pypy pkg-configAfter setting this up, translation (described next) will find the libs as expected via pkg-config.やったーMacのところだけ簡単だーって思ったけど
pypy: The x86_64 architecture is required for this software.
のエラーがでて進めない。 なんとpypyをビルドするためにpypyをインストールしなければならないらしい。 それなんて無理ゲ？
brewにまだ存在しないので無理ですね
— ✹うにだよ✹ (@u2dayo) 2022年12月7日
PyPy使って約20分かかって、CPythonだとその2,3倍かかるみたいなので、1時間くらい待てばいけそうです
CPythonに依存パッケージ入れて、この後の工程でPyPyの代わりにPython使えばいけるかもしれません pic.twitter.com/iA9kzOULnc
unidayoさんのありがたい助言により、Cpythonつかってビルドすることに。
Run the translation
translationがなんのことかわかりませんが（ビルドとどう違うの…？）
推奨されている
pypy ../../rpython/bin/rpython --opt=jit
を行うに当たって、pypyのインストールが必要なので、このコマンドは使えません。
途方に暮れてpypyフォルダを眺めていたところMakefileを発見
あ、これ普通に
make
でビルドできるんじゃね？
ここからが地獄だった…
python2がない
まずrpythonはおそらくpython2で書かれており、最新のmacではpython2が抹消されているため、python2をインストールし、pathを通す(しかもpython2ではなくpythonで通す)必要がありました。
これは
pyenv install 2.7.18
して
.zshrcに
export PATH=$PATH:/Users/ainem/.pyenv/versions/2.7.18/bin/
PATHを通せばおｋ
pycparserがない
pip2 install pycparser
python2用なのに注意
expatがない
これめっちゃ困りました
expat何者なんだ… pic.twitter.com/QfTP5NO34l
— ainem (@ainemixion) 2022年12月7日
expatって検索しても出てこないし… https://docs.huihoo.com/pypy/2.5/windows.html#the-expat-xml-parser こいつです
cmake automake autoconf
expatを入れるために
brew install cmake
brew install automake
brew install autoconf
しました
やっとビルド
さて、pypyフォルダで
make
を実行すればなんかきれいな図形
うお！！なんかすすんだ！！！ pic.twitter.com/dMNLVsAuQ3
— ainem (@ainemixion) 2022年12月7日
Build cffi import libraries for the stdlib
ここでM1Macはtkinterが無理らしいので
PYTHONPATH=../.. ./pypy-c ../../lib_pypy/pypy_tools/build_cffi_imports.py
これに--no-tkinter_みたいなオプションをつけなければならない（画像どこかになくしてしまって正確なコマンドがわからない）
Packaging (preparing for installation)
ここはつまづかなかった
python pypy/tool/release/package.py --archive-name=pypy-VER-PLATFORM
シンボリックリンクの指定
さて、ここでやっとダウンロードしたものたちの出番 解答したファイルの中から
./bin/ ./include/pypy3.8/include ./lib/pypy3.8
というフォルダたちをどこか適当なところ(opt/pypyとかを推奨されている)に置く そしてbinにあるpypy(シンボリックリンク)をいい感じのところに置いて、さらにはPATHを通せば完璧 PATHの通し方、わからん…
めっちゃ怒られる
開発元を検証できない実行ファイルのため、めちゃくちゃ怒られる、というかFinderからじゃないとこの警告を解除できないので実質詰み…
https://mac-tegaki.com/basic-usage/sierra-mac-app-store-permission.html ここでこの記事を見つける なんか危険そうだけどとりあえずこれをしないと実行できないのでやっておく(ここのコマンドは上の記事から調べて、自己責任でお願いします！)
これでPYPY環境のできあがり！！！！！
うーん質問あっても答えられるかわかりませんが、一つの記録として！
AHC002 Walking on Tiles 〜実装編〜
問題文を理解したところでまずやりたいこと、アイデア出しですよね。
いろんな戦法が浮かびますよね。いろんな戦法が浮かびましたか？
そのうちのどれかはハズレ解法かもしれません。そのアイデアのうちいくつかを後で合体させるとスコアが伸びるかもしれません。
アイデアはメモ書きに留め、まずは状態を表す構造体など、後半を見据えた実装をすべきです。さもなければ、後に解法の乗り換えが不可能になってしまいます（あ、ここも変えなきゃ、あ、やっぱもとに戻したいな、など、考えるだけで胃が痛くなりますね、うぅ）
特に長期コンとなると、途中で方針をガラリと変えたくなることもしばしばなので、なおさらです。 構造体やクラス、アルゴではユニオンファインドのときぐらいしか使っていない、なんて方も多いんじゃないでしょうか。 今回のサンプルコードを糧に、慣れて頂けたらなと思います！！！！
ところで、この問題設定、世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門のゲーム例: 数字集め迷路にそっくりじゃありませんか？ ということでthunderさんから許可を頂いてサンプルコードのアルゴリズム部分にゲーム木探索の実装を使わせていただきました！
サンプルコードはこちらからどうぞ！ github.com
盤面を表す構造体を作る
この辺、我流なのでもし設計時点での便利な方法なんてございましたらこっそり教えて下さい。
探索を進めた時にはじめの１手目と例えば５手目、その中で変化するもの、しないものを考えます。
入力で与えられるもの - タイルの配置 - 得点の配置 これらはゲーム中変化することがないので盤面でもつ必要はないですね。
構造体に必要なもの - 現在位置 - 踏んだタイル - 現在の得点 - 最初の行動
これをRustで実装すると
/// 入力で与えられる情報をまとめた構造体 /// s: 開始位置 /// tiles: タイルの位置 /// ps: 座標ごとの得点 pub struct Input { pub s: (usize, usize), pub tiles: Vec<Vec<usize>>, pub ps: Vec<Vec<i32>>, } #[derive(Clone)] struct TileState { END_TURN_: usize, turn_: usize, seen_: Vec<bool>, pos_: Position, pub output_: Output, pub steps_: Vec<(usize, usize)>, pub game_score_: i32, pub evaluated_score_: ScoreType, pub first_action_: Action, } impl TileState { pub fn new(input: &Input, end_turn: usize, pos: (usize, usize)) -> Self { // タイルの枚数(input.tilesの最大値) let M_ = input .tiles .iter() .map(|t| t.iter().max().unwrap()) .max() .unwrap() + 1; // タイルを踏んだかどうか let mut seen_ = vec![false; M_]; // 現在位置 let pos_ = Position { i_: pos.0, j_: pos.1, }; // 現在位置は踏んでおく seen_[input.tiles[pos_.i_][pos_.j_]] = true; // 移動経路(座標) let steps_ = vec![(pos_.i_, pos_.j_)]; // 得点(実際の得点) let game_score_ = input.ps[pos_.i_][pos_.j_]; // 探索上で評価したスコア let evaluated_score_ = 0; Self { END_TURN_: end_turn, // 終了するターン(サンプルでは使用していない) turn_: 0, // 現在のターン seen_, pos_, steps_, output_: String::new(), // 出力用移動経路 game_score_, evaluated_score_, first_action_: !0, // 探索木のルートノードで } }
こんな感じになります。
ビジュアライザからわかること
tools/src/bin/lib.rs
pub fn compute_score_detail(input: &Input, out: &Output) -> (i32, String, Vec<usize>, Vec<(usize, usize)>) { let mut used = vec![0; N * N]; //本当はタイルの総数Mで十分だが、N*Nで足りなくなることはない let (mut i, mut j) = input.s; // 現在位置、最初はスタート地点 used[input.tiles[i][j]] = 1; // スタート地点を踏む let mut score = input.ps[i][j]; // スタート地点の得点も含む let mut steps = vec![(i, j)]; // 通った経路 let mut err = String::new(); for c in out.chars() { // 出力を一文字ずつ見ていく let (di, dj) = match c { // cがLRUDのうちどれかによって値を変える 'L' => (0, !0), // Lなら(0, !0) 'R' => (0, 1), // 以下略 'U' => (!0, 0), 'D' => (1, 0), _ => { return (0, "Illegal output".to_owned(), used, steps); } }; i += di; // 現在地点から移動 j += dj; if i >= N || j >= N { return (0, "Out of range".to_owned(), used, steps); } steps.push((i, j)); if used[input.tiles[i][j]] != 0 { err = "Stepped on the same tile twice".to_owned(); } used[input.tiles[i][j]] += 1; // 座標(i, j)のタイル番号を踏破済にする score += input.ps[i][j]; } if err.len() > 0 { score = 0; } (score, err, used, steps) }
わりと素直な実装な気がします。
!0について
Rustのusize型は実行環境によってu32かu64として扱われる符号なしの整数型です。 Rustでは配列のindexは必ずusize型にしなければいけない決まりがあり、困ってしまうのが、グリッド探索をしたい今回のような場合です。 (
[(1, 0), (0, 1), (-1, 0), (0, -1)]のような配列を作れない) そこでわざとオーバーフローを起こしてi + !0 = i - 1 + std::usize::MAX + 1 = i - 1と、うまく計算するテクニックが競プロではよく使われます(業プロでも使われますか？)!0は0のbit否定(pythonでいう~チルダ)で、usizeの最大値をとります。0 + !0 = !0(>N)となるので境界条件の設定が(i + di) < Nだけで済みます。 えびちゃん先生とのやりとりも是非ご覧ください
自前のビジュアライザ
今回かなり頑張って見やすく作ったつもりです、力作です！！！！
サンプルコードの「強さ」について
今回のこのサンプルコードに込めた思いがあります。 「ヒューリスティックってとりあえずビームサーチか焼きなましなんでしょ」という意見への反抗心です！ 今回実装してあるどの方法も大した点数にはなりません。ビームサーチを実装する、というのはあくまでスタート地点で、 なぜそれでうまく行かないのか、を考察して小さな工夫（たまに度肝を抜かれるような大きな工夫もある）を積み重ねて点数を上げ（たり下がったりし）ていくのが AHCの楽しみ方なのです。
焼きなましについて
今回の問題は「どう焼くか」を考えることが点数に結びつくと考えたため、焼きなましについては実装されていません！(焼きなまし法の理解についてはIntroduction to Heuristics Contest 解説やナップサック問題を様々な解法で解くを、焼きなましの改善については焼きなましのコツをオススメします)
コメントや質問があれば、この記事が充実していきます！反応があると嬉しいです！
AHC002 Walking on Tiles 〜問題文読解編〜
AHC002 Walking on Tiles 〜問題文読解編〜
問題文
大きさが
マスの床に、大きさが
,
(横長),
(縦長)の３種類のタイルが敷き詰められている。スタート地点の座標
から移動し、移動経路上のマスに書かれた数字の合計を得点として得ることができるとき、できるだけ高い得点を得られる移動経路を求めよ。
ただし、移動には以下の条件がある。
から移動できるのは
の４方向
- 同じタイルは2度踏めない
条件を満たす移動
マニュアルモードで遊ぼう！
Web版ビジュアライザにmanual modeが実装されているときがあります。その場合はまずマニュアルで遊んでみましょー！
百聞は一見にしかず！！！
すぐに問題文を理解できることでしょう。
Seed:に適当な数字を入力し、Visualizeボタンを押下します。
□ manual modeにチェックを入れると、方向キーで遊べます！！
入力
タイルの総数をとすると
入力具体例
0 0 0 0 1 2 3 3 4 4 5 3 8 2 9 5 4 1 6 7
このケースは説明のため床の広さがになっている。本番では
となることに注意。
出力
からの移動をそれぞれ
として、移動経路を文字列で表し、1行で出力せよ。
正の得点を得る
この記事の目標です。
どのAHCでもまずは最初に高い点数を得ようとせず、最小限の点数を得ることをオススメします。
今回の出力は移動経路ですが、WAにならないように、ただ得点を得るだけならば…？
答えは この問題のFirst AC
おわりに
いよいよ第2回みんなでAHCを解く会コンテスト（a9ua1i0nさんの皆解会という略称をつかっていきたい）が始まりました。今回はサンプルコードの時点でいろいろなことできるようになっている予定です。次回、実装編をお楽しみに！
AHC016参戦記
AHC016
グラフへの理解を求められていた?苦しかった。
あとビジュアライザから得られる情報が少なかったのも辛かったかも…
クリークについて、最後思いついたところまで行ったのでいずれもう少し解き進めたい。
パソコン修理中なのでいずれ清書したい…はてなでLatexをうまく書けないので直します！
(2022/11/24清書しました！)
問題文
個のグラフ(頂点数
)を作り、出力する。
以下のクエリに100回答える。
「出力したグラフの中から1つが選ばれ、辺が繋がっているかどうかがの確率で反転され、頂点番号がシャッフルされる。変換される前のグラフはどれかを答えよ。」
答えが間違っていた回数をとして
を暫定スコアとし、
各ケースごとに
を求め得点とする。
グラフの変換について
グラフの変換の理解がイマイチなので、ビジュアライザを読んでみる。
以下はtools/src/bin/tester.rsの46~63行目にコメントを入れたもの
01文字列の受け取り
let mut gs = vec![];
for k in 0..input.M {
let g = read(&mut stdout)?; // 出力された01文字列を受け取る
let cs = g.chars().collect::<Vec<_>>(); // 扱いやすいようにVec<char>に変換
if cs.len() != N * (N - 1) / 2 || cs.iter().any(|&c| c != '0' && c != '1') {
// 01文字列の長さがN*(N-1)/2でなかったり、01以外の文字を含んでいる場合エラー
return Err(format!("Illegal output (g_{}): {}", k, g));
}
let mut g = mat![false; N; N]; // 変換後のグラフ(隣接行列)
let mut p = 0; // cs(01文字列)をどこまで読み進めたか？
for i in 0..N {
for j in i + 1..N {
// この2重for文で辞書順に(i, j)の組を全探索
g[i][j] = cs[p] == '1'; // cs[p]が1ならtrue, 0ならfalse
g[j][i] = g[i][j]; // 無向グラフなので反対側も同様にする
p += 1;
}
}
gs.push(g);
}
から
への変換
64~90行目にコメントを入れたもの
let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(input.seed);
let mut E = 0;
let mut result = String::new();
for k in 0..Q {
let mut vs = (0..N).collect::<Vec<_>>(); // 頂点番号をもった配列を初期化
vs.shuffle(&mut rng);
let s = input.ss[k]; // 正解の番号
let mut h = String::new();
for i in 0..N {
for j in i + 1..N {
if gs[s][vs[i]][vs[j]] ^ rng.gen_bool(input.eps) {
// エラー率epsilonの確率で辺をもつかどうかが反転
h.push('1');
} else {
h.push('0');
}
}
}
let _ = writeln!(stdin, "{}", h);
let _ = stdin.flush();
let t = read_usize(&mut stdout, 0, input.M - 1)?; // 判定した番号
if s != t {
E += 1;
result.push('x');
} else {
result.push('o');
}
}
もとは同じグラフでも、クエリが違えば違うグラフが生成されるということがわかりますね。
具体例
7頂点を持つ完全グラフをひとつ、辺のない頂点を4つもつグラフ（下図中央）
頂点番号を失い、ノイズが加わったグラフ(下図左)
点線の辺がノイズによって失われた辺、青い辺がノイズによって加えられた辺です。
得点について
Nを増やしてでも言い当てる確率を上げたほうが得か？
E(誤答)を増やしてしまっでもNを減らしたほうが得か？
これをみるとNが40を超えると減り方がなだらかになる
(逆に、Nを40以下にするとEが多少増えても点数が増加する？)
正答率80％ぐらいを目指さないと全然点数が上がらないことがわかる
この図の正しい見方を教えてくれ……
相対評価について
アイデア
サンプルと同じように辺の個数で判定→ボツ
$ N=100 $とかにすれば辺の個数を0 ~ 4950まで持てるから多少ノイズが乗っても大丈夫？ 否、でも$N$を大きくすればするほどノイズの影響も大きくなってしまう $\epsilon = 0.40$なら4950*0.4で2000個くらい増減する 逆に、$N$をできる限り小さくした場合そこそこの点数が出る(114191306点)
連結成分の大きさで判定→ボツ
頂点を0から順番にi個ずつ連結したグラフを作る。
判定の際には各頂点からDFSし、連結成分の頻度を求め、一番多く存在する連結成分の大きさが答え。
これはうまくいかない。
まずN>=MのNの設定が必要だし、連結成分どうしが簡単につながるので全く正解できない。つらい。
が低い時だけ頑張る
ABC232Cを参考に同型グラフの判定を行う
で11個、
で34個、
で100個以上の同型でないグラフが得られる
10億点ぴったしのスコアはのときのみ答えた場合のスコア
グラフの特徴量
- 連結成分(大きさ)→ノイズに弱そう
- 連結成分(数)→ある大きさ以下を排除したらある程度ノイズに耐えそう？
- 連結成分(直径)→ノイズに弱そう
- 連結成分(形)→表現方法は？ 連結成分の直径を求め、端から端までの次数のリストで表現？
- 閉路の数→ノイズに弱そう
- 次数→BTreeMap
- 辺の数
頂点数自己辺の数今回ひけない
グラフの直径の求め方
適当な点から最遠の頂点を求め、その頂点（V1とする）からまたBFSしてみつけた最遠の点V2までの距離
以下日記
11/11
コロナ療養明け。明日やっと外の空気吸える。 開催直前にパソコン壊される。 問題文読解。
11/12
パソコンの修理、全然予約取れず…しかも1〜2週間預かりになりそう
エラー率で場合わけ?
とりあえずビジュアライザ読むか…
とりあえず問題文通りのことはできそう
11/13
まずは提出。 エラー率/0.08(この数字は勘)の分バッファを持たせて辺の数で答える、でもめっちゃ点数低い、多分外しまくってる ノイズに強いグラフを作らなければ…
例えばグラフの領域いっぱいまで連結成分i個のグラフを敷き詰めるとか なかなかバグって提出できない
エラー0.4でどんな感じになるか実験必要
ローカル環境つくらなければ 01文字列からグラフに変換する関数 →作った
11/14
めっちゃ仕事忙しくて泣く。
連結成分の大きさiのグラフを敷き詰める作戦、なんかうまく行かない
エラー率0なのに狂う。これ、問題文を理解できていない？？→DFSがバグっていた。
でも連結成分の大きさiの作戦だとNが100必要。詰んだ。
あとNが100だとエラー0.01でもめちゃくちゃ狂う。特に連結成分の大きさ、簡単に全部つながるので全く正解できない。つらい。
24番目のグラフは本来大きさ24の連結成分が3個あるはずなんだけど、ノイズのせいで全部つながっちゃっているので、判定で75になっている、の図
11/15
もうグラフの作り方を考えるんじゃなくてランダムにグラフつくって特徴量の近いグラフを探せばいいんじゃないかって思えてきた まず思いつく特徴量を100回試行でどれがどんだけばらけるか、実験してみよう
11/16
グラフの構造体、特徴量を求める関数を実装する。バグりまくって苦しい。
グラフの直径を求めて経路復元するのなんてきっと緑diffとかなのに辛い。
解決策はわかっている、テストを書くことだ。オンラインジャッジに頼らないことだ。
心の中のえびちゃん先生に睨まれている。
をみたす最小の
を設定し、グラフの番号=辺の本数とする提出をしてとりあえず得点をとる。準備していることは進まない。
11/17
焦り始める。 0番目のグラフの01文字列を全て0に、1番目のグラフの01文字列を全て1にして、 それ以降のグラフは今までのグラフとの差異の最小値が大きくなるようにランダム01文字列から山登りして作成
11/18
明日macちゃんを修理に出すのでほぼ最終日。やばい。
次数はUFで初期化する時に調べたほうが早そうなので実装したい。
あとN=4で11個、N=5の時点で34個グラフ作れるのでN=6で100個ぐらい作れるんじゃない？
ローカルで100個同型じゃないグラフを作ればのとき完全攻略できるんじゃね？
さっそくやってみた、点数改善！でもこれきっとみんな思いついているやつだな…点数の上がり方に対して順位の上がり方が微妙
完全グラフの性質を使ってみる？ 直径1の連結成分の頂点数だけ信用することにして 直径が2以上の連結成分はトリミングする？(次数の少ない頂点を消す) それとも密なグラフの個数で割る？完全グラフが2つつながってたら1個にするイメージ？
11/19
ノイズ、強すぎぃ…
ここでパソコンがドナドナされたので試合終了。くやしー！
こんなかんじでした
センターマン！https://t.co/xSHN8qB2S4 pic.twitter.com/aDvJnx4a0b
— ainem (@ainemixion) 2022年11月22日
AHCにおけるローカルテストについて
第一回 AHCをみんなで解く会コンテストのための記事です。
ローカルテストの必要性
ジャッジに投げるだけだと
- 提出制限があり、短時間に何度も提出できない
- テストケースの偏りにより、最終ジャッジでは点数が下がる可能性がある
- ビジュアライザによる分析ができない
難易度別ローカルテスト
難易度は私の主観で決めています。
レベル１ Webビジュアライザを使う
環境構築の必要性ゼロ！！ AHC001ビジュアライザ
入力の準備
出力の準備
コードテストなり、IDEなりでプログラムを実行し、出力をコピー
結果のビジュアライズ
output: 欄に貼り付けて、Visualizeを実行
考察
結果を眺めて、アイデアを出す
〜環境構築の壁〜
みなさん、競技プログラミングをするときには何を使ってコードを書いていますか？ 私はしばらくコードテストを使っていました。 なぜか？そう、環境構築の壁が立ちはだかるからですね。 環境構築とは、プログラムの実行環境を整えることです。書いたプログラムを、自分のPCで動かせるようにする、ただそれだけなんですけどね… 使っているOSによってやり方が違ったり、昔の記事がアテにならなかったり、エラーの内容が多岐にわたっていたりで、非常につまづきやすいポイントだと思います。 中には黃や橙レートの、私からみて現人神のような方々でさえ、環境構築は難しいとおっしゃっているので、私なんかが説明するのは無理です… ググってくれ！！
レベル５ ビジュアライザを使う
ありがたいことにAHCでは毎回Rust製のビジュアライザが提供されています。 環境構築(自分の言語 + Rust)さえ乗り越えれば、Webビジュアライザよりも多数のテストを高速に行ったり、自分で必要な情報のみを受取ることができたりといいことづくしです。
テストケースの生成
seed値という数字から、テストケースを生成するプログラムがgen.rsです。
ダウンロードした時点で既に50個用意されていますが、いずれ足りなくなってくるので、たとえば1000個のテストケースを用意したいというときに使うプログラムです。
以下、ビジュアライザのREADME.ja.txtを補足する形で説明していきます。 まず8行目
以下の解説では、このREADMEファイルの置かれているディレクトリ上に現在居ることを想定します。
ここから躓いたひとはいませんか。当時の私です。
これはVSCodeやzshやコマンドプロンプトなど、ターミナルでtoolsディレクトリを開いているということです。cdコマンドなどで移動します。もしくは、MacであればFinderから任意のフォルダでターミナルを起動できます
inディレクトリに予め生成された入力ファイルが50個用意されています(暫定テストやシステムテストで用いられる入力とは異なります)。より多くの入力ファイルが欲しい方はseeds.txtに欲しい入力ファイルの数だけ乱数seed値(符号なし64bit整数値)を記入し、以下のコマンドで生成して下さい。cargo run --release --bin gen < seeds.txt
seeds.txtはダウンロードしたままでも予め用意されているので、まずはこのコマンドを説明します。 （テストケースを増やしたい場合はseeds.txtにずらーっとseed値を書き込むことになります。1000個も数字を手打ちできないのでpythonとかで作っちゃいましょう。
print(*(i for i in range(1000)), sep = "\n")
）
cargo run --release --binはRust製のプログラムを実行するコマンド(リリースビルド、バイナリ実行のオプションについては私も詳しくないので割愛…)
gen < seeds.txtgenというファイルを実行するときに標準入力としてseeds.txtを用いますよ、という意味です。
ビジュアライザ
cargo run --release --bin vis <input_file> <output_file>入力ファイルとその入力に対する出力ファイルを読み込み、出力結果のビジュアライズ結果を
out.svgというファイルに書き出します。 標準出力にはスコアを出力します。 svgファイルは画像ビューアソフト、webブラウザなどで表示できます。vis.htmlファイルを開くことでも表示できます。
cargo run --release --bin visがvis.rsを起動するよ！の意味で
<input_file> <output_file>でテストケースが書いてあるテキストファイルとそのテストケースから得られた出力が書かれたテキストファイルを指定します。
（補足）
ターミナルでのコマンドでは、<が標準入力の指定(リダイレクト)の記号として使われるので、gen.rsでは< seeds.txtという引数を与えていましたが、vis.rsではcargo run --release --bin visの後のコマンドを<なしでも読み込めるようにプログラムが書かれているので、<なしでも動きます。うーん書いててわからなくなってきた
とにもかくにも、これでテストケースと出力からローカルでビジュアライザを動かすことができました！ …でもこれだけだとWebビジュアライザを動かした方が早いし見やすいですよね？
レベル6 スクリプトでビジュアライザを動かす
ところで、pythonにはsubprocessというモジュールがあります
subprocess --- サブプロセス管理 — Python 3.11.1 ドキュメント
先程までターミナルに手打ちしていたコマンド、退屈ですよね？退屈といえば、退屈なことはpythonにやらせようですよね？（未読）
import subprocess subprocess.run("cargo run --release --bin vis input.txt output.txt", shell=True)
subprocess.run("<command>", shell=True)を用いるとターミナルに
import subprocess for i in range(100): input_file = f"in/{i:04d}.txt" output_file = f"out/{i:04d}.txt" subprocess.run(f"python3 main.py <{input_file} >{output_file}") subprocess.run(f"cargo run --release --bin vis {input_file} {output_file}", shell=True)
100個のテストケースを事前に用意していれば、100個まとめで一つのスクリプトで実行できてしまうのです！
