競プロ日記

差分: +39

4完
Dに時間がかかりすぎた。
苦手だったわけではないが、単純に舐めていた。
真剣に解いていたつもりだけど真剣じゃなかったというのかな・・・。
後50分は縮められたはず。

A問題

かんたん。

B問題

かんたん。

C問題

相当悩んだ。
なるべく差が小さい2つの値の積でNを表せれば良いというまではすぐ分かった。
「同じ周の長さの長方形なら面積を最大にできるのは正方形である」というのはなぜか昔から何度も考えたことがあったので、この方針に疑いはなかった。
ただそれを全く実装できない！
とりあえずNを素因数分解して、あとはその組み合わせの積でなるべく差が小さくなるようにする、ナップサック問題的な問題なんじゃないか？とずっと考えていた。
でもそうするとおそらく間に合わないし、そもそもC問題レベルではないと思ったのでそういう解き方ではないと考えた。
あるときふと思いついた、「√Nから探索始めればいいじゃん！」と。
頭カチカチって感じ。
かなりの長時間考えていた気がするが、改めて確認してみると意外と20分しかかかっていなかった。
ここまで24分。

D問題

これ解くのにおよそ1時間！遅い！
算数の問題だな！と思って紙とペンで頑張ってみたのだが全く進まない。
小学生時代相当頭良かったので解けるだろうと高をくくっていたので解いている途中ずっとショックとも戦っていた。
"数学"ではなく"算数"だと完全に認識してしまっていたので、三角関数なんていう概念はなかったのが敗因。
なんとかして相似とか合同とかで解こうとしていた。
角度が30°とか45°とかで固定で、どれだけ溢れるでしょうとかが算数の問題で、サンプルの回答に無限小数らしき実数が出てくる時点で三角関数が出てくるのは明白だ。
サンプルを見るのが遅すぎたのもよくない。
なんならサンプルを見た後にも、今までの算数の思考が残りすぎて、「無限小数？なんで？どうやって出てくるの？長さの掛け算割り算で角度がそんなことになる？」となかなか理解できなかった。
それもあって三角関数使えると気づいてからもすんなりいかなかったが、それでも10分程度でACまで持っていけたと思う。
二分探索でも解けるみたいだが、角度ごとに溢れるかどうか計算できるならそんな遠回りせずに普通に最大角度求められるんじゃないか？と思う。
深く考えていないが、溢れるかどうかだけでも条件分岐が必要とは書かれていたものの、直接求めるよりは単純に計算できるんだろうか。
これを解いた時点で82分。
さすがにきつい。

E問題

Dを解けるはずという確信はあったので、Dを解いている途中にはちらっとしか見ていない。
18分弱で一応考えてみたが、さすがに無理だった。
消化コストAiと食べにくさFiを小×大となるようにソートするところまでは思いついたが、その先がうまくいかなかった。
完食にかかる時間XとFiのペアーをsetに入れて、最も大きいものを取り出してFi減らしてまたsetに入れて～というのをやろうにも、あまりにもKが大きすぎる。
Fiの最小公倍数を求めれば、全ての人が(LCM/Fi)回修行すれば、最初のsetの順番はそのままで全ての要素がLCMだけ減る！という方針が思いついた中では一番考えている感がある。
考えている感はあるが、Fiに10^6, 10^6-1があった時点で終わってしまうのでたいぶしょうもない。
あまり解放について調べていないのだが、答えを決め打ちして二分探索するっぽい。
その解き方自体はどこかでそういうのがある見たレベルにはあるのだが、詳しくは知らないので勉強ポイント。

F問題

未だに問題すら読んでいない。


これから算数の問題っぽいものも数学の問題と心構えて解きます・・・。

最近件の3完のEを解いたのだが、何も見ずに解けてしまった。
参加したコンテストのEで想定解が新しい知識を必要としないものは一番最初だけだったので、久々に自力で解けて嬉しい。
時間的にもそんなにかからなかったので、D解けてたらEも行けたかもなあと惜しい気持ちもある。
この3完は置いておいて、少なくとも練習だとEもたまにじゃなくて安定して解けるようにならないと始まらない感じがたいぶ出てきたので、頑張って経験積んでいきたい。