AHC 014

 

 

AHC 014

AHC 014 でやったことのメモです。暫定 45.5M です。

忙しい人は最後の「まとめ」だけ読めばおけです。

 

9/17-19

親戚の結婚式を兼ねて家族旅行

 

9/18

移動中はできないと思っていたが、マニュアルモードでスマホでもできることに気付いたので遊んでみる

 

ぱっと思い付くのはこんな感じ。

  • 中心付近にたくさんおいても大したことないので、なるべく「外側」に置きたい
  • 中心付近に置くことで邪魔されないように、最も「外側」に行ける点を毎回選ぶのである程度点数が出そう？
  • これを数手先まで読んだりしてみる（例えば 2 手先で一番外側に行けるように、みたいに）のはアリ？
  • 焼きなましみたいにする場合、「点の削除」が必要になるので、点と点の親子関係（ある点を消すには他のどの点を消さないといけないか）を保持しておくと良さそう？

 

 

9/19

実装の方針

なんか全く思いつかない。

 

 

9/20

とりあえずクラスを作ってみよう！

 

クラスの設計

  • 使った格子点を記録（ N^{2} 配列で愚直に持つ）
  • 各格子点から出ている線の向きを記録（ 8 方向あるので 8 bit で持てる → 必ず同じ方向だけ見ることにすると 4 方向で良いのでそちらを採用した。）
  • 点の追加の判定・実行：追加する点とその対角にある点の座標および「軸に平行か、 45 度傾いているか」を引数とすれば良い *1。 (x0,y0) および (x2,y2) を対角とする追加ができるかどうかを判定する関数と、実際に追加をする関数を定義した。
  • ランダムな点の追加： N^{2} 点から 1 点、 8 方向から 1 方向を選ぶことで点の追加ができれば行う

 

はじめての提出

 

何も思い付かないので「ランダムに点を追加する」のをたくさん行って、追加できなくなったら best_score と best_state を更新して終了する

のを時間いっぱい繰り返して一番良いものを選ぶだけのコードで出してみる。これで 32.9M 点。ループ回数は 50 回ぐらい。

 

 

Submission: 

https://atcoder.jp/contests/ahc014/submissions/35013761

 

 

毎回貪欲に一番外側に置く貪欲方式も試してみたがあまりよくならないので断念。

 

 

9/21

今は 1 点を追加するときにランダムで追加する点を（ N^{2} 点から）選んでいるが、最初に追加可能な点と方向のリストを持っておけばもう少し高速化できそう。

 

やってみたら 35.5M （切り捨て、以下同じ）で 111 位。ループ回数は 1000 回ぐらい。まずまず。

 

 

Submission:

https://atcoder.jp/contests/ahc014/submissions/35024674

 

 

そう言えばいつも思うけど、 AHC だとコードテストで出力が全部出ないからデバッグしづらいんですよねー。結果をビジュアライザに貼りつけて動くことぐらいは確認したいけど、結果だけで出力制限に引っかかることが多い。「質問」で聞いてみたけどダメとの返答が *2 。。まあ手元でデバッグして、コードテストはループ回数とかどの処理に時間かかってるか調べるだけで良いか・・・。

 

 

9/22

いくつか高速化。

  • （毎ターンどこに追加できるか調べるのではなくて）追加可能点のリストを持って、この中からひとつをランダムに選ぶようにした
  • 点を追加したときの追加可能点の更新を、追加した点から 8 方向で辿れるところだけ見るようにした

あと山登りじゃなくて焼きなましにした *3 。

これで 39.9M ぐらい。

計算量でどれぐらい違うのかを調べてみる。手元 Python とコードテスト PyPy で 4 倍ぐらい。得点にすると 1 割ぐらい違う。 PyPy と高速な言語だとだいたい 4 倍ぐらい違うと仮定して、手元時間をさらに 4 倍にするとまた 1 割ぐらい変わる。

期間長いし別言語への乗り換えも視野に入れるか・・・。

 

9/23

さすがに C++ とかを使うのはやだけど、 numpy ならワンチャンあるかと思って、 numpy に適したコードに書き換えつつ高速化をちょこちょこする。具体的にはこんな感じ。

 

  • 選択可能な手の一覧を取得するのを O(N^{3}) から O(N^{2}) に落とした *4 。
  • クラスのテーブルを一次元化した。
  • その他、各クエリ処理で x,y を明示的に計算せず、なるべく xy\ (=x*width+y) のみを使うように変更した *5 。

 

9/24

上位層のビジュアライザ結果を見ると、密に詰め込まれていて無駄がない感じ。「詰まってる」感をうまく定量化できればプレイアウトする前の途中状態でも評価関数を作れるかも？

具体的には、各マスについて、埋まっているかどうかだけでなく、 8 方向のうち何方向の線が埋まっているか *6 によってペナルティを設定すれば良さそう。例えば最初の 2 方向を使うことはペナルティが大きいけど、 6 → 8 にするところはうまく使えている証拠なのでペナルティを小さくする。

→ やってみたけどいまいちなので戻した。。

 

 

9/25

やっぱり高速化ぐらいしかやることがない・・・。どうせアイデアないし numpy とか numba で高速化するのはあり？文法とかなんも知らないけど一週間あればなんとかなるのか？

numpy ちょっと試してみたけどよく分からん。。 numba はがんばればできる？もっと分からん・・・。 C++ は大変そうだし・・・

そういえば最近 Rust が流行ってるという噂があるな。・・・え？

 

9/26

なにもアイデアが

 

9/27

浮かびません。。

 

9/28

Rust 、なんか型がちゃんとしてるとかデバッグしやすいとか言ってたから初心者でも書きやすかったりしないかな。

とりあえず ABC の A ～ C 問題の Rust の提出を漁りまくって文法を勉強しよう。

 

環境ないのでテキストファイル（秀丸）で書いて AtCoder のコードテストに出してみる。型？なにそれ？ usize ってなんですか？ struct と impl なんですか？慣れない概念が多くてつらいけどこのへんはなんとかノリで A 問題ぐらいの計算ならできそう。

いろいろググってみたら「借用」とか「所有権」とか出てきてこれはさすがにいみふ。調べてもこういう場合には & を付けますみたいに書いてるのはあるけど、 & の意味がよく分からん。所有権というのは言いたいことはなんとなく分かった気がする。 *7 

ただコンパイラさん、エラーが分かりやすいし候補とかも書いてくれてすごい（ここもしかして "&" 付けた方がいいんじゃね？とか "self" 忘れてない？とか教えてくれてイケメンか！ってなってた）。コンパイラのない世界で生きてきたんだけど、こういうもんなの？

Python コードは手元にあるので、それをちょっとずつ直訳してみる。むずそうなところは計算量とか多少サボって実装する *8 。

 

9/29

型変換 *9 に苦しめられたり、 "&" とか "*" とか "mut" をコンパイラさんに言われるまま付けたり消したりしながら、丸一日以上かけてなんとか計算量さぼりバージョンの移植がだいたいできた。ただ、なぜか結果を見るとまだ追加できる点が残っている。なんで？

 

9/30

RE もたまに出るな。なんでだ？

型変換と範囲チェックあたりがあやしい予感はしてたけどどうもよく分からん。手元実行していろいろ確認したいけど、コードテストの出力制限がしょぼすぎて、 ANS を出力すると盤面情報が出せないし、盤面を見ようとすると ANS が出力できないという状況でデバッグめちゃくちゃしづらい *10 。仕方ないので Random じゃない関数を作って Python で実行した結果と比較して少しずつデバッグ。

これも丸一日ぐらいかけて調べると主にふたつが悪さをしていることが分かった。どっちも unsigned の取り扱いが悪かったみたい *11 。ひとつは引き算したときにマイナスになってほしいから usize を i64 に変換してたつもりだけど、 usize 同士で引き算をしたあとに i64 変換してた。

もうひとつは x 座標が 0 以上であることを確認するときに "if 0 <= x" みたいに書いてたんだけど、この x が usize だったのでそもそもマイナスにならなくて必ず true になってしまうみたいな話だったっぽい。。

 

はじめての提出

焼きなましめんどいからとりあえず単純山登りで時間いっぱい回すやつで投げてみることにした。 Rust はじめての提出で緊張・・・

 

Submission: 

https://atcoder.jp/contests/ahc014/submissions/35254461

 

45.5 M 点！ループ回数は 4000～5000 回ぐらい。計算量しょぼいバージョン *12 であることも考慮すると、言語差で 5 M ぐらい変わった印象。

 

ところで AHC 打ち上げに誘ってもらったけど、私以外全員 60M 超えでつらい気持ちに・・・。

 

まとめ

「いくつか削除 → ランダムプレイアウト」を近傍とする焼きなましを PyPy3 で出すと 42 M ぐらい。 Rust で雑に *13 書き直したら 45.5M ぐらい。暫定 106 位。

 

 

 

*1: あとは再現できる

*2:ただ、次回のジャッジアップデートで制限緩和予定とのこと

*3:とは言え、どのみち Delete をはさむ（近傍があまり近くない）ので効果がどれぐらいあるか不明

*4:最初に各方向に対して何マス目に黒丸があるかを前計算する

*5:ただしこれはむしろ若干遅くなっていそう。あとで戻す手もあるか・・

*6:どの方向かも一応考慮する。縦横と斜めは分けるのと、上下の 2 本が残るのと上右とかの 2 本が残るのでは使い勝手が若干違う（後者なら点の追加に使える）

*7:このへん Rust 使ってる人に聞いたら教えてくれるかもだけど、直接ロジックに関係ないとは言え、コンテスト中に教えてもらった内容で提出するのはさすがに気が引けるので仕方ないから自分で調べるか。。

*8:Python コードも初期のころに書いてた計算量が悪いコードが残ってるのでそのへんも組み合わせながら。

*9:usize とか i64 ってなに？

*10:ANS だけでもある程度短いものじゃないと制限超えちゃうので、わざと低い点数になるようにしたりして調整しないといけない

*11:Python にはないので慣れない

*12:点を追加した直後の候補点リストの更新を盤面全体を見て再計算している。本当は追加した点から 8 方向だけ調べれば十分

*13:一部計算量サボったり（焼きなましじゃなくて）山登りにしたり

AHC 013

 

 

AHC 013 でやったことを書きます

 

結論

（時間がない人はここだけ読めば OK です。）

  1. 盤面（ケーブル情報も含む）
  2. Move の履歴
  3. Connection の履歴
  4. 注目しているコンピュータの種類

を持つ山登りで、 1 種類のコンピュータを優先して進める貪欲方式で Pretest 265,366 点取れた（暫定 61 位）。

 

Sample 1 の結果（5350 点）

 

日々の進捗

1 日目（8 月 9 日）

飲み会（チームの歓送迎会）

 

2 日目（8 月 10 日）

飲み会など

 

3 日目（8 月 11 日）

飲み会など

 

4 日目（8 月 12 日）

飲み会（会社の偉い人たち）

 

5 日目（8 月 13 日）

問題を見た感想：

  • 密盤面の調整するときは、 AHC 011 のスライドパズルのライブラリそのまま使える？
  • パラメータによって結構違うゲームになりそう
  • 実装むずそう
  • （例えば山登り・焼きなましなどするとして）どういう情報を持つべき？
  • 別種類のコンピュータを混ぜるのはあまりメリットなさそう
  • まずは 1 種類のコンピュータを全部繋げるのを目指すべき？（これで 4950 点なので 50 ケースで 25 万点弱）

 

最初の方針としてはとりあえずこんな感じが良さげか

 

  • まずは 1 種類のコンピュータのみをつなげる
  • 他の種類はとりあえず無視
  • 長いケーブルを引くと制約が増えるので、各種類について短い方から Move なしで貪欲で引いてみる
  • 一番よさげな種類をひとつ選んで固定
  • とりあえず山登りしてみる
  • 持つ情報は、「盤面（ただしケーブル情報も保持）」「Move の履歴」「Connection の履歴」
  • 「見ている種類のコンピュータを 1 マス動かす」「見ている種類の 2 つのコンピュータの間に異種コンピュータがあり、かつその隣接マスに退避できる場合は退避する」の 2 種類を、得点の増え方が多くなる方を優先でできるだけ行う

 

得点の増分をキーにした理由は、メインクラスタに繋げていく方が有利そうなので。毎回全部選ぶと計算量やばくなるし、結果的に全部繋げられれば変わんないので、これが良いかはよく分かんない。

とりあえず頑張って実装すると RE 。

 

〇 － 〇 － 〇

 

から真ん中のやつを 1 つ下に下げると、左右のはくっつけることができるんだけど、上にくっついてるものがある場合にどちらか片方しか選べないのでその判定をミスっている模様。

バグ探しにいろいろ苦労したけど 2 RE ののち 132,355 点をげっと。実行時間は 3 秒ぎりぎり。

 

まだだいぶサボっていて、

メインの種類以外のコンピュータは見てない（たとえ隣り合っていても結んでいない）

そもそも操作回数のカウントもしていない

 

 

  • 「退避」による接続は、間のコンピュータが 5 台まで増やした
  • 時間チェックを入れるようにした
  • 回数チェックはまだ入れてない

 

これで 196,533 点。

 

5 ～ 6 日目（8 月 13 日 ～ 14 日）

 

「一番大きなグループ」に空マスだけを通って辿り着ける同じ種類のコンピュータは、 BFS で連結マスまで移動するとくっつけられる。

これを入れると 229,710 点。

 

7 日目（8 月 15 日）

 

空マス以外を通る場合も、邪魔コンピュータを移動しながら動かすと行ける可能性がある。

BFS（Dijkstra）を 2 回すると実装できる *1 。これを頑張って実装すると 241,079 点。

この時点でまだ 1 種類しか繋げていない（つまり理論値は 4950 * 50 = 247,500 点）ので、理論値の 97.4% が取れていることになる。

いずれにしても 25 万点超えを目指すには 2 種類目を使うしかない。

 

 

2 種類目

種類数が増えても大丈夫なように実装しようと思っていたけど、一部うまくできていないので変えるのは大変。

苦肉の策として、「今見ているメインの種類をすべて壁マスにする」 *2 という処理を行って、その後はその色は最初からなかったかのように扱うことで既存の関数がある程度そのまま使うことにした *3

 

1 種類目の関数をそのまま使って頑張ると 258,223 点まで出せた！

 

 

 

省スペース

得点が低いケースを見てみると、スペースがなさすぎて 1 種類目すらうまく繋げていないことが分かった *4 。 1 種類目をある程度繋いだ後に、省スペース策として

  • 一方向にしか出ていないマスを上下左右のどこかに動かせるなら動かす

は簡単に実装できる *5 ので入れてみると 264,840 点。

 

あとは 3 種類目を入れるなどして 265,227 点。

 

 

 

 

8 日目（8 月 16 日）

「同じ種類のみを繋ぐ」縛りでやってきたが、狭い盤面のときなど 1 マス挟んで大きなブロックが結合できない場合もあるので、無理やり繋ぐのを実装した。

これも実装を一から変えるのは大変なので、実装上は強制的に色を変える（ 3 - 4 - 3 - 3 みたいになってたら 4 を 3 に塗り替える）ことにした。これでもその後の最適戦略は（ほとんど）変わらない *6 。得点は変わるが、何点下げるかの調整を入れればよい *7 。

主に狭いケースで改善がみられて、 Seed 9, 25, 37 などでは 1000 ～ 2000 点近く上がった。 15 ケースに 1 ケースで、 1500 点上がるとすると、 Pre-test の 50 ケースでは 5000 点ぐらい上がるかな？と思って出してみたが 100 点ぐらいしか上がらず・・・。該当ケースがなかっただけなのかも。

 

 

アニメーション

 

方針的に、疎の方が動きに余裕がなくて困りがち（点数が低くなりがち）。

Seed 0 / Seed 7 （密バージョン） / Seed 1 （疎バージョン） それぞれこんな感じ

 

 

できなかったこと

本当は 1 種類目のコンピュータを固定して 2 種類目にいくのではなくて、 2 種類同時に動かせればより柔軟性が上がる *8 。

その場合、データの持ち方を変えないといけないのはもちろんだけど、評価関数をどうするかも結構難しそう *9 。あと近傍への移動を実装するのも結構難しそう。少なくとも「ケーブルの繋ぎ変え」は考慮する必要がありそう。

逆に「繋ぎ変え」さえうまくできれば、あとは適当に焼きなましに乗せることもできるかもしれない。

 

 

 

 

デバッグ環境について

コンテスト中、言及されていた模様 *10 。

 

 

これはその通りで、今回も PyPy 環境構築もたくさんループして確認するのも諦めていました。実際、手元環境はいつも通り Jupyter Notebook なのでめちゃくちゃ遅いです（Visualizer 用の出力も合わせて、 1 つ回すのに 1 分ぐらいかかる）。

 

まあでも一般的には

  • たくさん回して得られる情報は最後の調整以外は大したことない
  • 早いうちからパラメータチューニングをやりすぎると良くない *11

ので、環境構築については特に意識していなかった。

結局、まじめに考察をして新規アイデアを出さないと抜本的な改善は見込めないんですよねー。 1000 ケース、 10000 ケースの平均得点を正確に出すより、特徴的な数ケースの結果を正しく分析・考察する方がよほど大事 *12 。

 

デバッグは

  • Jupyter による実行
  • Jupyter の結果を Visualizer に貼りつけて実行 *13
  • コードテストによる実行 *14
  • 本番提出

 

をうまく使う感じで。

目的ごとにコードを変えるのはめんどくさいので、 Jupyter の実行と本番提出は全く同じコードでできるようにした *15 。コードテストと本番提出は区別できないので、コードテスト時には 1 文字だけ変えるようにした *16 。

 

 

ランダム要素

 

乱数は使ってないので、時間打ち切りの影響の差のみ出るはず。

同じコード *17 で 2 回出し直してみると 3 点しか変わらなかった。

 



 

 

 

 

 

 

 

 

 

 

 

*1:１ 回目は空マス以外に 20 の重みを付ける重み付き Dijkstra 、2 回目は邪魔マスを空マスに移動させる BFS

*2:実装上はもう動かせないマスを 7 として実装した

*3:若干きもいけど仕方ない

*4:サンプルの 9 など

*5:既存の関数がそのまま使えた

*6:Move や Connection の出力にも影響しない！

*7:ちょっとはしょった

*8:実際、デバッグ画面を目視で確認すると、最初の種類が邪魔をして点数が伸びない状況が多かった

*9:一番大きいところを優先するのでだいたい良さそうだが

*10:コンテスト中なので反応できなかったけど

*11:局所最適になりがち

*12:もちろん、ある程度のレベルになってくると平均得点を正確に把握することで有利になるのは間違いないんだけどね。特に入力条件別の得点を把握することでパラメータ調整が正確にできる。ただ今回だと私が 26 万点台でもがいているとき、トップ層は 38 万点台とか出していて、パラメータ調整とかしようとも思えないレベル。

*13:途中経過も保持しているのでアニメーションになる

*14:得点とステップごとの時間を出力している

*15:Local で流すときは LOCAL = 1 を事前にしておくことで判定できる

*16: "if 0" を "if 1" に変える

*17:最終の 1 回目のバージョン

ゆきこ 352 Writer 記

 

 

ゆきこ 352 の Writer をやっていました。

 

みなさん参加ありがとうございました。

 

yukicoder.me

 

各問題（作問・総評）について

一部ネタバレを含みます。ご注意ください。

 

A問題

簡単枠ですが、 E 問題とセット（布石）になっています。

B問題

よくあるちょっと計算すればソート条件が分かるパターンですが、★ 1.5 にしては難易度が高いんじゃないかという反応が多かったようです。 *1

C問題

最適化問という意味で B と若干かぶるかなと思ったけど、個人的に設定・解法とも気に入ってたので強行で出してしまいました。ただかぶっているという反応は確認した範囲ではなさそうでした。こちらも ★2 の割に難易度がむずいんじゃないかという反応が多かったようです。「飲酒プログラミング」がはやっていた時期に考えていた問題ですが、タイムリーではなくなったかもしれません（？）。 *2

あとサンプルの説明に不備がありました。ごめんなさいです。。

D問題

幾何は苦手な人が多いですが *3 、典型に入れても良さそうなのに過去に出題を見たことがなかったので出してみました。知らない人は覚えておくと使えることがあるかも。

E問題

個人的には目玉問題でした。一見、「これ解けるの？」という気になりますが、「解けるならこうなっているはずだ」「こうなっていると嬉しい」みたいなところから絞っていくと道筋が見えてくるはずです。解けたときの爽快感を味わって頂ければ嬉しいです。 Fav も一番もらえていたようでありがとうございます *4 。

F問題

知ってればやるだけな気もしていましたが、コーナーケースの処理などで苦戦している人も多かったようです。

G問題

一番アルゴ問っぽい問題かなと思っています。最終問にしていますが、数え上げ・確率が得意な人は考察しやすかったんじゃないかなと思います。

 

賞金について

いろいろあって賞金を出すことにしてみました。思ったより考慮することが多くて大変でした。

 

考慮するべきルールなど

  • 当選者数・金額
  • 応募方法・本人確認方法
  • 抽選方法
  • 応募者の当選結果を公開するかどうか
  • 非応募者の当選結果を公開するかどうか
  • 個人情報の管理
  • 賞金の送付方法
  • 未成年の保護者同意確認
  • 運営さんへの謝礼

 

満たしたかった条件

テスターさんには無償でやってもらっているのと、テスターをやってもらった時点では賞金の話もしていなかった *5 ので、賞金対象から除外するのはないかなと思っていました。一方、 1 位から順に賞金を出す方式はテスターさんが有利になりすぎるかなと思いました。また当選の番号を予め決める（例えば「10 位が当たり」とする）みたいなのは、わざと順位を下げるモチベーションができてしまって、競技としていまいちな気がしました。結果として、上位ほど有利になる抽選が無難かなという結論になりました。

ただ、私自信が参加者に知り合いが多いので、こっちが恣意的に当選者を決めていると思われると面白くないかなと思いました。そこで、当選順位は予め分かっていないが、機械的に当選者が決まり、かつ公正に決めたことが参加者から確認できるようにルールを作りました。

 

RSA 暗号もどき

競プロをやっている人なら簡単に確認できる *6 方式として RSA 暗号もどき *7 を使うことにしました。

大きな素数 p,\ q を適当に決めて、 M=pq を法として e 乗根を求めるような操作 *8 は、 p,\ q を知っていないと難しいけど、確認は誰でも簡単にできるという条件を満たすので、今回のニーズにぴったりでした。

 

ランダム性のある Key

当たり確率を適当に決めて、順位表からある程度ランダム性のあるものを Key とする方式にしました *9 。

 

掲示板方式

当初考えていた方式として、「掲示板方式」がありました。これは順位表から得られるランダムな整数を Key として、そこから得られる mod M の数をひとつだけ決める方式です。これを例えば 5 桁の数字がたくさん並んでいると思って、前から見て「当たり番号」が最初に出た 5 人が当たりという方式です。「当たり番号」は順位の重みの分だけ発行されます *10。これだと抽選作業がラクになる（ひとつだけ e 乗根を計算すれば良い）という意味では良いんですが、応募していない人の当落情報を公開してしまうことになるのでよくないかなと思って断念しました *11 。

あまり大きな問題にはならないかもですが、アンケートによると（賛成票が多いものの）否定派の人もいるようなので、勝手に情報公開するのは良くないかなと。

 

 

個別抽選方式

結果的に採用した方式です。

参加者ごとに RSA 暗号もどきで抽選をします。これなら応募者のみ抽選すれば応募していない人の情報は漏れることがありません *12 。この場合の問題として、当選人数を固定にしづらいというのがありました。

予算は適当だったので、期待値 5 人ぐらいで多少ぶれても良いかなということで、上限を決めたうえであとは個別ランダムにしました。少なすぎても多すぎても微妙でしたが、結果的に 4 人当選ということでちょうど良かったかなと思っています。

暗号理論をうまく駆使すれば応募していない人の情報を公開しないかつ当選者を固定人数にする方式もありそうでしたが、そこまで考えられませんでした *13 *14 。

 

応募方法

掲示板方式なら応募は不要（当選者にこちらから DM すればよい）ですが、個別抽選方式なら応募は不可欠です。専用のサイトを作る手もあったのですが、めんどくさいので Twitter 上で ツイート へのリプを送って応募するという形式になりました。 TL で盛り上がるといいなというのも少しありました。

 

本人確認

金銭が発生するので、本人確認は最低限する必要がありました *15 。 yukicoder には Twittter ID を登録する機能があったので、それをベースに本人確認を行いました *16 。

Twitter ID を登録していなかった人にはお手間をかけてしまいましたが、なりすましによる応募を防げたので良かったかと思います。

 

 

重大なミス

RSA 暗号もどきの Key として、当初は順位を使っていたのですが、それより得点にした方が参加者による裁量 *17 が大きくなって面白いかなと思って得点（を整数に丸めたもの）を Key にすることにしました。実はこれが大きなミスでした。 yukicoder では同じ問題でも解いた順番によって得点が違うものの、ある程度の順位からは同点となる参加者が多くいます。順位によって当落条件は若干違うとは言え、場合によっては同点メンバーがまとめて当選してしまう可能性がありました。例えば 52 点の参加者は 24 人いましたが、 10 人を超えて当選した場合は 10 人分の賞金を山分けするような例外を公開していたので、仮に当選しても半分以下しかもらえないという可能性がありました。結果的に同点当選はなかったのでことなきを得ましたが、設計上の不備となっていました。 *18

 

個人情報の管理

基本的には個人情報を集めると管理上の責任が出て大変なので、極力個人情報を持たないことにしました。アマゾンギフト券の送付も（メールアドレスを聞かずに） Twitter の DM 上で行いました *19 。

 

FAQ

 

Q: A 問題、簡単すぎじゃない？

A: 賞金チャンスをたくさんの方にという理由で、 A 問題のハードルは極力下げてみました。実際この問題だけだと楽しみ要素は少ないんですが、 E 問題への布石になっているので（まだの方は）ぜひ E 問題と一緒に楽しんで頂ければと思います。

 

Q: E 問題のタイトル名、 Hard じゃないんですね？

A: 結構迷いました。タイトルからは GCJ とかの Hidden *20 のことをイメージする人もいたかもですが、入力が Hidden になっているというパターンも面白いかなと思ってこちらにしました。

ちなみにツイートで類題 *21 を出したことはあります。

 

Q: 賞金を出した理由は何ですか？

A: 特に理由はないです。しいて言えば yukicoder がさらに盛り上がると良いかなというのはありました。 yukicoder 上で賞金を出すならどういう形式になるんだろうと思って考えていたら、いつのまにか出すことになっていました。

 

Q: 賞金を出したら参加者数増えましたか？

A: コンテスト終了時点でサブミッションは 172 人（うち正の得点 167 人）でした。直近だと 110 人台ぐらいの回が多かったので 50% ぐらいは増えたと言えそうでしょうか。

 

Q: Key に 10^{60} を足したのはなんでですか？

A: ふつうに整数範囲で 3 乗根が存在する可能性があったので、それを排除するためにある程度大きい立方数を足してみました。

 

Q: 最近は 998244353 で割った余りを求める問題をよく見ますが、 B 問題で10^9+7 にしたのはなぜですか？

A: これ作ったのだいぶ前で、まだ 998244353 がそこまで主流じゃなかったときに作ったものなんですよね。。

 

Q: こどふぉとかぶってませんでした？

A: これはまじで未確認でした。ごめんなさい＞＜

 

 

Q: 作問でこだわったところはありますか？

A: 一番こだわったのは E 問題ですね。いかに見つけづらい感じにするかはこだわってました。単にそれっぽいのを掛け合わせるだけだとだめで、「反例」が出るのもある程度大きいところで出るように調整しました。 10^7 \le M \le 10^{18} の条件もなるべくさりげなく入れるために A 問題で同様の設定にしたりしてみました。

制約の 5000 以下という制約も、普通は計算量を 2 乗に抑えないといけないみたいな意味に捉えられがちですが、そもそも 5000 を超えると成立しないというパターンにしてみました。

 

Q: 逆に作問で不安なところはありましたか？

A: たくさんありますが

  • E のスペシャルジャッジが合ってるかが一番不安だったのでランダムテストたくさんやるなど確認しました。
  • E はテストケースも大事なので、いろいろためしてちゃんと落ちるか確認してました。
  • G でより計算量が良いのがあるかも気にしてました（最悪 log 1 つはありそうだなと思ったらあったようですが、まあ許容範囲かなと思ってます）
  • F のマラソンは落としたいと思ってました。
  • 小数問題が多かったので、誤差が大丈夫か（特に想定解が死んでないか）は注意して確認しました *22 。
  • あまり例を見ない問題（特に D と E）もあったので、難易度が妥当かどうかは心配でした。 D、E、F は同じにして「逆転」が起きてもいいようにしてましたが、 B や C も外れていたようで反省です。

 

Q: 参加者にしてほしいことはありますか？

A: 解いた感想や、どういう思考で解法にたどり着いたかを教えてもらえると嬉しいです。別解法がある場合は、ユーザー解説も書いてくれると嬉しいです。面白い問題だと思ったら Fav も付けてくれると嬉しいです。

 

関連ツイート

関連ツイート

 

 

 

*1:関係ないですが、 TL で無限にアルバイトしている人を思い出していました。

*2:関係ないですが、 TL で無限にお酒を飲んでいる人を思い出していました。

*3: すみません私のことです

*4: 個人的には前回の D 問題 枠に近いです。 

*5: 賞金を出すのが決まってから個別に連絡しました

*6: 特に Python など多倍長のある言語ならなおさら

*7:「もどき」と言っているのは、通常は平文を送りたい人が暗号文を作るのに対して、本抽選ではランダムな暗号文から平文を復元するというところが若干違うのでそう言っています

*8: e は通常 3 や 65537 を使うことが多いらしいですが、 65537 を全面に押し出すと E 問題のヒントになりかねないので 3 にしました。

*9: 具体的には、今回は 7 問の FA のタイム（秒）を使いました

*10: 例えば 23 位の人の当選重みが 5 なら 02300、02301、02302、02303、02304 の 5 つを 23 位の人の当選番号とする感じです。

*11:HTTF とかでも見た目順位で出してるのであまり気にしなくても良いのかなとも思いつつ、ただあれは参加登録時にいろいろ記入してるんだよなとも思いつつ。。

*12: 251 桁の半素数が素因数分解ができてしまうとあれなんですが、そこはできない前提で・・

*13:応募しない人が 1 人なら必ずバレてしまうので、それなりの人数いる前提です

*14:良い方法があれば教えてください

*15:そうしないと、上位参加者になりすまして応募することで、金銭を得ることができてしまう

*16:Twitter ID を登録したくない場合もあると思ったので、その場合はサブミッションに特定の文字列を入れてもらうことで認証することにしました

*17: 意図して選ぶことはできないんですが、参加者による要素が大きいという意味で

*18:あとそもそも非応募者の当落情報を公開しないというところに反してしまっています・・

*19:Amazon の公式の方法にはないんですが、一旦自分のメールにギフトを送る → 結果を DM で送る、という感じでできます

*20:ジャッジ結果がコンテスト中に表示されない

*21:入力が与えられないという意味で

*22:ちなみにジャッジ用の数値は、多倍長整数で少なくとも 100 桁ぐらいは計算していたのであまり気にしてませんでした

AHC 011

 

 

AHC 011 でやったこと・考察したことなどをつらつら書きます。最終的なアルゴリズムを見たい人は最終日（9 日目）の項目へ。

 

1 日目（5/28 土）

【昼】

子供と公園に行ったり人生ゲームをしたりしていたので実装はできなかったけど、問題文は読めた。

 

【考察】

15 パズルの一般化として「 N^2-1 」パズルを考える。 15 パズルはやったことがあるので分かるけど、到達可能な配置であれば *1 基本的に 1 枚ずつ決めていける。角になるときはスペースが足りなくてつらいけどそれ以外はすでに決めたタイルを動かさずに決められることが簡単に分かる。「到達可能」かどうかは、本当は偶置換・奇置換の問題があるが、本問では同じタイルが少なくとも 1 組はあるので大丈夫。

手数は 1 枚決めるのに O(N) かかるので、全体で O(N^3) 手でできる。

本問では同じタイルがたくさんあるので、各タイルを見る際に必ず距離 O(1) の範囲に同じタイルがあると仮定すると、全体で O(N^2) でできそう。定数倍がそこそこあるのと N が小さくて怖いけど、本問の制約 2N^3 だとまあなんとかなるだろう。

 

よって、おおまかな戦略として下記があげられる。

 

① タイルの多重集合が与えられたケースと同じにあるような「木」を探す

② その木をターゲットとして 15 パズル（「 N^2-1 」パズル）を愚直に頑張る

 

これをするなら全ケース「木」にできる前提になっちゃうけど、まあできるかなという感覚（つまり最低でも 25M 点は出るはず）。直感的にはさすがに全ケース「木」はできるとして、 30M ～ 40M ぐらいを目指さないといけないのかなというイメージ。

 

【戦略】

一番簡単な戦略としては、上で挙げた

 

① 木を探す

② 木に合うように 15 パズルをする

 

を独立に（①→②の順に）する方法がある。もっと効率よくするなら②で有利になるように①を決めるとか、①と②を合体して焼きなましするとかいろいろありそう。

焼きなましは（Python だと時間的に）不利になりそうなので、メインの解法としてはあまり選択肢には入れていない。

 

 

【夕】

1 時間ぐらいあいたので実装してみる。

この時点で 25M はいないので、上の戦略で大丈夫なら提出できるところまでいければそこそこ上位に行けるはず。

 

【①について】

適当な「木」を作ってからランダムに入れ替えるみたいな雑な操作でいけないかな。

木をキープする近傍は、まじめにやると大変だけど、コの字型になっている 4 マスの空き辺を動かす操作は O(1) でできるので、とりあえずこれでできればラッキーということでやってみる。

 

「ぴったり一致」まではいけず・・・

（コの字型の図解は下で）

 

 

【夜】

賞金 ABC があったので出てから AHC の実装に。

 

夕方やってたのをもう少しちゃんと実装してみた。具体的には、

 

・ランダムに木を作成する

・入力で与えられたタイルの多重集合との差分を考える

・差分がなるべく小さくなるように「コ」の字型を回す操作をたくさんする *2

 

をランダムにやる。「ぴったり一致」じゃないと意味ないので、焼きなましはあまり使えなさそう。とは言え局所解は怖いので、「ある程度小さくなったら逆側もたまに許す」みたいにすると、一応非現実的とまではいかない時間でぴったり一致するものが出てくることもありそうなことが分かった *3 。とりあえず全部繋ぎ（ 25M 相当）を作りたいので、前半部分の高速化はあとでやることにして、その後の 15 パズル部分を（雑にでも）実装したい。

 

② 15 パズル部分

アルゴリズムとして簡単なのは、 1 枚ずつ順番に決めていく方法。これだと、動かしたいタイルを 5 手で 1 マスぐらい進めることができる。まあ T の制約にはぎりぎり間に合いそうだけど最善からは程遠い感じ。一度実装してしまうと後戻りしづらいので悩んでるうちに時間が過ぎてしまった。

 

 

ところで、デバッグ時に盤面を表すのに「罫線文字」をうまく使うと見やすくなった *4。

デバッグ用の盤面の出力

 

 

2 日目（5/29 日）

 

自分も家族も体調不良でダウン。。「いのちだいじに」

寝ながら脳内考察は少しだけ。昨日は偶奇の問題は大丈夫と思ってたけどそうでもない気が。同じ種類のマスが複数あるのでたしかに必ず到達可能ではあるんだけど、好きな順に貪欲に決めていくと最後に困る可能性があることに気付いた。同じマスがなくなる瞬間に気を付けるか、最初から最後の 3 マスに同じ種類のマスを 2 種類入れておくなどをするとラクそうと思った。

 

3 日目（5/30 月） ～ 4 日目（5/31 火）

 

仕事＆体調不良でほぼ進まず。最高 38 度の熱と頭痛・喉痛・鼻水で何も考えられない。火曜日は有給とって病院で診てもらいつつ PCR 検査もしてもらった。

その後もほぼ寝たきりだけどちょっとだけ考察。ただ、脳内考察をしても実際に実験してうまくいくかとか時間・試行回数がどれぐらいになるのかを試せないのがとてもつらい。

 

 

 

発狂しながら冷静になって考察したところいくつか気付きなどを得た。

  • 「コの字型」以外にも、「一本だけ出ているマス」も自由に回転して良いことに気付いた。これで自由度が上がるので前半ステップが速くなるはず（？）。
  • 前半ステップが終わった段階で、ターゲットまでの距離の合計とかで簡易判定すると良さそうなものを選別できる。距離の合計の最小値は Min Cost Flow でできる。計算時間はよく分からないけどまじめに後半ステップをするよりは早いだろう。
  • 15 パズルとかでググってみると、 A^{*} というアルゴリズムがあるらしいということが分かった。ヒューリスティック関数というのを使うと高速で探索できるとのこと。よく分かってないけど後半使えるかも？

 

回転について

「コの字型の部分を回転する」、「一本出ているマスを回転する」の図解はこんな感じ。

 

コの字型の回転

 

1 本出ているマスの回転

 

コの字は 4 マス、一本は 1 マス（とそれに隣接するマス）が対象。図のように緑の部分を移動しても「木」であることは保たれる。

 

A^{*} について

ググるといろいろ出てくるが、寝ながらスマホで理解しやすかったのはこれ。

yamakatsusan.web.fc2.com

 

通常の Dijkstra では、スタートからの距離 d_v が小さい頂点 v から順に探索する方法だった。

A^{*} は、予め（手動で）ヒューリスティック関数 h_v を決めておき、 d_v の代わりに d_v+h_v の小さい順に探索を行う方法とのこと。 h_v は頂点 v からゴールまでの距離に近いものが望ましいが、実際の距離以下であれば正しい結果を返すことが保証される（これでも Dijkstra より高速化される）。 h_v を実際のゴールまでの距離よりも大きくすると、正しい結果が保証されない代わりにより高速化できる。

 

 

 

5 日目（6/1 水）

体調はまだだいぶ悪い（頭痛・鼻水・喉痛）けど 1 日目の 1 マスずつ愚直に動かすアイデアをやっと実装してみる。結構汚い実装でつらいけど、なんとかできた。ただ最後の偶奇とか途中のコーナーケースはあまり考えていない。雑にやった感じ、 N=10 でちょうど 2000 手ぐらい。これだと 25M ぎりぎり乗るかどうかで細部詰めてもいまいちになりそう・・・。

 

6 日目（6/2 木）

【夜～翌朝】

今こそ発狂しながら覚えた A^{*} を使うときが来た。いくら A^{*} でもさすがに 10^{2} マスは全部はきつい印象だけど、 2 ～ 3 マスずつ適用すれば今の 1 マスずつよりだいぶ短くできるはず。

ヒューリスティック関数としては、各パネルのマンハッタン距離の合計を使うのが良いと書いてあったが、近いところはうまくいかないかもなので「 \max( \mathrm{ManhattanDistance} - 2, 0) * K 」みたいにした *5 。 K は 3 ぐらいまで下げればほぼ理論値になる気がする。高速化したいときは 10 とか 100 とか適当に増やせば良さそう。

 

雑に実装すると、手数が N=10 で 1000 手ぐらいになった。ほかの N でも N^{3} ぐらいになってるので、これが確実にできれば 37.5M になるはず！

 

あとは偶奇調整が残っているけど、めんどくさいので

  • 右下の 3\times 3 の 9 マスの中に同じパネルが少なくとも 1 組あるようにする（そうでないと棄却する）
  • 最後の 9 マスは一気に A^{*} をする

という手抜きで乗り切ることにした。

前半がミスる確率は \displaystyle\frac{_{15}C_{8}}{15^{8}} \fallingdotseq 10\% ぐらいなので大きな問題にはならないだろう。

9 マス A^{*} は Python だとそこそこ時間ロスだけどこの際仕方ない *6 。

 

ついでに「一本だけ出ているマス」も実装する。

木の盤は、簡単のため必ず右下が空パネルになるように決めた。あとパネルを決める順番は右上からヘビ状に順番に決めることにした。

 

ここまでのロジックは

  • 与えられた状態を board とする
  • 木の状態の盤 tree_board をランダムに作る
  • tree_board のうち、「一本だけ出ているマス」または「コの字型になっている箇所」を探して回転するという操作を、 board と tree_board のパネルの集合が一致するまで繰り返す。
  • ただし、差が 9 枚以上なら山登り（差が減る方向のみに進む）、差が 8 枚以下なら簡易焼きなまし（差が増える場合は 20\% の確率で採用）、みたいにした *7 。
  • board と tree_board のパネルの集合が一致したら、 tree_board をターゲットとしてパネルを合わせていく。合わせる順番はヘビ状（下図）で、最後の 9 マスは一気に合わせる。
  • 合わせ方は、基本的には 2 枚ずつ A^{*} をする。具体的には、次に決めたい 2 マスに使うパネルを、最も近いものから選ぶ。選ばれたパネルを目的地に移動する（疑似）最短距離を A^{*} で求める。という感じ

 

決めていく順番

 

1 回まわすだけで TLE になったり、謎の RE が出たりで苦しんだ。

TLE 解消として、前半の山登り・簡易焼きなましでのコスト変化を O(N^2) かけていたのを O(N) に落としてみた *8 が、特にコードテスト環境だとあまり速くならず泣いてしまう *9 。

それでもいろいろ軽くしたり RE の原因をつぶしたりしてなんとか AC 。

 

 

35M でこの時点で 46 位。当初の予定だと 37.5M ぐらいは出て欲しかったけど、 TLE をなくすためにいろいろサボったのでまあやむなし。

さてここからどうするか。

 

 

7 日目（6/3 金）

 

－－－－－ここから余談－－－－－

頭痛・喉痛・鼻水に加えて、薬を飲んでるせいか常に眠気がひどく、現実と夢と AHC の世界が混じっているような感覚が一週間続いている。

イギリスの夢はゆうさんろんどんの影響？

 

 

子供が「テキシコー」という、プログラミング的思考を学ぶ番組に興味を持ったみたいで、繰り返しみている。良い傾向。

ついでにこの前プレゼントであげた理論的思考力を鍛えるゲームにもハマっている模様。これも良い傾向。

人生ゲームを毎日させられるループから抜けられるか。

 

－－－－－余談終わり－－－－－

 

 

夢から覚めて、試してなかった Min Cost Flow を実装。前半パートを適当な時間まで試して一番良いものだけ後半パートをすることに。

後半の時間が読めないので時間をどうするか迷うけど、とりあえず N ごとに適当な時間を決め打ちして、「ひとつ以上盤面があるかつ時間を超えている」場合に後半パートに移ることにした。

 

あと時間計測をして気付いたのは、後半パートの最後の 9 マスでかなり *10 時間がかかっている模様。

A^{*} のパラメータをいじって高速化することに。

パラメータは近距離の調整と全体のファクターの 2 つ。通常時と最後の 9 マスに分けてパラメータ設定してみた。

DistanceAdjustment は大きいほど正確になるが遅くなる。通常は 2 、最後の 9 マスでは 1 にした。

全体のファクター HeuristicFactor は小さいほど正確で遅い。通常は 10 * (N - 5) 、最後の 9 マスでは 5 にした。通常時は 10\times 10 の盤面をフルに使うような場合には最悪探索数が爆発する *11 ので大きめにしている。

 

\max( \mathrm{ManhattanDistance} - \mathrm{DistanceAdjustment}, 0) * \mathrm{HeuristicFactor}

 

 

 

 

8 日目（6/4 土）

 

割とやることがなくなってきた。

とりあえず 1 ループが結構でかくなってきたので、「ループが回って時間過ぎてたら終わる」だと途中で TLE に引っかかる可能性が高い。いろんなところに強制 EXIT を入れて、少なくとも 1 つ ANS を見つけている場合は時間が来たら途中で打ち切りみたいにした。これで TLE の不安はだいぶ減った。

 

あとアイデアとしては

  • 全体で A^{*} を雑にでもしてみる
  • そもそも前半ステップと後半ステップを完全に分離しているのでうまく融合する
  • A^{*} のパラメータ調整
  • 木の盤面に合わせるときの順番を一意に決めているので、逆回りなどいくつか試す

 

などがある。前後半の融合は今からだと厳しい。パラメータ調整はやれば多少上がるかもだけど長時間 Run する余裕がない（のとそもそもそういうプロセスができていない）、しかもあまり上がりそうにないのでパス。

「逆回り」は一度で二度試せてお得なのでこれを入れることに。あと結局最小費用流はやめて愚直に Score を計算する方針に変えた。もろもろやってみたが、 36M 台ぐらいでほぼ変わらず。

 

コードテストで見てみると、 N が小さいときの方がループ回数が小さいという謎現象が起きていることに気付いた。特に前半ステップが遅そう。自由度が低すぎてうまくいかないのか。前半ステップは手抜き実装でやってるのでうまくやればもっと効率化できるんだけど今からだと厳しいか。

 

ぐぬぬー。いま A^{*} を 2 マスずつやってるけど、 3 マスにしたら速くなったりしないかな・・・と思っていじってみると有意に上がりそう。投げたら 37.3M ！よしよし。

当然 4 マスならどうかと思って実験すると点数は 1 ～ 2 M 上がりそうだけど 5～8 秒かかるケースがあって TLE になりそう。

Python （ PyPy ）を使っている以上、スピード勝負に持ち込むと不利なのは分かってるのでなるべく別路線で行きたいけど、今回はスピード勝負にならざるを得ない感じか、ということに今更気付いてきた。まあしょうがない。

その後細かい調整などで約 37.5M （37,497,152 点）が出た。結果的にこれがプレテスト最高得点になった。

 

あと公開されている seed=0 を結果の盤面も見てみた。

この時点で一番良さそうだったツカモさんの盤面が、幸い（左右逆だけど）端っこに空マスがあるので、前半部分をこれで丸コピして、後半部分を自分のロジックでやってみて何点取れるかやってみた。結果は 76 万点ぐらいで、全部自分の方法でやったのとそんなに変わんない感じ。うーん。

 

 

 

 

最終日 9 日目（6/5 土）

何度か出し直したけど特に変更してない。

 

最終的なアルゴリズムはこんな感じ。

 

  1. ランダムに木の盤面を作る
  2. 「一本マス」と「コの字型」を回転させて、入力盤面とパネルの集合が一致して、かつ最後の 9 マスに重複を含む木盤面を探す
  3. 入力盤面から木盤面への path を A^{*} で 3 マスずつ決める（ただし最後は 9 マス一気に決める）
  4. 最大スコアなら Ans を書き換える
  5. 逆回りで 3. 4. をやりなおす
  6.  1. ～ 5. を時間いっぱい回す

 

A^{*} のヒューリスティック関数は下の形で、

\max( \mathrm{ManhattanDistance} - \mathrm{DistanceAdjustment}, 0) * \mathrm{HeuristicFactor}

 

3 マスのとき： \mathrm{DistanceAdjustment} は 2 固定。 \mathrm{HeuristicFactor} は使う盤面の広さ *12 に応じて 5 ～ 100 を段階的に適用

9 マスのとき： \mathrm{DistanceAdjustment} は 1 、 \mathrm{HeuristicFactor} は 5 でそれぞれ固定。

 

スコアを計算する回数は N=6 で 4 ～ 10 回程度（つまり上の 1. から 6. が 2 ～ 5 回まわる）、 N=10 では 1 ～ 4 回程度。特に前半ステップはばらつきが大きいので十分な回数回ってないイメージ。

 

最終提出のスコアは 37,307,105 点。最高得点 37.5M から若干下がってしまったけどまあ誤差の範囲か。

 

 

全体の感想

身近なゲームに類似の題材でとても面白かった。 A^{*} も初めて書いたけど、実装が簡単なわりに便利で勉強になった。

前半ステップは「 O(1) で変更できる」と思って喜んで採用したが、もう少し効率が良い方法がある気がする。

時間勝負になると追い込みが苦しい。手元の実行環境も生 Python なのでたくさん回して実験などがしづらい（今回はしなかった）。 AHC は PyPy にこだわらず言語を変えるのもひとつの手だが。

上位陣の点数すごいので勉強したい。

 

*1:全部ばらばらの場合は全パターンのちょうど半分が到達可能

*2:この操作で木であることが崩れない。「コ」の字の場所を見つけたあとは O(1) で処理できる

*3:手元実行は 生 Python なのでめちゃくちゃ遅いけど、実際の提出だと PyPy なのできっとそこそこ速くなって間に合うかも？まあだめならいくらでも高速化できるはず（？）

*4:「けいせん」で変換すると出てくるやつ。 1 本だけのものは良い罫線文字が見つからなかったので矢印で代用した。 1 本は慣れないとつながりが見づらいかもしれないけど、私の解法だと重要（「回転」できる）なのでこれはこれで見やすい

*5:後述のとおりパラメータはあとで可変にした

*6:ちゃんと判定するのめんどくさそう

*7:枚数と確率はそいろいろ変えた

*8:本当は O(1) でできるけど定数倍激重なので手間の割に影響ほぼないかむしろ遅くなりそうなのでサボった。

*9:PyPy だとランダムアクセスが遅いのが効いてるのか・・・？

*10:コードテストで 1 秒とか、いくつか試した最悪ケースだと 2.5 秒以上かかっているものも

*11:と言っても 2 マス探索だと O(N^6) ぐらい

*12:N^{2} ではなく、関係するパネルを含む最小長方形の広さ

探索アルゴリズムを使わずに CodinGame の Line Racing をやって Legend になった話

 

CodinGame を知っていますか？

私はよく知りませんでした *1 。

ちょうど TL で少し流行っていた Line Racing というのが初心者向けと聞いてやってみました。

1～2 週間ほどやりましたが、一旦やりたいことはだいたいできたので *2 感想を書いておきます *3 。

 

CodinGame って何？

  • 対戦ゲームをプレイするプログラムを作って、強いプログラムを作った方が勝ち

 

Line Racing って何？

いわゆる常設コンテストという部類らしく、期間無制限で遊べるらしい。

ルールはこんな感じ。

  • 2～4人対戦で、 20×30 のグリッド内でリボンを上下左右に伸ばしていって、伸ばせなくなった人が負け
  • 3人以上の場合、負けたプレイヤーのリボンは丸ごと消えるので注意
  • 制限時間は一手100ms（Python だと結構きつい）

www.codingame.com

 

どういう戦略？

おそらくこういうゲームでは探索アルゴリズム（ビームサーチとか minimax とか？）で何手先まで読むかみたいな勝負になりがちな気がしました。

そっちを勉強しながらやってみる手もあったかもですが、今回は評価関数のみでやってみました。

理由はいくつかありますがこのあたりです

  • Python でやると C++ などの言語にスピードで負けるため、何手先まで読めるかみたいな勝負をしても勝てる気がしないため *4
  • 評価関数で実装する方が簡単な気がしたため
  • ゲームが単純かつ盤面がそこそこ広いので、数手先まで読むより大局的に評価する方が有効な気がしたため

 

結果的には

  • 探索アルゴリズムを一切使わない *5
  • 山登り・焼きなましなどのマラソン手法も使わない
  • すべての処理を O(nHW) で行う *6

という感じになりました。

 

結果は？

順位は常に変動しますが、最終的に 30 位台ぐらい *7 （Legend の上位 6% 程度）までいけました。

最初は正直どこまでいけるかは分からなかったですが、初めてにしては十分かなという気はします。

 

 

具体的なアルゴリズムは？

基本的には「自分が一番近いマスの個数」をベースに作った評価関数が一番高くなるマスに移動します。

詳細なアルゴリズムはここには書きませんが、ツイートにいくつか心の声が漏れていたので、参考に。

 

よく考えたら正規分布の累積分布関数とかでも良かったかもです。プロットしたら似てたのでまあ良しということで。

あと例えば自分と相手がどっちも Closed になったら逆転が難しくなるので評価を極端にするなどもしました。

 

関節点があると行った後戻って来れないんですよね。実装大変だった。

先に死にそうな相手がいる場合に、どの連結成分からなら何ターン後に行けるかみたいな判定も大変です。細かいところは正確性を多少犠牲にして実装をサボりました。

 

競プロ（アルゴ・マラソン）のコンテスト・精進との違い

コードの書き方

長期戦になりがちなので、コードの書き方がかなり変わりました。

変数名もちゃんと分かりやすい名前にしたり *8 class も一から作ったり *9 。

 

 

作業の進め方

Last Battles をたくさん見て、一つずつ確認していく作業になりました。提出コードから毎ターン標準エラーに状態を吐き出すことで、手元でデバッグできるようにしてからだいぶラクになりました。

 

  • アイデアを考える
  • ロジックを決める
  • 設計を考える
  • 実装する
  • 大丈夫そうなら Submission する
  • Last Battles をたくさん見る
  • 意図していない挙動があれば手元でデバッグする
  • 考慮できていない理由で負けていたらどういう判定にすればよいかアイデアを考える

 

改善したつもりでも順位が下がったりすることもあって、どれが良くてどれが悪いのかの判断がとても難しかった気がします *10 。

レアケースだけど、そのケースにおいては必ず得になるみたいなのもいくつか思い付いたけど、結局コスパを考えてあんまり入れませんでした。「2 人かつ初期配置が対称的かつ自分が後手」の場合は対称戦略で勝てるというのだけは、実装も簡単なので入れました。

 

 

感想

ちょうど AtCoder の Rated がない時期だったのと年末年始休暇も使えたので、ゆっくり取り組めました。

アルゴのコンテストとは違う面白さがありますね。

自分が提出したとき、自分のプログラムが戦っているのを見るのはテンション上がりますね。寝るときもずっと Last Battles TV を見続けてしまってました。

自分が提出したとき以外にも勝手に戦っているようで、気付いたら順位が上下しているのも常に参加している感じで良いですね。

頑張って実装したのに順位が上がらないのはつらいですが。

 

あと同時期にやっていたメンバーがいたのはモチベーションになりましたね。さんだーさんがちょうど狙えそうな位置にいたのも良かったです。

アドバイスくれたさんだーさん、同時期にやっていたかえでさん、ゆうさんろんどん、クルトンさん（？）には感謝です。

 

 

 

*1:実は前回のやつに参加していたみたいですが、ルールとかを理解する前にやめてしまってました

*2:疲れたので

*3:期間無制限なので、何か書くとかしないとやめどきが難しいんですよね

*4:こどげは PyPy も使えないようで、 C++ などに比べると数十倍遅くなる可能性があります

*5:「敵プレイヤーが一手進めた状態」などを計算しない

*6:定数倍はそこそこ重い。これでも TLE でたまに落ちてた（！）

*7:本記事執筆時点で 34 位

*8:Global のは X とかもあったけど

*9:アルゴではライブラリになってるもの以外 class はほとんど使わないので

*10:同じコードでも Legend の 30～60位ぐらいまで変動することもあったり

競プロでたまに出てくるけど忘れがちな定理

競プロでたまに出てくるけど忘れがちな定理・公式などをまとめる予定です。
クリックで開くよ

（まだ下書き中）

定理

数え上げ系

行列木定理

問題例

n 頂点 m 辺のグラフの（ラベル付き）全域木はいくつありますか。

答え

ラプラシアン行列の任意の余因子の行列式の (-1)^{i+j} 倍

ピックの定理

問題例

格子点を頂点とする穴のない多角形の内部にある格子点の個数を i、辺上にある格子点の個数を b とするとき、この多角形の面積は？

答え

S=i+\displaystyle\frac{1}{2}b-1

LGV 公式

問題例

DAG（有向無閉路グラフ）および始点集合 A と終点集合 B が与えられる。 A と A が整合的（※）であるとき、これらを始点・終点とするパスの組であって、どの 2 つのパスも頂点を共有しないものの数はいくつあるか。
整合的とは
2 つの始点 a_{i} < a_{j} \in A と2 つの終点 b_{i} > b_{j} \in B があるとき、 a_{i} から b_{j} のパスと a_{j} から b_{i} のパスは必ず交わる

答え

x_{i,j} を a_{i} から b_{j} に向かうパスの個数とすると X=(x_{i,j}) の行列式 https://atcoder.jp/contests/abc216/editorial/2561

Lucas の定理

問題例

_{m}C_{n} は \mod p で

答え

_{m}C_{n} \equiv \displaystyle\prod_{i=0}^{k} {_{m_{i}}C_{n_{i}}} \mod p

ただし m_{i} は m の p 進法表記の下から i 桁目

BEST theorem

問題例

オイラーグラフ G に含まれるオイラー閉路の個数は？

答え

c(G, v) \cdot \displaystyle\prod_{w \in V} (\mathrm{outdeg}(w) - 1)!

ここで c(G, v) は頂点 v を根とする有向全域木(全ての辺が根の方を向いている全域木) の個数 (実は c(G,v) の値は v によらず一定なので v は任意にとって良い)、 V は G の頂点集合、 \mathrm{outdeg}(w) は頂点 w の出次数である。


（ Editorial - AtCoder Beginner Contest 336 より抜粋）

グラフ関係

Dilworth の定理

問題例

Dilworth の定理の主張をグラフの用語で言ってみてね。

答え

DAG 上の最小 path 被覆（全ての頂点を適当な path に属するようにして分割する時の必要な path の最小本数）は、 最大 antichain（頂点の集合であって、集合に属する任意の 2 頂点に関して、それらを結ぶような path が存在しない）の要素数と一致する
ABC 134-E の解説 より

ちなみに 2 部グラフ上の最大独立集合は「頂点数マイナス最大マッチング」なのでこれが関係する問題もある （ABC 137-Ex の解説）。

Erdős–Gallai の定理

問題例

有限整数列 d_{1},\ \cdots,\ d_{n} が無向グラフの次数列（頂点の次数を降順に並べたもの）になる条件は？

答え

総和が偶数かつ {\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)}

Tutte 行列

問題例

(V, E),\ V = \{1,\ \cdots,\ n\} に完全マッチングが存在する条件

答え

{\displaystyle A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i \lt;j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i \gt;j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}}
で表される n \times n 行列の行列式が（多項式として）ゼロ

証明系（？）

結婚定理

問題例

略

答え

略

LP 双対

問題例

弱双対性・強双対性

答え

弱双対性： \max \{𝑐𝑥\ |\ 𝑥 \ge 0,\ 𝐴𝑥 \le 𝑏\} \le \min \{ 𝑦𝑏\ |\ 𝑦 \ge 0,\ 𝑦𝐴 \ge c\}
強双対性： \max \{𝑐𝑥\ |\ 𝑥 \ge 0,\ 𝐴𝑥 \le 𝑏\} = \min \{ 𝑦𝑏\ |\ 𝑦 \ge 0,\ 𝑦𝐴 \ge c\}
hos さんのスライド 79 ページ付近から

母関数関係

ラグランジュの反転公式

問題例

F と G が互いに逆関数である（すなわち G(F(x))=F(G(x))=x ）とき \lbrack x^n \rbrack G(x) を F(x) で表してね。

答え

Multiset

問題例

\mathcal{B} = \mathrm{MULTISET}(\mathcal{A}) が \mathcal{A} の多重集合の構造のとき、母関数 B(x) を A(x) で表してね。

答え

文字列関係

繰り返し文字列

問題例

X, Y を空でない有限文字列とするとき、次を有限文字列の条件・式で答えよ。
① X^{\infty}=Y^{\infty} と同値な条件は？
② X^{\infty} \neq Y^{\infty} のとき \mathrm{lcp}(X^{\infty}, Y^{\infty}) は何と等しい？
③ X^{\infty} \lt Y と同値な条件は？

答え

？？？（作成中）

？？？？？

問題例

？？？？？

答え

？？？？？

Memo

Tweet

Codeforces で Grandmaster になりました

 

わーい！ 

特に書くことはないんですが。

 

レートグラフ

なんかこんな感じです。濃橙から 1 年ちょい。

 

f:id:Kiri8128:20210627023706p:plain

https://codeforces.com/profile/Kiri8128

 

 

緑 → 青 ： 9 日

青 → 紫 ： 3 か月

紫 → 薄橙 ： 4 日

薄橙 → 濃橙 ： 1 年 2 か月

濃橙 → 薄赤 ： 1 年

 

 

Python/PyPy Only だと初 GM らしい

ほんと？少しテンションが上がりました。

まあ他の言語を使えていないというのは本当は喜ぶことでもないんですが。

 

codeforces.com

 

 

と思ったら嘘（mod 取り忘れ）で通ってたみたいでごめんなさい。

 

 


 

 

Q & A

 

Q: 嬉しい？

A: 嬉しいけど AtCoder 橙になったときの方が断然嬉しかったです。 B が嘘だったのも微妙ポイントのひとつ（笑）

 

Q: やったことは？

A: こどふぉに特化した対策は特にないんですよね。出れるとき（気付いたとき）に出るのを繰り返したぐらいです。精進は AtCoder をメインでやってました。

 

Q: こどふぉ Python だと TL きつい？

A: AtCoder よりきついことが多いけど、まだ私レベルだと単純にアルゴリズム力が足りてなくて落としてる。

 

Q: こどふぉ対策はする？

A: AtCoder とは違う傾向の問題も多いのでちゃんと対策すれば勉強になりそうな気はしています。でもすぐにやるかというと・・・

 

Q: IGM なれそう？

A: だいぶ遠いなー。超上振れが 10 回ぐらい続いたら・・・。気長に頑張ります。

 

 

 

前の記事

https://kiri8128.hatenablog.com/entry/2020/06/19/113740?_ga=2.257347407.510264320.1624728738-1380712366.1624285197