2023-10-26

第34回高専プロコン参加記

2023/10/14~15に開催された高専プロコン競技の参加記です

開発環境

OS: Windows10,11, WSL
使用言語: C++(mingw,gcc, OpenSiv3D)、JavaScript(Nodejsで簡単な対戦サーバを作成)
使用ライブラリ: OpenSiv3D
GitHubレポジトリ: https://github.com/UScuber/procon34
開発期間: 4~8月でゆっくりいろいろ試して、9月後半から本格的に開発を始める

競技ルール

募集要項(https://www.procon.gr.jp/wp-content/uploads//2023/04/4d890277c1072170185a2709f89342d4.pdf)に概要が書かれてます

1対1の対戦で、職人がそれぞれ何人かいて、移動や壁の建築などを繰り返して壁で領域を囲んでいく感じの問題です

領域内にある城の数と、領域の大きさ、建てた壁の数でなるべく敵チームとのスコア差を大きくするように対戦をする感じです

敵の城壁を解体したりして、領域ができないように妨害したり、領域を奪ったりすることもできます

最終的な解法

人間側が建てたい壁の場所を伝えるビジュアライザと、それを入力として味方の職人の行動を決定するソルバーを作成しました

ソルバーのアルゴリズム

ソルバーは建てる壁の座標が複数与えられるので、その情報から、職人を動かしてなるべく最小ターン数ですべて建築をしてください。

といった問題を解きます

複数人の巡回セールスマン問題み(TSP)たいな感じです

移動にかかる距離(コスト)は、何もない場所へ移動を1、敵の壁がある場所へ移動を2(破壊の行動が含まれるため)として、最短経路を求めました

初めに、貪欲法で職人が建築を担当する壁を決めます。貪欲法では、選択された壁それぞれについて、最も距離が近い職人にその壁の建築を担当してもらいます

その後、各職人が担当する壁でTSPを解き、担当する壁をすべて建築する順番のうち、最短となるものを求めす

その後、焼きなまし法を使って、職人全体の移動・建築コストを下げていきます

(これは上の問題を解く良い解法が特に思いつかなかくて焼きなましを使ったので、もっと正確に求められる解法はあると思います)

先ほど貪欲的に決めた職人が担当する壁とその順番を入れ替えたり、担当する壁を変えたりする近傍を探すことでより良い建て方はないか探します

評価値は各職人が担当する壁をすべて建てるまでにかかる最大ターン数としています

評価値の計算は以下の動的計画法を用いて毎計算 $O(N)$ で処理をしました:

$dp[i][j]$ : $i$ 個目までの壁を建て終えて、現在 $i$ 個目の壁から $j$ の方向に職人がいるときの最小コスト $(0 \leq i \leq N)$

差分だけスコアの更新をすることで、指定された城壁が30個くらいだと、 $5\times 10^{5} [\mathrm{回}/\mathrm{s}]$ ほどの処理をすることができました

これだけだと、各職人について行動を求めているだけなので、たまに職人同士で衝突してしまうときがあります。その場合は焼きなましで解を求めた後に、動けない職人のうちどちらかを行動るようにしました

また、大会当日に、壁を建てない職人が出てきて(与えられた建設予定の場所が少ないや、遠すぎるなどが原因)、何も行動しない職人がいた場合は、とりあえず4方向に壁を建てる行動をするようにしました

この解法にする前に考えてたこと

7月くらいまでは、職人全体の行動を探索するようなmctsやαβ法などを実装して城壁を建ててくれるか試したりしましたが、思うように動いてくれない&&パターンが多すぎて探索ができないといったことがあり、この解法はあきらめました(城壁を建てる場所を探索すれば良くなったかもしれない)

あとは、職人1人の行動をあらかじめ探索して、探索した行動の中から一つ決めて全体の盤面の評価値を上げていく焼きなまし法を使った実装も思いついて試してみましたが、これもうまくいきませんでした

自分が実装できそうな方法は何かないかなと思っていたところ、いい感じの場所に城壁を建ててくれないなら、指定した場所に城壁を建てるようにするのはできるかもしれないと考え、上で紹介した最終的な解法を実装しました

ビジュアライザの機能

今回作成したビジュアライザはこんな感じです:

大会で使用した主な機能としては、

建てたい城壁を指定する
- クリックやカーソルで城壁を建てたいマスをクリック
ターン数や得点、得点の差などの情報の表示
職人や壁、池、領域、城などがすべて識別できるような盤面の表示
- 職人は円、壁や池は四角、領域は背景の色を変え、城は星型になっている
行動していない職人の表示
- 何も行動しないターンがあった職人はその時に表示されている番号が薄くなる
初めの対戦データの取得や、データの送受信
- ターンの更新情報の取得は0.1秒に1回サーバーへ問い合わせて変更を検知
- OpenSiv3Dのライブラリを使ってすべて実装
ソルバーへの職人の行動や壁のデータの送信と、ソルバーからの職人の行動の受信
- ChildProcessでソルバーのプログラムをはじめに呼び出し、標準入出力を使って職人の行動データをやり取りする

といったものがあります

自分が初めに想像していた量の2倍以上あり、さらに通信プログラムで大会近くまでバグを修正していたりなどいろいろと大変でした

バグ探し

大会2,3日前くらいにソルバーとのデータのやり取りができていないことがありました

必死になって探した結果、原因はPOSTリクエストが正常に送信できておらず、同期がとれなくなっていることがわかりました

送信する時間を制限時間の700[ms]前ほどにするとこの時は正常に動作しました

今年の大会の目標とか大会までの話

今回の大会の目標は、ファイナルステージ進出して1回勝つ、ほどでした(解法に自信がないということや、チーム内で対戦練習がほとんどできていなかったりしたので)

今年は上位に行くよりも、福井と高専プロコンを楽しもうという感じで出場しようと思っていました

大会の話

大会情報

実際の試合はここから見れます

1日目(ファーストステージ、セカンドステージ)
- https://www.youtube.com/live/pH3l8jdcf0I?si=csKGXZxY149yZEqg
2日目(敗者復活戦、ファイナルステージ)
- https://www.youtube.com/live/9aFyoXUaKxg?si=Mah1J50DLJK8k6oz
対戦履歴
- https://procon2023.kasahara.dev/logs

大会前日

ビジュアライザの壁の指定をやりやすくする(指定したマスの4方向を建設予定にする)

ソルバーは敵の城壁の破壊をしないバグを修正したりする

1日目

予行練習

正常に動いてるかどうかで戦略AI(敗者復活戦で戦う戦略AIとは別)との対戦をする

めっちゃ強いかと思ったけど、いざ対戦してみると戦略AIはランダムに動いてるっぽかった(敗者復活戦で使われた戦略AIは普通に強かった)

ひとまず正常に通信ができて、ソルバーが止まらずに動いてることに一安心

ファーストステージ

始めはグループ内での対戦をしました

Dグループでは、新モンゴル、宇部、釧路高専の計4チームです

第一試合は、新モンゴル高専と対戦しました

試合開始後、数ターンほど相手が行動しなかったため、通信かプログラムがうまくいっていないのかなと思い、始めは攻めるだけ攻めました

先行後攻が反転した後は、大きく逆転されないように守りにてっして、勝つことができました

第二試合は宇部高専と対戦しました

結果はぼろ負けでした...

全体的な戦略がほとんど決まっていないまま対戦したのですぐに陣地が取られてしまいました

対戦チームは横一列に並んで対戦をするのですが、隣から声が聞こえてくると、その数ターン後に大きめの陣地が取られてしまい、これは負けるなと思ってました

ファーストステージで2位だったため、セカンドステージに出場します

セカンドステージ

セカンドステージは米子高専との対戦でした

試合が始まるまでに、この対戦で使用される盤面を事前に見ておき、戦略を3人で考えました

第1対戦では、職人の初期配置が外側だったので、外側に入らないように城壁を建てたあと、周りの城壁を囲みつつ相手の様子をうかがうという感じでいきました

相手が最初の数ターンうまく動いていなかったので、近くの城壁を囲んだ後、中心に入り、相手に陣地が取られないようにしました

第2対戦では、内側の城壁を先に囲み、その後内側に入られないように城壁を建てるという戦略で行きました

セカンドステージは勝つことができ、ファイナルステージに出場できました

1日目夜

ビジュアライザに城壁を立てる命令を送り切れておらず、何も行動しない職人が発生していたため、何もしない職人は周りで建築or解体がないか調べて行動するという処理を追加し、職人が動かないことがないようにしてみました

実装自体は2日目のファイナルステージ前くらいに終わりました

ごはんを食べたらちょうど9時だったので、ABCに参加しました

2日目

ファイナルステージに進出しているチームはちゃんと戦っていたので、勝てるか少し不安でした

次の試合の競技フィールドと対戦相手の戦略をだけをできるだけ読み取ってそれぞれの試合をしていきます

ファイナルステージ第1試合

ファイナルステージ第1試合は鳥羽高専と試合をしました

相手はファーストステージでは城の周りから少しずつ領域を作っていく感じだったので、自陣への侵入を防ぎつつ、自陣内で領域を確保して得点を稼ぐという戦略を立てました

第1対戦は相手があまり行動できていなかったので、戦略を変更し、相手の陣地へ入り大きめに領域をとる方針にしました

プログラムもうまく動いてくれたおかげでかなりの点差で1試合目は勝つことができました

第2対戦では、試合の途中でソルバーでエラーが出て止まってしまいました...

原因は前日から追加で実装していたところのバグが原因です

ソルバーの仕様上、初期状態しか盤面の同期をしないため、半ば無理やりビジュアライザをもう一度起動させます

職人の位置や盤面がずれまくってるのでとにかく何か行動してくれと願って、大量に壁を指定しまくりました

試合後のビジュアライザはこんな感じになってます:

相手もうまく動いていなかったのと、第1対戦で大きく点差をつけることができたのがあり、勝つことができました

ファイナルステージ第2試合

第2試合は松江高専と試合をしました

相手は市松模様をベースに陣地を少し大きめに確保している感じだったので、先に内側の城を取りに行く戦略を立てました

第1対戦は、初めに中心に集中しすぎて上のほうで大きめの領域を取られてしまいました...

その後もずっと優位に立たれていたので、何とか取り返そうと陣地を大きく囲める場所を頑張って探してました

105ターンあたりで真ん中の城を囲んだ領域を囲めそうなのに気づいたので城壁の場所を指定します

116ターン目で大きく陣地を取り返すことができ、何とか逆転できました(スコア遷移を見ると一気に逆転しているのがわかります)

第2対戦は、戦略を少し変えて、大きめの陣地を取られないように、敵の動きを妨害するように試合をしてみました

上のほうでは領域を作られるのを事前に防ぎ、ほかの職人が建築/解体を繰り返す状態に持ち込んだり城を囲んだりしながら耐えてました

取り返した城の周りからちょうど陣地を作れそうなところがあり、城壁を建てるよう指定し、117ターン目で何とか逆転し、最終的に勝つことができました

この試合は対戦が終わるまで勝てるかわからず、ずっと緊張と不安がありました

スコアを見ると途中まで接戦でした

(去年の悔しい思いを払拭できた気もします)

ファイナルステージ準々決勝(第3試合)

準々決勝は香港VTCと試合をしました

過去の対戦を見ると、外側の領域を取りに行く感じがしたので、相手の行動を妨害していく戦略を立てました

第1対戦は、中心からスタートだったので真ん中の城を取った後、入れないように周りを塞いでから内側から陣地を少しずつ取りつつ、相手の職人の妨害をしました

第2対戦は、外側の城を囲みつつ、領域がとられないように相手の職人の妨害をしました

相手が次に何をしようとしているのか考えながら指示を与えていたので、めちゃくちゃ頭が疲れました

これも何とか勝つことができました

ファイナルステージ準決勝(第4試合)

準決勝(第4試合)は福井高専と試合をしました

1,2対戦とも、あと少しで領域が囲めそうという場面がいくつかあったのですが、どうやって囲めばいいのかわからず、点差が開いたまま終わりました

試合前に戦略を考えていたのですが、ここまで進めるとは思っておらず、あまり対策してきていないのでなかなか思うようにいきませんでした

福井強い...

ファイナルステージ3位決定戦

3位決定戦では、ハノイ工業大高専と試合をしました

準決勝の試合で、大きい盤面の場合は城をたくさん囲みに行くのが良いということが分かったので、なるべく城を囲みつつ、相手に領域を作らせないといった戦略にしました

第1対戦では、内側に職人がいたので、内側の城を優先的に建てていきました

なるべく相手の妨害をしつつ城を取っていこうとしたのですが、職人が同じ個所に集まったり、意図した場所に移動しなかったりなどがあり、陣地が少し多めに取られてしまいました

スコア差は120点とかなり抑えたほうかなと思います

第2対戦は、第1対戦の相手の行動を少しまねしつつ、城を取りに行きました

初めは城をどんどん建てていき有利な状況だったのですが、途中で城と領域を取られてしまい、その後逆転されてしまいました

このまま、また4位かなと思っていたのですが、199ターン目で左上の職人が敵の城壁を解体して逆転したそうです(スコア遷移を見るとすごいことになってます)

自分でも盤面を把握しきれておらず、どういう状況なのかあまり理解してませんでした

2試合目で270点差をつけ、合計で150点差でギリギリ勝てました

最終結果は全体で3位でした！

去年悔しい思いで4位だったので、1つ順位を上げることができて嬉しいです

改善できそうなこと

個人的にほかの高専の戦略などを見て改善できそうだと思ったことは、

ビジュアライザに味方/敵だけの城壁などの状態を表示する機能をつける
近くに相手の職人がいないときは陣地がたくさん取れるような行動をするようにする
現在指定されている建設予定の城壁を建てるのにかかるコストの概算を高速に計算して表示する
特定の職人を指定した場所に強制的に移動する

です

メインで開発していた期間がかなり短かったのと、案が思いつかなかったというのもあり、ここまで取り掛かれなかったです

感想

去年より良い順位を出せて、去年目標にしてた3位は達成できました(去年は4位だった)

今年の目標はファイナルステージ進出程度だったので、思った以上に進めることができてめっちゃ嬉しいです

来年も出れたら出たいけど、後輩への競技部門の引き継ぎを優先しようかなと思ってます

2023-03-03

PAST12 (第12回アルゴリズム実技検定) 解説

アルゴリズム実技検定(PAST)の第12回の解法の紹介です

URL：https://atcoder.jp/contests/past202209-open

A - 信号機/Traffic Light
B - クレジット/Credits
C - 偏ったサイコロ/Biased Dice
D - 採点 / Marking
E - 棒倒しゲーム/Hitting Stick Game
F - 薬剤師 / Pharmacist
G - Wildcards
H - ３種の硬貨/Three Types of Coins
I - 毎日のリンゴ / Buying Apple Everyday
J - スプリンクラー/Sprinkler
K - 連結チェック/Checking Connectivity
L - 展覧会 / Exhibition
M - シリーズ / series
N - 上からと横から/From Above and From the Side
O - ２個のボール/Pick Two Numbers

A - 信号機/Traffic Light

問題文が読みにくいけど、頑張って読み解いて実装する

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327282

int main(){
  int x,y,z;
  cin >> x >> y >> z;
  cout << max(y, x + z) << "\n";
}

B - クレジット/Credits

$N$ が最大で500000桁くらいあるので、整数では受け取れない

100で割って切り捨て → 1,2桁を消すと同じなので文字列でそれを行う

サンプルのケースにもあるように1~2桁の時に0を出力しないといけないということに注意して実装する

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327302

int main(){
  string s;
  cin >> s;
  rep(i, 2) if(!s.empty()) s.pop_back();
  if(s.empty()) cout << "0\n";
  else cout << s << "\n";
}

C - 偏ったサイコロ/Biased Dice

サイコロを振る数が3回なのでfor3重ループで全探索できる

ans[i]=サイコロの目の合計がiの時の確率として答えを求めていけばよさそう

誤差が怖いので、整数で計算してから最後に $100^{3}$ で割ることにする

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327358

int main(){
  constexpr int n = 6;
  vvi p(3, vi(n));
  rep(i, 3) rep(j, n) cin >> p[i][j];
  vi ans(18 + 1);
  rep(i, n) rep(j, n) rep(k, n){
    ans[i+j+k+3] += p[0][i] * p[1][j] * p[2][k];
  }
  for(int i = 1; i <= 18; i++) printf("%.10lf\n", ans[i] / 1000000.0);
}

D - 採点 / Marking

多重辺があるか、自己ループがあるか、頂点の番号がおかしくないかを毎回確認すればいいので

自己ループ： $u,v$ が同じ値のものがあるかどうか
頂点の番号の確認： $u,v$ が $N$ を超えていないかどうか
多重辺：ほかに同じ $u,v(u\lt v)$ の辺が存在するかどうかをstd::setを使って確認

を辺を追加していくごとに確認していけばいい

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327394

void ng(){
  cout << "No\n";
  exit(0);
}
int main(){
  int n,m;
  cin >> n >> m;
  set<pair<int,int>> cnt;
  rep(i, m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    if(a > b) swap(a, b);
    if(a >= n || b >= n || a == b || cnt.count({ a, b })) ng();
    cnt.insert({ a, b });
  }
  cout << "Yes\n";
}

E - 棒倒しゲーム/Hitting Stick Game

ラウンドが途中で終了するなら、合計が $N$ になっていなければいけない
$M$ 回行ってスコアが $N$ 以下であれば、そこでそのラウンドが終了する
合計で $R$ ラウンド行われている

の条件を満たしているかを調べればいい

最後、ゲームの途中で急に終わっていないかなどのチェックも忘れずにやる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327487

void ng(){
  cout << "No\n";
  exit(0);
}
int main(){
  int r,n,m,l;
  cin >> r >> n >> m >> l;
  vector<int> s(l);
  rep(i, l) cin >> s[i];
  int tot = 0, num = 0, cnt = 0;
  rep(i, l){
    tot += s[i];
    cnt++;
    if(tot > n || cnt > m) ng();
    if(tot == n || cnt == m){
      tot = cnt = 0;
      num++;
    }
  }
  if(tot || cnt || num != r) ng();
  cout << "Yes\n";
}

F - 薬剤師 / Pharmacist

各人が持っているアレルギーの種類の合計は $2\times10^{5}$ 以下なので、 $N$ 個の薬それぞれについて $O(D_i)$ で薬を与えられるか判定すればいい

$N$ 個ある薬それぞれに、特定のアレルゲンが含まれているかどうかを $O(1)$ で管理できるようにすれば間に合いそう(提出コードのcntにあたる部分)

計算量は $O(\sum_i C_i + N\sum_i D_i)$

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327642

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<bitset<200010>> cnt(n);
  rep(i, n){
    int c; cin >> c;
    rep(j, c){
      int x; cin >> x;
      cnt[i][x] = 1;
    }
  }
  int q;
  cin >> q;
  rep(_, q){
    int d; cin >> d;
    vector<int> y(d);
    rep(i, d) cin >> y[i];
    int mx = 0, idx = -1-1;
    rep(i, n){
      bool ok = true;
      rep(j, d) if(cnt[i][y[j]]){
        ok = false; break;
      }
      if(ok && chmax(mx, a[i])) idx = i;
    }
    cout << idx+1 << "\n";
  }
}

G - Wildcards

制約的に?の位置は全探索できそう

bit全探索を使ってbitが1になっている数(popcount)が $K$ の時だけ調べるようにして、 $T$ を $N$ 個の文字のどれかにして全探索する

計算量は $O(_NC_KLN^{2})$ 。だいたい $2\times10^{9}$ になるけどたぶんC++だと間に合う(C++で提出すると642[ms]だった)

もう少し高速化を考えると、?になる部分を除いた文字列の中で一番多く重複している文字列の数を求めればいいのでmapを使えば $O(CLN\log N)$ で解ける。だいたい $2\times10^{7}$ くらい。公式解説に書かれている解法です

下のソースコードは遅いほうで書かれてます

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39327743

int main(){
  int n,l,K;
  cin >> n >> l >> K;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  int ans = 0;
  rep(i, 1 << l) if(__builtin_popcount(i) == K){
    rep(j, n){
      int num = 0;
      rep(k, n){
        bool ok = true;
        rep(p, l) if(!(i >> p & 1) && s[j][p] != s[k][p]){
          ok = false; break;
        }
        num += ok;
      }
      chmax(ans, num);
    }
  }
  cout << ans << "\n";
}

H - ３種の硬貨/Three Types of Coins

銅貨より銀貨、銀貨よりも金貨の価値が飛びぬけて高いので、まず金貨を最大化していき、その次に銀貨をなるべく使わないようにするのが一番最適になりそう

袋と銅貨の枚数の2つの状態を持つ動的計画法を考えてみる

$dp[i][j] =$ 袋 $i$ まで見て、銅貨が残り $j$ 枚の時、金貨の枚数を最大化して銀貨をなるべく残したときの金貨,銀貨の枚数

std::pairを使うと比較したときにfirst, secondの順に優先的に並べられるのでこれを使ってfirstに金貨の枚数、secondに(-銀貨の枚数)を入れるといい感じにできる

初期状態は $dp[0][X]=\{0,0\}$ 、ほかはすべて $\{-\infty,-\infty\}$ にする

遷移は袋を買うか買わないかの2通りを考えればいい

下の実装では1次元配列にしてメモリの削減をしてます

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328031

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> a(n), b(n), c(n);
  rep(i, n) cin >> a[i] >> b[i] >> c[i];
  // dp[i][j]: 袋iまで見て、銅貨が残りj枚の時の{金貨,銀貨}の枚数の最大値
  vector<pair<int,int>> dp(x + 1, { -mod, -mod });
  dp[x] = { 0, 0 };
  rep(i, n){
    auto nxt = dp;
    for(int j = x; j >= b[i]; j--){
      pair<int,int> v(dp[j].first + c[i], dp[j].second - a[i]);
      chmax(nxt[j - b[i]], v);
    }
    swap(dp, nxt);
  }
  int k = -1, g = mod, d = -1;
  rep(i, x+1){
    if(chmax(k, dp[i].first)){
      g = -dp[i].second;
      d = i;
    }else if(k == dp[i].first){
      if(chmin(g, -dp[i].second)){
        d = i;
      }else if(g == -dp[i].second){
        chmax(d, i);
      }
    }
  }
  cout << k << " " << 1000000000-g << " " << d << "\n";
}

I - 毎日のリンゴ / Buying Apple Everyday

商品券の枚数 $k$ は $\mathrm{ceil}\left(\frac{Ai}{M}\right) = \mathrm{floor}\left(\frac{Ai+M-1}{M}\right)$ で表せる

$N$ 日間リンゴを買うのは確定しているので商品券の部分だけを考えると、 $\sum_{i=1}^N {\mathrm{floor}\left(\frac{Ai+M-1}{M}\right)}$ を求めたい

これはfloor sumを使えば高速に解ける

floor sum：https://judge.yosupo.jp/problem/sum_of_floor_of_linear
- この問題でいう $N,M,A,B$ を $N+1, M, A, M-1$ にすればいい

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328179

void solve(){
  int n,a,m;
  cin >> n >> a >> m;
  // sum M*((Ai+M-1)/M)-Ai
  ll v = (ll)n * (n+1) / 2 * a;
  ll vv = floor_sum(n+1, m, a, m-1) - floor_sum(1, m, a, m-1);
  cout << vv*m - v << "\n";
}
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  rep(i, t) solve();
}

J - スプリンクラー/Sprinkler

幾何は苦手なのでライブラリに頼ります(https://ei1333.github.io/luzhiled/snippets/geometry/template.html)
- ここの関数Real area(const Polygon &p, const Circle &c)を使うと楽に解ける

円の中心を長方形の中心に置いたときが一番大きい面積になるので、ライブラリの円と多角形の共通部分の面積を求めるものを使うと解ける

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39350450

int main(){
  double h,w,d;
  cin >> h >> w >> d;
  Polygon p{ {0,0}, {w,0}, {w,h}, {0,h} };
  Circle c({ w/2, h/2 }, d);
  printf("%.10lf\n", area(p, c) / h / w);
}

K - 連結チェック/Checking Connectivity

連結判定の問題 → UnionFindを使う

UnionFindは追加が得意で消去は苦手なのに対して、今回の問題は辺の追加クエリが少なく(最大で10個)、辺の消去クエリが多い

クエリを逆向きに処理するということを考えるとUnionFindが得意な形に持っていくことができる

クエリを逆で見たとき、UnionFindでの消去は高々10回しか実行しないので、消去したい辺以外をもう一度すべて結び直せばいい

クエリの最後から始めるのでどの辺が張られていて張られていないのかを気を付けて確認しながら実装する

実装で辺の管理はstd::setを使った

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328625

int main(){
  int n,m;
  cin >> n >> m;
  set<pair<int,int>> cnt;
  rep(i, m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    cnt.insert({ a, b });
  }
  vector<int> use(m);
  int q;
  cin >> q;
  vector<int> t(q), x(q), y(q);
  rep(i, q){
    cin >> t[i] >> x[i] >> y[i];
    x[i]--; y[i]--;
    if(t[i] == 1) cnt.insert({ x[i], y[i] });
    if(t[i] == 2) cnt.erase({ x[i], y[i] });
  }
  UnionFind tree(n);
  for(const auto &x : cnt){
    tree.unite(x.first, x.second);
  }
  vector<int> ans;
  per(i, q){
    if(t[i] == 1){
      tree = UnionFind(n);
      cnt.erase({ x[i], y[i] });
      for(const auto &x : cnt){
        tree.unite(x.first, x.second);
      }
    }else if(t[i] == 2){
      cnt.insert({ x[i], y[i] });
      tree.unite(x[i], y[i]);
    }else{
      ans.push_back(tree.same(x[i], y[i]));
    }
  }
  reverse(all(ans));
  for(const int x : ans){
    if(x) cout << "Yes\n";
    else cout << "No\n";
  }
}

L - 展覧会 / Exhibition

なんか難しそう...

未満以上の基準となる $Q_j$ がバラバラだと判定しずらいので、 $Q_j$ の値をindexにして $P_j,L_j,R_j$ を管理しておくことにする

動的計画法で考えてみる、現在の位置と左右に何個あるのかが必要そうなのでとりあえず、

$dp[i][j][k]=i$ まで見て、 $i$ から左は $j$ 個展示されており、 $i$ より右には $k$ 個展示されているときの点数の最大値

としてみる。が、これだと状態数が $N^{3}$ になってしまい、TLE、MLEになってしまう

ここで、問題の定数倍部分に注目してみると、左右に何個展示されているのかという情報は3で割ったあまりで判定できることがわかるので

$dp[i][j][k]=i$ まで見て、( $i$ から左に展示されている数)%3が $j$ 、( $i$ より右に展示されている数)%3が $k$ ときの点数の最大値

としてみると。うまくできそう

初期化は、左には何もないので0として、右は何個展示されているかは初めの状態では未定なので $k=0,1,2$ について、 $dp[0][0][k]=0$ としておく (この時、 $Q_j=1$ の中で条件を満たすものがあればスコアを加算する)

答えを求めるときは初期化と同じように右はわかっていて左側の展示数は

遷移は $i$ 番目の絵を選ぶ/選ばないの2通りある

選ばないとき：この時 $i+1$ の左右にある絵の数は変わらないので $dp[i+1][j][k] \leftarrow dp[i][j][k]+S$ ( $S$ は $i+1$ の時に加算されるスコア)
選ぶとき：番号 $i$ にあたる絵が展示されるため、 $i$ のときに右側にあった $i$ の番号の絵が $i\rightarrow i+1$ になったときに左側に移る。そのため $dp[i+1][(j+1)\%3][(k-1)\%3] \leftarrow dp[i][j][k]+S$ となる

3は定数倍なので計算量は $O(N+M)$ になる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39328958

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<vector<int>> p(n+1), l(n+1), r(n+1);
  vector<int> len(n+1);
  rep(i, m){
    int v,q,a,b;
    cin >> v >> q >> a >> b;
    q--;
    p[q].push_back(v);
    l[q].push_back(a);
    r[q].push_back(b);
    len[q]++;
  }
  // dp[i][j][k]: iまで見て、iまでで選んだ数%3==j, iより後で選ぶ数%3==kの時の点数の最大値
  vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(3, vector<ll>(3, -1e18)));
  rep(i, 3){
    dp[0][0][i] = 0;
    rep(j, len[0]){
      if(l[0][j] == 0 && r[0][j] == i) dp[0][0][i] += p[0][j];
    }
  }
  rep(i, n){
    rep(j, 3) rep(k, 3){
      // select
      ll v = dp[i][j][k] + a[i];
      const int nxt_l = (j+1) % 3, nxt_r = (k-1+3) % 3;
      rep(pos, len[i+1]){
        if(l[i+1][pos] == nxt_l && r[i+1][pos] == nxt_r) v += p[i+1][pos];
      }
      chmax(dp[i+1][nxt_l][nxt_r], v);
      // not select
      v = dp[i][j][k];
      rep(pos, len[i+1]){
        if(l[i+1][pos] == j && r[i+1][pos] == k) v += p[i+1][pos];
      }
      chmax(dp[i+1][j][k], v);
    }
  }
  ll ans = 0;
  rep(i, 3) chmax(ans, dp[n][i][0]);
  cout << ans << "\n";
}

M - シリーズ / series

DPで解けそう

$dp[i] = i$ 巻目まですべて買ったときにかかる最小コスト

とする。

今回はdpの遷移がちょっと難しい

L~Rの区間で購入するとき、 $dp[R] \leftarrow dp[L] + B$ をするといけそうだけどちょっと怪しい...

区間の本を購入したときのDPの更新を2回行ったとき、共通部分ができていても互いに更新されないようになってるのでこれじゃダメだとわかる( $L={1,3}, R={4,6}$ の時とか)

同じシリーズの本を複数購入しても問題はないので、L~Rを買うときは $dp[R+1] \leftarrow \min_{i=L,...,R} {(dp[i])} + B$ とすればいい

1点更新、区間最小値のセグ木を使うと $O((N+M)\log N)$ で解ける

下のコードのSegmentTreeは1点chmin更新、区間最小値取得のセグ木です

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39329860

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<vector<pair<int,int>>> v(n);
  rep(i, m){
    int b,l,r;
    cin >> b >> l >> r;
    l--; r--;
    v[r].emplace_back(b, l);
  }
  SegmentTree<ll, min> dp(n + 1);
  dp.update(0, 0);
  rep(i, n){
    for(const auto &x : v[i]){
      int val,l;
      tie(val,l) = x;
      dp.update(i+1, dp.query(l, i+1) + val);
    }
    dp.update(i+1, dp.get(i) + a[i]);
  }
  cout << dp.get(n) << "\n";
}

N - 上からと横から/From Above and From the Side

$H,W\leq2\times10^{5}$ かつ $HW\leq2\times10^{5}$ なので、 $\min(H,W)\leq\sqrt{2\times10^{5}}$ となる

横向き(T=1)の場合、dequeを使うと末尾削除と先頭追加のクエリが $O(1)$ でできるので高速に答えられる

縦向き(T=2)の場合、愚直に操作を行って $O(H)$ かかってしまうことになる

$\min(H,W)\leq\sqrt{2\times10^{5}}$ というのを使うと、 $H>W$ の時、縦横をすべて入れ替えてクエリを処理すると、T=2のクエリが最遅でも $\sqrt{2\times10^{5}}$ で答えることができる

そうすると全体で計算量 $O(Q\sqrt{2\times10^{5}})$ でできる

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39330394

int main(){
  int h,w,q;
  cin >> h >> w >> q;
  const bool flip = h > w;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<deque<char>> d;
  if(flip){
    d.resize(w, deque<char>(h));
    rep(i, h) rep(j, w) d[j][i] = s[i][j];
    swap(h, w);
  }else{
    d.resize(h, deque<char>(w));
    rep(i, h) rep(j, w) d[i][j] = s[i][j];
  }
  string ans;
  rep(_, q){
    int t,p; char c;
    cin >> t >> p >> c;
    p--;
    if(!((t - 1) ^ flip)){
      d[p].push_front(d[p].back());
      d[p].pop_back();
      ans += d[p][0];
      d[p][0] = c;
    }else{
      ans += d[h-1][p];
      per(i, h-1) d[i+1][p] = d[i][p];
      d[0][p] = c;
    }
  }
  cout << ans << "\n";
}

O - ２個のボール/Pick Two Numbers

$x = a|b, y = \mathrm{popcount}(a)+\mathrm{popcount}(b)$ と書いてあって複雑なので、とりあえず $x = a|b$ が与えられた時を考えてみる

$a|b = x$ となるすべての $(a,b)$ について $A_a \times B_b$ の合計 $f(x)$ を求めたい。式で表すと $f(x) = \sum_{(i|j) = x} {A_i B_j}$ となる

これはBitwiset Or Convolutionを使うと $O(N2^{N})$ で $f(0),f(1),\cdots,f(2^{N}-1)$ を求めることができる

Bitwiset And Convolution：https://judge.yosupo.jp/problem/bitwise_and_convolution

あとはpopcountをどうすればいいかを考える

$a,b$ でそれぞれpopcountをある値に固定してあげるとOrの畳み込みを使っていい感じに解けそう

-> popcount=0~Nでそれぞれ固定して、それに合ったindexの値だけを使って(それ以外をすべて0にして)Orの畳み込みをして答えを求めていくとできそう

計算量は $O(N^{3} 2^{N} + Q)$ 。ちょっと厳しいかもしれないけど、TLが4[s]でC++であれば何とかなるはず(実際に提出してみると実行時間は1983[ms]でした。提出コード：https://atcoder.jp/contests/past202209-open/submissions/39342834)

高速ゼータ変換したときに、popcountの部分もついでに計算してから戻すというようにすると $O(N^{2} 2^{N} + Q)$ が実現できる。これで提出すると305[ms]になった

提出コード：https://atcoder.jp/contests/past202209-open/submissions/39342872

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,q;
  cin >> n >> q;
  vector<vector<mint>> a(n+1, vector<mint>(1 << n)), b(n+1, vector<mint>(1 << n));
  rep(i, 1 << n){
    int x; cin >> x;
    a[__builtin_popcount(i)][i] = x;
  }
  rep(i, 1 << n){
    int x; cin >> x;
    b[__builtin_popcount(i)][i] = x;
  }
  // bitwise or convolution
  rep(i, n+1){
    fzt(a[i]);
    fzt(b[i]);
  }
  vector<vector<mint>> v(n*2+1, vector<mint>(1 << n));
  rep(i, n+1){
    rep(j, n+1){
      rep(k, 1 << n){
        v[i+j][k] += a[i][k] * b[j][k];
      }
    }
  }
  rep(i, n*2+1) fmt(v[i]);
  rep(i, q){
    int x,y;
    cin >> x >> y;
    cout << v[y][x] << "\n";
  }
}

2023-03-01

RECRUIT 日本橋ハーフマラソン 2023冬 (AHC018) 参加日記

最終解法

最初に距離をもとに水源を含む最小全域木を求めて(初めにすべての水源を結んでおけば計算できる)、使われなかった水源はこれ以降使わないようにする
上の操作で残ったところから上下左右に掘っていき、固い部分が来たら方向を変えてまた掘っていく。というのを繰り返す
- 削るマスと今まで壊してきたマスとの距離が12未満の場合、削るのをやめるようにしてます
そのあと、2つの水源/家での最短距離を出してそれを使ってもう一度最小全域木を作る
辺が結ばれているところの頂点間を壊していく。現在から目標とする場所が右上にあったとき、一つ上と右のところを見てすぐ壊せそうな方向に進むようにする
岩盤を壊すパワーは、隣接しているところですでに壊れているときは、その場所を壊すのに使ったパワー*(3/5)で壊す(2回くらいで壊れるのを想定)、初めて壊すときは初期値を決めてだんだん倍にして壊れるまでやる

という感じです。あんまりいい解法ではないです

(提出コード：https://atcoder.jp/contests/ahc018/submissions/39207430)

日記

1,2日目

月と火にテストがあったので実装はせず考察だけやることにした

問題を見た感じの感想

初期の盤面が与えられない&壊れるか壊れないかしか判定できないのであんまり岩盤が固いところはいかないほうがよさそう

最初に盤面の全体を何個か削ってみて盤面を推測するとかもできそうだけど、削る回数がかなり増えてしまう

薄いところだけを行きたいけど、盤面を確認するために削りすぎるとダメそう

どれくらい周りを探索していいのかとか、どれくらい遠回りするべきなのかがまだよくわかってないのでSijがすべてわかった時でどうなるか確認したい

3日目

残り1日テストが残ってたんですが、コードを書いてしまいました...

Sijをを受け取って必ず1回で一つの岩盤を壊せるようにしてみた

上下に行くだけいって、左右に動いて目的地まで付くのをコストにして、kruskal法を使って求めてみる

もう一つ、Sijで各頂点の最短経路を求めてそのコストに応じてkruskal法を適用する

この解法でだいたい理論値がでるはず

seed0だと8倍くらいコストに差が出た(思ったより大きい)

少し色が濃い部分に入るだけで値が1000近くあったので、色が薄い部分だけをたどるような解法にしてみる

4日目

thunder本を買う

テストが終わって疲れて寝たので何も進んでないです

5日目

とりあえず、上下の移動から左右の移動をする、みたいな動作でやってみる

掘削の初期値はを決めて、壊すまでにある程度回数がかかるならパワーを2~4倍にする、1回で壊せるなら1/4~1/2倍にする、みたいなことをして、1ブロックを壊を1~3回くらいで壊せるようにしてみる

seed=0のとき、Cost=539798になった(visualizerの見た目は前のと同じなので省略)

Sijを知っている時がCost=511018だったので少し悪くなってるくらいになった

Sij込みの時のプログラムが残っていて、冗長な部分が多いです↓

提出コード(絶対スコアは11672399): https://atcoder.jp/contests/ahc018/submissions/39096621

通る場所が固定されているのでなるべく壊れやすいところだけを通れるようにしたい

それを一回、Dijkstraで適当に探索してみたところ、こんな感じになってしまったのでもう少し簡単な問題設定にして実装する(これで1日使った...)

上下左右の移動を回数を決めてなるべく壊れやすいところに移動するように探索してみる

が、あまりうまくいかず...

掘削回数が多く、Cが小さいときにスコアの改善があったのでひとつ前の解法と場合分けしてやってみると少し更新

2ケースだけTLEするが、ローカルでテストしても問題がないため原因がわからず...

6日目(木曜)

この日は実装はほとんどできず、考察だけした

いろいろ考えたけど、どれも具体的にどうやって実装すればいいのかわからなくて詰む

7日目(金曜)

一つ実装できそうな案があったのでそれを実装する。内容はこんな感じ

すぐ壊せるところだけ上下左右に壊していき、いけなくなったら方向を変えるというのをBFSみたいに繰り返す
これをすべての頂点について行う
そのあとに、kruskal法で伸ばしたところからの距離がなるべく小さくなるようなところ同士を結ぶように愚直に掘る

実装するとこんな感じになった(seed=0)

1~2個目を行うと、

こんな感じで、最後につなげると、

こんな感じになった

前回のコードのスコアが393390くらいだったのでだいぶ良くなった

まだ、冗長な部分が多いけど、いい感じに伸ばせてそう

提出 -> 16Gから14Gまで下がる...

少し訂正して何とか17Gまでは上がるが渋すぎる(実際は20G近く行くんじゃないかと思ってた)

8日目(土曜)

17.3Gからちょっとしたことを改善して少しだけ上げて、17.6G（絶対スコアは9.3M）

伸びなさ過ぎて気力を失くす

9日目(日曜)

これ以上何やればいいかわからなかったので、一番良かったコードを最終提出する

最終結果

暫定で380位、システス後の最終結果は374位でした...

今回の敗因は、思いついた案を実装して確認せずに、考察の時点でやめてしまったところな気がする

thunder本を読みこんで、次のAHCでいい結果残せるように頑張ります

2022-11-23

AHC016(HTTF予選) 参加記

コンテストの結果

暫定結果は相対スコアが9,695,567,980点(絶対スコアは693515946点)で225位でした

システスでの絶対スコアが27,135,329,698点(絶対スコアは422181214166点)で217位でした

解法

i番目のグラフは頂点0~iまでそれぞれ0~n-1まですべて辺を張ったグラフを作成
matrixで見た時のL字の部分に含まれている0の数と、L時以外の領域に含まれている1の数がなるべく少なくなるようなグラフを全探索

送られてきたグラフを次数の大きい頂点順にソートして山登り法みたいな方法で2頂点をスワップしながらスコアスコアがなるべく少なくなるところを適当に探す
その中で一番与えられたグラフと近かったものを採用する
$\varepsilon$ がかなり小さい(0.00~0.05くらいの値)時はN=4~6にして同型ではないグラフをM個作って理論値を狙いにいく

というような解法で解きました

Visualizer ↓

得点別の解法

ここからコンテスト中の考察を得点順に分けて書いてあります(メモ代わりなのでかなり適当です)

54097055点

頂点を二つランダムに選んで辺を張るという操作でグラフの作成をしてみました

Nは20固定で、辺の数は各グラフについて0~N(N-1)/2までの等差数列になるように設定してみました

提出コード: https://atcoder.jp/contests/ahc016/submissions/36384936

174271158点

Nはmaxの100に固定

それぞれの頂点のペアに対して辺を張る/取り除くということを確率的に行うのでi番目のグラフ( $G_i$ )での辺の数を $e$ とすると、そのグラフの辺の数の期待値は $e$ から $\varepsilon e$ だけ減って、 $\varepsilon (N(N-1)/2-e)$ だけ増えた値なので、その期待値とノイズ入りのグラフにある辺の本数が一番近いグラフを探すようにしてみる

そこから少し頑張ってみて176408919点までは取れた

提出コード: https://atcoder.jp/contests/ahc016/submissions/36395001

そろそろ辺の数という情報だけじゃ厳しそうなので、グラフを利用した解法を考えていくことに

333075586点グラフの数を数えてみる

頂点の数がN個のグラフの種類数(頂点を入れ替えて同じになるものはすべて同じ種類とする)を数えるプログラムを適当に作ってみた

少しだけしか探せなかったけどこんな感じになりました(これ以上は時間がかかりすぎた)

(N, 種類数) = (1, 1), (2, 2), (3, 4), (4, 11), (5, 34), (6, 156)

割と少ない頂点数でもグラフの種類がたくさんあることがわかる(N>=6の時点で100超える)

とりあえず、 $\varepsilon = 0.00$ の時だけに特化したプログラムを書いてみる

上から2~3桁目のスコアしか変わらないと思ったら2倍くらい伸びてびっくりした(ただし相対スコアは伸びず...)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36473676

439238657点

必ずしも $\varepsilon = 0.00$ でないといけないわけではないので辺の数も考慮して0.02~0.08くらいまで許容してみた

思ったより上がる

提出コード: https://atcoder.jp/contests/ahc016/submissions/36474305

535391293点

このあたりから得点を上げるのにかなり時間がかかった

i番目のグラフは頂点0~iまでそれぞれ0~n-1まですべて辺を張ったグラフにしてみる

受け取ったグラフは次数順でソートして次数の差が一番大きいところを探してそのindexを出力する。という感じでやってみた

(このあたりでVisualizerにグラフをmatrixで表示させることができるのを知る)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36522240

578834111点

一部のテストケースでランダムに辺を作って解いていたのでそれをやめて基本的に上の解法で解くようにしてみる

スコアはあんまり上がってないけど、順位は思ったより上がった

今回訂正したのが $\varepsilon$ が高いテストケースで、そのケースのスコアを見ると相対的にかなり高くなってたかもしれない -> 正答率をとりあえず上げることを目標にする

提出コード: https://atcoder.jp/contests/ahc016/submissions/36530599

670527986点

$\varepsilon$ の値によって右下に余らせる頂点の数を変えるように改善

提出コード: https://atcoder.jp/contests/ahc016/submissions/36546380

693515946点(最終提出)

2頂点をランダムに入れ替えて作成したグラフと近くなるかを適当に試した(が、あまり効果がなかった)

提出コード: https://atcoder.jp/contests/ahc016/submissions/36583530

感想

今回のAHCは、実装がどうこうというよりも、考察ができないから実装すらできないみたいな感じでコンテストが終わってしまった...

ヒューリスティックも黄色目指して頑張ります。

2022-10-20

第33回高専プロコン参加記

2022/10/15~16に開催された高専プロコンの参加記です

開発環境など

OS：Windows10, Ubuntu(macでの仮想環境)

使用言語：C++(mingw, gcc)(ソルバーなど), Python3(通信プログラム)

使用ライブラリ：なし

GitHubレポジトリ(汚いのは許して)：https://github.com/UScuber/procon33

開発期間：募集要項が公開された4月から大会(10月)までゆっくり進めてました

競技ルール

募集要項(https://www.procon.gr.jp/wp-content/uploads/2022/04/7cd7daa1edc6ad3c7077207f1814c2fc-1.pdf#page=9)に書かれています

読みデータの読みの開始位置をずらしたものが複数重ね合わせられたものが問題データとなっています

問題文の誤読について

読みデータの読みの開始位置をずらしたものが複数重ね合わせられたものが問題データとなっています

僕がそれに加えて、問題データの中で札を読み始める位置が変わるという風に勘違いしてしまいました

大会終了まで気づかずに問題に取り組んでいたので、とりあえず誤読した状態の問題の解法を説明していきます...

誤読した状態での解法

今回は焼きなまし法を使いました

ここではNを重ね合わせられている札の数とします

音声データに含まれている札の種類、その音声の開始位置、長さ、音声データへの貼り付け位置の4つの状態をN個、合計4N個のパラメータをランダムに変更しながら問題データへと波形を近づけていきます

4N個のパラメータと読みデータから音声波形を足し算で合成して、受け取った音声データとの波形の差の総和をスコアとしてそのスコアの最小化を目指していきます

始めはシングルスレッドで音声のサンプリング周波数を2000[Hz]にして大まかに推測し、最後にマルチスレッドで6000[Hz]にして解析して少し精度を上げるという感じでやりました

具体的に、焼きなましの近傍の探索はこんな感じに行いました↓

焼きなまし法の近傍(前半)

選択中の札を選んで、長さと開始位置、貼り付け位置をすべてランダムに変更
選択中の札を別の札に変えて、長さ、開始位置、貼り付け位置をすべてランダムに変更
選択中の札を選んで、長さを前後約0.3秒ランダムに変更
選択中の札を選んで、長さ(音声の始まりの部分)を前後約0.3秒ランダムに変更
選択中の札を選んで、音声の貼り付け位置を前後約0.3秒ランダムに変更
選択中の札を選んで、音声開始位置を前後約0.3秒ランダムに変更
選択中のある札の別の札に変更
選択中の札を選んで別の札に変更し、ほかの選択中の札の情報(長さなど)に変更

焼きなまし法の近傍(後半)

選択中の札を別の札に変えて、長さ、開始位置、貼り付け位置をすべてランダムに変更
選択中の札を選んで、長さを前後約0.3秒ランダムに変更
選択中の札を選んで、長さ(音声の始まりの部分)を前後約0.3秒ランダムに変更
選択中のある札の別の札に変更
選択中の札を選んで別の札に変更し、ほかの選択中の札の情報(長さなど)に変更

プログラム実行時、前半と後半に分けてそれぞれ遷移を変えました

前半と後半で分けたのは、前半だけにある遷移が最後のほうになるにつれて使われなくなっていったからです

プログラムの高速化

音声のサンプリング周波数を下げる

ある程度速度が出て、分析がうまくできる周波数を探しました

シングルは2000[Hz]でマルチは6000[Hz]で解析するのが一番良かった
関数のインライン化

大量に呼ばれる関数はinlineを付けたり、行数が短ければ直接埋め込んだりして高速化をした
実行ファイルが高速に動くコンパイラを探す

gcc, mingw, clangなどで動作の確認してみる

最終的に普段使っているmingwが一番速かった
高速なコンパイルオプションを探す

-O3とか-Ofastなどの最適化オプションなどを付けて探してみる

-Ofast -unroll=4が一番良かった
近傍の変化の種類によってスコア計算を場合分け

ちょっとだけ速くなった(そんなに変わらん)

練習結果

長さ8秒弱、札20枚の音声データを作成して150回テストした結果ですこの時は札20枚で、1回の解析に5分かけてました

(analyzeディレクトリのresults6.csvに結果が載ってます)

焼きなましの一回の実行時間は $5.8\times10^{-7}[s$ ]くらい(1秒間で大体 $1.7\times10^{6}$ 回ほど)で実行してくれます

大会当日の話

大会結果はここから見れます：https://www.procon.gr.jp/?p=78751

予行練習

ネットワークの接続で多少戸惑ったが、何とか通信できるようになった

解析のプログラムもうまく動いてそうで安心

受け取る分割数は全部でなくても行けそうだったので1回戦までに分割データを一部だけ受け取れるようにプログラムの修正をした

1回戦

すべて分割数2にしてパーフェクトを狙った

予行練習よりも圧倒的にスコアが高くて不安だったけど何とかなった 1回戦は無事1位で通過

1日目の夜

分割数1にしたときにバグが発生したのでそこを修正

原因は、問題データに入っているすべての読みデータは1秒以上流れているというのをプログラムに入れており、1秒未満の分析の時に配列外参照をしてしまっていた

訂正後、1回戦のデータをすべて分割数1で実行するとすべて正解だったのでこのままでいくことにした

そのあと、特に直すところはなさそうだったのでABCに出る

準決勝

少し攻めて分割数をすべて1にしてパーフェクトを狙い、大阪公大と弓削と同率になるという作戦で行く

最初は数の指定ミスで2にしてしまったが、何とかパーフェクトで1位通過

松江高専が敗者復活戦からかなり精度を上げて迫ってきてる

お昼に、決勝では分割数の指定をミスしないように分割数をあらかじめ指定しておくようにプログラムの変更をした

決勝

分割数はすべて1で行くことに(ここで取らないと上位に行けないので)

1問目の結果

最初、札の枚数が12枚とそれなりに多く、かなり精度が落ちてしまった(ここで5ミス)

残りの2~4問目はミスした部分を変更札にしていきながら何とかすべて正解

最終結果は......

4位でした

分割数を1にして攻めてみましたが、1問目の5ミスがスコアにかなり響いてしまい、松江高専と差をつけられてしまいました...

大会に出た感想

もともとは決勝戦出場を目指してやってきたので決勝に出れて嬉しかったんですが、長い期間やってきた分、3位を譲ってしまったことにかなり落ち込みました

自分にもっと実力があればなと思ったりとかもしました

高専プロコン自体はめちゃくちゃ楽しかったです

大会終了後

募集要項が公開されてからずっと誤読していたことに気づく。

もし、元から気づいていれば3位になれたのではないかと思い、かなり落ち込んだ。

誤読していない状態での解法

長さと張り付け位置は常に変わらないのでそのパラメータを取り除いてコードを修正していきます

さっきの解法のコードよりもだいぶシンプルになってます

ソースコード：https://github.com/UScuber/procon33/tree/fix

修正後の実行結果

大会で出題された問題をすべて分割数1で実行してみました

1回戦

1回の実行は1分以内でできて、2~3回実行すればどれかが確実に完全一致した

焼きなましの近傍1回の実行時間はは大体 $1.7\times10^{-6}[s$ ]～ $4.0\times10^{-6}[s$ ]くらいでした

準決勝

準決勝～順位決定戦の問題データの一部をいただいたのでそれを使わせてもらいました(ありがとうございます)

実行時間は少し長めにして実行

温度を調整して実行してみると、すべて完全一致

いい感じ

決勝戦

1問目で2ミス(うーん...)

2~4問目は完全一致

順位決定戦

9/20個一致でした(かなりひどい)

大会で使ったプログラムだと分割数1で15/20個一致でした

もうこれは乱択の限界な気がする

まとめ(感想など)

今回のプロコンの関係者の方や、自分のチームを応援してくださった方、ありがとうございました！！

問題の誤読が原因で決勝戦で解析がうまくできなかったので、来年は募集要項を読み込んで、たくさん質問できるような状態にしていこうと思います。

来年は3位(あわよくば2位)を目指して頑張ります！！！

目次

開発環境

競技ルール

最終的な解法

ソルバーのアルゴリズム

この解法にする前に考えてたこと

ビジュアライザの機能

バグ探し

今年の大会の目標とか 大会までの話

大会の話

大会情報

大会前日

1日目

予行練習

ファーストステージ

セカンドステージ

1日目夜

2日目

ファイナルステージ第1試合

ファイナルステージ第2試合

ファイナルステージ準々決勝(第3試合)

ファイナルステージ準決勝(第4試合)

ファイナルステージ3位決定戦

改善できそうなこと

感想

目次

目次

最終解法

日記

1,2日目

3日目

4日目

5日目

6日目(木曜)

7日目(金曜)

8日目(土曜)

9日目(日曜)

最終結果

目次

コンテストの結果

解法

得点別の解法

54097055点

174271158点

333075586点 グラフの数を数えてみる

439238657点

535391293点

578834111点

670527986点

693515946点(最終提出)

感想

目次

開発環境など

競技ルール

問題文の誤読について

誤読した状態での解法

焼きなまし法の近傍(前半)

焼きなまし法の近傍(後半)

プログラムの高速化

練習結果

大会当日の話

予行練習

1回戦

1日目の夜

準決勝

決勝

大会に出た感想

大会終了後

誤読していない状態での解法

修正後の実行結果

1回戦

準決勝

決勝戦

順位決定戦

まとめ(感想など)

今年の大会の目標とか大会までの話

333075586点グラフの数を数えてみる