AHC001 参加記

AHC001に参加しました。
長期のコンテストにC++を使いたくなかったのでRustで参加

githubで管理してたので公開します https://github.com/kanra824/ahc001

1日目

  • (x, y)に1 * 1の正方形をおいて初期化: 823090
  • それぞれの長方形をランダムに選んで拡張する: 35830035700

  • 長方形を広げたり縮めたりしながら山登り: 44048518763

  • 50個分を非同期実行するシェルスクリプトを書いた（2並列 * 25回）

  • （脳死で50個同時に非同期実行させて回しまくってたらブルスクが起きて焦った　CPU温度が大変なことになるからやめようね）

  • ビジュアライザが出力した画像の一覧をブラウザで見れるようにした　素のJSでゴリッと

  • 公式のビジュアライザを改造して、全体のスコア(/ 109)や長方形ごとのスコア(*100) が表示されるようにした
    f:id:mdyh2a380824:20210308001844p:plain
    こんな感じ

2日目

  • 焼きなまし: 47498289869

  • 拡張する時に他の広告が重なるならその広告を縮める: 47804220369

  • テストケース生成をｼｭｯとできるスクリプトを書いた

3日目

  • 更新するidxを選択するときの確率分布をスコアに応じて決められるようにした
  • 差分更新をより高速化

その他

  • optunaで初期温度と終了温度を探索するやつをかいた（使うかな？）
  • ビジュアライザをシークバーで動かせるようにした
  • 動画: https://github.com/kanra824/ahc001/pull/15

4日目

  • 広告がずれてくれるように、縮小して拡大する遷移を追加した
  • 序盤はスコアが均一になるようにした: 48176775941
  • 今までやってきた焼きなましが時間を書けてもそんなに変わらないことに気づいたので、何度か回すことにした
  • ループを回しながら、各回の焼きなましの結果スコアが低かった広告をいくつか取り出して、次のループではそれらの広告が最初に拡大されるようにした: 48453049603

5日目

進捗0

6日目

  • 広告の変化しにくさみたいなパラメータを入れる
  • 長方形の辺と辺がぶつかったとき、たまにいい感じに縦横を入れ替える
  • めちゃくちゃバグっています　HELP
  • なおった
  • スコアが....スコアが伸びない.....

7日目

  • 色々試したけど伸びなくて、結局4日目のやつを提出

感想

490にのせたかったけど、結局485にも乗らなかった... Rustはとても良くて、リファクタリングをするときに威力を発揮してくれたと思う。 C++でやってたら途中で管理しきれなくなっていた

チーム練(2019 RUPC)

チーム練

全完！
A, C, Fの考察実装とGの実装をした

A (Md, 00:02)
B (番兵, 00:04)
D (のん, 00:38)
E (のん, 01:34)
G (番兵Md, 02:01)
C (Md, 02:38)
F (Md, 02:50)



A, B:
はい

C:
ギャグすぎる
絶対置けない場所があって、サンプルを見るとそこ以外は絶対置けることがわかる

D:
頂点1, 2, 4, 8...をビットとみなして、各ビットが立っているときそのビットとの間に辺をはる
あとは1, 2, 4, 8...を聞くと答えがわかる

E:
逆順に最長減少部分列を求めると最大値がわかる
復元はまあできる

F:
これすき
abs(a[i] - i)はa[i]とiに+, -符号を割り当てることに対応するので、符号で分けて+側の配列と-側の配列を持っておく
やることは+側の一番小さな要素と-側の一番大きな要素を貪欲にswapするだけで、実はこれでうまくいく

G:
燃やす埋める

チーム連 7/4 (2017 ACM-ICPC, Asia Daejeon Regional)

チーム練

BCDEFGIK 8完
ひさびさに顔を合わせてチーム練した　ついでに本番っぽく一台のPCでやった
L, Hは冷静に考えたら解ける問題だった
これのあとでこどふぉに出たら脳が機能を停止していて、反省...

B (Md, 02: 07)
C (Md, 00:32)
D (Md, 00:18)
E (のん, 02:43)
F (番兵, 01:01)
G (のん, 04:48)
I (Md, 03:09)
K (番兵, 03:25)

B
枝狩り全探索

C
次数が小さい順に並べてDP

D
一回操作をしたあとの数が729以下に抑えられるので、一周するか停止するまで操作を繰り返す

E
各辺について、自分より小さいコストの辺だけをつかった部分グラフについて今見ている辺の両端を非連結にしたい
最小カットに落ちる

F
頑張って再帰的にやると通るらしい

G
座圧

I
周期pを固定したときにkをどこまで伸ばせるかはにぶたんできる
にぶたんの各判定はロリハをつかってO(n / (pの長さ))なのでpを全探索すると考えれば調和級数でO(nlogn)の気持ちになる
pを全探索 + kをにぶたんするとn * (調和級数のlogn) * (にぶたんのlogn)に落ちる

K
知らず

7/10追記
H
NTT

L
それぞれのグラフについて
dp[i][j]: j回目に頂点iにいるときのコストの最小値
をj <= 200000くらいまで求めておいて、最後に組み合わせる

チーム練(2014 RUPC)

チーム練

ABCDEG6完
当時なら優勝だし成功です
Fときたかった

A (Md, 00:12)
B (番兵, 00:19)
C (のん, 00:56 + 1)
D (Md, 01:13 + 1)
E (のん, 02:42 + 1)
G (Md, 02:01)

解説

A,B
はい

C
問題文がわかりづらい というか解釈ブレ起きない？（気のせいかも）

D
DPを3回　丁寧丁寧丁寧に

E
幾何　いい感じに候補を全探索

F
解けなかった
自明なDPの遷移式をCHTで高速化するやつ
知ってるテクだったのでくやしい

G
i番目の要素をj番目に動かすコストはp_i * abs(i-j)なので，
結果が完全順列となるように重み付き二部マッチング

チーム練(ICPC 2019 Pacific Northwest Regional)

チーム練

問題が解けるセットは　たのしいね

9完8ペナ あと一問通したかった
小さなミスが多すぎる

A (のん, 02:55 + 1)
B (番兵, 02:49 + 3)
C (Md, 00:32)
D (Md, 00:18 + 1)
E (番兵, 00:24)
G(Md, 04:37 + 2)
I (Md, 01:23)
L (のん, 03:33)
M (のん, 00:48 + 1)

解説

A
全方位木DP　ゆきのんががんばって遷移を生やしてくれた

B
数字ごとに一番うしろに現れる点を持っておいて、セグ木でがんばる

C
最短路を交互に塗るのが最適 dist(1, n) - 1が答え

D
ペナを生やしちゃ、だめだろ

E
気づいたら通ってた

G
移動する時間を考えなくていいように適当にずらしておく
始点と終点それぞれを表す区間和のセグ木beg, edをもつ（累積和で良かった）
列の各区間についてセグ木に始点と終点を登録する
行の各区間pについてactivateされない列の数はed.query(0, p.first+1) + beg.query(p.second, MAX)
なので足し合わせて n - 総和が答え

同じ線に複数回パルス波が流れると勘違いしててやばかった

I
二要素をswapして同じ文字列になるようなもの同士を辺でつないだグラフを作って、その上で最大独立集合を求めたい
このグラフは二部グラフになるので、n - 最大マッチングがこたえ

L
気づいたら通ってた

M
頂点数 + 連結成分の数 - 辺数