日記0220 ABC192感想
閉寮だった
日付変わってからなんとなく眠く無くてなろうを読んでいたら午前6時になってしまった。
今から寝て昼に起きれなかったら帰省できなくてやばいので起き続けることを決意する。
モニターアームやpcデスクを分解して箱にしまう作業をしていた。めんどくさい これをまた組み立てないといけないのがしんどい
なんでそんなめんどくさいことをしないといけないのかというと今年は全ての荷物を寮から持ち帰らなければいけないためだ。なぜかは知らない。
夜はクッソ疲れてて眠たかったがABCがあったので参加した。
レートが下がったのでカス.......という気持ちになった。
レートが下がると嫌なのでいつもはAから解いて提出してるけど今回はEまで解けたら出そうと思って参加した。
A,B,Cは普通の問題だった。Bを解くまでに5分程度かかっていて衰えを実感した。
D問題は難しくて、適当にサンプルだけ合うやつを書いて解けたことにした。
E問題は自明で、前回ダイクストラをライブラリ化したのでそれを貼って(スニペットからラムダ式の形で展開して)、2,3行いじったら解けた。
5完できたっぽいので提出。D問題がTLEだった。そのときは愚直にやっていたので二分探索にして言語をPythonからC++に変更した。なぜPythonでやったのかというと、オーバーフローしそうで怖かったため。C++で多倍長整数を使う方法を調べると
これだけで済んだのでこれからはこれもライブラリに追加しとこうと思った。
D問題はそれでも解けなかった。TLEはなくなってWAが10何けーすか存在した。よく考えると誤読していてnの数を数えていた。1のとき無限にならないか??と思って問題文をにらむと値の種類数と書いてあるのでlen(x)==1のときがコーナーケースだとわかる。その時の処理をcout<<1<<endl;と書いて提出。WAが6ke-suまで減った。コンテスト中はここまでしかわからず。
解説を読むと、len(x)==1のときにmと比較して、1か0か判定しないといけない。アホすぎ
F問題はkを決め打ちするとsumもxもkで割った余りでいいなと思って部分和DPをする。dp[i][j][S] := i番目まで見てj個使って和がSになる。
サンプルはあったがサンプル以外は合わなかった。
ねむかったので23時過ぎに寝た。