結果
時間ギリギリの3完。今週はまあまあ精進したつもりだったので、ショックが大きすぎます。
A問題
問題の読解に時間を要しました。今回のコンテストはなんだか難しい予感がビンビンしました。開始直後に抱いたこの予感は的中してしまいました。
B問題
入力のとりうる値が小さいB問題は大抵全探索で解ける気がします。個人的にはA問題よりB問題の方が解きやすかったです。
C問題
問題を見た時、「いやこれ間に合わないでしょ。」って思いました。最初に思いついたのはAにもCにも影響を及ぼしそうなBを1から√nまで全探索して、そこから二分探索してなんとか条件を満たすAとCの数を求めるというものでした。実装してみましたが、入力が10**11の時に全く間に合いません。その他に解法も思いつかないのでD問題を解くことにしました。ラスト15分で返ってきて再考すると、Aがとりうる範囲が一番小さいんだからAから見ていけば良いんじゃないのか？と気づき、血眼で実装したらなんとかACできました。最初の考察でこれに気づくことができていればレートを減らさずに済んだかもしれません。完全なる力不足です。
D問題
最初、昨日履修したセグメント木を使えるのでは？なんて考えがよぎるも、あ、無理だと思いました。履修した内容がすぐに出題されるなんていうそんなラッキーはそう簡単に起こらないみたいです。その後は、「まずはaをソートして上からk個とってきた配列をtmpとする。残った配列をresとする。これの最小値を取り出して、最終的な答えに加算。resから最も大きいものをtmpに加える。」という操作をresがなくなるまで繰り返す解法しか思いつかず、それを気合いで実装。最初はTLEとWAの嵐。誤りに気付いて再度実装し、勝ちを確信して提出すると12AC、17WA。デバッグに大量の時間を注ぎ込むも、何が間違いか気づくことができず諦めてしまいました。
解説を見てびっくり仰天＋感動しました。プロジェクトをp個として、各部署からp人を超えない範囲でできるだけ多くの人を派遣した合計が、p*kを上回れば、そりゃプロジェクトをp個作ることができますね。。。問題を見る角度を変えて解くという力が圧倒的に不足しています。頭の弱さを痛感するばかりです。
E問題
密かに5完を狙ってましたが、問題を見ることすらできませんでした。来週までにACしたいと思います。
総括
年内水色が現実的ではなくなってきてしまいました。精進あるのみです。
余談
今週、vimiumっていう便利すぎるchromeの拡張機能を知りました。Webページの閲覧、移動がキーボード入力で行える超優れものです！使ってない方はぜひ使ってみてください！
