AGC044
0点orz
最初0とNの両方から探索して出会うところを見つけようとしてTLE、その振る舞いを観察したら+1の連打が起きてたので、未探索の場合デフォルトでxのコストはxDとする修正を入れてかららNから降りてく方に変えた
WAが出て、理由が思い当たらなかったのでBに移動した
AGC044A AC
---
>>> solve(4, 1000000000, 1000000000, 1000000000, 1)
4
1000000002
B
人が抜けるたびに探索すると間に合わないに違いないと考えて、あらかじめ距離のマップを作っておき、抜けた人の前後左右の人の距離を更新しようと考えた
しかし、人が抜けると「隣接」が変わることに気づいて2次元行列からグラフに変更、しかも玉突き的に更新されることがあるので…TLEで死亡
とりあえずコケてるテストケースを確認しようかなと思ってるけど、今日7.5時間もコンテストに参加してるわけなので休んだほうがいい気もする笑
Related Pages
- →past5h×abc184e×past4j×past4k×abc175d×arc106×abc164d×素因数分解を_o(n^(1/4))_でする×abc189×abc190e×abc194f×atcoderのpythonでmemoryerrorを出すとreになる×agc048×abc179d×深さ優先探索×aoj_grl_5_c×arc107×AGC044A×past2n×past3o×頂点を塗るのか辺を塗るのか×past4m×abc178f×abc192×abc191→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×sparse_table×rmq×atcoder→
- →アルゴリズム実技検定×atcoder×past3×past202005×past3d×past3e×past3f×past3g×past3h×past3i×past3j×past3k×past3l×past3m×past3n×past3o→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]