競プロ日記

順位: 1671

パフォーマンス: 1053

新レーティング: 1048

差分: -2

5完
5完なのにレート下がるなんてそんな・・・。
全体的に簡単が過ぎる・・・。
E問題もうちょっと早く解けても良かったのと、F問題の考察進める速度が遅すぎた。
生活習慣ゴミだったので、ほぼ徹夜明け+テレビ見ながらと、コンディションはなかなかに悪かったのが言い訳になりそう。
M-1見たかったからね。

かんたん。
実装楽にするためにどうしようかちょっと考えた。
ハッシュ化すれば簡単そう、いやハッシュ化できるならそのままでも・・・、という流れで6-A-Bじゃんとなった。

かんたん。
B問題でこんなに簡単なの久しぶり？

かんたん。
C問題でこんなに簡単なの初めて？
前回のbit全探索見習って。
最小公倍数のライブラリ作ってて良かった。

貪欲でいけそうと比較的すぐ気付いたものの、実装で手間取った。
素直にforの中でif使えば良いものの、連続要素数える時と似てるな、ということでwhileなんて使うから1WA+タイムロスを生んでしまった。
15分かかってしまったが、5分で解けても良かった。

なんだこの数列は・・・。
制約すごいからLogかけられそうということで行列累乗を試してみる。
式は作れたものの、変数が出てきてしまってうまく繰り返し二乗が使える形に持っていけない。

最初のいくつかをシミュレートして数式辞典で調べてみるとそれ知ってるよーと教えてくれた！
二重階乗というらしい。
なんならn!!とか記号までついてる。
名前も記号も初めて見たんだが？
一般項もあったが、どう頑張っても誤差出ますよーって見た目してる。
それに多倍長でも無理だろって桁になりそう。

諦めて0が何個続くかに重点を置いて考察していくと、10作るなら2×5しかないと気づく。
・・・これどこかでやらなかった？？？
2は山程あるから5だけ数えれば良いってすごいどこかでやった考え方。
どこでやったのか全然思い出せなかったし、今も分かってない。
とりあえず方針は立ったが5の数え方はすぐに出てこなかったので、いくつか書いてみたら5^nごとに1回ずつ出てくるというのが分かった。

その通り実装するも、ここで恒例の凡ミス。
forの更新式でi*=5で5^nを計算していきたかったのだが、i*=iとしてしまって答えが合わない。
考察25分+凡ミス10分で35分くらいかかった。

ここまで57分。
時間は余裕というわけではないが、なんか解けそうな雰囲気。解けなかった。
考察が全然進まなかったが、コンテストの時間内では最終的に、「u, v間の最短経路を通って高橋くんが青木くんにギリギリまで近づき(近づいた後の頂点をaとする)、その近づいた際に通ったルートの各点から(各点をbとする)、青木くんのいない方にできるだけ頂点がある道に進み、その頂点数+aとbの距離が逃げられる最長距離。偶奇によって±1がありそう。」という考えになった。
考察にかなり時間がかかった上、実装も結構ややこしかったのでタイムアップ。
実装に取り掛かったのは30分後くらいだと思うが、考察も続けながらなので厳しかった。
さすがにまだDFS2回はスラスラ書けないねー。

方針はあってそうなんだけどなーと思っていたので、コンテスト終了後も自力で解き続けてみた。
実装を進めていくと、近づいた際の各点bからのルートは、近づいた最終の頂点aからのルートに含まれていることに気付いた。
つまり、「u, v間の最短経路を通って高橋くんが青木くんにギリギリまで近づき、近づいた後の頂点から青木くんのいない方にできるだけ頂点がある道に進み、その頂点数が最長距離。偶奇によって±1がありそう。」とかなり実装が簡単になった。
順調に実装を進めて提出するとWA。
よく考えると偶奇の処理が正確でなかったので直してAC。
コンテスト終了後の所要時間は15分くらい。
解説見ずにF通せたのは初めてかもしれない。
diff水色だけど。

まとめ

E問題diff茶色ってマジ？おかしくない？
バッドコンディションが脳死行列累乗に繋がって、それに時間かけたのはかなり悪手だった。
とは言え茶色に時間かかるのは苦手問題ってことなのかなぁ。
それよりは単純にFの考察をもっと短く正確にというのが本筋か。

-2とは言えレート下がってしまったので、年内水色難しそう。
しかもブログの移行関連で面白そうなものを見つけてしまい、そればかりで全く問題を説いていない。
今日はAGC明日はABCと一応出るが、今日の初AGCがどうなるかで決まる感じがある。
AGCは過去問すら1問も解いていないので不安しかない。
なんとか頑張っていきたいところ。

ブログのシンタックスハイライトは直ったみたい。
やっぱり悪いのは忍者ブログだった！
直ったからブログの移行はまぁいいやとしても良いのだが、前述の通り面白そうなのを見つけて結構時間をかけているから移行はする。
色々考えた結果デザインが1から自分でになったのがつらすぎる。
こっちも年内目標。