Go to Qiita Advent Calendar 2024 Top
LoginSignup
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@tus_yuuki

AHC018参加記

Last updated at Posted at 2023-03-01

自己紹介

初めまして、Javaで競技プログラミングをやっています。ゆうきです。
普段はシステムエンジニアとして同じくJavaでプログラムを書いています。(たまにSQLも)
競技プログラミングの歴は1年ほどなのですが、すっかりはまってしまいアルゴ、ヒューリスティック共に青コーダーになりました。(ｽｺﾞｲｯ)
今回はAHC018で良い成績(当社比)がとれたので参加記を書いていこうと思います。
暫定67位でした。
※追記　先程システムテストが終わり、64位でした。

問題内容

問題リンクはこちら
Excavation

今回はインタラクティブ形式の問題です。入力と提出プログラムだけで出力が見れないので少し苦手ですね。
内容は以下になります。

【前提】

  • $N$行$N$列の土地がある。$(N=200)$
  • 土地$(i,j)$の岩盤の頑丈さは$S_{i,j}$。$(10<=S_{i,j}<=5000)$
  • $W$箇所の水源がある。$(1<=W<=4)$
  • $K$箇所の家がある。$(1<=K<=10)$
  • 基本コスト(勝手に命名)$C$が設定されている。$(C \in \{1,2,4,8,16,32,64,128\} )$
  • 水源が存在する箇所の岩盤を破壊するとその箇所に水が流れる。
  • 水が流れている箇所に隣接する岩盤破壊済みの箇所にも水が流れる。

【できる操作】

  • 体力$C+P$を消費することで岩盤$(i,j)$の頑丈さを$P$減らす。
  • 岩盤$(i,j)$の頑丈さを$0$以下にすることで岩盤を破壊できる。

【求めたいもの】

・すべての家に水が流れるようにするための岩盤の破壊計画。
・ただし、消費する体力をなるべく少なくしたい。

提出プログラム周りの解説

今回は途中で根本的な方針の変更はなかったのでプログラムを作成順に書いちゃいます。

1.ジャッジプログラムの作成

今回はインタラクティブ形式なので、入力を受け取り適当な解を出力するだけはどんな動きをしているのかよく分かりません。
そのため、提出プログラムの出力に対しジャッジと同じ入力を返すプログラムの作成を行いました。
中身は詳しくは触れませんが、連結判定をUnionFindで管理するだけだったのですぐ作成できました。

ジャッジプログラム内で提出プログラムのインスタンスを作成し、提出プログラムで掘削を行うメソッドをオーバーライドしてローカル検証を行えるようにしています。

提出プログラムの掘削メソッド

class Main{
  /**
   * point (point=i*N+j) をpだけ掘削する
   */
  int dig(int point,int p){
    //座標i,jをpのパワーで掘削するという出力をする
    out.println(new int[]{toi(point), toj(point), p});
    out.flush();
    //ジャッジの入力を受け取り返す
    return in.it();
  }
}

ジャッジプログラム

class Tester{

  void test(){
    //提出プログラムのインスタンスを作成
    Main main = new Main(){
      /**
       * オーバーライドする
       */
      @Override
      int dig(int point,int p){
        //出力は同じ
        out.println(new int[]{toi(point), toj(point), p});
        out.flush();
        //ジャッジの戻り値を計算して返す。
        return judgeDig(point,p);
      }

      /**
       *ジャッジと同じ値を返す処理 
       */
      int judgeDig(int point,int p);
    };

    //実行
    main.run();
  }
}

これで自分のコードの動きをビジュアライザで見られるようになりました。
※パワーの調整も実際にはやってるのですが、2で記載します。
試しにななめ一直線に掘ってみた場合
image.png

2.掘削パワーの調整

これは完全に感覚で、あまり詰められてませんでした。コンテスト終了直後にガウス過程やCNNなどの単語が飛び交っていたので便利なものが調べれば出るんだなぁと思ってTLを眺めていました。
また、掘削し始めると完全に破壊するまで掘削するようにしかできてません。

ので、実装したアルゴリズムをそのまま書いちゃいます。
1 そのセルの総掘削量costを0で初期化する。
2 そのセルの推定硬さestを推定値テーブル※から取得する
3 パワーpを推定値で設定する。
4 パワーpで掘削する。
5 破壊完了したら抜ける。
6 破壊できなければ以下の式で更新して3に戻る。

  //お気持ち
  //・破壊できなかった時に推定値を5000に近づけたい
  //・今の推定値が小さいときはゆっくり、大きいときは早く近づけたい(est/5000が大きいほうがrが大きくなる)
  //・Cが小さいときはゆっくり、大きいときは早く近づけたい(est/5000の肩が小さいほうがrが大きくなる)
  //    よく言えば職人芸、悪く言えば自分ルール適用マン
  double r = Math.pow(est /5000,1.4 -C /320.0);
  est = est *(1 -r) +5000 *r;
  //総掘削量を加算
  cost += p;

※推定値テーブルの算出は3に記載します。

3.推定値テーブルの更新

こちらも完全に自分の感覚でやってました。
○○推定とかちゃんと調べようね。:disappointed_relieved::disappointed_relieved:

ある点を掘削した時にそのセルの硬さが分かります。(ほんとはオーバーしてることもあるので分からない)
また、近くのセルの硬さは似通うのでいい感じに伝播させます。
こちらも実装したアルゴリズムそのまま書いちゃいます。

・estimate[] セル(i,j)の推定値
・estSum[] セル(i,j)の確かさ

各セルに対して以下の式で更新


    //掘削した箇所のi,j座標
    int si = toi(point);
    int sj = toj(point);
    //そのセルの総掘削量を推定値とする
    double est =cost;

    double k = 0.7;

    for (int i = 0;i < N;i++)
      for (int j = 0;j < N;j++) {
        double d = dist[Math.abs(i -si)][Math.abs(j -sj)];
        //掘削した箇所からその座標が遠いほど確かさが少ない(そのセルによる確かさの寄与を0.7^dにする)
        double r = Math.pow(k,d);
        int p = top(i,j);
        //その座標に対しての確かさrを重みにして合成する
        estimate[p] = (estimate[p] *estSum[p] +est *r) /(estSum[p] +r);
        estSum[p] += r;
      }

この推定で10*10のグリッドの中心をそれぞれ掘削するとこんな感じに土地の硬さを推定できました。
ぼくの推定
image.png
ビジュアライザ
image.png

まあまあそれっぽいのでこれでええやろと思ってしまったんですね。。。:disappointed_relieved::disappointed_relieved:
※実際にはこんなに掘ると調査だけでかなりの体力を使ってしまうので調査箇所を減らしてしまい、かなり精度は落ちました。
　最終的には水源、家の土地と経路上を等間隔のみの調査になりました。

4.実際に掘る経路の算出

ここまでは下準備でした。実際に掘る経路を求めます。
特に難しいことはせずに以下を水が行き渡るまで繰り返しました。

  1. 水源→いずれかの家の最短経路をダイクストラ法で求める。
    　※最小シュタイナー木というものは終了後に知りました。ので、近い順につなげています。
  2. 経路上を10マスおきにサンプリングする。
    　サンプリング箇所の近くがすでに掘削済みの場合はスルー(硬さの推定が十分とみなす)
  3. 効率が悪い経路だった場合サンプリング後に最短経路が変わるので経路が変わらなくなるまで1,2を続ける。

google-chrome-2023-03-01-16-45-11.gif
少し早送りなので見にくいですが、サンプル経路の途中で硬い箇所を通ると最短経路が更新されて別の道を試すようになっています。

コンテスト中に行っていたこと

考察方法などを書いていきます。

1.3000ケースで実行した結果の分析

ぼくのPCはRyzen™ 9 5950X (16コア/32スレッド)というつよつよCPUを積んでいるのでいつも頑張ってもらっています。
今回の場合、ケースごとの平均実行時間が3秒程度だったので、20ケースずつ並列実行して大体6分半で終わります。

集計の様子
実行結果をcsvに吐き出して、Excelのパワークエリで読み込んでいます。
%はすべて良いほうが大きい値になっています。

image.png

左側のテーブル

  • file～time 実行した入力の情報やスコア
  • Best比 最も良い成績の実行結果との比較
  • Best差分 同差分
    　Best比が悪いケースをビジュアライザで見比べて何が原因で悪くなっているかの考察をしています。
  • 理論値比 ケースごとの歴代最良スコアとの比較

中央の表

cur 今実行した結果の平均値
best 最も良い成績の平均値
として、以下の分け方でBest比、理論値比を集計しています。
主にパラメータ調整に使っています。
例　あるパラメータを大きな値にした場合に、スコアがKと相関しているようであれば、そのパラメータをKの一次式にする。

  • 全ケース
  • Wごと
  • Kごと
  • Cごと

右側のテーブル

計算用にBest実行時のケースごとの値、理論値をとってあるだけです。

2.試してだめだったこと

改善案として試してみたものの改善しなかった修正です。

  • 経路の算出を水源⇔家だけでなく連結でない家⇔家でも出してみる
    　実装が面倒だったくせにスコアは5%ほど下がりました😡😡
    　ビジュアライザで見てみると経路を出した後のサンプリングする箇所が多くなっていたようです。
  • 一番近い水源⇔家だけでなくすべて水が行き渡るような経路(森になる？)を作ってからサンプリングとかする。
    　一つ目と同じ感じでだめでした。
  • 近くに掘削されたところがないところを柔らかい想定にしてみる。
    　どうしても硬いところを頑張って進んじゃうことがあり、それを回避するためにごちゃごちゃやっていました。が、うまくいきませんでした。(考察不十分)

3.思い出せない…

思い出したら追記します。
パラメータいじいじしかしてなかったかも…

ハイライト

楽しかった思い出です。

初提出

開始16時間で初提出でした。(2回TLE)
絶対スコア 10142998
何人提出していたか覚えてないですが16位で、橙パフォにとても満足していました。

お友達と麻雀

プログラム解説部分に書いたことはこの時点で大体実装していたのですが、パラメータ調整や少し乱暴な実装箇所もあったのでまだまだあげられるつもりでした。

ちょっと改善

開始38時間、深夜2時半でした。
絶対スコア　6187189
ブラッシュアップ程度のことをしただけで結構伸びたのでハイになってますね。

結局朝までやってました。

開始43時間、朝の7時半でした。
絶対スコア　5567329
楽しそう

テンションのピーク

開始57時間、夜の8時半でした。
絶対スコア　5511033
開始して3日も経ってないですが、初めて1桁の順位になることができてとてもうれしかったです。
沢山いいねをもらって調子に乗っていますね。

PC自慢

全然スコアが上がらないのでなんとなく自慢しました。それだけ。
実際はこれ以上全然伸びなかったので半分病んでました。(ちゃんと寝てないのが悪い)

最終提出

後半はパラメータ調整しかできませんでした。
絶対スコア　5023683

コンテスト後に試してみたいこと

精進のために備忘録として書いていきます。

  • サンプリングのための試し掘りは少しだけのパワーを抑える。
    　かなり硬いところを通るのは最終的にも非効率なので、例えば500以下のところしか通らない！みたいな感じでやるとよさそうだなと思いました。
  • 最小シュタイナー木の構築
    　最初に似たようなことは考えたはずなのですが、むずそうだなと後回しにしてそのまま忘れてました。
    　次回以降は参加記を書きながら取り組むのでそこにちゃんと書いておきます。
  • 硬さの推定アルゴリズム
    　ガウス過程、逆距離加重法などのワードが飛び交っていたので勉強するつもりです。
  • 硬さSを既知とした時の最適解を出力してみる。
    　すごい良い解を参考にするのはいつもやっていたはずなのですが、今回忘れちゃってました。😡😡
    　スコアを改善した時にどれだけ良くなったか、悪くなったかの評価がしやすくなると思います。

さいごに

今回の問題はかなり好きな部類の問題でした。
インタラクティブは苦手なのですが、経路を探索する系が好きなのかもしれません。
※一番好きなAHC011 - Sliding Tree Puzzle もスライドする経路を探索するパートが楽しかったです。
何か思い出せば追記します。

5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?