titiaのノート: Codeforces Round #617 (Div. 3)

2020年3月10日火曜日

　変な勘違いでE2が通らず全完を逃した……と思ったらFもHackされてしまった。

コンテストへのリンク

A. Array with Odd Sum

　和を奇数にしたいので、mod 2で考えると分かりやすい。

　元々の和が奇数ならOK。

　和を変えるためには、mod 2で0のものと1のものが存在していないといけない。

　効率よくキャッシュバックをもらうには、10の倍数のものを買うのが良い。n円お金があるとき、n//10円のものを買う、としてシミュレーション。

　同じ場所を二度通っていたら、その区間は削って良い。

　ので、まずロボットがどう動くかシミュレーションして、同じ場所を二度通っていたらその区間を一つ出力。

　「モンスターを倒した次は自分のターン」というclarがないと問題文が不明確でした。もし、「自分が倒したら、次は相手のターンでスタート」だったら、大分面倒になりそうです。

　今回の問題では、各モンスターについて、何回テクニックを使えば経験値を得られるか計算できるので、ソートして貪欲に使っていけばOK。

　これは先にE2を見るべきでした。

　二色ということにこだわってよく分からない実装をしてしまった。結局は、LISをO($N^2$)でやるのと同じことをしたと思うんだけど……。

　index i, j (i<j)で、S[i]>S[j]のとき、その二文字は交換しなくちゃいけないので、別の色を割り当てなくてはダメ。

　この考え方はLIS（今回はこの逆で、最長減少部分列）と同じですね。
　本番では、LISと転倒数を混乱して、ライブラリを貼り間違えて悩んでいるうちに時間切れ……。

　けんちょんさんの解説記事では、ABCの問題と同一であると指摘されているけど、これが同一と理解するのは難しいと思う（私はまだよく分かってません……）。「LDSに帰着できる」、ということさえ分かればこの問題は解けます。

　ただ、見た目の結構違う問題を同じと気付ける（言い換えられる）かどうかは、もっと難しい問題を解く上では大切ですよね……。

　最初、全ての区間の美しさを$10^6$に設定しておき、美しさの最小値が大きい質問から順に、その区間のうち$10^6$の部分をその値に更新→十分性チェック、という方針でやった。

　毎回DFSで区間を求めてもO(N*M)だから大丈夫なはず……と思ったらTLEでHackされてしまいました。

　解法を少し変更して、更新された値が一つでもあればOK、として十分性チェックをなくしたりしてもダメ。

　結局、TLEが出ていた原因は、node aとnode bを繋ぐedgeの番号を調べるとき、dict D[a,b]とtupleを使っていたのが不味かったようで。そこを(a<<13)+bのようにしたら通りました。

　なお、初期値を0に設定して、質問された全ての区間を質問の値に更新していく……という方針もありますね。他の方のコードを見て知りました。