今日解いた競プロの問題。
ARC111-C: 自力AC。とても美しい解法を自力でスッと出せて、とても気持ちがいい！！！
まず大雑把に問題を読んで分かることとして、人の順番には特に意味がないので適当にソートしたくなる。答える時に必要になるので、元の位置と持っている荷物$p_i$は保持する必要があることだけ注意。
操作回数の最小化と達成可能性の判定の2つの目標があるが、とりあえず達成可能性の判定から考える。
ナイーヴに考えると、1つずつ片っ端からマッチングさせて行きたい。(人1, 荷物k), (人i, 荷物1)という2人がいるとしたら、この2人でスワップすれば良い。これを片っ端から繰り返せば操作回数も最小になる。しかしこの問題では「自分より重い荷物を持つと疲れてしまう」という条件があるので、単純にそういうわけにはいかない。この例の場合、人1は(どちらかが既に疲れているのでない限り)必ず荷物1にありつけるが、$i\neq k$の可能性があることから人iは必ずしも自分の荷物にありつけない。$a_i\leq b_k$ならばそのまま疲れてしまい、手詰まりになる。
もう一つ気付くこととして、上のような操作をした場合、人1は基本的に以降の操作から排除される。自分の荷物が自分以上に重ければ、正しくマッチングした時点で当然動けなくなるし、またそうでなくても一度自分の荷物とマッチングした後に再度手放すのは操作回数の無駄になる(ここはちょっと厳密な議論でないかも)。なので、一度自分の荷物を受け取った人は以降の操作から排除していくと思って良い。
以上のことから、順に正しい荷物を受け取らせ、正しい荷物を受け取った人から排除していくイメージになる。ではどのような人からその対象にすべきか。体重の重い人はより重いものを持てるので、一番軽い人はいつ排除しても構わないことが分かる。一番軽い人が持てる荷物は他の全ての人が持てるからだ。ということで、体重の軽い人から順に正しい荷物を受け取らせるのが最善の戦略になる。
一番軽い人を人iとし、荷物iを持つ人を人jとする。$i\neq j$かつ$(i,j)$で操作を行えなかった場合、これは手詰まりである。操作を行えた場合、この操作をして以降の選択肢が狭まることはない。なぜならば、一番軽い人iが荷物を持って疲れていないということは、この荷物は他のどの人も持って疲れることがない。またこれで人iが戦線離脱しても、人iが出来ることは他のどの人も出来るので一切損をしない。この戦略で不可能ならば条件は満たせない。また一回操作をするたびに必ず1人又は2人マッチングされるので、この戦略が操作回数も最小になる。(若干厳密な議論でないかも)
ARCの青diff、それも苦手な順列を解けたので気分が晴れがましい。ソートしてそこで保存される特性を用いた議論みたいなのも、解説でよく見るけど自力でなかなか思いつけないやつのひとつなので、それを出せたのも嬉しいかも。
久しぶりにチャーハンを作った。なんか自分の手際が良くなっているのを感じる。
Categories: 未分類