結果
D問題までの4完。Highestが更新されていく。
A問題
での場合分けを間違えて1WA。サンプルにあるのに合ってないものを提出してしまうとは。自動でサンプルの成否確認して提出するプログラム欲しいと思うこともあるけど、コンテストに出る際の環境が複数ありえるのがちょっと困りどころで。
B問題
斜め方向をstd::mapに詰めていくとできる。C++のSTL(Standard Template Library)はかなり強い。
C問題
問題の見た目がそうなので正だけ負だけと正負混合で場合分けだなというのはすぐ見えるしそこから実現可能な最大値はすぐわかるけど、手順を出す方ところでちょっと手間取る。ソートして先頭 or 末尾にほとんど吸収させる方針で考えるのが個人的には楽だった。
場合分けに気づくところではパターンマッチ感が強く、思考している感じがなかった。競技プログラミングに最適化してしまっているだけではと思ってしまう。棋は別智。
D問題
自分の解法が合っているのか自信がない。
まず交換は何度でもできるので、Bでは最初にまず全てどんぐりに戻して良いことに気づく。というわけでBの最初で持てるどんぐり数をまず最大化したくなり、それはAで金を買う数(0から最大5000) * 銀を買う数(0から最大5000)を全探索すれば銅の数はレートを見てでどうすればいいかわかるので求まる。
そしてBでどう金銀銅を買うかだけど、だいたい気持ちとしては一番レートが良いものをできるだけ買い、次に二番目にレートが良いものをやっぱりできるだけ買い、最後に三番目にレートが良いものをB→Aのレートが上昇するかを見て決める。ただし、端数の関係で一番、二番目にレートが良いものも限界まで買い切らない方がよい可能性がある。よって限界から限界 - 5000までを試してみる。こうすると通る。レートが良い順番もまじめに求めるのが面倒くさかったのでを総当たりした。よくわからない解き方をしてしまった。
解説PDFを見たけどDPなんですか。はぁ。多分僕の解き方は正当ではない気がする。最小公倍数が大きくなるケースが怪しいのかとは思いつつ、具体的に落ちるケースを示せと言われたら無理。
