AtCoder Regular Contest 122
xooxxx (572nd)
悔しかったので初投稿です
汗落としてすっきりした状態でコンテストに望みたかったので風呂に入ったのに開始ギリギリまで熱くて辛いものを食べて汗ダラッダラの状態でスタート よく考えて夕飯を決めましょう
歯を磨いていたら遅刻する 準備はコンテスト前に終わらせる(反省1)
A - Many Formulae (400)
各項が何回マイナスになるかは3通りしかないしそれぞれ計算すればいいな！となる 20分くらいかかって実装まで終える サンプルがあわない
冷静に考えると何もかもガタガタであることに気づく 一回何もかも忘れて考察し直す というか多分 DP なのでそれを考える
DP 考えると、i 番目を正/負にしたときのその時点までの総和/パターン数の 2 つを計算すれば OK 10 分くらいかけて実装する サンプルがあわない え？
10 分くらいパターン数とか出力して睨んだりするんだけど今度は何が悪いのかわからない
お腹が痛くなってきたのでトイレに行く 準備はコンテスト前に終わらせる(反省2)
トイレで冷静になった 多分頭がすごいことになっているので一旦次に行く
B - Insurance (500)
こんなんどうあがいても だろ でも今頭がおかしいので
の図を書いたりして確かめる あってそう 書く long double で書いていたけど怖いので long long で書き直す 5 分くらいで通る
C - Calculator (600)
操作が高々 130 回で だと操作回数に対する指数オーダーで増やさなきゃダメ
はそれぞれ単調増加だし、おおまかに増やしたあと最後の方で細かく調節するみたいな方針には向いていなさそうなので捨てる
まあ操作がフィボナッチ数のソレと相性が良さそうだしこれも指数オーダーだしこの方針を詰めようかなとなる 一通り性質を考えたりしたあと結構時間が経っていたので一旦落ち着くためトイレに行く
そういえばフィボナッチ数の和で自然数を表す何かがあったなとなる ググる ある 勝ちじゃん
基本的に操作 3,4 を交互にやる、 以下のフィボナッチ数
を降順に全列挙しておいて、残りの
が
ならそこに
を足すとすると自然と
が構成できるはずだなとなる
頭が怖いので実装が終わってから assert かけつつ大きいケースとか試す が
になっているので操作逆転させる これは考慮していたし発生したときの対処も考えていたので OK 出す AC
D - XOR Game (700)
開く 10 分くらい考える 答えの最上位 bit が容易に求まることがわかる その後の構成が微妙なので E を開いてからどっちやるか決めることにする
E - Increasing LCMs (800)
LCM を陽にもつのはどう考えても不可能 LCM/GCD がそれぞれ max/min と同じ構造で、こっち使って考察したほうがよさそうだなとなる あと D よりこっち選択するほうが良さそう
2項間でのみの前後関係はすぐにわかるんだけど、必要なのは部分集合との関係で、それはさすがにできなさそう
紙がきれる 家の中を探し回る 準備はコンテスト前に終わらせる(反省3)
別の方針を考えてみようかなとなる は一意 その項しか持っていない素因数があるものを後ろの方に置いていけばもうちょっときれいな問題になるかなとなる いやそれに限らず貪欲でええやんとなる
残り 20 分くらい時間が残っていたので実装を始める 実装終わる バグっとる 🤪
コンテスト終了 1 秒前に提出、手元で動くのに CE うしからパクってきた prime_factor が int64_t で書かれておる そりゃそうじゃ 自分で書いたものがあるんだから自分で書いたものを使おう！(反省4)
ちょっときれいに書き直して出す TLE 速い方の素因数分解探すのサボって のやつを貼っておいたんだった 直す 出す AC
反省
準備ちゃんとやる 動画見ながらダラダラ夕飯を食べたりしない 紙も用意する
小さい紙に小さい文字で考察するのをやめたい 富豪を目指す それか大学から紙を強奪してくる
直近 2 ヶ月で橙 perf を逃した原因が全部実装が下手くそだったことなの悔しい 実装力を改善するために問題を解きまくっているのに考察だけすくすく育つ
AOJ-ICPC とかで苦しみ始めてもいいかもしれない あと準備はちゃんとやる
うまくできたら色変できてたねえ
