5完。
悪くない出来だったけど勝った気がしない...。
各問題
A - Rightmost
後ろからチェックして、'a' ならその位置を出力して終了、最後まで見つからなければ -1 を出力して終了します。
B - Adjacency List
map<int, set<int>>
を用意して、mp[A_i].emplace(B_i)
と mp[B_i].emplace(A_i)
をして、最後に1から順に set の数と中身を出力するだけです。
C - Previous Permutation
今週の特大目玉。
prev_permutation
を知っていますか?私は知っています。(慣用句)
はい、与えられた順列を prev_permutation に通してから出力すれば終わりです。
D - Divide by 2 or 3
まず、各 a を2と3で割り切れるだけ割ったものが、すべて一致しない場合答えは No です。
一致する場合、各 a が 2 で何回割れるかを数えて、最も少ないものに合わせます。例えば 4, 16, 8 なら, 22, 24, 23 で、最終的に 4, 4, 4 (22, 22, 22) にするのが一番得です。min の 4 (22) より大きくすることはできませんし、小さくすると無駄にたくさん割ることになってしまうからです。結局、16 は 2 で 2回 (4 - 2) 割る、8 は 2 で 1回 (3 - 2) 割ることになります。
3についても同じことをします。
E - Round Trip
今週の超目玉。
Sの上(or 右 or 下 or 左)からBFSをする。ただしスタート直後に S には戻れない。で、できます。
F - Double Chance
A_i より大きいものの和と、A_iより小さいものがいくつあるかがほしいので、を平衡二分木とかセグ木とか活用して頑張ろうとしましたがたどり着けず。解説見たら Fenwick tree でよいらしい。そうですか...。
まとめ
うーん、Fは考察間違ってなかったので、時間も1時間近く残っていたのに通せなかったのが残念無念。結局水パフォ中位安定ですか...。