Cまでの三完で101位でした。Highest更新できて嬉しい！
ただ、難問が解けたわけではないんですよね。早解き回では時々良い成績が取れるんですが、早解きが得意というわけでもないので、なんというか、運任せのようになってしまう。今回は、BもCも結構最初から正しい解法を考えていたけれど、偶然に近いものね……。
もっと難しい問題を解く力を付けないと。
B - Greedy Division
初手で実験を書いたのが結果的には正解だったと思う。
実験というのは、Wの配列に対して、どんな順列がありうるか……というのを順列全探索で求めるコードです。
それを眺めていたら、「あれ、和がSUM/2に一致していれば、高橋君や青木君の取り方をどんな順番にしても、正しい順列が一つ求まるのでは？」と気付き（気付けば証明もしやすかった）、後はナップザック問題みたいな感じでした。
計算量が四乗になるのがちょっと不安だったけれど、定数倍が小さそうなので大丈夫だろう、と提出したら無事AC。
C - Roughly Sorted
これは、「2 1 4 3 6 5」でK=1の場合などを考えました。この例で、1や3はいくらでも後ろに動かせるけど、2が4の後ろにいくと途端にダメになるんですね。
それを見て、「自分より前に登場している自分より大きい数の個数」がKに一致しているものしか動かせないんだな、と気付けました。
（DかEはできれば解説ACしたい）
0 件のコメント:
コメントを投稿