2015/Practice/模擬地区予選/案内 - ACM-ICPC Japanese Alumni Group
メンバー
- 私
- OUDON氏
- 23氏
解けた問題
A. M and A
KADOKAWAとdwangoが云々という説明をする。「LCSするだけやん!」と謎の早とちりをしてWAを量産してしまう。つらい。
OUDON氏にGreedyにやるだけだと諭される。バグを仕込む。つらい。
自分で見つけられなくてOUDON氏に指摘される。AC。やったぜ。
B. Change a Password
「同じ文字が含まれないような数字って多くないよね」「それ高々10!やん」「あっ(察し)」やったぜ。
stringstreamが遅くてchar配列で書き直す。つらい。
C. Delete Files
「高い山を見つけて分割していってDPで〜♪」といった誤解釈でWAを量産してしまう。つらい。
OUDON氏 & 23氏 チームが謎Greedyを提案してくれる。僕には理解できないが,今までに作ったテストケースが全部解けるようなので淡々と実装する。AC。たまげたなぁ。
D. Line Gimmick
「夏合宿の問題みたいに1回のシミュレーションはdancing linksでO(N)で出来るよね」「N <= 105だから100回くらいはシミュレーションできるよ。log N回で決められないかな?」「log N… あっ(察し)」
(「あるマスxから始めると左から出て行ったならば,xよりも左側にある任意のマスから始めても左から出ていく」と仮定します。この予想が正しければ,左から出て行くマスと右から出て行くマスの境界が二分探索によりlog N回で決められます。あとは,境界の右と左からシミュレーションすることにより,乗ることが出来るマスの数を計算すればよいです。時間計算量はO(N log N)です)
E. Shifting a Matrix
OUDON氏にやるだけと言われる。殺人的に実装量が多い予感がしたが,それほどでもなかった。
H. Donut Decoration
範囲update (加算ではなく変更),範囲minを実現する平方分割が,いわゆる遅延セグメント木のテクニックを応用することにより実現できた記憶があったので,すんなり実装できた。TLEは5秒だし間に合うでしょ → 2200msでAC。やったぜ。
(平方分割によるセグメント木の代用は,3〜5倍程度遅くなる程度で済むことが多いです。この差が致命的になることもあるのかもしれませんが,セグメント木は実装によって速度に幅が出るので,多くの問題ではTLEに余裕を持たせています。)
解けてない問題
F. Modern Announce Network
これグラフ理論の何ていう問題だっけ?というところから忘れていた(最小シュタイナー木)。もちろん計算量も忘れていた。
グループが3つしか無いことを利用して何かやるんだろうということから変な解法を実装してみたけど,コンパイルエラーを直している間にモーダルが現れて死。
その他
私は読んでいない。
まとめ
貪欲は私以外のメンバーに任せるとポジティブな結果が得られる。