Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder 第二回全国統一プログラミング王決定戦予選

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してしまったので、何らかの高速化というか、辺を最小限にする工夫が必要なのですが、その方法は見つからず。

まとめ

いやもういいかげん立ち回りを手堅くしていかないと、無駄にレートを溶かすばかりです。 水色タッチしてから気が抜けてしまったのかなぁ・・・。いいかげんちょっと取り組み方というか、競プロとの付き合い方を考え直さないといけないですね。

まあそこをちゃんとすればレート下がってないわけで、ちゃんとしようということですね、はい。

f:id:mdstoy:20191110001524p:plain