１２時３０分に起きた。１４時からサークルがあるのでそれに向けて急いで支度をしたが結局家を出るのはかなりギリギリになってしまった。２時間テニスをして帰りに田中そばによることになった。久しぶりに食べたのだがこってりは安定でおいしかった。そういえば、授業開始は今週の金曜日からという重要情報を得た。しかし、コース発表が木曜なのでそれまではいいかなと思わなくもないが、さすがに前日にやるのはまずいので明日起きたらやろうと思う。
かえってすぐシャワーを浴びて寝た。起きたのは２１時くらいだったか。今日div3があると思っていたのでとりあえずこの前のABCのFを解いた。最近のFの中ではだいぶ簡単な方だと感じた。１時間ほどスマブラをしてそろそろかと思ってコンテストサイトに入ったがどうやら今日ではなく明日だったみたいだ。やることのなかったので前回のARCのC問題を考え始めた。考察は進んだがいまだに答えにはたどりつかない。明日中には終わらせて典型９０の続きをしていきたい。
ABC216
A,Bやるだけ
D queueでシュミレーション、典型らしいがめっちゃ時間かかった
E 二部探索だが実装に死ぬほど時間かかって死亡
ABC146-F Sugoroku
直線上のすごろくで踏んではいけないマス目があり、コマの目が１～Mの時、最短手数とその時の辞書順で一番小さい目の出方を求めよ、という問題。
前から貪欲にいけば最短手数はすぐ求まるなと思ったが辞書順最小がややネック。少しして貪欲をすると必然的に辞書順最大になるから、後ろから貪欲すればいいことに気付いた。配列の後ろから見るというのもよく使う手法だなと思った。
E-All you can eat
答えが時間の昇順になることを利用してknapsack dp
A,B,C問題はやるだけだった。D問題について、エラトステネスの篩をつかってなんかできそうと思ったがそもそもアルゴリズムとその計算量を忘れかけていて時間がかかった。問題は、N個の整数が与えられていてそのどれともgcd(A[i],k)=1となるようなkをすべて列挙せよ、というものだ。それぞれ素因数分解したら間に合わなそうだから、エラトステネスで素数判定する中でA[i]に入るかも判定しようとしたがどうも計算量とそのアルゴリズムがはっきりしなくて時間がかかってしまった。ここまで３０分。
E問題は、bitdpだな－とは思いつつもなかなかちゃんとしたdpを組めなかった。
dp[i][S][j]と３次元にしてしまうと計算量がきつくなりそうでずっと２次元で行ける方法を探していたが、結局見つからず残り１５分程度で３次元dpを書くことに踏み切った。
遷移を考えたら思ったよりシンプルで計算量は多くてO(10^7)だった。
先日のABCで解けなかったD問題を考えていた。本番は問題を勘違いした挙句実装に苦しみ死亡したが、冷静に考えたらとても簡単だった。Union Find にその連結成分の個数を持たせるというものだ。
E問題について、本番残り25分くらいあってD,Eどちら行くか迷ってEにした。10分くらいで貪欲法に気付いたが、Dの影響で頭が混乱していてすぐに実装できなかった。multisetを久しぶりに使ったが、常にsortされた配列としてとても便利だ。iteratorの扱いだけ、その値は＊を付ければ知れるということは覚えておきたい。
F問題も見てみた。数え上げの問題で、まずできるだけ前に詰めて文字を選ぶという条件も加える。dp[i]=最後がiの場所で終わる文字列の個数,として前に着けることだけ意識すれば解けそうともったがまだ実装してないからわからない。
朝起きたら１０時ごろだったと思う。特にやることもなかったから本を読んで寝てを繰り返していた。朝ご飯を食べたのは１１時ごろだった。部屋に戻ってスマブラをしながらだらけていた。その後３時くらいまではyoutubeをみて寝そべっていた。今日もこのまま終わってしまうことを危惧して外に出た。本屋で漫画を読むだけだったがその時間はとても良かった。やっぱり一回外に出てふらつく方がだらけが取れてよい。
