htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Grand Contest 018 参戦記

o---- 1358 -> 1355 (-3)

A - Getting Difference

結果:AC(1WA)
Submission #1446363 - AtCoder Grand Contest 018 | AtCoder

問題文一通り読んでどういう問題なのか全く把握できなかったので辛かった。

入力例 2
3 5
6 9 3
出力例 2
IMPOSSIBLE
どれだけ操作を行っても、5 の書かれたボールを箱の中に入れることはできません。 よってこの例の答えは、IMPOSSIBLE になります。

この例がなければ全く解けなかったかも。要するにxの倍数のボールしかない場合は何回abs(n*x - m*x)してもxの倍数しか作れないので、K-max(A)xの倍数でなければIMPOSSIBLEだというわけ。ただしmin(A)xの倍数であるケースに注意(A = [6, 9, 12]の場合xは3)。要するに最大公約数を取れという問題。

B - Sports Festival

結果:ダメ

貪欲じゃないよなーと思ったら貪欲だった。計算量的にも余裕だった。700点だから何かしら知らないと解けない問題だよなーと思ったんだよ……!言い訳ですけど。

全てのスポーツが開催される前提で第一希望を見比べて、その中からスポーツを廃止して第二希望以降をリストから取ってくる……という考え方自体はあったんだけど、何を血迷ったのかどこかのリストが空になった場合にその時点での答えは最適なのか??みたいなことを考えてしまった。全員は全てのスポーツについて第M希望まで持つので、どこかのリストだけが空になることはなく全ての希望リストが同時に空になる(あたりまえ)。よって単に全員の第一希望から一番多く被っているスポーツを消してって次の希望リストから補充する、をちょうどM回繰り返せばいい。補充するときにすでに消したスポーツは捨てて補充し直すことだけ注意する。

Submission #1450906 - AtCoder Grand Contest 018 | AtCoder