最終更新: 2024-04-03T08:25+0900
AtCoder をプラットフォームとして利用する有志コンであり、AtCoder の問題ではないけども、競プロカテゴリとして AtCoder に分類しています。
リアルタイム参加はしていない。ABCDFHIE をこの順に解いたのでふりかえって書く。
出現数を数える。Array#tally そのもの。
２本の線が一致することはないので、必ず３つか４つに分割される。ソートするなりしてうまく分類する。
うまくできませんでした。
数列が a,1,b であるとする。そうすると、b=a+1、a=b+1、b=a+1 と操作を繰り返すことで無限に大きな要素を作ることができる。A[1]=1 の場合であっても、A[1] を無限大にすることができる。初期数列が１以上の要素を含んでいることが必要十分条件だと思いました。証明は知りません。
間違えました。最初は、２つの要素を足して１以上になることが必要十分条件だと思ったんだよね。証明は知らないとか言ってっからだよ。
すごーく難しかった。４回間違えた。順番に WA×13、WA×3、WA×2、WA×1。
まずは問題を理解する。X 座標と Y 座標について、正負どちら方向に移動することもできるけど、移動量の絶対値が一致していなければいけない。
どういう操作を構成するか。最初からずっと想定していたのは、まずは X 座標もしくは Y 座標の、ずれが小さい方の数字を一致させる。その後はずれが大きい方を、偶数回の操作で一致させる。偶数回というのは、先に合わせた方の座標をずらしたくないので、移動量を等分して打ち消し合わせるということ。
この考え方で WA×1 まで行ったのだけど、一方のずれに対して他方のずれが非常に大きい場合に答えが微妙に合わなくなる。
結論を書くと、最初に目指すべきポイントは近い方の座標ではなかった。偶数回の操作の折返し点を目指すべきだった。要するに、X 座標のずれが DX、Y 座標のずれが DY だとして、DX<DY なら最初に目指すべき点は DX+(DY-DX)/2 だったということ。DX だけ移動してから DY-DX を偶数回で移動するのではなく、DX+(DY-DX)/2 移動してから (DY-DX)/2 移動する操作を構成するのだった。
ARC で 400 点ぐらい配点してもいい問題だと思います。400 点というのは、数学的センスがある人は瞬殺するけども、自分は１時間以上苦しむという、そういう問題。
任意の部分列について成り立たなければいけないので、一番極端なケースを想定する。つまり、N=1 のケースと N=2 のケース、そして中央値に対して極端に平均を下げるような列を。
N=1 のケースでは中央値と平均値が一致する。N=2 のケースでは a1<a2 なる列の中央値が a1 なので平均値が必ず中央値を上回る。N>=3 の場合で N が偶数のとき、中央値より大きい値の数が小さい値の数より１つ多くなるので、平均値は大きくなりがち。だから N が奇数の場合だけを考える。もっといえば、N=3 で成り立つなら N=5 でも N=7 でも成り立つと思うんだけど、そんな気がするだけ。
N=3 のケース。a1<a2<a3 としても構わないのでそうする。平均を下げたいので a1 は最低の 0。a3 がいくつなら平均が a2 以上になるだろうか。2×a2 が最低ライン。N の制約が 20 万以下ということだけど、要素が倍々に増えていくなら ai≦10^9 の制約から実質的な上限は 30 程度になる。
問題文の表現にひっかかりがありますね。「氷の張ってある道をなるべく通りたくないです
」「氷の張ってある道を通る時間を最小化して街 N に移動するとき
」。要するに氷が張っている道を通ることもあると言っている。01BFS みたいに、氷が張っている道を０回通る場合の最小値、１回通る場合の最小値、２回の場合の……、を N にたどり着くまで繰り返して求めれば良さそう。うまくやればいらないかもだけどプライオリティキューを使ってダイクストラ法をした。
01BFS ということでこれは２本のキューを切り替えながら使った。
氷の上を何回通ったかと経過時間とを１つの値にエンコードすることで、キューを１本だけ使う普通のダイクストラ法になった。
まずは問題を理解する。ある要素を１つ後ろに移動し、その際に K を加算する、というのが操作。
最初は後ろにある要素に操作を繰り返して大きくすることで昇順の列を作ることを考えた。最低２つの要素があれば、交互に操作対象に選ぶことで任意の回数 K を加算することができる。２つの要素の初期の差を解消したり拡大したりすることはできないけど、１回の操作で昇順にできるので問題ない。
これの問題は K=1 で Ai が上限の 10^9 に近いとき。初期数列が A1=10^9、A2=1、A3=1 だったとして、A2 と A3 に操作を繰り返して A1 以上にすることは可能だけど、操作回数が 50 万を超えてしまう。
次に考えたのは、最小値を列の前に持ってくること。i 番目に最小値があるとして、i-1 から 1 まで下りながら操作することで A1 から A_{i-1} にそれぞれ K を加算しつつ、Ai を先頭に持ってくることができる。以降これより後ろの数列に対してどんな操作を繰り返したとしても、Ai より小さい値が後ろに出現することはなく昇順が保たれる。
初期数列が降順にソートされている場合が最悪ケースだけど、N*(N-1)/2 回くらいの操作で昇順になる。N≦1000 だからちょうど操作上限の 50 万回を下回るくらい。
しょうもないミスをした。
vector の任意の位置から値を追い出すときに、末尾の要素とスワップしてからポップするというテクニックがある。順番に意味がないときは使って損がない。
順番に意味はあったのだ。順番が保存されていないと正しい操作対象が選べない。いや、自分は壊れた順番の中で正しい対象を選んでいたのだけど、そのせいで勘違いしたのだけど、ジャッジが正しさを検証できなければ意味がない。
300 点だけど難しかった。これが解けたのが嬉しくて今日の日記を書いているところがある。
とある赤い亀さんの日記を読みました。
学びのある問題だった。