RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）解法など

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013） に参加しました。時間をかけてどっぷり参加でき、システス前 355,714 点 14 位、システス 14,231,546 点 14 位の結果を出すことができました。本解法には以下の特徴があると思っています。

  • コンピュータの移動方法 + コンピュータの接続方法で焼きなましを行う。
  • BFSやDFSといった探索を行わず、貪欲も行わないので実装は軽め。

問題を見たときの第一印象

  • コンピュータの移動はスコアに直接寄与しないので、移動回数を最小限にして接続回数を稼いだほうが良さそう。
  • とりあえず、同じ種類のコンピュータ同士の接続のみを考えたい。
  • 接続の交差を許さないのがめんどくさそう。平面グラフに関するアルゴリズム何も知らない...。
  • 移動するパート + 接続するパートの 2 つを同時に考えるのが難しそう。

方針決め

  • 連結成分の大きさの 2 乗オーダーでスコアが増えるので、小間切れのクラスタをたくさん作るのではなく、 1 つの大きなクラスタを作ったほうがお得。
  • 1 種類のコンピュータを全部つなげた場合 4950 点 ( 50 ケースだと 247500 点) になるが、上位陣のスコアはそれよりも全然高い。

よって、 1 種類のコンピュータでクラスタを作成しつつ、 2 種類目のコンピュータでのクラスタ作成も視野にいれることで、 5000 点あわよくば 10000 点を取れうることを目指す。

どうやって方針を実現する？

主に以下の 4 点で悩んだ。

  • Q1. クラスタを作る 2 種類のコンピュータをどうやって決定する？
  • Q2. コンピュータの移動方法をどうやって決める？
  • Q3. コンピュータの接続方法をどうやって決める？
  • Q4. 移動回数と接続回数のバランスはどうやって決める？

それぞれに対して、以下の通りにした。

  • A1. 1 種類目のクラスタをどのコンピュータにするかを固定し、後述する近傍で山登りを行う。 K 種類の結果のうち最もスコアが高いものを使用する。 2 番目のクラスタについては適当に決める。

  • A2. 「どのコンピュータ」が「どの向きに1マス移動するか」の順番を決めておく。移動にてコンピュータ同士が衝突してしまった場合は移動を行わない。

  • A3. コンピュータから右もしくは下へとケーブルを伸ばす順番を決める。盤面外に到達する（赤色点線）、他の種類のコンピュータに到達する（青色点線）、既存の接続と交差する（緑色点線）場合は接続しない。それ以外の場合は接続する。

ケーブルを伸ばす順番を変更することで、以下の 2 つの状態間を遷移できる。

  • A4. 200 回程度の接続回数を確保できるように、移動回数を固定しておく。例えば K = 1 のときに移動回数は常に 50 回とした。もし移動にてコンピュータ同士が衝突した場合、衝突した回数分を接続回数へと追加した。

A1 で作成した初期解を元に、A2, A3の状態で焼きなましを行えそうだったので、焼きなましを行った。

焼きなましで保持する状態

  • 移動方法 (対象コンピュータ, 移動方向) の手順。配列で表現。
  • 接続方法 (対象コンピュータ, ケーブルを伸ばす方向) の手順。配列で表現。

焼きなましの近傍

  • 移動手順の 1 点更新。これをランダムに m 回行う。
  • 接続手順の 2 点スワップ。これをランダムに m 回行う。

ただし、コンピュータの密度を d (=100 \times K / N^2) としたとき m = \lfloor 1 / (1-d) \rfloor とする。コンピュータが密であるほど m は大きくなる。狙いとしては、コンピュータが密であるほど、コンピュータ同士がぶつかり移動が無効なるケースや、そもそも接続同士が交差しないケースが発生しやすいので、たくさん更新することで状態が変わるようにした。

スコア計算、評価関数について

  • 移動手順をシミュレートした後に、接続手順をシミュレートする。
  • シミュレート後の盤面の状態を元にスコアを計算する。
  • 接続の管理には Union Find を使用する。AtCoder Library で言うところの group() を使えばそれぞれの連結成分の大きさが分かり、スコア計算ができる。
  • 正確なスコア計算とは別に以下の評価関数を用意した。
    • 評価1. 1 種類目と 2 種類目のコンピュータのみを評価に使い、連結成分の 3 乗オーダーで評価する（大きなクラスタを過大評価する）。
    • 評価2. 1 種類目と 2 種類目のコンピュータのみを評価に使い、連結成分の 2 乗オーダーで評価する。
  • 焼きなまし過程では時間経過ごとに、評価1を利用、評価2を利用、真のスコアを利用するようにした。

高速化について

  • vectorや配列を使いまわし、生成をできる限り行わないようにした。
  • UnionFind の経路圧縮を行わないようにした。
  • コンピュータの位置や接続状態などを map や unordered_map で持つのではなくサイズ N × N の配列で管理した。
  • コンパイラを GCC ではなく Clang を使用した。

コンテスト後

  • 普段のコンテストでは Python を使ってますが、C++ を使用しました。調査やベンチマークの時間を十分に確保できたので勉強になりました。特に、定数倍高速化の知見が蓄えられたと思います。
  • コンピュータが密なケースにてスコアが伸び悩んだようです。コンテスト中はそんなものだと思っていたので、改善しようとすら思いませんでした。
  • システスに提出した解法は、接続順番の 2 点スワップが実行されておらずバグってました（えー）。諸々のバグを修正したところ、355,714 点 -> 369,069 点まで伸びました。もったいない...

WUPC2020参加記

WUPC2020に、つるさん（@oinori1197）とチーム名「sleep_and_beer」で参加しました。お互いに初めてのチーム戦で不安もありましたが、結果としてすごく楽しめました。ここに記録を残します。

事前準備

  • お互いの得意苦手を考慮して優先担当を決めておく。
    　つるさん：フロー、数え上げ、数学
    　私：ゲーム
  • 使用言語が異なるためコーディング方針は各自に任せる。
  • コンテスト開始直後は私がA問題、つるさんがB問題を考える。
  • 順位表で既に解かれている問題を中心に考える。

コンテスト開始

序盤1（ここまで0完）

私がA問題を、つるさんがB問題を考える。

A問題：場合分けで焦った。緊張で手汗がすごかった。AC（私 00:06）

B問題：構築問題だったようで、つるさんから相談を受ける。

つるさん「（問題の概要を説明）」

私「n が偶数のとき、B_i、B_(i + 1) を適当に決めると A_i * B_i + A_(i + 1) * B_(i + 1) = 0 にできますね」

つるさん「確かに…！！」

私「でも n が奇数のときはどうするんでしょう…」

つるさん「奇数のときは （省略*1）するとうまくできますね」

私「確かに…！！」

みたいな話をして、無事AC（つるさん 00:22）

序盤2（ここまで2完）

私がC問題を、つるさんがF問題を考える。 

C問題：題意を理解したところで、解法が全く見えない。つるさんに相談。

私「（問題の概要を説明）」

つるさん「最大値を求める問題なのに、MOD = 10 ** 9 + 7 を取るんですね」

私「たしかに…なんでだろう…」

落ち着いて考えると、二項係数で重みを考慮した総和を考えると良いことに気づく。「だから、MODを取る設定だったのねー」と合点。サンプルがあったので提出。 AC（私 00:35）

F問題：つるさんがサクッと通してくれた。ありがてえ。AC（つるさん 00:48）

中盤1（ここまで4完）

順位表から、M問題が解かれてたので見る。 

私「これ全方位木DPにしか見えないんですがどうですか…？」

つるさん「全方位木DPですね…」

実装の担当をつるさんに押し付けお願いしました。AC（つるさん 01:23）

︙

つるさんがM問題を実装している間に、G問題を考える。

  • ナップサックで前計算した後に、DPすれば解けるのでは…？
  • dp[休憩をした回数][現在の時刻]で最大筋力を計算できる？ → 一回の遷移にO(T)かかりそうなので、合計O(T^3)で厳しい。
  • DP[最後に休憩した時刻][現在時刻]で最大筋力を計算すると、合計O(T^2)でいけそう...？

つるさんがM問題を通した後、実装に取り掛かるが遷移が破滅。つるさんに助けを求める。

　私「G、なんかバグります…」

　私「何もしてないのに遷移が壊れました…」

　私「自分が書いたコードをうまく説明できません…」 

みたいな話をしてしまって、かなり落ち込む。つるさんに話を聞いてもらうことで冷静にれたのか、個数制限なしナップサックで解けることに気づく。何とかAC(私 02:08)

中盤2（ここまで6完）

つるさんがE問題を、私がJ問題を考える。

E問題：サンプルがなかなか合わず苦戦してた模様。コンテスト終了後に聞いたところ、包除のあれこれでバグってたようでした（包除バグらせがち、分かる）。無事AC（つるさん 03:26）

J問題：SCCして逆辺を貼ってDFSすれば行けるのでは？実装もそんなに難しくなさそう。

K問題：こういうのはまねっこ戦略なんですよね〜 → まねっこ戦略じゃん！

つるさんから、コーディングを譲ってもらって実装。KとJをAC（02:36, 02:53）。コンテスト前に相談していたように、ゲームを担当して解けたので安心しました。

残り1時間30分 （ここまで9完）

この時点で、I問題を30人ほど解いてたので解きたい。つるさんが残りの問題をざっと見たところ、L問題の考察を進められそうとのことで、

  • I問題：私
  • L問題：つるさん

で分担。つるさんが机上でカリカリと考察を進める間、I問題の目処が立ったので、実験コードを書きながら実装。

  • サンプルが合ったので提出(04:10)　→　TLE
  • 計算量を見直して提出(04:33)　→　RE
  • バグを発見したので修正して提出(04:37)　→　WA
  • バグを発見したので修正して提出(04:44)　→　WA

消えたい…

残り15分（ここまで9完）

L問題に関して、つるさんから相談を受ける。

つるさん「三項間漸化式に落とせたんですが、どうしたらいいのか悩んでて…」

私「行列累乗ですかね？」

つるさん「累乗和として求める方法が分からないんですよね」

私「あー、ABCか蟻本で見たことあるような…（蟻本P184に累乗和の話があることを発見する）」

つるさん「これっぽいです、実装してみます！」

つるさん、L問題をコーディングする。私、I問題のバグを目視で探す。 

残り3分（ここまで9完）

ん？これを

f:id:neterukun_cd:20200913190719p:plain

こうすると…？

f:id:neterukun_cd:20200913190721p:plain

 I問題、AC（04:58）！！ 

f:id:neterukun_cd:20200913190830p:plain

バグらせすぎなんだよなぁ...

残り0分

ABCEFGIJKMの10完、全体35位でした。わいわい

f:id:neterukun_cd:20200913190840p:plain

残り−10分

つるさんがL問題をAC！！「流石やでぇ…！！」となりました。本当に惜しかった…

 

感想など

  • チーム戦、楽しい！！！！！！！！！！！！！！
  • 得意不得意をお互いに補えたので良かった。私が取っ掛かりすら掴めなさそうなE問題、L問題を相方が解き進めているという安心感。私は私で、K問題やちょっとした相談などで役割を果たせて良かった。
  • 5時間、意外と集中できる。持て余す時間はなかった。
  • 使用言語が違ってもなんとかなった。ただ、言語が一緒だとお互いのバグ取りなどスムーズにいってた可能性はありそう。
  • コンテスト全体のうち、あと10分ほど時間を捻出できたらL問題通ってたよなぁ。バグを減らすのもそうなんですが、慣れや進め方でも時短できそう。チーム戦面白い。

おわりに

つるさん、チーム一緒に組めて楽しかったです、ありがとうございました。運営の皆さん、面白い問題揃いでまたとない5時間でした、ありがとうございました。　

*1:x * b_0 + y * b_1 + z * b_2 について、b_0 = -z, b_1 = -z, b_2 = x + y とすると良いです

水色になりましたので学びを整理します

はじめまして、ねてるくんと申します。

AtCoderを初めて約3ヶ月、ABC123で水色になれましたので今までの勉強内容を整理します。

f:id:neterukun_cd:20190414143925p:plain

 

 使用言語はPython3です。C++を勉強する予定は当面のところないです。

 

覚えたアルゴリズム

・深さ/幅優先探索（DFS/BFS）

グラフや2次元グリッド上を全探索したいときに利用します。実装には両端キューdequeによるスタック/キューを使います。再帰関数を用いた深さ優先探索もありますがコンテスト本番では実装できた記憶がないです（再帰関数が苦手です…）。

  

・貪欲法

ソートして前から/後ろから順番に考えていきます。難しい問題では、何を基準にソートすれば貪欲に解けるか分からなくなります。貪欲法のための勉強はあまりしませんでしたが、区間スケジューリング問題は知っておくと様々な問題で応用が効きました（区間の重なりが問題になるときによく使えます）。

  

・メモ化再帰、動的計画法（DP）

計算結果の再利用や、漸化式の作成によって計算量を落とせます。難しいです。「再帰の動作を正しく把握する」「状態を同一視してまとめる」というのがとても苦手です。DPまとめコンテストでナップサック問題、LCS、累積和によるDP高速化などを勉強しました。

 

・UnionFind

「2つのグループをまとめる」「2つの要素が同じグループに属するか調べる」をそれぞれO(logN)よりも小さい計算量で実行できます。グループは木構造で管理されます。

グループのまとめ方として、木の高さrankを基準にした実装、木の大きさsizeを基準にした実装がありますが、どちらの方法でも計算量は変わらないようです[要出典です]。昔はランクを用いて実装していましたが、ABC120-Dを経てサイズによる実装をライブラリ化しました。

 

・累積和

任意の区間の総和を求める計算量をO(N)→O(1)にできます。頻出だと思います。添字をバグらせがちですが、2次元累積和まで書けるようになりました。

 

・いもす法

区間クエリを足し合わせるやつを、O(QN)→O(Q+N)にできます。Qはクエリ数、Nは区間幅です。たまにつかいます。

 

・二分探索

探索対象に単調性がある場合（ソートされている、条件を満たす満たさないの境界が一つだけ存在するなどの場合）に探索に必要な計算量をO(N)→O(LogN)にできます。次の2つの場面でよく使いました。

  1. ソート済みリストから値を探したい。
  2. 解を探す問題に対して、解を仮定して判定問題として処理したい。

1に関してはbisectモジュールを使うと容易に実装できます。

一方、2の方が重要っぽくて、めぐる式二分探索と呼ばれている方法によって簡潔に実装できます。典型として蟻本に載ってる最小値の最大化、最大値の最小化、平均値の最大化などを学びました。実践では二分探索を使えることに気づけ無いことが多々あり、「単調性」を意識しておくことが重要な気がします。

 

・最短経路アルゴリズム

ワーシャルフロイドだけ書けるようになりました（forループを3回まわすだけで実装が簡単なので）。ベルマンフォード法は未勉強です。ダイクストラ法は勉強しましたが忘れてしまいました。ABCの範囲ならダイクストラを使わずにDFSで対応できる問題が多いように思えます。

 

・その他、思考停止でライブラリ化したもの

 素因数分解、最小公倍数、最大公約数、ユークリッドの互除法、逆元を用いた二項係数のmod計算

 

取り組んだこと 

・過去問をたくさん解く

文法練習としてABCのAB問題を解き、基本的なアルゴリズムを身につけるためにCD問題を解いてきました。最近はARC056以前のARCのAB問題に取り組んでいます。

f:id:neterukun_cd:20190414155504p:plain

4/14時点で解いた問題です

・できる限り解説を見ずに過去問を解く

初見の問題に対する考察力を上げたいお気持ちなので、できる限り解説は見ない方針で問題を解いています。解けない問題は基本後回しです。しかしこの方法だと、解けない問題が放置されるので、苦手が苦手のままになってしまいがちです…

 

・蟻本を買って流し読みする

蟻本を持っていると安心感があります。中級編の3-2までを一部飛ばしながら流し読みました。

 

・Twitterを見る

モチベーションの向上になります。コンテスト終わった後は、他の方がどういう方針で問題を解いてたか学べます。困ったときは、強い方からアドバイスを頂けます。本当にありがたいです…

 

・コンテストに出る

コンテストで解けなかった問題は記憶に残り定着します。目先のレートよりも今後に向けた大事な知見が得られる気がします。近々だとABC122-Dが本番で解けなくて悔しい思いをしました。

 

取り組まなかったこと

・解の正当性を証明する

問題を解くときに、それっぽい解放が生えたらテンションが上ってすぐ実装に取り掛かってしまいます。結果、実装中に「あっ、これ嘘解法じゃん…」となりがちなので良くないですね、はい。 

ところで、証明って難しいです。アルゴリズムと同様に、証明にも背理法や帰納法などの典型が存在すると思うのですが、典型の使い時が理解できてないです。練習あるのみでしょうか…？

 

・AtCoder以外でのコンテストに出場する

とはいうものの、最近はyukicoderにときどき参加しています。海外のコンテストには参加してません（生活リズムがバグりそうなのに加え、そもそも仕組みがよく分かってないので）。

 

・読みやすいコードを書く

コーディング規約という概念を知ったので今後はそれに倣ってコードを書いていきます。

 

最後に

今年中に青色相当の実力をつけることを目指して頑張ります。