青になった記念。YATTA!!!
経過
A見る。操作よくわからん。とりあえずi番目にiより大きいのは来なさそう。そうじゃなきゃできるんじゃね？実際に順番を復元しないといけないのでどうするか。サンプル3を見ると、後ろからうまく復元できそうな感じになる。なんかいい感じのアルゴリズムが手で思いついたが、eraseしないと行けなくてめんど...しかもO(N^3)か。まあええわ通るやろ→AC(24:42)
B見る。グラフかつ構成ゲーやめろ！！と思ったけど、手で書いたらなんかできた。は？？簡単じゃね？？まあ通すか→WA
は？？？？あ、偶数のケースで構成ミスってたわ、ゴミ。修正してAC(39:02)
ここで順位表を見ると、上位がみんなDを通していたので、Dを見る。しかし何も分からない。諦め。
C見る。なんかグラフ。サーキットってなんだよ。でも、サーキット3つあればいいし、次数偶数でそれなりに辺があったら絶対できるんじゃね。ワンチャン通らんかな→WA
知ってた。反例ありそう。探すか...
(しばらくして)こういうのがダメっぽい。
他は大丈夫だし442222...だけ優遇してみるか。片方の4から自分へ向かう道があったらYes, 無かったらこの例でNoか。書けそう→書く。通るかな...→AC!!!(85:17)
あとは何もわからないので、残り時間でこのブログを開設する(カス)
結果
ABCの3完、85:17(+2)で、154位でした。
pf2399は過去最高！YATTA！
rateは1570→1720で、青色到達です。
解法
A
bの他に123...Nという数列cを用意します。
後ろからbとcを見て、b[i]=c[i]の場所があれば、b,c共その場所を消して、cのi番目以降の数字を1減らします。これを繰り返せばできます。
という操作で実装したのでなぜかO(N^3)だったが、解説見てcがいらんことに気付いた...。cずっと123..になるやんけ、なにこれ。
B
Nが奇数の時は1とN-1, 2とN-2, ..., (N-1)/2と(N+1)/2を組に、Nが偶数の時は1とN-1, ..., N/2-1とN/2, Nを組にして、ペアの辺以外全部引くと(k部完全グラフ)にするとできます。
完全グラフの補グラフと考えるともっと簡単だったかもしれない。実装はそうしたのにね。
C
上で述べたとおり、次数がすべて偶数かつM>=N+1かつ44222..の上のパターン以外、という条件になるはず。このコーナーケースも頑張って除けます。
D
わからん...と思ったけどDPなんすかこれ。DPやめろ！
EF
なんにもわかんないね。また今度。
今日のWA
B
Nが偶数のときの捨てる辺を奇数の時と同じにしてた。橙pfを逃すゴミみたいなミスなので反省。
C
コーナーに気付かず提出。まあこれはしゃーない。
まとめ
グラフありがとうございます。
3完はしたものの、議論やコードの無駄がまだまだたくさん。精進あるのみ。
