sankantsuのブログ

技術メモ・競プロなど

AHC034 参加記

2024/06/16 15:00 - 19:00 に開催された AHC 034 に参加した。 この記事では今回の参加について振り返る。

問題概要

atcoder.jp

N x N (N = 20) のグリッド上の領域があり、各マスの土の高さ h_ij が与えられている。 土の高さは全て合計するとちょうど 0 になる。 高さをならして平らにするような手順のうち、コストが最も低くなるものを求めたい。

結果

最終 135 位 (パフォーマンス 1918)

解法

トラックにあまりたくさん土を積みすぎると移動コストが高くなるので、一定量 K 積んだらそれらをいったん全て埋めに行く。 積み荷が空になったら、また土を積みにいって、積み荷が K を超えたらそれらを全て埋めてという手順を繰り返す。 各時点で拾いに行く場所 (または埋めに行く場所) は h > 0 (または h < 0) のうちBFS で最も近いマスを選ぶ。

なお、K を決め打ったときの1回の実行は 1ms 以下で終わるので、K の値を 80 から 280 まで動かして実行し、最も良いものを選ぶ。

 実行例 (seed0, score=40,829,712)
実行例 (seed0, score=40,829,712)

提出コード

https://atcoder.jp/contests/ahc034/submissions/54640810

経過

問題を一通り読んだ感じでは今回は良さげな解法がさっぱり浮びません。 ターン数重視なのか、それともターン数が増えても積荷の重さを低く抑えたほうが良いのかといったトレードオフがどのくらいのバランス感覚なのかというのが難しそうに思いました。

完全に平らにしなくても一応得点はつきそうな感じですが、さすがにストーリー設定からも高さ 0 に揃えるのは守ったほうが良さそうな気がしたので、とりあえず全マスの高さを 0 にできる簡単な実装を書いて観察してみることにします。

最も簡単そうな感じがしたのは、1周ジグザグに全マスを走査して、h > 0 のマスから余剰分を全部回収しておき、2周目は逆向きに回って h < 0 のマスを全部埋めていくというものです。 若干バグらせつつも完成させ 16:05 に最初の提出。この時点でのスコアは 725,909,637 で 350 番台中盤。 あまり筋の良い方針では無さそうです。

ナイーブな改善として思いついたのは、1周目の間に積荷を持っている状態で h < 0 のマスを通過したら、そのときついでに積荷を下ろしてしまうというもの。運ぶ途中の積荷の重さが軽くなるので良さそうな気がします。 修正量はあまり多くないので 16:18 に提出できました。この時点でのスコアは 1,958,208,123 で倍以上良くなりましたが、まだ 300 番台です。

ちょっとまずいなと思いつつ、ビジュアライザでスコア的に良く無さそうな場所を観察してみると、やはり積荷が重くなりすぎるのが良くなさそうな感じがします。1000 以上載せた状態でしばらく走っていることもありました。

そこで、積荷の重さが一定以上溜まらないように制限して動かすことにします。そこで、積荷を K=100 だけ積んでは全部下ろすループに書きかえを行いました。 また、毎回律儀にジグザグに走るのは明らかに無駄な動きが多いので、目的地はジグザグの経路順で前にあるものから決めるものの、次の目的地までは最短路で動くように書き変えて 17:14 時点で 5,021,333,480 です。 この時点で 140 番ぐらいまで上がり、ようやく希望が見えてきた感じがしました。

さらに目的地自体も BFS で最も近い場所を探すように書きかえて 17:40 時点で 6,230,818,105 になり、さらに K を探索対象として複数パターン実行して良いものを選ぶことで 18:21 時点で 6,974,281,630 になりました。この時点では 2 桁順位まで上がっていましたが、結局ここから時間内にはスコアを伸ばせず 135 番でフィニッシュでした。

おわりに

今回は上位方針があまり想像できないまま終わってしまった感じがします。 良かったところがあるとすれば、正解方針があまりよくわからなくても、貪欲でまずまずのスコアを出すこと自体には少し馴れてきた部分かなと思います。

今回はなんとなくアルゴが強い人たちが上位にいるような感じ (フローとか使ってるっぽい?) がして、そのあたりでも差がついていそうです。 上位の人たちの解法のビジュアライザを見ると、自分が全然想定していなかった動きをしているので、ちょっと今回はちゃんと復習しておきたいかなあと思います。

AHC033 参加記

2024/05/17 から 2024/05/27 までの期間に開催されたトヨタ自動車プログラミングコンテスト2024#5 (AtCoder Heuristic Contest 033) に参加した。 この記事では今回の参加について振り返る。

問題概要

atcoder.jp

N x N (N = 5) のグリッド領域がある。 左端のマスに与えられた順にコンテナが搬入されてきて、これらのコンテナを右端の指定されたマスに、(搬出口ごとに) 指定された順番で搬出する。 すべてのコンテナを運び終えるまでに経過したターン数が絶対スコアとなる。

結果

プレテスト 76 位, 最終 71 位 (パフォーマンス 2132)

AHC031, AHC032 に続いての 2桁順位。 少しずつだが順位が上がっている気がするのは嬉しい。

解法概要

ターンごとに、そのターンの「進捗」(後述) が最も大きくなるような行動のうち実行可能 (小クレーンとコンテナやクレーンどうしの衝突が発生しない) なものを選ぶような貪欲法で解いた。 この貪欲法は 1周あたりおおよそ 15ms 程度で回るので実行時間は余裕がある。 そこで、一時置き場として利用する空きマスの利用順やコンテナの搬入順の組み合わせを 144 パターン実行して最も良い解を選ぶことにした。

Seed 0 から 2000 までを手元で実行した際のターン数の簡単な統計は以下の通り。 平均的にはぎりぎり 80 ターンを下回るぐらいという感じ。

Best: 67, Worst: 96
Mean: 79.88, Geometric Mean: 79.78

ターン数分布のヒストグラム
ターン数分布のヒストグラム

最もターン数の短くなった seed 969 の実行 (67 ターン) の実行の様子を以下に示す。

seed 969 の実行 (67ターン)
seed 969 の実行 (67ターン)

よく見る seed 0 は 91 ターン。難しい。。。

詳細な解法説明

盤面の使いかた

(1-index で) 3,4 列目の 1,2,4,5 行目をすぐに搬出できないコンテナの一時置き場として用いる。 2 列目や 3 行目は小クレーンの経路確保のため常に空けておく。

1 列目 (搬入口) は空になっている場合に限り一時置き場として利用しても構わないことにする。

コンテナの一時置き場として利用する場所の説明
コンテナの一時置き場として利用する場所 (赤枠)

一時置き場のマス目を利用する順番は事前に決め打ってしまうことにした。たとえば、1行目4列目のマスが利用順で 1 位である場合、このマスが空いていたら遠くてもここに置きにいく。 この方法は実装上楽だったので採用したが結構非効率なので、これを緩和するため複数パターンの空きマス利用順を試すことにした。

ターンごとの行動決定について

ターンごとの行動決定は大きく分けて次のような 3 ステップで行った。 これらの 3 ステップの実行は毎ターン行う。

  1. タスク候補 (そのターンに運ぶ対象にしたいコンテナの優先度付きリスト) の生成
  2. 各クレーンに対するタスクのマッチングを決定
  3. タスクに対する進捗の合計を最大化するような行動の決定

1 のタスク候補の生成は、以下のように行う。

  • 前ターンの終了時点でクレーンが運んでいる最中のコンテナがあれば、そのまま今考えているターンのタスクとして追加する。
  • 搬出の順番的に今運び出したいコンテナが盤面上に置かれていればタスクとして追加する。
  • 搬入キューからコンテナを出すために、搬入口にあるコンテナを一時置き場にどかすタスクを追加する。

上の項目のタスクほど優先度が高いものとする。 搬入口からどのコンテナをどかすかについては、i) 今運び出したいコンテナが埋まっている搬入口を対象にする ii) 一時置き場の利用が少なくなるように事前に決定した搬出順に従って対象を決める の 2 通りを考えた (ターンごとに切り替えるわけではなく、貪欲法1周分の間では一定)。

2 のタスクのマッチングは、以下のように行う。

  • コンテナを運んでいる最中のクレーンがあればそのままそのクレーンを目的地へ運ぶタスクを割りあてる。
    • 順番的に搬出可能なタスクであれば搬出口を目的地とする。
    • そうでない場合は一時置き場 (のうち利用順の優先度が高い場所) を目的地とする。
  • コンテナを運んでいないクレーンには、次に運ぶコンテナの場所を目的地としてそこに近づくタスクを割りあてる。
    • これから運ぶコンテナの割り当てについては、優先度の高いタスクから順に最も近くにある空きのクレーンを割りあてていく。

3 のタスクに対する進捗の合計を最大化するような行動の決定について、進捗は以下のように定義する。

  • コンテナを持っているクレーンが目的地に到達したとき、Q (コンテナを降ろす行動) は進捗 +1
  • これから運びたいコンテナの真上にクレーンがある場合、P (コンテナを拾う行動) は進捗 +1
  • コンテナを運んでいる (または次に運ぶコンテナの場所に向かっている) クレーンが目的地に近づいたら進捗 +1, 動かなかったら進捗 0, 遠ざかったら進捗 -1

これらのもとで各クレーンに対して可能な行動とそれに対する進捗の組を列挙する。ただし、進捗として有効な Q や P が実行できる場合はそれ以外の行動は禁止する。 このようにしてクレーンごとに列挙した行動の、全クレーン分についての組み合わせを全て列挙してクレーン同士の衝突が発生しないかチェックし、実行可能な行動の組み合わせのうち最も進捗の合計が大きいものを採用する。 ここでは最悪数千程度の数の組み合わせを毎ターン列挙しているはずで、各組み合わせごとに N2 程度の衝突チェックが入るので結構重く、実行時間的にはボトルネックだったようである。

コンテナの数が 5 個以下になったとき

基本的にこれまで説明した戦略では搬出口を目的地に運搬するのは今すぐに運びだせるコンテナだけである。 そのため、最後に 10,11,12,13,14 のように依存のあるコンテナが残ったりすると、前のコンテナを完全に運び終わるまで次のコンテナを運び始めてくれないため悲惨なことになり、ひどいと 30 ターンぐらいロスしてしまう。

これに対する対処として、残りのコンテナが 5 個以下になったら、すぐに搬出できないコンテナを含めすべてにクレーンを割りあてて、目的地に向かわせるようにした。 ただし、もちろん搬出順に逆転が起こるといけないので、各コンテナについて搬出口までのマンハッタン距離から到着予定ターンを計算し、逆転する場合には後ろのコンテナは目的地に向かわせないようにした。

複数パターンの探索

以上で一時置き場マスの利用順を決め打ったときの貪欲戦略を説明した。 空きマスの利用順を決め打ってしまうと、一時置き場の経由のせいで運搬経路がかなり遠まわりになってしまうこともありあまり嬉しくない。 そのため、今回は 1,2,4,5 行目のどの順番で空きマスを利用するかを 24 パターン順列全探索した。 また、空きマスを行方向に先に使うか列方向を先に使うかの 2 パターンも両方探索した。

さらに、コンテナの搬入順についても空きマス利用が少なくなるように事前に決め打つ 2 パターンと、各時点での搬出可能コンテナのある搬入口からのみ運びだす対象にする 1 パターンの計 3 パターンを調べた。 空きマスが少なくなるような搬入パターンは搬入個数 4 つか 5 つ区切りごとに一時置き場に置く必要があるコンテナの数が最小になるような組み合わせを事前に探索した (上位は DP で全探索した人が結構多かったようである。賢い。。。)。

これらの 24 * 2 * 3 = 144 パターンをすべて実行し、最もターン数が短いものを選ぶものを最終解法とした。 実行時間は間に合いそうだったものの不安だったので、2800 ms 経過した場合は次のパターンは探索せずに打ち切るようにした。

提出コード

github.com

感想

今回は解法説明が長くなったので時系列の日記パートは省略して全体的な感想としてまとめて書く。

実装の大変さ

全体を通しての感想として、今回は特に実装が大変だったように感じる。 問題文を読んだ段階ではややルールが複雑には感じたものの、盤面が小さいし書きあげるのにはそれほど苦労しないのではないかと思ったが、いざ書いてみるとクレーンの衝突が思った以上にやっかいで、今回の実装はこれまで参加したコンテストと比較しても 1番苦労したような印象がある。

今回は終盤になるまで探索要素を入れておらずローカルで簡単に 1000 ケース程度のテストを数十秒で回すことができたのでローカルテストはかなり積極的に回していたが、あるケースでバグを発見して直していよいよ大丈夫かと思ってまたテストを回してみると全然違うテストケースで全然違うバグが発生しているというのを何度も繰り返して心が折れそうになっていた。

最終提出でも実は完全にバグがとれているわけではなく、特定シードの特定の空きマス利用順では行き先が衝突したクレーンどうしが動かなくなったり振動したりしてしまうケースが残っている。 これらは正面からルールベースで対処することを避けて、空きマスの利用順を複数試してうまくいくパターンを見つけることで回避している。

実装はかなり大変だったが、一方であまり高度な知識が無くても比較的素直に思いつくアイデアを完全に動くところまで泥臭く実装できればそれなりに戦える回でもあったのではないかと思う。

Rust での参加について

今までのコンテストは基本的に全て C++ で参加してきたが、今回初めて Rust での参加を行なった。 選択理由としては、

  • 単純に Rust に興味があったから
  • 他の人の Rust の提出コードを読めるようになりたかったから

というのが主な理由になる。 Rust が単純に流行っていて気になるというのもあったし、自分が利用する実ソフトウェアでも Rust で書かれているものが増えているように感じていたので、これらの実装を読めるようになりたいというのもあった。また、言語的にも所有権のチェックやマクロまわりの表現力などにも興味があった。 もう一方の理由については、wata さんの提出コードをきちんと読めるようにしたかったというのが一番大きい。 また、公式提供のビジュアライザ等のツールが読めたり場合によっては流用できたりというのも結構大きいと感じる。 今回も基本的な盤面のデータの持ち方などは初日に読んだ公式提供ツールの実装をかなり参考にした。

少し前から ABC の過去問などは Rust で解いて練習を始めていて、ある程度馴れてきたかなという感覚もあったので、書きかた等でわからないところがあっても調べながら進められる長期 AHC で実戦投入することにした。 今回は実際かなり良い実装練習になったと思う。

まだ不慣れではあるので C++ で書くときよりも実装方法に関して調べることは多かったとは思うが、メモリまわりの変なバグを踏まないというのはやはり開発体験としては良く、全体として開発効率が落ちたということはそれほど無かったのではないかと思う。 また、イテレータまわりの操作などはサードパティーの itertools なども合わせると Rust のほうがだいぶ充実しているように感じて、普段ループで書いていたような処理をイテレータを使ってサクッと 1 行で書けたりするとなかなか気持ちが良い (C++ の std::ranges もう少し使いやすくなってほしいな... 単に馴れてないのも多少あるだろうけど)。

今後やりたいこと

今回は参加途中ターンベースの行動についてのビームサーチなどを構想していたが、実装切り替えの難しさや完成していた貪欲法から見積ったときの実行時間的な厳しさから諦めてしまっていた。 上位解法は見かけた限りやはり何がしかの形でビームサーチを採用しているものが多いように見えるが、どうやってビームサーチ化できる形に書きあげているのかというのはいろいろ見てみたい。 (正直、実装が重すぎてしんどかったので再現実装するところまで復習する気力があるかは微妙である。。。)

また、100 ターンを切るぐらいにそれなりに効率良い解法になってくると、ビジュアライザを眺めていても何がボトルネックなのかよくわからなくなってしまっていた。Kiri さんのカスタムのビジュアライザ みたいなのをサクッと実装できたら格好良いなと思っていて、ビジュアライザの実装なども少し練習してみたいなーと思っていたりする。

次回 AHC も楽しみです!

AHC032 参加記

2024/04/07 19:00 - 23:00 に開催された AHC 032 に参加した。 この記事では今回の参加について振り返る。

問題概要

atcoder.jp

N x N (N = 9) のグリッド上に数字が書かれている。 グリッド上の 3 x 3 領域を選んでスタンプを押すことで、スタンプに書かれている数字をグリッド上の数字に足すことができる。 最終的に、グリッド上の各マスの数字の mod 998244353 の和を最大化したい。

結果

最終 87 位 (パフォーマンス 2130)

前回 (AHC 031) に続いて 2 桁順位。 短期コンでは今までで一番の成績になった。

解法

基本で貪欲左上から合わせていく。 左上の 6 x 6 はスタンプの左上位置を合わせて押したあとの mod が最大となるように 1 回だけ押す。 右上の 6 x 3 ブロックは、各行あたりスタンプを 3 回ずつ使って mod の和を最大化。左下 3 x 6 も同様。 最後に残る右下 3 x 3 ブロックはスタンプ 6 回使って mod の和を最大化。

この配分だと 3 回分スタンプが余るので、余った分は左上ブロックに適当に配分。 余りの分配先のマス集合を変化させて山登りで時間いっぱい回す。

実行例 (seed = 0)
実行例 (seed = 0)

提出コード

https://atcoder.jp/contests/ahc032/submissions/52152178

経過

まずは適当なランダム解法とスコア計算を実装。 最初問題文を読み間違えて mod の和ではなく 和の mod の最大化だと勘違いしていて、スコア計算が合わないことで気づいた。

焼きなましできなくはなさそうだが、1 回の操作の影響範囲が大きいので焼きなましだと近傍つくるのが難しそう。 焼くにしても、とりあえずある程度良い初期解をつくっといたほうが良さそうだと思ったので、とりあえず貪欲で良さげな解をつくる。

一回合わせた場所は後から触らないようにすることで、左上から 1 マスずつ合わせていくことができるので、その方針で実装。 まずは右下の L 字領域は無視して左上 7 x 7 マスで 1 回ずつスタンプ押して合わせていく方法で実装。 さらに、右下の L 字について 3 列ずつや、3 x 3 ずつ各スタンプ 1 回で最大化する実装を書く。 スコアは 10.70T。 ここまでで 59 分。

だいぶ実装がコピペで膨らんでいたりしたので一回リファクタリングをはさむ。 まだこの時点では、まとめて最大化している部分で赤に近いスコア低いマスが目立っていたので、こちらに余りのスタンプ回数を使いたい。 そこで、同じ場所に複数回スタンプを押す際のパターンを全列挙して一番良いパターンを選択する実装を書いた。 スタンプの回数の配分などが概ね落ちついた時点でスコア 11.49T。 ここまでで 133 分。

この時点では実行が 48 ms でだいぶ余っているので、左上ブロックでスタンプを 2 回消費してるマスを適当に変えて複数パターン試してみることにする。 最初単純に乱択にしていたが、後から少し工夫してマス集合を 1 箇所ずつだけ変化させる山登りにしてみる。 貪欲パートがまあまあ重く、山登りの繰り返し回数はあまり多くならないので焼きなましまではしなくてもいいかなという判断。これでスコア 11.59T。 ここまでで 179 分。

最後の 1 時間はスコア計測スクリプトを書いてパラメータ調整を主にしていたが、結局スコア上昇はなし。 終盤は同じような提出を複数回やってもスコアが下っているような気が...。終盤は駆け込みで提出が増えて重いのか、繰り返し回数が減ったりしてるんじゃないかという気がしなくもない。

おわりに

今回は短期 AHC ではじめてある程度良い成績が出たので嬉しいです。 上位陣とおおまかには近い方針を引けている気がするけれど、一方でまだ超えられない壁があるようにも感じます。 細かい点を含めて他の解法などを読んでみて、差が出る場所を考えてみたいと思います。

AHC031 参加記

2024/03/22 から 2024/04/01 までの期間に開催された MC Digital プログラミングコンテスト2024 (AHC 031) に参加した。 この記事では今回の参加について振り返る。

問題概要

atcoder.jp

W x W (W = 1000) のグリッドを長方形の区画に分割して、与えられた予約に割り当てる。 このとき、

  • それぞれの予約に対して割り当てる区画の大きさがその予約が要求する大きさを下回るとコストが生じる。
  • 連続する日付に対して区画の区切り線の変更があると、区切り線の長さに応じてコストがかかる。

問題例 (seed=1)
問題例 (seed=1)

結果

プレテスト 89 位, 最終 94 位 (パフォーマンス 2051)

AHC 011 以来 2 回目の 2 桁順位をとることができた。 長方形への分割戦略として比較的良いやり方を早い段階で考えられた点が良かったと感じている。

最終的な解法

最終的な解法はおおまかには次の 3 ステップからなる。

  1. グリッド全体をいくつかの横線で区切る (この横線は全ての日程で共有する)。
  2. 1 でできた横長の長方形内部に縦線を引いて日ごとの予約に対する区割りを決定する (焼きなまし)。
  3. 隣接する日付について、縦線を少し移動させることで縦線を再利用できないか試す。

1 では、s_k を「各日付の k 番目に大きい予約のうち最も大きいもの」としたとき、上から順に s_1, s_2, ... の大きさの長方形を確保するように線を引いていくことにした。 このようにした意図は、特定の日付に大きめの予約が固まって出てきたとしても要求を満たす区割りが実現できるようにと考えたためである。 1 でつくった横線は全ての日付について動かさず必ず再利用されるので、この部分については区切りの変更によるコストがかからない。

2 ではとりあえず縦線の再利用については考えずに日ごとに独立に、各予約を面積要求を満たすように 1 でつくられた行に割り当てる方法を考える。 これは、問題文で与えられたスコア関数をほとんどそのまま使って焼きなましでつくる。 近傍としては、以下の 3 種類を用いた。

  1. 予約を 1 つランダムに選んで割り当てる行をランダムに移動させる (20.0%)。
  2. 予約を 2 つランダムに選んで割り当てる行を交換する (79.7%)。
  3. 行をランダムに 2 つ選んでそれらに含まれる予約を貪欲に割り当て直す (0.3%)。

計算時間のほとんど (2800ms) をこの焼きなましステップで使っている。

最後に、3 で縦線の共通化によるペナルティ削減を試みる。 まず 2 で求めた各日付の配置について行ごとに小さいほうの予約から順番に左から詰めていって日ごとに仮配置を決める。 その後隣接する日付の配置を見て、縦線を少し右にずらすことで予約に対する面積不足を発生させることなく縦線を共通化できるならそれを採用する。 「i 日目の配置を j 日目の配置を見て変更する操作」を (i, j) と表わすとき、(1, 2) → (2, 3) → ... → (n-1, n) → (n, n-1) → ... → (2, 1) のような順で操作を一通り繰り返すというのを、5 周分行った結果を最終的な結果とする。 複数周分回すのは、一度合わせたつもりの区切りが参照先としていた配置自体が後から変更されてずれてしまった場合に区切り位置を合わせなおすために行っている (つもり)。だいたい 3 周もすれば基本的に配置が動かなくなった。

以下に、実行例を示す。

seed=0 の実行例 (score: 860)
seed=0 の実行例 (score: 860)

seed=1 の実行例 (score: 73385)
seed=1 の実行例 (score: 73385)

提出コード

https://github.com/sankantsu/competitive-programming/blob/master/ahc/ahc031/main.cc

日記 + 考察過程

03/22 (金)

前回の AHC 030 から競プロに復帰していて、今回は復帰後 AHC 2 戦目。 開催開始後に気づいた前回と違って今回は始まる前から楽しみにしていた。

初日は出先だったのでコードは書けないが、とりあえず問題を読んでおく。 ざっと読んだところだと、最終的に面積不足のペナルティと区切り線変更のペナルティがどのくらいの比率で効いてくるのかよくわからないが、とりあえず面積不足のペナルティは最低限減らせるようにしないと厳しそうである。 余剰スペースがほとんどないとして、面積不足を発生させないように長方形をつくり隙間なく敷き詰める問題を考えてみるが、結構難しそう。

その後で入力生成方法をよく読んでみると多少スペースの余りが出るように入力がつくられていることがわかり、一番簡単なケースでは平均で 1/4 も面積が余るようにできているらしい。 前回 AHC 同様に相対スコア制なので簡単なケースでベストに近い点数を出すのは重要だし、難しいケースで面積不足ペナルティが発生するのは多少許容してとりあえず面積余りが出やすい条件をターゲットにして、線を再利用しやすい配置を考えてみると良いかもな、というぐらいの考察をしておいて実装はせずに初日は終了。

03/23 (土)

前日の考察もふまえて実装を行っていく。

最初にやったのは、サンプルの移植と、サンプルについて長方形の縦幅を予約を満たすように広げるようにした拡張版。 それに続いて、スコア計算を問題文どおりに実装した。 素直に定義通り一般の配置に対するスコア計算をやると結構計算が重いので、後々焼きなまし等にもっていくなら差分計算できるように制限して解を考えるのは必須だろうと感じた。

ここまでの考察をふまえて、

  • いくつかの線を再利用し続けられる
  • スコアの差分計算を行いやすい

という点を念頭に、配置方法を日が変わっても動かさない横の固定線 + 日ごとに動かす縦の変動線の組みあわせで構成する、いわゆる「短冊配置」戦略を中心に考えてみることにした。 縦線の隣接日程での共通化は念頭にはあったが、とりあえずは日ごとに独立に面積不足を出さない配置ができないか考える。

固定線の配置については最低限、全日程で最も大きい予約を入れられる大きさは確保しなければならない。 そのように確保した区画に仮に各日付で最も大きい予約を詰めるとしたら、次に面積不足に陥いる可能性があるのは「各日付の中で 2 番目に大きい予約のうち全日程を通して最も大きいもの」であると考えたので、これに合わせて次の固定線を決める。 このような調子で「各日付の k 番目の予約のうち最も大きいもの」に合わせて固定線をつくれるところまでつくるという方針で固定線を引くことで面積不足が発生しづらい固定線の引き方が達成できそうだと考え、この方法を採用することとした。 結局この固定線のつくりかたは最終解法までそのまま引きつがれることになる。

縦の変動線については、各日付ごとに独立に 予約 id -> 割り当て行 の対応を解くことで決定する。 具体的には、各日付について最も大きい予約から順に予約を満たすことのできる行のうち最も残り面積が小さいものから順に割りあてる貪欲法を採用した。

ここまでで横線を完全に横線を再利用しつつ、面積余りを発生させる頻度がそれなりに少ない解法を組むことができたので提出してみると、一瞬だが 9 位という好位置につくことができた。 一瞬でもこのような順位をとれたことは無かったのでこれは嬉しい。

03/24 (日)

この時点でわりと方向性としては悪くない解法を引けている感覚があったので、さらに改善すべく変動する縦線の隣接日程間での共有に考えをうつしてみる。

隣接する日付の予約で面積が近いものがあれば、小さいほうの予約を大きいほうの予約の面積に合わせることで区画の大きさを共通化できるはずである。 この考えに基づいて、隣接する日付の予約から面積の差が最も小さいものからいくつかペアをつくる。 そのうえで、ペアにしたものについて同じ区画を優先的に配置した後で、残りをこれまでと同様大きい予約から順に貪欲に割り当てるという解法を試してみる。

しかし、この解法はうまくいかなかった。 うまくいかなかった原因は、より大きい予約よりもペアになっている小さい予約を配置してしまうために、後から大きい予約を詰められないケースが出てきて面積不足ペナルティでスコアが大幅に悪化してしまっていたためだった。

結局この日は提出は行わず。

03/25 (月) - 03/29 (金)

今回は結局平日は全く時間がとれず、たまに考察はしてみるものの実装は全く進まなかった。

03/30 (土)

一度は 9 位まで上がった順位もほぼ丸 1 週間も放置したので 220 位台ぐらいまで下がっていた。 縦線の共通化は結構難しそうかつできたとしても少し共通化できるぐらいだと限定的な効果しか無いだろうと感じていたので、一度立ちもどって日ごとの縦線の配置を貪欲解法ではなく焼きなましで改善するのを試みることにした。 これでより面積ペナルティを少なくすることと、縦線の長さの合計を減らすことを狙う。

解としては各予約に対して割り当て先の行を対応させる長さ N の配列を持つことを基本として、スコア計算を O(1) にするために行ごとの割り当てた予約の数と割り当て面積の合計を同時に更新する形とした。 近傍は、最初予約の割り当て行の移動と swap の 2 種類で実装した。

近傍が上の 2 種類だけだと面積不足が発生していても局所解から抜け出しにくい傾向があるように感じられたので、もう少し大幅に状態を変化させる近傍として、2 行選んでそれらに含まれる予約すべてを貪欲に配置しなおすという近傍を追加した。 この近傍は他と比べて計算が圧倒的に重いので、iteration 回数を確保するために使用頻度はかなり小さく設定したが、それでもスコア上昇の効果はあったようである。

焼きなまし解法を使うことで、正確な順位は覚えていないが 70 位台ぐらいまで回復した。

03/31 (日)

日ごとの区画方法決定部分の焼きなまし化もとりあえずできたので、改めて縦線の共通化に取り組んでみる。 共通化を優先して先に配置したりしていると面積要求を満たせなくなって本末転倒になることを先週の実装で学んでいたので、今回は縦線の共通化はあくまで補助的な手段で、運が良いときだけできれば良いぐらいの感覚で行ってみることにした。

アイデアとしては、隣りあう日付で偶然近い位置に縦線があったら一方をずらして同じ位置まで持っていけないか考えてみるというものである。 より具体的には、隣りあう日付についてある行の配置を取りだしてきて、一方の配置の縦線位置を左から見ていったとき、もう一方の配置内に存在する縦線位置に重なるところまで右方向に動かせるなら動かすという貪欲法で縦線を重ねていくことにした。 一回の処理では隣接する日付しか扱えないので、これを全ての隣接する日付のペアについて繰り返していく。

最後に、visualizer や繰り返し数のログを観察しながら焼きなましのパラメータを調整する作業をして最終提出とした。

04/01 (月)

改善のアイデアとして

  • 細い長方形区画が連続する配置が出現するなら区切りの方向を変えることで長さを削減する
  • 縦線の共通化を試す前の仮配置として面積順に詰めるのではなくシャッフルしてみるなどして探索パターンを増やす

といった候補を考えていて、余裕があったら試してみようと考えていたが、結局実装する時間がとれず試さなかった。 最終日はときどき順位表を開いて順位が下がっていくのを眺めるだけになっていた。

終了後の感想・反省点

上位陣の解法を見ても配置方法はいわゆる「短冊型」が多く、おおまかな配置戦略としては当たりを引けたかなという感じがした。 ただ、一見似たような短冊型であっても内部の配置を決めるための方針には意外とそれぞれの参加者ごとに工夫があって、スコアもかなり差がついているという印象だった。 解説放送で説明していた固定線と中身の配置の 2 重の焼きなましや、変動線部分の共有を行うための焼きなましなどにつても、いずれも自分では思いつかなかった部分であり面白いと感じた。

これらの情報を見たうえで考えたところスコア影響がありそうな反省点としては、以下などがあげられそうである。

  • 横の固定線配置を貪欲で決めうったまま最後まで改善しなかった。

固定線の配置を今回の自分の解法で割りふると、固定線の配置間隔が必要以上に離れたものになってしまうことがあるように思われる。 これによって、縦線一本あたりの平均コストが必要以上に高くなってしまったり、区画内部の面積余りが発生しやすく最終的に面積不足ペナルティを解消しづらくなっていた可能性がある。 詳細順位表の情報から、自分の提出は N が小さいケースで弱かったことがわかっているが、N が小さいケースでは特に固定線の配置間隔が広がりやすかったと想像される。

  • スコア 1 の最適解達成可能パターンを落とした。

今回の問題では、一部パーティションを全く動かさずスコア 1 を達成できるパターンが存在する。 このこと自体は固定線配置のための貪欲を考察の延長として気付いていたが、スコア 1 が達成できるパターンを実際の入力ケースの中に探したり達成できているか動作を見たりすることはしなかった。 実際 seed 32 がそのようなパターンに相当することを後から知ったが、自分の解法の動作を見てみるとスコア 1 を達成していないことがわかった。 解説放送内での発言によればシステムテストではスコア 1 可能パターンは 28 個あったらしくこれらを取れていると特に自分の順位帯にとっては無視できないスコア影響がありそうである。

  • ローカルテスト・入力傾向の分析をサボった。

今回はコンテスト自体にあまり時間がとれなかったこともあり、基本的に解法の評価を seed 0 - 5 あたりの visualizer で確認するぐらいしかしていなかった。 ローカルテストを気軽に行えるような手順の整備などは今後の長期コンテストに向けての課題である。 また、入力の分布の分析などもやらなかったので、例えばスコア 1 達成可能パターンの発生確率なども評価できていなかった。

解説などで紹介されている方法をいくつか延長戦で試して、また次の AHC に備えたい。

ARC 173 感想

atcoder.jp

結果

Aのみ 1完 50:22 (+0ペナ) Performance: 1395, Rating: 1321 -> 1329

前回 ABC で冷やしていたが、今回は微増

感想

ARC はもともと苦手意識がある。 A 問題から結構難しいし、B 問題解ける確率は 5 割あるかも怪しい気がしていたので結構レート的に厳しい展開になることが多そうだなあと思っていた。

しかし、前日の ABC は私用で出られないことが決まっていたし競プロモチベが上がっている今 rated で出られるコンテストに出ないというのももったいないと思ったので ARC 173 は出ようと思い、週はじめから少しずつ ARC 過去問を解いて対策していた。

案の状、A から結構苦戦するし B はだいたい難しいし、C に至っては現状解く気すら起きないが、コードを書けない移動中などに延々と脳内 ARC (考察だけ) とかやっていると、そのうちなんだか ARC の問題も面白いかもしれないぞという気がしはじめていた。

A

K 番目の "Neq Number" (桁表示の数字が隣接しない数字) を求める。

Writer が同じ chinerist さんということで、直前に A - Periodic Number を解いていた (デバッグ終わってなかったけど...) ので、なんだか見た瞬間似てるなあと思った。

問題文読んでいきなり、11739090 って Neq Number じゃなくない (1 が連続してる)?? って思って困惑したけど、誰か質問するだろうし、まあとりあえずサンプル合わせにいけばいっかと思って放置 (結局誰も指摘しないの...)。

桁 DP っぽい感じはわかって、その上で "K 番目の Neq Number" より、"M 以下の Neq Number の個数" のほうが桁 DP 的に楽そうだなあと思ったので、"M 以下の Neq Number の個数" を O(log M) で求めて二分探索でいっか、とそこまで大きく迷わず決まる。

桁 DP で考えると基本各桁になにがしか数字が入っていてほしいので、便宜上最上位より上は 0 埋め相当で考えていたが Neq Number 的には最上位に 0 が隣接してても "同じ数字が隣接してる" と見なしてはいけないということに気付かなかったりでしばらくバグらせ、なんだかんだ 50 分かかった。

B

座標平面上の与えられた点を使って三角形をできるだけたくさんつくる。

ぱっと見なんか難しそうだなあという印象。 ただ制約小さめ (N <= 300) なので、N^3 でもいいのかあとわかる。 そこから逆算して N^3 でなんかそれっぽいことできるかなあと思って、全部の i,j,k のペアについて点 k が点 i,j を結んだ直線上にあるか? みたいなのは全部計算できるなあと考えた。

そのあたりの情報使ってあとはなんか貪欲とかで解けるんじゃないかなあと思ったけど、いい感じの貪欲が思い浮かばなくて結局何も書けず。 ちょっとマッチング問題ぽさも感じたけど、グラフ的な考察はあまり役に立たなそう? (むしろ hyper graph な気もする。使えそうな定理あるか知らないけど)

終了後になってから、なんなら乱択山登りでもワンチャン通っちゃうんじゃない? と思って適当に書いてみたら通っちゃってびっくり。これ今回は正当解法なのね... writer の第一想定解ではないっぽいけど。 アルゴだからといってあんまり見込ある解法思いつきそうになかったら、それなりに見込ありそうな乱択考えてみても良いのかなあという学び。

面白い問題だった。

C

数列の左から奇数番目の数が中央値にならないように区間を広げたときの大きさを全部求める。

B がすぐ解けなさそうだったのでとりあえず問題だけ見てみたけれど、やっぱり C は難しそう。 区間だし頑張ればセグ木とか乗るの? とか適当な考察をしてみるも、区間の中身ほとんど全部覚えとかないと区間合併して中央値とか求まらなくない? と思ってやっぱりよくわからないので諦め。

まだ書いていないけど、解説放送聞いて解法のお気持ちは理解したつもりなので、後で勉強がてら書いてみよう。 考察が少し難しいけど、あんまりマニアックな知識がいるわけではないしよくできてるなあと思った。

yukicoder 5020 (Averaging) 感想

yukicoder という有志作成の問題を解くコンテストに参加した。 今回は4時間の短時間 heuristic コンテストで、作問は E869120 さん。

問題

https://yukicoder.me/problems/no/5020

N (=45) 枚のカードの表裏に数字が書かれている。 2 枚のカードを選ぶと、表裏の数字のそれぞれを 2枚の平均に変化させる。 50 回以内の操作で 0 枚目のカードの表裏の値の両方をできるだけ 5 x 10^17 に近づけたい。

結果

39,532,303 点で 27 / 84 位とまずまず

解法

適当な貪欲法 (スコアが高くなるように 0 と何回か交換) で初期解をつくり、ランダムな操作の挿入/削除を近傍とした焼きなましを行った。 改善としては初期解の改善や、近傍の変更として

  • 操作内容のランダムな変更
  • 適当な 2 操作の順番の swap

を行ってみたが、スコアは改善せず。

終了後

writer 解を見てみると、0 と他すべてのカードの交換を基本として操作順の swap を行って焼きなますというものだった。 これだけで 80M 以上出るとのこと。

自分の解と比べて何が良いのかというと、近傍でのスコア変化が小さく設計されているということらしい。 最初のほうの順番の変更はその後の操作で値が均されてほんの少ししかスコアが変わらなくなるということだろう。

実際少しためしてみると、ほとんどチューニングしなくても 78M のスコアが出た。 焼きなましの改善で何をすれば良いかわからなくて止まってしまったけれど、今回のポイントはスコアが極端に変化しないように近傍を設計することだったのかなあと学びを得た。

ABC342 感想

2024/02/24 1 年半ぶりに algorithm コンテストに参加した。

コンテストページ

https://atcoder.jp/contests/abc342

結果

  • ABCDE5完 (71:20) 0 ペナ
  • パフォーマンス 1652
  • Rating 1311 -> 1354

かなり久しぶりに参加していろいろ忘れている気がしたが、意外と良いパフォーマンスが取れて安心している。

https://atcoder.jp/users/sankantsu/history/share/abc342

感想

先日 AHC030 に参加して久々に競プロ熱が高まっており、algorithm も参加するかと思って出てみた。 かなり久しぶりだったので、当日開催前に ABC341 の問題を解いてリハビリしたりしていたが、overflow やら範囲外アクセスやらでかなりミスを重ねていたので、やっぱり競プロ慣れが抜けているなとちょっと心配になるところもあった。 アルゴリズムもいろいろ知識が抜けている感じがある。いろいろな記事を眺めていると、前に勉強したのにどんな内容だったか思いだせないデータ構造などが結構あった。

レーティングが下がるんじゃないかという不安はあったが、それでも参加するのが慣れを取り戻すには一番だろうと思い、参加はしてみることに決めた。 いざ参加してみると、思ったより順調に進みペナルティもつけずに 5完することができて、レーティングも上昇した。 問題の相性が良かったのではないかと感じるが、ひとまず満足のいく結果がとれて安心した。

A

文字列の中で 1 文字だけ異なるものの index を見つける。

解けないことはないのだが、最初どうやって書くか少し迷ってしまい 9 分も溶かしてしまった。 前後 2文字を先読み後読みすることで解決したのだが、後から解説を読んで 2重ループにしているのを見て、計算量気にしないなら確かにそれが楽だよなと学んだ。

B

数字の出現順のクエリについて答える。

列の長さもクエリも少ないので、計算量気にせず愚直に。 特に迷うところなく、5分ぐらい。

C

1文字置換を繰り返してできる文字列を求める。

文字列もクエリも長いので愚直だとだめ。 少し迷ったが、アルファベットごとの変換テーブルを更新していく形で O(σ(Q+N))。 12 分ぐらい。

D

かけ算して平方数になる値のペア数を求める。

平方数を除算して同値分類するというアイデアはすぐに思いついたが、少し実装をバグらせて時間を消費。 17 分ぐらい。

E

特定の駅に到着するための終発の時刻を求める問題。

問題文が長く、パラメタが多いので読解に時間がかかったが、実質的にはただのダイクストラで queue につっこむ探索候補を少し工夫するだけなので、それほど迷うところはなかった。 そんなに難しくない印象だったが、Atcoder Problems で確認すると水 diff 上位ぐらいになっているので思ったより高い。 自分がこういう無駄に問題文が複雑なパターンを読解するのが比較的得意な部類ということだろうか。 26 分ぐらいで実装。

F

ブラックジャック風のゲームで最適戦略をとったときの勝率を計算する。

E を解き終った時点で残り 30 分あったので取りくんでいた。

まずディーラーの行動は確定的であるので、結果の分布が正確にわかるので、ここから考察してみる。 累積和を組み合わせた DP で終了状態のパターン数が正確に計算できることには気付いた。 しかし、その後最適戦略が何であるかは時間内にはわからなかった。

ディーラーの結果の分布から、プレイヤーが特定の値で stay したときの勝率は正確にわかる。 したがって、stay の勝率と draw の勝率が逆転するかどうかを N から下にむかって検証していき、stay するかどうかの境界を定めれば良いと気付く。 draw の勝率も、累積和 + DP で計算できる。

あとは、この戦略をもとに各値で終了する確率をディーラーのときと同様にプレイヤーの終了分布を計算すれば正解できる。 誤差評価はあんまりよくわかってない。

考察に時間がかかったが、自力 AC することができた。数少ない黄 diff 自力なのでうれしい。