5完1WA。
各問題
A - Rotate
文字をばらして並べ替えて数値に変換して足す、をしました。
こういう問題はどうとでもできるっちゃあできるんですけど、どうやるのが一番早いのか未だによくわからず・・・。今回も無駄に3分以上かけてます。つらい。
(追記)
abc + bca + cab
は、a*100 + b*10 + c + b*100 + c*10 + a + c*100 + a*10 + b = a*111 + b*111 + c*111 = (a+b+c)*111
となるそうで。いや言われてみればそれはそうすぎる・・・。
B - Climbing Takahashi
単純に現在位置と右隣と比較して、移動できたらして、移動できなくなったらそこが答えです。右端の処理は、0を余分にくっつけるでもよし、ループが最後まで行ききったら最後のHが答えだとしてもよし。
C - The Kth Time Query
map<int, vector<int>>
で、各a毎に何番目に登場するかを保存しておけば、m[x]
のサイズがkより小さければ-1
だし、大きければmx[x][k - 1]
を答えればよいとなります。
D - Multiply and Rotate
数値変換の最中に同じ数字を経由するのは意味がなく、桁数が減ることもありえないので、最悪でも106回で処理が終わります。よってメモ化再帰を書けばよいだけです。
E - MST + 1
最小全域木なのでクラスカル法をすればよいのですが、Gに含まれる辺もクエリで出てくる辺もすべて含めてソートしてしまってから、クラスカル法をします。
採用された辺がGに含まれる辺なら (Union-Find Treeに) merge、クエリに含まれる辺なら"Yes"を出力、採用されなかった辺がGに含まれる辺なら無視、クエリに含まれる辺なら"No"を出力、とすればよいです。
それ以降
なんもわからん・・・。
まとめ
10ヶ月ぶりのHighest更新となりました!!
しかし青パフォは遠い・・・。Eの解法をすぐに思いつけるようにならないとだめという領域に来てしまったのかー。