2019-02-23
■ みんなのプロコン 2019
実は皆勤賞です、皆勤賞なんですが、オフィスまでの行き方が全く覚えられない
A
えーっ何これは.... -> まあ積分すればいいけど受験数学2年くらいやっていないため... -> サンプル合わない、どぼじで -> 飛ばす
B
流石に2つの木の直径の端4つから2個取るのがベストのはずで、それなら簡単 -> AC
C
まともにやると絶対やばいのでスマートな方法を考える -> 4つに分ければ全て長方形反転クエリになる -> Fortune Telling (JOI 2012 sc)って、知ってるかな...？僕は知っています -> AC
D
setで管理して、幅に対応したフィボナッチを掛ければOK -> 無限にバグる (行列をsegtreeに乗せるか、setに番兵を載せるのが良いですね....) (フィボナッチも相当バグらせたので頭がない) -> なんとかAC
A (再)
冷静に見るとh-aをaにtypoしてる...(許せね～～～) -> AC
E
数え上げ、数え上げなんですけど、分からない (は？？？)
結果
8位
感想と反省
順位に関してはADで嵌ったのが悪いんですけど、Eが分からなかったの不味いなあ (N<=100, M<=10^9の時点でそういう方向性の思考をしなきゃいけないし、良く分からないものを左から順に切った時の条件で表現する系は結構見るし、色々とダメ)
行列周りのライブラリ全然整備できてないし、「面倒なことで有名なDP」も1回も解いたことないし、課題が山積していることが分かったので良かったかな...
■ 日経コン本選
1週間前なので記憶があいまい
最寄りが後楽園だと思っていてしばらく歩く羽目になった、会場はなんか豪華な見た目をしていてすごかった
A
やる
B
制約が優しい、やるだけなんだけど遅い
C
縦横のにぶたんの変数が被っていて無限にバグった、すぐに気づいたので良いけどやばい
D
この問題の上位互換 (スタートの長さ自由、伸びるペース自由、長さの上限あり、各切断クエリごとに切断長のsumを求める) が出題されたことがあるため.... (貼りました、カス)
E
数え上げ典型、v番目が最初の埋まらない場所として考察するとdpを下から更新できる
F
ちょっと考えたけどよくわからない、飛ばす
G
少し考えると「どこかの辺までダイレクトに行き、その辺を残り反復」が良いことがわかる。
様々なパスに対してmaxを求める -> 重心分解、コストの形がax+b -> envelope -> い つ も の -> ライブラリを貼ってちょっとやる
-> こどふぉのテストで通るけどAtCoderだとCEする (どぼして) -> ちょっと直す、AC (やったー)
F(2回目)
よく考えると、動き方が限定できるので普通に1D segtreeで出来ることがわかる、頭がバグりまくってダメダメだったけど一発で通ってくれたので良かった (ちょっと複雑になると遅くなるの直したいね....)
結果
2位
感想と反省
DとかGの「ハマった」感に大いに助けられた、Eがすぐ見えたのも良かった
Hはチーム練習の時に解法が錬成されたんですがまだバグっていて辛い、誰か助けて～～
エキシビションは相手も相手だし人も多いしで相当緊張してダメダメだった、もっと図太くなりたいね
また開催されるらしいので次回は懇親頑張りたいな
■ TopCoder SRM 751
749, 750は爆発したので見なかったものとします
Easy
かなりびっくりしたが、どうせ枝狩りすれば早い系だろうと思って書いて最大ケースを投げたら0.3secだったので出した
Med
しばらく変なことを考えていたんですが、冷静になるとg^K ≡ h なるkがわかれば良いだけ、これはBSGSで出来る -> h=0だとやばくないですか？やばいね -> 出す
Hard
しばらく変なことを考えていた(xを挿入するときxの前と後ろを同時に管理しようとしていた)、もうちょっと落ち着くべき
challenge
h=0チャンスかな、いうても赤5だしな... -> +3 (問題が悪いね)
System Test
通る、1位
Rating
2479 -> 2626
感想と反省
なんか優勝してしまった... Hard解かないで勝つのあまり格好良くないのでいつかカッコよく勝ちたいですね (小並感)
真面目な話をすると、Hardはどう考えても右で左を管理するのがファーストチョイスのはずで、それで解けるんですよね... なんで思いつかないの... -> 練習、しよう！
