ARC102参加記
AtCoder Regular Contest 102 - AtCoder
2018-09-01(土) 21:00 ~ 2018-09-01(土) 22:40
一完Rated内361位,perf1632
レートはあがってるもののperfは落ち続けてるのでわりと冷え気味
E解きたかった…
(日記なので解説では)ないです
C - Triangular Relationship
サンプルから気合でエスパーすると,
・ K%2==1の時は%M==0の物を並べてできる数列
・ K%2==0の時は上に加えて,%(M//2)==0のものを並べてできる数列
で解ける気がする.実際サンプル1の例を見てみると
・ %M==0が{1,3}の2通りあってそれを並べた23通り
・ %(M//2)==1が{2}の1通りあってそれを並べた13通り
の合計9通りが書かれていることが分かる.(サンプル3とかも答えが33なのでそれっぽい)
このノリで実装するとサンプル全部合うのでこれで投げたら通ります(なんでこれで良いのかは知らない
コンテスト中に通ったもの Submission #3113626 - AtCoder Regular Contest 102
想定解は上のをちゃんと証明与えて実装するか、制約が弱かったのでa%Kで場合分けして全探索とかでも行けたらしいですね
D - All Your Paths are Different Lengths
トポロジカルという単語が見えたので逃げた
AC数見た感じだとこっち解いた方が良かったのかもしれない…
そのうち解いてなにかしら追記する(きっと(多分(恐らく
追記:なんとかACでできたので書いた
simamumu.hatenablog.com
E - Stop. Otherwise...
すごい解けそうな気がしたんだけど…なあ…
とりあえず図に書いて頑張って考察する
→いい感じにそれよりちっちゃい状態に落とし込むことで再帰的に計算できそう
→あれ包除原理っぽくね…解けませんが(不勉強
→がんばればできる!できた!(WA)
本番では80分考察&実装してコンテスト終了10分前くらいにようやくサンプル全部通るコード完成して投げたけど4WAで返ってきて絶望しました.
(結局例外処理ミスってただけなので終わった後1行くらい直したら通った)
考察その他は長くなったので別記事にまとめました
simamumu.hatenablog.com
感想
Eここまで考察できたからコンテスト中に通したかったん…(流石にこんなめんどくさいの想定解ではなさそうですが
2,3WAくらい出して終了間際で700一本通しても300早解きと正直そんなにパフォ変わららないはあるけど
ていうか一考もしないでEに移ったのは頭悪かったですね,今度からはちゃんと問題は一通り目を通そうと思います
まあ後日700点問題どっちもなんとか自力ACできたし、色々と学べたコンテストなのでその点は良かったです
レートは上がってるけどパフォは順調に落としてきてるのでそろそろ頭打ち感…
というかもっと500-600あたりの問題が欲しいぞ(700解けない人並感