平方数の末尾に同じ数字はいくつ続く？

ストーリー

ねこ：「 38^{2} = 1444 は末尾に同じ数字 4 が 3 個並んでるね。」
きり：「平方数で、末尾にもっとたくさん同じ数字が並ぶものあるかな？」
ねこ：「末尾が 0 のものは 10000^{2} = 100000000 のようにいくらでも長くできるね。」
きり：「 0 以外だとどうだろう？無限に長くできる？それとも最大値がある？」
ねこ：「気になるね。」
きり：「 10 進法以外で考えてみても面白そうだね。」
ねこ：「だね。やってみよう。」


なおこの記事はえびまさんの動画を参考に、議論を一般化したものです。




10 進法の場合

準備

a を b で割った余りを a \bmod b と書くよ。
また平方数 x^{2} を 4 や 5 で割った余りの制約は以下のとおりです *1 。

  • x^{2} \equiv 0,\ 1 \pmod 4
  • x^{2} \equiv 0,\ 1,\ 4 \pmod 5

これを使って、 10 進法で末尾に同じ数字がいくつまで連続して現れるか調べよう。

平方数の末尾に現れない数字

5 で割った余りに注目すると、平方数の下 1 桁が 2,\ 3,\ 7,\ 8 になることはないことが分かる。

平方数の末尾に1つまで連続して現れる数字

11 \equiv 55 \equiv 99 \equiv 3 \pmod 4 および 66 \equiv 2 \pmod 4 より、 1,\ 5,\ 6,\ 9 は平方数の末尾に高々 1 つしか連続して現れないことが分かる。なお、百の位以上は、 4 で割った余りに影響しないことに注意してね。
1 つ現れる例は 1^{2}=1,\ 5^{2} = 25,\ 6^{2}=36,\ 3^{2}=9 があるよ。

平方数の末尾に3つまで連続して現れる数字

4444 \equiv 12 \pmod {16} つまり 1111 \equiv 3 \pmod 4 より 4 は平方数の末尾に高々 3 つしか連続して現れないことが分かる。なお、一万の位以上は、 16 で割った余りに影響しないことに注意してね。
3 つ現れる例は 38^{2}=1444 があるよ。

結論

10 進法では末尾に 3 個同じ数字が続くのが最大で、例えば 38^{2}=1444 がそのひとつ。

定式化

ここから 10 進法以外に拡張する。まずは記号を定義する。

n \ge 2 および 0 \le a \lt n に対し *2、f(n,\ a) を、 n 進法で下 k 桁がすべて a になるような平方数が存在するような k の最大値とする。ただし、そのような k が存在しないときは 0 、無限に大きくできるときは \infty とする。また、 g(n) = \displaystyle\max_{1\le a \lt n} f(n,\ a) とする。

前節の議論から、 10 進法の結果は以下のように書ける。

f(10,\ a) = \begin{cases} 0 & (a=2,3,7,8) \\ 1 & (a=1,5,6,9) \\ 3 & (a=4) \end{cases}
g(10) = 3

中国剰余定理

S_{k} = 1 + n + \cdots + n^{k-1} = \displaystyle\frac{n^{k}-1}{n-1} とする。このとき、 n 進法で下 k 桁がすべて a になることがある条件は、

x^{2} \equiv aS_{k} \pmod {n^{k}}

となる整数 x が存在することである。

n の素因数分解を n=\displaystyle\prod {p_{i}}^{e_{i}} とすると、この条件は

\exists{x} \in \mathbb{Z},\ \forall{i},\ x^{2} \equiv aS_{k} \pmod {{p_{i}}^{e_{i} k}}

が成立することと同値である。

無限に長く続く条件

n,\ a を固定したとき、いくらでも長くできる条件は次のように表せる。

f(n,\ a) = \infty \iff \forall k \ge 1,\ \exists{x} \in \mathbb{Z},\ \forall{i},\ x^{2} \equiv aS_{k} \pmod {{p_{i}}^{e_{i} k}}

あるいは中国剰余定理より順番を入れ替えて以下のようにも書ける。
f(n,\ a) = \infty \iff \forall{i},\ \forall k \ge 1,\ \exists{x} \in \mathbb{Z},\ x^{2} \equiv aS_{k} \pmod {{p_{i}}^{e_{i} k}} \qquad (★)

以下この条件を満たす a が存在する n の条件を求める。

奇素数 p\ |\ n の条件

p\ |\ n のとき、

S_{k} \equiv 1 \pmod p

が任意の k \ge 1 について成り立つので、★の条件は v_{p}(a) が偶数で、かつ \displaystyle\frac{a}{p^{v_{p}(a)}} が平方剰余であることと言える。
ここで v_{p}(a) は p が a を割り切る回数である *3 。
特に a=1 とすれば任意の奇素数 p に対して★の条件を満たす。

素因数 2 の条件（ n が偶数のとき）

p=2 について★が成立するのは、 v_{2}(a) が偶数で、かつ十分大きい k に対して \displaystyle\frac{a}{2^{v_{2}(a)}} \cdot S_{k} \equiv 1 \pmod 8 であることと同値。

実は S_{k} は k \ge 3 のとき次のように書ける。

S_k \equiv \begin{cases} 1 \pmod{8} & (n \equiv 0 \pmod{8}) \\ 5 \pmod{8} & (n \equiv 4 \pmod{8}) \\ 7 \pmod{8} & (n \equiv 2 \pmod{8}) \\ 3 \pmod{8} & (n \equiv 6 \pmod{8}) \end{cases}

よって、★の条件は以下のように言える。なお \bmod 8 で奇数はそれ自身の乗法逆元となることに注意。

a_{\mathrm{odd}} := \frac{a}{2^{v_2(a)}} \equiv \begin{cases} 1 \pmod{8} & (n \equiv 0 \pmod{8}) \\ 5 \pmod{8} & (n \equiv 4 \pmod{8}) \\ 7 \pmod{8} & (n \equiv 2 \pmod{8}) \\ 3 \pmod{8} & (n \equiv 6 \pmod{8}) \end{cases}

無限になる例

前節の考察から、 n が奇数のときや 8 の倍数のときは a=1 とすれば無限に大きくできることが分かります。つまり、このとき f(n,\ 1) = \infty です。

例

例として 3 進法で考えてみましょう。たとえば

28177 ^ {2} = 793943329

ですね。これを 3 進法で表すと
(1102122121_{3})^2 = 2001022221111111111_{3}

となり、右辺の下 10 桁が 1 で続きました。この後も、左辺の該当の桁をいじって 1 桁ずつ伸ばしていけることが分かります。開平法の筆算（を左右逆に行う）の要領で順に決めていくと考えても良いです。

n が十分大きいとき

奇数と 8 の倍数のときは無限であることが証明できたので、あとは 2^{e}P \ (1\le e \le 2,\ Pは奇数) の形のもののみ。
実は n が十分大きいときは、必ず f(n,\ a) = \infty となる a \lt x が存在することが分かる。ここでは証明のイメージを理解するため、 P=p が素数の場合を考える。このとき、 kP \le y \lt (k+1)P \ (k=0,\ 1,\ \cdots,\ 7) のそれぞれの区間に奇数の平方数が存在することが言えれば十分。
\displaystyle\frac{31^{2}}{33^{2}} \gt \frac{7}{8} から、これは 8p \gt 33^{2} つまり p \ge 137 程度以上なら成り立つ。
*4

結果が有限になる n

実際にプログラムなどで調べて見ると、有限の長さまでしか伸ばせないのはちょうど次の 9 個に限られる。

n=2,\ 4,\ 6,\ 10,\ 12,\ 20,\ 28,\ 42,\ 60

例えば n=28 の場合、 \bmod 8 での議論から考えられる a_{odd} は a=5,\ 13,\ 21 の 3 種類、 a=5,\ 13,\ 21,\ 20 の候補があるが、 a=21 は 7 の指数が奇数なのでダメ、その他も \bmod 7 で平方非剰余なので条件を満たさない。他の n に対しても同様に条件を満たさないことが確認できる。
なお、各 n について、 n 進法での平方数の末尾に続く数字の最大数およびそれを満たす最小の例は以下のとおり。

n 最大長 x （十進表記） x^{2} （十進表記） x （n進表記 *5 ） x^{2} （n進表記）
21111_{2}1_{2}
41111_{4}1_{4}
63462116114_{6}13444_{6}
10338144438_{10}1444_{10}
1221419612_{12}144_{12}
203356126736(17,16)_{20}(15,16,16,16)_{20}
28312361527696(1,16,4)_{28}(2,13,16,16,16)_{28}
425554081230700597619344(1,32,33,2,4)_{42}(3,7,7,3,16,16,16,16,16)_{42}
603524274576(8,44)_{60}(1,16,16,16)_{60}

これにより、各 n について末尾に続く非零の数字の最大長 g(n) は以下のとおりであることが分かった。

g(n) = \begin{cases} 1 & (n=2,\ 4) \\ 2 & (n=12) \\ 3 & (n=6,\ 10,\ 20,\ 28,\ 60) \\ 5 & (n=42) \\ \infty & (\mathrm{Otherwise}) \end{cases}

おわりに

ねこ：「難しかったね。」
きり：「有限の長さまでしか伸ばせないのが 9 個しかないというのは非自明な結果で面白かった。」
ねこ：「ありそうな問題設定だけど先行研究あるのかな。」
きり：「簡単に調べてみたけど、ここまで体系的にやっているのは見つからなかったよ。」
ねこ：「OEIS にもこの 9 個の整数が連続する数列は登録されてなさそうだね。」
きり：「証明も思ったより大変だった。」
ねこ：「証明できたぜみたいな顔してるけど、範囲評価のところで P が素数じゃない場合の議論を誤魔化してなかった？」
きり：「ううう」


End

*1: 前者は \bmod 4 で (2k)^{2} \equiv 0,\ (2k + 1)^{2} \equiv 1 であることから、後者は \bmod 5 で k^{2} \equiv 0,\ (k\pm 1)^{2} \equiv 1,\ (k\pm 2)^{2} \equiv 4 であることから分かります。

*2:a=0 の場合は \infty であることは明らかなので、本稿では議論には含めない。定義としては外すと不自然なので含めている。

*3:a の p 進付値とも言える

*4:P が素数でない場合も平方数の存在証明の評価の方法は同様にできるが、 \mathrm{gcd}(P,\ x) が 1 でないものを選んでしまう可能性もあるので厳密に示すには工夫が必要。本記事では厳密な証明は諦める。

*5: 20 進法以上は各桁の数字に 10 以上が現れるため、カンマ区切りで表記している

焼きなまし法が書けなくても AHC 赤になれたよ

AHC 赤になりました

AHC049 後に AHC Rating が 2806 になり、入赤しました。 いい区切りなのでやってたことなどをメモしておきたいと思います。

これまでの記事

入橙記事

貪欲・評価関数の工夫などは入橙記事に書いているので、興味ある人はこちらもどうぞー。

kiri8128.hatenablog.com

アルゴ入橙記事

kiri8128.hatenablog.com

推移など

レート推移

AHCレート推移

レート寄与グラフ

直近の AHC048 などの貢献が大きいようです。以前取った 4 位の AHC026 はパワーがだいぶ下がって来ている・・。

レート寄与グラフ

なお、このグラフは AtCoder Graphs で描画することができます。

入橙時との差分

記事タイトル

さーて、入橙時から何が変わったでしょうか？！

  • 入橙時 → 焼きなまし法を使えたことがなかった！
  • 入赤時 → 1 回だけいい感じに使えた！

入橙時は「焼きなまし法が使えなくても」だったが、入赤したときの AHC 049 が焼きなましだったのでさすがに「使えなくても」とは言いづらいかなー。でも実際、 AHC049 では焼きなまし法部分は自分では書かず ChatGPT くんに全部書いてもらったんだよなー。ということで、タイトルを「使えなくても」→「書けなくても」に変えてみた。 ちなみにビームサーチはいまだに書いたことも使えたこともないのでちゃんと履修しないと・・・。

これまでで良かった回

Rated の 30 位以内だとこんな感じ。

（ New 印は前回の入橙記事からの差分）

入橙時は貪欲が得意的なことを書いた気がするけど、最近は貪欲というよりは戦略系で稼いでいる気がする。

言語とLLMについて

入橙時と変わらず、基本 Python で書いています。これまで最高パフォを出した AHC 048 は最終提出までPythonでした。 ただ LLM で言語変換ができるようになったので、短期などでは Python で書いたものを Rust に書き直してもらうこともあります。

LLM は主に以下の場合に使っています。

  • 焼きなまし法などの実装のため
    • 焼きなまし法は自分で書くのはあまり上手じゃないので、方針だけ伝えて書いてもらうことが多い
    • AHC041 では、自分でコードを書かず最初から LLM に書いてもらった（ 記事 ）
    • AHC049 では、貪欲まで自分で書いてその後の焼きなまし法は書いてもらった
  • 言語変換のため
    • 前述のとおり、 Python で書いて Rust などにしてもらうことが多い

その他ツール類

  • pahcer: 使えてない（使いたいが環境構築が・・・）
  • Optuna: 使ってない
  • Copilot: 競プロではほぼ使ってない
    • そもそも競プロでいつも使っている環境には入れてないので、使う場合は別の場所にコピペして補完してもらってまたコピペして戻すみたいなことをやっている
  • Visualizer:

力の入れ方について

長期では相対スコアの回が多いので、地味に 立ち回り の影響が大きい気がしています。 最高パフォを出した AHC 048 でも、これができてないとかなり順位が違ったと思います。

業務・職場の変化

入橙記事時点ではアクチュアリーだったので、コード書くことはありませんでした。 現在の職種はアルゴリズムエンジニアなので、何かしらのコードを書いていると思われるかもしれません。 実際は、私の場合はマネージャー寄りの立場なので、自分でコードを書いたり読んだりすることはないです。 ただ、競プロer が多い職場なので、勉強会や日々の業務の中で得られる AHC に関する知見は増えた気がします。

今後について

今後の意気込みと気持ち：

  • 得意回でパフォーマンスを稼ぐ方針は引き続き継続したい
  • 戦略ゲーは特に力を入れたい
  • 焼きなましを LLM でサッと書いて出すみたいなのもたまにはやりたい（が、最上位に行くのはむずいのでレート的にはそんなにおいしくない気がする）
  • ビームサーチもライブラリ整備して使っていきたい気持ちはある
  • LLM とルールの動向が読めず、今後は取り組み方や楽しみ方が大きく変わる可能性がある
    • （今の楽しみ方で）楽しめるうちに楽しんでおきたい気持ち
  • レートの計算方法的に 1 位が大きく評価されることもあり、 1 回ぐらい 1 位を取ってみたい気持ちはある
  • 作問もしたい気持ちはある

𝕏 入赤ポスト

END

AHC 045

 

 

AHC045 の参加記事です。

41.377B でプレテスト 47 位でした。

上位勢とは割と異なるところもあるので筋が良いかはあやしいですが、シンプルな実装でそれなりのスコアが出るのでご参考まで。

 

 

やったこと

  • 推定とグループ構築の2段階に分けてそれぞれを解く
  • 推定パート
    • 状態の持ち方
      • 各頂点について、初期状態以外は2次元正規分布で近似する
      • 点間の相関は考慮しない
    •  クエリの選び方
      • 正三角形を繋げるようなクエリを投げる
      • クエリ前に最も最長方向の分散が大きい点は必ず選ぶ
      • 2点目を決めた後は、隣接点を2頂点とする正三角形のもう一つの頂点付近から頂点を選ぶ
      • たくさん試し、点ごとに得られる期待情報量の重み付き和が最大になるものを選択する
      • 重みは最長方向の標準偏差
      • ただし L が6以下の場合は実際にシミュレーションを行い分散（の平方根）の減少量が最大になるものを選択した
    • 更新
      • クエリの結果はシミュレーションで反映
      • 事前分布からサンプリングを行う
      • 各頂点について隣接頂点（最小全域木の辺でつながれた頂点）の集合がクエリ結果と一致するものを採用する
    • クエリをすべて消費した後、もう一度同じクエリを最初から投げたと想定して再度更新を行う
  • グループ構築
    • 推定した座標に基づいて「『グループ内の2点間の距離の二乗和÷グループの要素数』の合計を最小化する」という問題に言い換え、これを焼きなまし法で最小化する
    • 言い換え問題は、スワップの差分計算が O(1) でできる！
    • 言い換え問題の結果をそのまま使い、できたグループごとに推定座標に基づく MST で結び方を決める
    • なお、後処理で最小全域木の長さを実際に計算する焼きなまし（山登り）も試したが特に良くならなかったのでやめた

 

考察いろいろ

どんなクエリが良いか

 

長さが近い辺はどちらが長いか不明であり、長さが明らかに異なる辺は逆転が起きないと仮定する。実際、事前分布の分散をもとに、近すぎる頂点は選ばないようにしている。そうすると、クエリの検出力は、クエリの応答として現れる結果の種類数とみなせる *1 。

選ぶ点の個数ごとに、どういうクエリの検出力が高いかを見ていこう。

クエリの検出力（結果の種類数） - 3点クエリの場合

 

クエリの検出力（結果の種類数） - 4点クエリの場合

 

 

クエリの検出力（結果の種類数） - 5点クエリの場合

 

結果としては、正三角形をたくさん連ねる形の効率が良さそうということが分かる。

なお分散が等しい場合、小さい正三角形でも大きい正三角形でも得られる情報量は変わらない。ただし標準偏差に比べ近すぎると位置の逆転が発生し良い情報が得られないので、ある程度以上離す方が良い。

 

 

クエリによる分布更新のイメージ

サンプリングと更新は以下のようなイメージ。黒の円が事前分布。下の2点を結ぶ辺が最も近い（MST に使われなかった）ことが分かった場合、1000回サンプリングして条件を満たす点が赤い点たち。そこから推定される2次元正規分布の2σ領域が赤楕円になる。

 

2次元正規分布からのサンプリング
Lが小さい場合


青の楕円はクエリ前の推定域を2σ水準で表示しています。つまり約86%はこの楕円に入ることになります。楕円でなく正方形になっている場合は、まだクエリとして一度も選ばれていないため初期分布から変化していないことを示しています。

赤の楕円はクエリ後の推定域です。クエリ前に比べて小さくなっていることから、精度が上がっていることが分かります。

 

クエリ前後の推定域の比較イメージ（Seed 26 - turn 189）
Lが大きい場合

点を正三角形状に順につなげています。一気に情報が得られるのでLが小さい場合に比べてターンあたりの情報量がお得です。

 

クエリ前後の推定域の比較イメージ（Seed 2 - turn 84）

 

グループ分け

何も良い方法が思いつかなかったので焼きなましです。

評価関数を MST の長さにすると計算量がやばいので工夫しました。

高校数学で習ったあれを思い出していました。

これ： | \vec{a} - \vec{b} |^{2} = | \vec{a} | ^{2}  - 2\vec{a}\cdot\vec{b} + |\vec{b} |^{2}

 

例えば k 点 A_{1},\ A_{2},\ \cdots A_{k} の集合に点 X を追加した場合の寄与は

 

\displaystyle\sum_{i=1}^{k}| \vec{x} - \vec{a_{i}} |^{2} = k| \vec{x} | ^{2}  - 2\Big(\vec{x}\cdot \displaystyle\sum_{i=1}^{k}\vec{a_{i}} \Big) + \sum_{i=1}^{k}|\vec{a_{i}}|^2

 

となるので、グループごとに \displaystyle\sum_{i=1}^{k}\vec{a_{i}} や \displaystyle\sum_{i=1}^{k}|\vec{a_{i}}|^2 を持っておくと O(1) で計算できます。

 

結果

推定結果

Lが大きいといい感じに推定できます。Seed 2 では誤差の二乗平均のルートが60弱ぐらい。

楕円（または長方形）が2σの推定域で、点が真の位置。

推定結果 - Seed2

 

Lが小さいときは全然だめです。

Seed 0 は以下のような感じ。楕円がでかすぎるせいで重なって見づらいので点0～49のみを表示しています。元の長方形からほとんど変わっていないものも多いですね。。

推定結果 - Seed0 （0～49）

 

 

 

スコア

結果はこんな感じ。

Lが大きいときは良い感じに見える。

結果 - Seed 2 （190,000点）

 

Lが小さいときはぐちゃぐちゃ。。

 

結果 - Seed 0 （256,632点）

 

クエリはかなり盤面全体を使っている感じです。

 

 

 

*1:実際は種類数が多いことだけが良い訳ではないですが・・。

ChatGPT コードそのままで AHC041 で 44 位が取れたよ

この記事は？

AHC 041 で ChatGPT が書いてくれたコードを貼るだけで 44 位が取れたのでやったことをメモしておきます。

前提

  • プラン
    • ChatGPT o1 （月20ドルのプラン）を使用
  • 筆者について
    • 普段 Python を使っている
      • 今回使った Rust は自力で変更することはもちろん、読むこともままならない状況
      • なんなら Rust は実行環境もない
    • コンテスト直前のレート *1 は 2671
      • レートはほぼルールベースの貪欲や評価関数で稼いでいる
      • 焼きなまし法はほとんど使えていない（部分的に使うことはあったが、それで上位に入れたことはない）
  • 今回 ChatGPT に頼った経緯
    • 前半 2 時間ぐらいは自力で頑張っていたが、 BFS を繰り返すような解法（本番 700 位相当ぐらい） *2 しか思い浮かんでいなかった
    • 普段なら諦めていたかもだが、賞金首 *3 だったのでさすがに何か出そうと思って一生懸命考えたけど何も思い浮かばなかったので、仕方なく焼きなましをお願いすることにした
    • 普段使っている Python じゃなくて Rust にした理由
      • 焼きなましするなら速度が速い方が良さそうなので
      • 自分で書き換えができないというデメリットがあるが、 o1 君を信じてお願いした

概要

やったことは概ね次のとおり。

  • 焼きなまし法の指示を与えて Rust でコードを書いてもらう
  • 温度の変化を線形→指数にしてもらう
  • 差分計算するようにお願いして高速化してもらう
  • 温度の初期値・最終値、イテレーション数のみを変更してコードそのまま提出

なお、本記事では最終コードを得ることに直接繋がったもののみを記載しています。 途中で試行錯誤して棄却したものなどは省略しています。

最終コード（75,120,936 点）

具体的なプロンプトの流れ

ChatGPT へのプロンプト全文は こちら にあります。 全文だとコード部分が長いなど流れが分かりづらいので、プロンプトとその意図などを以下で説明します。

ステップごとに、

  • ChatGPT o1 に投げたプロンプト

  • 意図・感想など

の順に記載します。プロンプトは折りたたんでいるので読む際はクリックして開いてください。

ソースを貼り付け

プロンプト

AtCoder Heuristic Contestで次の問題が出たよ。これについて聞きたいんだけど協力してくれる？

（中略：問題ページの HTML ソースをそのまま貼り付け）

次に質問するね。

まずは HTML のソースをそのまま貼り付けます。 質問内容をあとで変更しやすいように、一投目では質問をしないようにしています。 何も書かないとここで考察をしてきて邪魔になる *4 ので、次に質問すると伝えています。 （質問回数・トークン数 *5 の制約を考えると一気に聞いた方がお得な気もするのでこのへんは好みで。）

焼きなまし法を指示

プロンプト

焼きなまし法で実装したい
具体的には、
状態の持ち方は、
・各頂点の親番号（根の場合は-1）
・各頂点の子のリスト
・各頂点の深さ（問題文でいう「高さ」）

を持つ。
近傍は
・ある頂点の親を、別の隣接頂点に変える
　・それによって高さがHを超えた頂点は独立頂点とする

スコアの変動を計算し、温度関数によって採択されれば遷移する。
（N頂点全体を確認するのではなく、高さが変わった頂点のみ寄与を計算する。）

これをRustで実装してくれる？
あなたは優秀なプログラマーなので、必ず、そのまま提出すると先ほどの問題に正解できるコードを一発で書いてね。

ここで具体的な指示を与えました。 現時点では o1 はまだ自分で焼きなまし法のための状態や近傍を考えるのはそこまで上手ではないため、こちらで概要を指示しています。 なお、「高さが H を超えた頂点は独立頂点とする」というのは無駄が大量に発生しそうで正直いまいちな感じがして、まずは第一弾として投げてあとで近傍を再検討するつもりでしたが、案外それなりのスコアになったので結局最後までこのまま行きました。

温度関数を指数的に

温度関数を指数的に

let temp = start_temp * (1.0 - progress) + end_temp * progress;
のところを、指数関数的に温度を下げる場合は、この行をどう変更すればよい？

冒頭に書いたとおり、 Rust を書けないのでこういう変更もすべて教えてもらいます。 変更箇所が分かっていて全文は不要だったのでこういう聞き方をしています。

let temp = start_temp * (end_temp / start_temp).powf(progress);

という書き方を教えてくれました。

エラーが出た

can't call method powf on ambiguous numeric type {float}
って言われた

コードテストで実行するとエラーが出たので文句を言います *6 。 すると宣言のところをこう変えてねみたいなのを教えてくれました。言われたとおりに修正すると動くようになりました。

変更後コードを共有

（略：先ほど教えてくれた行を変更したコード全文をまるごとコピー）

ありがとう。こういう風にしてやってみた（どこを変えたか分かるかな）。
次に質問するね。

手元で動いたので、ついでにパラメータ（温度の初期値・最終値・イテレーション数）を変更した。 この時点で投げると 65,725,312 点（本番 510 位相当）になった。 提出コード

コードの同期も兼ねて現時点のコードを共有 *7 。

最初のところと同様、余計な考察はここでは書かないでほしい（ので「次に質問する」と書いた）が、変更箇所は把握してほしいという意図を反映しています。 すると、意図通り変更点のみ教えてくれました。

変更点を教えてくれた

主に以下の点が変更されていますね。

1. 温度を線形に下げる処理

（中略）
をコメントアウトして、代わりに
（中略）
として、指数関数的に温度を下げる方式に切り替えている。

2. 温度パラメータ

- start_temp: f64 = 3e2; (300)
- end_temp: f64 = 5e-1; (0.5)
のように開始温度や最終温度を大きく変更している。

3. 最大イテレーション数

- max_iter = 2000; から
- max_iter = 80000;
と、試行回数を大幅に増やしている。

これらの変更によって、探索範囲が広がりつつ、温度がゆっくり（指数的）に下がるようになり、より多くの近傍探索を行えるようになっています。

高速化のお願い

プロンプト

高速化するために、毎回BFSをするのではなく、差分計算でやってくれる？
各頂点vについて、深さがdからd_nextになった場合、スコアへの寄与は A[v] * (d_next - d) であることが使えるかな。

まじで Rust が読めないので遅そうなところがよく分からず。 直接の流れに影響はないので本記事では書いてないが、他にもいくつか高速化のお願いはしていた（が、あまり速くならなかったなどで棄却していた）。その中で、更新に O(N) かかるみたいなことを言ってたのでさすがにそこは改善できるなと思ってお願いした。

するとこれを実装してくれて、そのまま投げると確かにかなり速くなっていた。

お礼

プロンプト

ありがとう、良さそう！実験して、反復回数は80000→8900000（8.9e6）にしたよ。これでちょうど2秒に収まるぐらい。

700万回で投げると 1567 ms になったので、2 秒に収まるように雑に計算 *8 をして 890 万回にした。時間打ち切りでも良かったが、自分でコードいじれないのでめんどいのとシステスがないので適当に。 これが最終コードで、本番 44 位になりました。

返答

おお、そこまで回しても2秒で収まるのは素晴らしいですね！
焼きなましの反復回数を増やすほど探索精度が上がる可能性が高いので、<em>十分に高速化できている</em>のは大きなメリットです。

ただ、以下の点だけ注意してください：

1. ローカル環境とジャッジ環境の差
- AtCoderのジャッジサーバーは環境・CPU性能・並列状況が異なる場合があります。
- ローカルで2秒ぎりぎりなら、ジャッジ環境で微妙に超えてタイムアウトするリスクがあります。

2. 最適化フラグなど
- コンパイル時に <code>-O</code> や <code>-C opt-level=3</code> 相当の指定で最適化しておくことは非常に重要です。
- <code>cargo build --release</code> に相当するオプションを忘れないようにしましょう。

3. ホットスポット確認
- 更なる高速化を狙う場合、プロファイラなどでどの部分がボトルネックか確認すると良いです。
- もし一度の近傍操作あたりに走る「部分木再計算」の範囲が大きすぎる場合などは、近傍設計の工夫もアリです。

もっとも、<strong>2秒台</strong>で8.9e6回も試行できるのは相当高速化されていて立派です。引き続きうまく動作するように祈っています！

なんか最後すごい褒めてくれたけど、お前が書いてくれたんだよ感しかないです。

お礼を書く意味

ちなみに ChatGPT にお礼書いて意味あるのかと思う人もいるかもです。実際、これも質問回数やトークン数を消費するので書きたくない人もいるかもしれません。

本記事では最終結果に使った部分のみを書いていますが、実際にはプロンプトをいじっていろいろ変えているので、次節のとおり木構造を行ったり来たりします。 現時点では ChatGPT の木構造遷移把握の意味での UI はいまいちなので、どれが良い結果に繋がったのか分かりづらくなります。良い結果になった場合には、何点を得られたかやお礼を書いておくとあとで戻りやすくなります。 *9

（参考） ChatGPT の木構造について

ChatGPT では、一連の会話をしているとき、過去に聞いた質問を変えて再度投げることができます。 より具体的には、例えば Q1 -> A1 -> Q2 -> A2 -> Q3 -> A3 という流れで質問・応答が続いているときに、Q2 を Q2' に変えて再度投げるようなことができ、この場合、新たに Q1 -> A1 -> Q2' -> A2' という流れができます。 新たな流れを聞いたあとも、元の流れを閲覧したり、そこからさらに質問を追加したりできます。つまり全体として質問・応答を含めたやりとりが木構造のように保管されていて、任意の頂点から変更リスタートが可能になっています。

ただ、現時点では ChatGPT をブラウザで確認する通常の方法では、現在選択している流れ（木構造のうち根→葉のうちひとつ）のみ表示される仕組みとなっていて、分岐が多い場合には木全体の把握や、別の葉への遷移はしづらい UI になっているというのが実情です。

なお、 ChatGPT のクエリ処理としては、 (Q1, A1, Q2, A2, ...) の組からなるやり取り全体に対して次に来るべき回答を生成するという処理をしているので、木構造はあくまで UI のためのものだと考えられます。

感想・考察

  • ChatGPT 丸投げでも AHC に AC できる解法を作ってくれたのは衝撃だった
  • まじで書いてくれたコードから温度パラメータ、イテレーション数だけしかいじってない
  • コードを一切書けなくても AHC 44 位になることができることが分かった
  • 今回は o1 くんに実装方針を含めて指示を与えたので、アイデア面でどれぐらい使えるかは今回の結果からは不明
  • より適切な指示を与えていればさらに上位に入れた可能性は十分にある

*1:年始に公開された暫定レート

*2:これ

*3:対象社員より高順位だと賞金の対象になる。詳細はコンテスト トップページ を参照。

*4:見た目が邪魔なのはまだいいけど、あとのクエリへの応答にも影響するので困る

*5:トークン数の説明は本記事では割愛します

*6:私はエラーの意味を分かっていません

*7:手元でも git 管理などしていないので自分で「ここを変更した」と言うより正確

*8:(7.0 \times 10^{6}) \times \displaystyle\frac{2000}{1567} \approx 8.93 \times 10^{6}

*9:実はこの部分に関してはリンク共有するために無駄な部分を消したかったという理由もあります。

AHC 038

 

 

AHC038 に参加しました *1 。

プレテスト 8.6B で暫定 318 位です。

 

ぱっと見解法

  • 見るからに Robot Arms
  • フローっぽいがいろんなフローがある
  • 点集合が固まっていたらルールベースでも強そう？

 

 

最初のアイデア

 

上位勢の最終解法を想像すると、かなり無駄がないだろうと予想。「持ち上げる」→「回転・移動」→「置く」は基本的に 2 ターンで行うぐらいを目指す必要がありそう *2 。これは逆に 2 ターンで行けるやつをマッチングすればある程度いけるはず。

 

限定

クレーンの形状

このままだと考えづらいので、まずはクレーンの形を次のものに限定する。

  • 根から直列にいくつか関節点をつなぎ最終点を「基準点」とする
  • 基準点から直接行ける点に子（葉）を配置する

これにより、「基準点とその子たち」を移動する問題だと考えることができる。

 

タスク分解
  • たこ焼きを持ち上げる・置く操作は最小限にする
    • つまり、「初期配置にありかつ最終配置にないもの」のみを移動させる
    • 各たこ焼きは（途中置き場に置くことはせず）直接最終配置まで持っていく
  • 「持ち上げる」→「回転・移動」→「置く」を 1 セットとして、この単位で行動する
    • つまりあるたこ焼きを持っている状態で追加で別のたこ焼きを持つことは考えない *3
    • 複数のたこ焼きを持っている状態から一部だけを置くこともしない

 

また最後の限定により、やるべきことが小タスクに分解される。これらは任意の順番で行うことができるので、（有向） TSP に帰着できる。

 

平行移動
  • 基準点および子たちは、平行移動のみを考える

言い換えれば、各タスクでは基準点から先の子側の形（基準点からの相対座標）は持つ時点と置く時点で変えない。これにより、移動前後の点集合が固まっている場合など、無駄なくきれいに移動できる可能性が上がる（全体を平行移動できるので） *4 。

 

 

限定条件でのたこ焼きの移動のイメージ

 

なお、根は定義上は葉になるが、根で持ち上げる・置く操作は行わないこととした。

 

最初の実装

最初のサブミッションでは上述に加えさらに次の条件で実装した。

  • クレーンの根から基準点までの辺を 2 つとした
  • 基準点から各子までの距離は、可能な数を x として 1,\ 2,\ \cdots,\ x とした

 

2 辺の長さを決める

基準点までの辺 2 つの長さ（ a, b ）を決める。

辺の長さを固定すると、移動前の各点から移動後の各点までの移動回数が求まる *5 。移動前のたこ焼きの集合と移動後のたこ焼きの集合のマッチングのコストを最小費用流で求めることができる。 a, b を全探索してマッチングコストが最小になるものを選んだ。

 

移動ベクトルごとに分解

上述の限定では、移動ベクトル（ (di,\ dj) ）が同じものは一気に運べるので、最もよく使われている移動ベクトル（これはひとつ前の結果を使用）に属する点が多い方が嬉しい。

これを考慮して最小費用流でマッピングする。

 

図示すると以下の通り。

各文字 X に対して、黒文字 X から白文字 X の移動は平行移動になっている（のでまとめて移動できる）。

移動ベクトルごとの分解（Seed 2）

 

A だけ見るとこんな感じ。

移動ベクトルごとの分解 - 最大勢力のみ（Seed 2）

各移動ベクトルを 1 回で運べる量に分割しタスク化

例えば A の点たちを、いくつかのグループに分け、各グループの点はそれぞれある代表点から 1,\ 2,\ \cdots,\ x の長さであるようにする。

すると、問題は代表点の移動というタスクに分解できる。

 

TSP

各タスクはタスク開始時・終了時の状態（根の位置および各頂点の相対角度）が分かっている。

よってこれは有効辺 TSP に帰着できるので、適当に焼けば良い。

 

 

フローでできそうなこと

 

いろんな段階でいろんなフローが使える。使えなかったものも含めてめも。

  • どの点をどの点に持っていくかというフロー
    • 点から点へのコストを決めれば最小費用流で厳密解が出せる
    • 点と点を結ぶだけでは直接解法にならないので、本稿で紹介したようにマッチングの際などに使う
  • どの代表点をどの代表点に動かすべきかというフロー
    • 代表点から代表点への移動のターン数を前計算することで、マッチングした際に動かすターン数は最小費用流で厳密解が出せる *6 
  • 基準点の動きを決めたあとに、どの点を移動させるべきかを決めるフロー
    • 基準点の動きを決めた際に移動させられる点の個数は最大流で厳密解が求まる
      • これは上述の平行移動限定に限らずできる
    • 他の解法で作ったあとも、最後に 1 つ除いていけるかなど使えるかも

 

 

感想

今回はいい解法がなかなか思いつかず、後半に予定があったこともあり、モチベが上がらなかった（言い訳）。

 

どちらかというと今後にも使えることをやろうと思い、いろいろ試していた。

  • 提供されているツールの使用
  • Copilot
    • これまで競プロには Copilot を使っていなかったが、使うようにした
    • アルゴだとあんまりいらない気もするが AHC だとかなりラクになった
  • クラス化
    • いつもよりクラス化して書いてみた（途中迷走したのできれいではない）
  • ChatGPT
    • Python から聞けるようにした（けど AHC に使うところまで行けなかった）
    • 実行環境と連動させるのをやろうとしていた（断念した）

 

最初に上位を狙える方針を考えてからその方向に進むというのをやりたいところだが、今回はそれが見つからず何もできず終わるというパターンになってしまった。（1 手で結べるものをマッチングするのはワンチャンあるかと思ったけど実装したらダメなことが分かった。）

コンテスト後に TL で上位解法を見るとビムサなどの探索が多いのでどのみち苦手回だったか・・・。

 

End

 

 

*1:参加したと言えるほど参加したかと言われると怪しい

*2:持ち上げるのと置くのは同時にできないので、 2 ターンは理論的に最小。持った後の「回転・移動」には 1 ターンかけることができる。

*3:最後に全体のフローで最適化する余地はある

*4: V が小さいときはあまり良くない気がしたが、最初なのでまあ

*5:実際には一点ずつ動かす訳ではないので最終コストとは異なるが、どういう移動が効率が良いかを探るための簡易チェックとして使っている

*6:タスク間の移動は入っていないことに注意

AHC 036

 

AHC 036 に参加しました。

プレテスト 43,711,795,647 点で暫定 5 位です。やったことをメモがてら残しておきます。

 

 

アイデア

 

  • A の構築
    • 頂点のうち 1 つを「ターミナル」として、各頂点からターミナルに最短でつなぐ *1
    • これはターミナルを根とする木構造にすることで、各葉について「根→葉」のパスを持つことで達成できる
    • 長さがはみ出してしまう場合は類似パスを合体する
  • A を決めたあとの戦略
    • A のうち連続 L_B マスを使う方法のみを考えると、 \mathrm{DP} で最適解が求まる
    • これを基本として推移しつつ、 L_B 未満のマスだけ変えた方が得になる場合にはそれを採用する

 

木のイメージとメリット

こんな感じで、真ん中付近にあるターミナルから各頂点を最短で結びます。

木のイメージ
  • 仮にすべての頂点をターミナルから L_B 以内の長さで結べれば、どの遷移もコスト 1 以内で到達できる（総コスト 600 以内が達成できる）。
    • l_B が大きい場合 *2
  • L_B より長くなってしまっても、一旦ターミナルを経由することでどの頂点にも効率よく到達できる。

 

 

実際のケースの木のイメージ

Seed 0 ではこんなような感じ。

Seed 0 の木構造

 

  • 黄色がターミナル
  • 黒太線が木の辺
  • 青の頂点は葉
  • 灰色の頂点は不要なので使わない（ A に含めない）もの
  • ピンクの頂点は行き先にはならないが使うもの
  • 頂点の横の数字はターミナルからの距離

 

 

最終方針

A の構築

  • ターミナルの選定
    • 行き先となる各頂点までの距離の総和（行き先になる回数で重み付け）が最小となるものをターミナルとする
  • 木構造化
    • ターミナルを根とする部分木であって、ターミナルまでの距離を大きくしないものを選ぶ *3 
    • 各頂点から、ターミナルに近付く辺をひとつ選べば良い
    • ここで不要な頂点（行き先にならない頂点であって、中継点にもならないもの）は無視する
  • パスを抽出
    • できた木について、葉からターミナル（根）までの最短路（パス）を結ぶ
  • パスを合体（長さの節約）
    • これを愚直に並べたものを A としたいが、そのままだと L_A を超えてしまうので近いものを合体する
    • 具体的には、ターミナルを T として、 T \to a \to b \to c \to d \to e と T \to a \to b \to c \to f \to g \to h という 2 つのパスがあったら T \to a \to b \to c \to d \to e \to f \to g \to h のように合体する。
    • 共通部分の長さを x （この例だと x=3 ）、共通でない部分の長さをそれぞれ l_1 および l_2 として（この例だと l_1=2 、 l_2=3 ）、それらが行き先になる回数を c_1 および c_2 とする。
    • ターミナルからの到達時間は、約 l_1 \times c_2 / l_b だけ遅くなり、全体の長さが x だけ短くできる。この効率が良い（つまり x / (l_1 \times c_2) が大きい）ものから貪欲に合体させる
  • パスの連結
    • できたパスを連結して 1 本にする
    • 連結する際は、 2 つをペアにして根を 1 つ省略する感じで
    • 連結の順番は次の指標で雑に焼く
      • ターミナルをまたぐふたつは、なるべく連続目的地になるものを含める
      • ターミナルをまたがないふたつは、なるべく互いに隣接するものを選ぶ
    • 繋げたものを A とする

 

合計の長さを短くするため、類似パスを合体する

 

「根から葉」のパスたちをペアにして繋げる

 

A を決めたあとの戦略

DP による理論値
  • 常に幅 L_B の区間の信号を使うと決めた場合、信号の状態としてありえるものは L_A - L_B + 1 通り
  • 状態としては、 L_B の区間内にある頂点が連結でない場合はそれらを区別する必要があるが、下位互換を無視すれば（実験すると） 500 ～ 1000 程度になることが分かる。
  • これらの間の辺の数は 4 万から 40 万程度なので、 BFS をすることで各状態間で移り合うために必要なコスト（信号の切り替え回数）が求まる
  • さらに \mathrm{DP}[t][s] を「 t 番目の目的地に到達した時点で状態が s であるとき、残りの目的地をすべて辿るために必要なコスト」と定義するとこれは後ろから順に最適手順を計算できる。
    • なお s は t を含むもののみを調べれば良いが、これは多くの t についてあまり多くない

 

部分コピーが必要な場合
  • 長さ L_B の区間すべてではなく一部だけコピーしたい場合が存在する
  • これらの状態をすべて持つと状態が多すぎて \mathrm{DP} ができない
  • よくあるのは、目的地に到達したあともとの道を引き返す場合なので、この場合だけ愚直に処理することにした
全体を複数回トライ
  • 時間の範囲で全体をやり直して最も良いものを選ぶ
    • （と言っても Python だと 1 周 800 ～ 1800 ms ぐらいかかったので、 2 ～ 4 回ぐらいしか回らないが）

 

ビジュアライザ

Seed 0 と Seed 23 の結果はこんな感じ（長いので最後の部分のみ）。

Seed 0 ビジュアライザ

Seed 23 ビジュアライザ




A の経路

Seed 0 の A に現れる頂点を順に結ぶとこんな感じ。隣接していない頂点に移動する場合は緑線で示しています。

（なんか緑が多くて汚い気がしたけどいい方法が思いつかず・・・）

A の経路

感想・関連ポスト

  • 初サブはどれぐらいかなーと思って投げただけだが思いのほか 2 位が取れてびびった
  • そこから序盤元気マンをやるつもりだったが思ったより耐えた
  • 最後の方は小手先でちょっと改善するぐらいしかできなかった（上位勢は何やってるんだ・・）

 

 

 

 

END

*1:ターミナルの個数は 1 または 3 が良さそうだったが、最終的には 1 にすることにした

*2:Seed 23 など

*3:例外として、ひとつの頂点の距離を 1 伸ばす代わりに 1 つの頂点を「不要」とすることができる場合は採用した

AHC 033

 

AHC 033

プレテスト 47 位でした。

 

Seed 0 （83 点）

 

やったこと概要

雑貪欲です。

  • タスクの優先度を決めて、優先度が高い順に貪欲に動き方を決める
  • 具体的には、時刻と位置の組 (t, i, j) （以下、単に「3 次元テーブル」と呼びます）のうちどの部分を占領するかを決める
  • これをたくさん繰り返す

 

前提（自主制約）

問題を簡単にするために、自主的な制約として次を設定する。

  • 各コンテナは、搬入場所と搬出場所を除く中間位置には高々 1 回しか置かない
  • 25 マスのうち下図の 8 マスを一時置き場にする
    • これにより、搬入場所→一時置き場、一時置き場→搬出場所の移動が必ずできる
  • 搬入場所から移動するときは、最初は必ず右方向に移動する（搬入場所内で上下には移動しない）
    • 搬入場所（左端のマス）で上下に動くことを許すと、新しいコンテナが出現してほしくない場合に出現させないようにできるなどメリットがある
    • 一方で私の方針だと実装がややめんどいのでラクすることにした

 

 

最適化方針

  • コンテナの搬出の順番（優先度）を決める
  • 優先度の高いものから運び出すこととすると、「直接搬出場所に移動できる」か「一時置き場に避難する必要がある」かが自動的に決まる
  • 8 個の一時置き場のどの位置に置くかを適当な評価関数で決める
  • これにより、やるべきことは「コンテナ x を (i_1, j_1) から (i_2, j_2) に移動する」という形のタスクに分解できる
  • タスクの優先度は、適当な評価関数で決める
  • 優先度の高いタスクから順に下記を行う
    • 最適なクレーンを選び、そのクレーンでタスクをなるべく最短で行う（そのために必要な 3 次元テーブルを埋める）
    • この判定は DP で簡単にできる
  • 最初のステップ（搬出順）を変えて上記を繰り返す焼きなまし
    • 近傍は、隣接タスクの入れ替えと、あるタスクを可能な限り早く・遅くする、の 2 種類
    • 数百回しかまわらないし毎回一から貪欲してるので焼きなましと言えるかは謎

 

ビジュアライザ

現時点の状況だけでなく、各クレーンがどのように動いているか（止まっているか）を認識したかったので、現時点の状況と全体の動きの両方が見えるようにした。

 

 

 

相対スコア記事について

コンテスト前に相対スコアの立ち回り記事を書いていたところ。

 

kiri8128.hatenablog.com

 

ごめんなさいポイント

記事では、「相対スコアを導入する場合は、ケースによって得点の取りやすさが大きく異なることが多く、単純平均や絶対スコアは全く参考にならない」という話が趣旨のひとつで、その説明のために様々な理論や例を持ち出して説明しました。しかし今回の AHC 033 に限っては、実はどんなケースでも得点の取りやすさはそんなに変わらない（トップ勢のスコア比率は通常 10～20% 程度以内、どんなにひどくても 2 倍になることはまずない）設定だったので、実は絶対スコアの単純平均や対数平均でも十分良い指標になる回でした。

もちろん、記事の趣旨を正しく理解した方は、問題設定を読みどの指標が使えるかを考えることが重要と理解されているはずなので問題なかったかと思いますが、結論のみに注目するとややミスリーディングになったかもしれません。コンテスト開始 5 分でやべーと思ったんですが、さすがにコンテスト中に記事を修正する訳にもいかないので残りの 239 時間 55 分はごめんなさいという気持ちで過ごしていました。

上位勢のスコアがテストケースごとにあまり変わらないことは、順位表からもある程度確かめることができます。

 

 

一応使えたかもポイント

スコアの定義が段階的に変わる場合の説明

相対スコア AHC の立ち回り - Kiri8128の日記

 

今回は、ターンペナルティ、順番（転倒数）ペナルティ、不正な搬出口のペナルティ、搬出されないペナルティ、と 4 段階のペナルティがありました。記事で書いたように、上位勢はほぼ理論値を取ってくる前提で考えてよく、そうするとターンのペナルティ以外は取らない前提で考えるのが良いです。

つまり「搬出口は必ず正しい場所から搬出しないといけない」「搬出順も必ず守らないといけない」として問題ありません。そうすることで考察や実装の手間を省くことができます。