2AC1WA。
ただ、またしてもBの考察で詰まったあげくCDをしばらく考えてしまったので、無駄に時間を使ってしまいました・・・。学習しないなぁ自分。
各問題
A - Sum of Two Integers
正直に言いますと、多分なんとなく直感で(N - 1) / 2
だろうなと思って投げたら通りました。(え
まあいくつか実験してみて一般化すればそうなります。
B - Counting of Trees
組み合わせは、「上位の頂点数」の「下位の頂点数」乗になります。あとはそれを順次掛け合わせるだけです。(といいつつ、自分はそれに気づくのにとても時間がかかってしまいましたが)
ところで、与えられたDでは木が構築できないケースは0としなければいけません。頂点1が0でないとか、途中に0になっているレベルがあるとか。
幸い私はひっかかりませんでしたが、コーナーケースに分岐した時にreturn
するのを忘れて1WAを出してしまいました。
C - Swaps
「N-2
以下」の条件を無視すれば、お互いの列をソートして条件を満たせばOKというのはすぐ気づきます。
また、すべてを循環させなければならないケース(例えば'2 3 4 1'とか)はN-1
回が必要ということも気づきました。
しかし、どういう時にそのN-1
のケースに当てはまるのかを調べる方法がわかりませんでした。
D - Shortest Path on a Line
単純に条件通り構築してからダイクストラではTLEしてしまったので、何らかの高速化というか、辺を最小限にする工夫が必要なのですが、その方法は見つからず。
まとめ
いやもういいかげん立ち回りを手堅くしていかないと、無駄にレートを溶かすばかりです。 水色タッチしてから気が抜けてしまったのかなぁ・・・。いいかげんちょっと取り組み方というか、競プロとの付き合い方を考え直さないといけないですね。
まあそこをちゃんとすればレート下がってないわけで、ちゃんとしようということですね、はい。