hitoare日記

たまに書きます

AHCに取り組む上で心がけていること

先日のAHC032でHeuristc橙を達成した記念の記事です。 この記事では自分がAHCに参加するときに心がけていることを記します。参考になれば幸いです。

問題文をよく確認する

条件を読み間違えたまま考察し始めると悲惨なので、問題文は入念に読むことを心がけています。

また、アルゴのコンテストより時間に余裕があるので、それ以外の要素もしっかり確認します。

  • ストーリー

問題のイメージを把握するために重要です。

  • 制約

制約を確認しないと部分的に全探索するような解法を見逃す可能性があります。

  • スコア計算方法

スコアの計算式から最適なパラメータが計算できることがあります。

  • 入力生成方法

テストケースの特徴が解法の本質的な部分に関係していることもあります。

ビジュアライザを活用する

解を出力するプログラムが書けたら、とりあえずビジュアライザに突っ込んでみるのが良いです。

利点の1つとして、まずバグが発見しやすくなります。「山登り法を実装したはずなのに解が悪化している」「そもそも制約に反した解を出力している」といったことにすぐ気づけます。

もう1つの大きい利点が、「自分の解法の悪い部分・改善すべき部分を見つけやすくする」という点です。

例えばビジュアライザが明らかに無駄な動きをしている場合、そのような無駄が生まれない美しい解法に到れるのが理想ですが、次善策として強引に無駄を無くす処理を最後に加えたり、ペナルティを重めに課すようにするだけでもスコアが良くなります。

「最終的な解の理想形」をイメージする

これは結構重要で、ここを正確にイメージできるかどうかが最終的な順位にかなり関わってきます。 ヒューリスティックコンテストは多くの場合最適解を求めるのが困難ですが、「最適解はどうなっているか」を雰囲気だけでもイメージできると、そこから使用するアルゴリズムを逆算できます。

例えばAHC032の場合、最適解は「全てのマスで高得点(90%~95%以上?)」が1つのイメージとなります。 その場合、例えば山登り法や焼きなまし法で、「最適解に近い解」から「より良い解」への遷移を具体的に求めたり、乱択で発見することが困難であるという予想が立てられるでしょう。 一方で「1マスだけ最適な値になるスタンプを押して、そこはもう変化させない」という戦略をとれば、少なくとも81マスのうち49マスについては高得点をとれそうです。

また、スコアの上界を求めるのも1つの有効な戦略です。

例えばAHC027では、各マスを訪れる回数を√dに比例させ、かつ等間隔で訪れるものが理論上最適な解であることがわかります。これに近いものを貪欲的に求めたものを初期解として焼きなましなどで改善する手法が有効でした。

なお、この戦略は「理想的な解」のイメージを間違えてしまった場合の修正が難しいというデメリットがあり、特に操作の自由度が高い長期コンの場合に起こりがちです。

私はAHC025で、「最適解では全てのアイテムに対する重さの比がほぼ完全に求まるはずだ」という思い込みから抜け出せず、最後まで良いスコアをとれませんでした。

解を決め打って解く

具体的な解法に近いテクニックですが、「ランダムに最終形を決め打ってそれを達成する手順を求める」を時間の許す限りひたすら繰り返す、という解法が有効なことがあります。(例:AHC011)

アルゴが得意な人が手を付けやすい解法であると思います。

解法を決め打たない、考察の幅を狭めすぎない

例えば「問題文では3種類の操作が与えられているが、効果が薄そうだから操作3は使わなくてよい」などと決めつけて一度考察を始めてしまうと、実際は操作3が必要であってもなかなか原点に立ち返って一から考察することが難しくなります。

とはいえ実践するのは難しく、十分注意していないとコンテスト中の焦りも相まって楽で単純な解法に固執してしまいがちです。

また、アルゴコンでもそうですが、問題を考察する時には「何のアルゴリズムを使うか」から考えてはいけません。 問題に向き合い確実・着実なアルゴリズムを考え、それを改良するという手順で考察するべきです。

パラメータ調整は最後までとっておく

正直これは正しいのかどうかわかりません。適当すぎるパラメータではアルゴリズムの良さも判定できないような気もします。

ただ、パラメータ調整で簡単にスコアが上がるのが楽しいあまりそれに時間を使ってしまうのは当然注意が必要です。

あとがき

とりあえず短期コン1桁順位、長期コン1ページ目を目標としてこれからも頑張ります。

Project Euler difficulty100% 難易度Tier表

現時点でProject Eulerの問題を全て解いているので、今回はdifficulty 100%の問題27個について解説をします。

ProjectEulerは101番以降の問題は原則解法の共有が禁止となっています。 解法の核心には触れないレベルでのコメントを添えてあります。

注意点

  • 完全主観
  • この辺の難易度だと実装はほぼ考慮しない
  • 類題があると気持ち低め
  • 「典型」と書いてあっても、あくまでEuler内で典型というだけであって他の場所ではあまり見ないテクニックだったりする
S+

#763 Amoebas in a 3D Grid - Project Euler

個人的には現時点でPE最強枠 シンプルな設定だけどどこから手を付ければいいのかから難しい 解としてありえるものの構造を考えることになるがかなり複雑

S

#499 St. Petersburg Lottery - Project Euler

正直評価が難しい 重要な性質があるのでそれを見抜けるか、もしくはエスパーするか

#585 Nested Square Roots - Project Euler

Eulerらしい問題 重複を取り除くのに苦戦した記憶

#597 Torpids - Project Euler

どの順で当たったらこの順になる…を整理するのが難しい、 それ以降はゴリ押しっぽいけどそれなりに数学する必要はある

#780 Toriangulations - Project Euler

solved数が異様に少ないけど個人的にはそこまでだと思ってる 条件を丁寧に1つずつ処理してサンプルに合わせる

#792 Too Many Twos - Project Euler

簡単そうに見えて難しい 二項係数関連は公式がありすぎて逆にどれを使えばわからなくなりがち 苦労して通した後にForumの一番上の解法を見て魂が抜けた

#798 Card Stacking Game - Project Euler

すみません完全に実験で通しました

#806 Nim on Towers of Hanoi - Project Euler

結構な量の考察が必要とされる 競プロ的な要素が結構ある問題でオススメ

#812 Dynamical Polynomials - Project Euler

数学パズル好きには刺さる問題だと思う

A

#450 Hypocycloid and Lattice Points - Project Euler

いかつい式が出てきてもきちんと式変形で条件を整理するのが重要

#459 Flipping Game - Project Euler

人によってはC以下かも

#478 Mixtures - Project Euler

(1:1:1)を作れる条件を整理するとよく見る形に

#489 Common Factors Between Two Sequences - Project Euler

計算できる形に式変形する 制約は小さいので甘えよう

#494 Collatz Prefix Families - Project Euler

方針さえ引き当ててしまえば後はやるだけ というかそうでないと困る

#566 Cake Icing Puzzle - Project Euler

「こういう形で求めれたらいいな」的な雰囲気が出つつも計算量を落とすのは工夫がいる 実装はほぼ考慮しないとはいいつつこれは難しかった

#579 Lattice Points in Lattice Cubes - Project Euler

一応それぞれの要素は典型だから地力枠っぽいけど面倒そうな部分が実は全探索でよかったり 最後の最後に一捻りあったりで翻弄される

B

#344 Silver Dollar Game - Project Euler

この手のはまず実験 ただ実験だけで必要十分条件にたどり着くのは難しいのでちゃんと考察も必要

#415 Titanic Sets - Project Euler

典型枠 典型に帰着するまでがちょっと工夫がいる

#439 Sum of Sum of Divisors - Project Euler

これも典型だけど他に比べて1段複雑なのでこの位置に置いた

#502 Counting Castles - Project Euler

ゴリ押しゲーはゴリ押しできると気付くのが難しい 求める値が3つあるが大した問題ではない

#584 Birthday Problem Revisited - Project Euler

典型っぽく見えて雑にやるとオーダー増える 一応PCぶん回しを考慮するとC

#696 Mahjong - Project Euler

発想の似た問題がAtCoderにあるがそのままではないのでこの位置 素で思いつくのは少しむずかしい

C

#331 Cross Flips - Project Euler

着実に考察する

#483 Repeated Permutation - Project Euler

テクニックとしてはかなり面白いと思うけど露骨な類題があるので…

#484 Arithmetic Derivative - Project Euler

典型枠で実装も軽い PCが壊れたときに解法が思いついたのでネカフェで実装して提出した思い出がある 100%最易かも

#495 Writing $n$ as the Product of $k$ Distinct Positive Integers - Project Euler

完全に典型枠になってしまった感じではある

#559 Permuted Matrices - Project Euler

競プロ的にはこれも典型か

総評

この表を作って改めて100%の問題を全部見た感想

  • 763が考察の質・量で頭一つ抜けてる。763と780は(約2年を要して)solved数が最近ようやく100を超えたけど、763は純粋な難しさ由来としても780は考察すら諦めた人がほとんどじゃないかと思う。ただ解法を導くのはそこまで難しくなく、過大評価気味
  • 400番台前半は今では(Eulerで)ド典型になっているやつもあって過大評価気味
  • 494,566とかは他所でまず見れなさそうな問題で凄い
  • 700番台以降とかは難易度は高いけど、ARCとか大学有志コンのボスとかでギリ出そうではある
  • 「式変形してしまえばあっさり」的な問題が多く、やはり問題の見た目で惑わされずにしっかり手計算で考察することが一番重要

Alien DP についてのメモ

Alien DPの自分なりの理解をメモ。

アルゴリズムの説明

 M = ( M_0, M_1, ..., M_n ) を広義で上に凸であることがわかっている未知の数列とする。

与えられた kに対して M_kを求めることを目指す。

 a_i = M_{i+1}-M_i とおくと、 Mが広義で上に凸であることから a_iは広義単調減少である。

この時関数 f_i, g  f_i(x) = -ix+M_i  g(x) = \max\limits_{0 \leq j \leq n}  f_j(x)で定義すると以下の補題が成り立つ。

補題

 x \in [a_i : a_{i-1} ]の時、 g(x) = f_i(x)である。

(ただし便宜上 a_{-1} = \infty, a_n = -\inftyとする)

証明

 a_i \leq x \leq a_{i-1} として、 0 \leq j \leq nに対し f_j(x) \leq f_i(x)を示す。

 j \geq iの時と  j \leq i の時で場合分けする。

 j \geq iの時、

$$ \begin{aligned} f_i(x)-f_j(x) &= -ix+M_i+jx-M_j \\ &= (j-i)x-(M_j-M_i) \\ &= (j-i)x-(a_i+a_{i+1}+\ldots+a_{j-1}) \\ &\geq (j-i)x-(j-i)a_i \\ &= (j-i)(x-a_i) \\ &\geq 0 \end{aligned} $$

である。  j \leq i の場合も同様。

(証明終)

上の補題から、全ての 0 \leq i \leq nに対して g(x) = f_i(x)を満たす xが存在することがわかる。

また、 そのような xが取りうる範囲 [a_i : a_{i-1} ] iが増加するごとに負の方向に移動する。

したがって 0 \leq k \leq nが与えられた時、 g(x) = f_k(x) = -kx+M_k となるような xを求めれば、  M_k = g(x)+kx M_kを求めることができる。

下の画像は M= ( 0, 10, 14, 14, 9 ) の時の f_i(x), g(x)のイメージ。

補足
  •  xが与えられた時に g(x)がそれなりの速度( O(N)とか)で求められる必要がある。

  • 競プロでは M_kを「それぞれにスコアが与えられている何かの集合の中から(条件を満たしつつ) k個選んだ時のスコアの合計の最大値」のように定義した場合、すなわち
     M_k = \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t
    のような形の時、

  
\begin{aligned}  
g(x) &= \max\limits_{0 \leq k \leq n} \left( -kx + \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t \right) \\  
&= \max\limits_{0 \leq k \leq n} \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} (c_t-x) \\  
&= \max\limits_{S \in {\cal S}} \sum\limits_{t \in S} (c_t-x)  
\end{aligned}

と変形でき、DPで g(x)の値と、 f_i(x)=g(x)となる iの値が簡単に求まることがある。

  • 上の議論より、 {M_i}が全て整数ならば g(x) = f_k(x) = -kx+M_k となるような整数 xが存在することがわかる。

  • また、そのような xを二分探索する範囲は [a_{n-1} : a_0 ]を含むように取れば良い。*1

  •  x_0 = a_l = a_{l+1} = \ldots = a_{r-1} の場合、すなわち Mの傾きが [l:r]で単調な場合、全ての i \in [l:r]に対して f_i(x)=g(x)となる。
    後述の問題例のように「 M_k \leq Xを満たす最小の kを求める」ような場合に注意が必要となる。

  • 下に凸な場合は f_i(x) = ix+M_i  g(x) = \min\limits_{0 \leq j \leq n}  f_j(x) とおく。

問題例

atcoder.jp

公式解説より、「 N個のランプのうち隣り合う2つを選ばないように R個選ぶときのスコアの合計の最大値」を求める問題に帰着される。

提出→https://atcoder.jp/contests/abc218/submissions/42826600



atcoder.jp

素直に M_i=(絵をi個選んだ時の価値の総和の最大値)として適用できる。

提出→https://atcoder.jp/contests/nadafes2022_day2/submissions/42869527



atcoder.jp

上の2つと異なり最小値を求める問題。

 M_k \leq Xを満たす最小の k (  =D とおく )を求める必要がある。ここで M_iは下に凸で単調減少である。

公式解説で「上の解説で説明した Alien DP の方法と同様に個数を持って DP して二分探索でも計算できますが、傾きが一定な部分の扱いで少し複雑になるので…」として省略されている二分探索を利用した解法で解いたので、それを紹介する。

 xを固定した時、 g(x) = f_i(x)となる i g(x)が求められれば、何らかの iに対する M_iは求まることと、 M_iの単調性を利用して二分探索すれば良いのだが、

 g(x) = f_i(x)となる iが複数存在する場合は注意が必要である。

最小値を求めるので、補足に書いたように f_i(x) = ix+M_iと置いていたとする。

もし f_l(x) = f_{l+1}(x) =  \ldots  = f_r(x)=g(x), (l < r)かつ M_r \leq X \leq M_lだった場合、単純にDPをするだけでは Dを求められない。

この場合は M_i = g(x)-ix \leq X i \in [l:r] から  i の取りうる範囲を求め、最小値をとれば良い。

提出→https://atcoder.jp/contests/abc305/submissions/42870515

参考にさせていただいた記事

H - Red and Blue Lamps 解説 by Nyaan

Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms

Ex - Shojin 解説 by Nyaan

*1:実際は [a_k : a_{k-1}]を含んでいれば十分だが、両端のほうが目安をつけやすい