ABC260
まとめ
A, B, C, D, F が解けました。
Fはかなりギリギリでした!
A - A Unique Letter
文字列の中の文字をカウントする関数を使いましょう。
B - Better Students Are Needed!
実務でもありそうな面倒臭さを感じる問題です。
ちょっと複雑なソートをうまくやれますか?ということが問われている感じ。計算量は問われない制約です。
ソートに加え、合格済みのフラグ管理をきちんとやる必要があってちょっと面倒です。
もっと楽に解ける方法がありそうな気がしましたが、愚直に頑張りました。
C - Changing Jewels
問題文を見て、高橋君には操作を行うバリエーションがあるのかと思ったのですが、どんな順番でやろうと結果は変わりません。なので、あるだけ宝石を変換していく過程を計算していくと良いです。
漸化式をイメージできれば、DPなりメモ化再帰なりで実装できます。
赤い宝石、青い宝石をそれぞれレベル毎に配列で持たせて上のレベルから下に配る要領でやりました。
D - Draw Your Cards
ソリティアっぽい問題です。
解説放送ではニムトというゲームが似てるって言ってた。
サンプルにもありますが、K = 1 の時はカードの順番からそのまま答えが出せます。
K > 1 の時はシミュレーションを頑張りましょう。
まず重ねる対象の「xよりも大きい値の中での最小値」は #平衡二分木 を使うと高速に見つけられます。 重ねた場合、平衡二分木の値も入れ替えておきましょう。
重ねた結果、枚数が K だったらそのタイミングでまとめてカードが食べられます。
重なりについては単純なグラフ構造で表現できます。
色々なデータ構造が活躍する面白い問題でした。
E - At Least One
解法が思いつきそうな感じがしなかったので、Fに行きました。
F - Find 4-cycle
変わった制約の問題です。具体的には、$ T = 3000 が最も気になります。
最初は DFS を実装して長さ4のサイクルを愚直に捜索しましたが、当然ながらTLEですしWAも出ました。DFSの計算量をしっかり把握してない・・
まあDFSで解ける問題であれば、不思議な制約を持っているわけがない、というのはある。
制約をまじめに読むと、 4-cycle は $ V_1a, V_2a, V_1b, V_2b みたいなルートしか考えなくて良い、ということがわかりました。
サンプル1でいうと、 [1 4][1 5][2 4][2 5] みたいな4つの辺がある。こういうのを検出できれば良い。
ここまでわかると、実はグラフ的なアプローチは全く必要なさそうな問題だなー、となった。
ここで $ T = 3000 が活きてきそう。具体的には $ O(T^2) がTLEにならない。
つまり、$ V_2の頂点のペアを全部列挙しても大丈夫。
$ V_2 のペアを全部列挙しておいて、そのペアと繋がっている $ V_1の頂点が2つ見つかればOK。
という実装をするだけでも $ O(ST^2) になりそうな気しかしないのだが、提出したら通ってしまった。
解説を見ると鳩の巣原理ということで、実際そこまでループが回らないということか・・
G以降は見れませんでした。