ABD3完 74:43 + 3ペナ 249位
配点がC<Dで、Dが得意だったおかげで救われた
ひさしぶりのARCでレートプラス
A Copy and Paste Graph
問題設定が少し複雑なので、手元で書いてどういう操作をしているかわかりやすくします
たとえばN=3, K=2のときに、A1,1=1の場合を考えます(サンプル1)
A1,1=1ならば、A1,(1+N) = A1,4 = 1のようになるので、できる操作は
「Ai,j=1ならば、Nで割ったあまりがi -> Nで割ったあまりがj に自由に移動できる」
ということがわかります
よって、「あまりiからあまりjへの最短経路」を求めることができればよく、これはもとのAに対して、0をINFに変換したうえでワ―シャルフロイドをすればよいです
(AC 10:27)
B GCD Subtraction
一瞬愚直でいいかも？と思いますが、そのとき順位表を見るとおおよそ50AC / 400Tryだったので、さすがに愚直を落とすようにしているんだなと思って考察します
大小関係はどちらでもいいので、あらかじめA≦Bとしておきます
まず、現在のgcd=Gとして、A-G, B-Gをしてもgcdが減少することがないということがわかります(常にGの倍数ではあるので)
常にGの倍数であることを利用すると、次に到達できるgcdは絞れそうかな～と思います
ただ、G=1のときなどに候補がすごく多くなってしまうので困ります
もう少し考えると、gcd(A,B) = Gということは A = Gx, B = Gyと表すことができるので、B-A = G(x-y)となり、Gの候補はB-Aの約数でいいことがわかります
ここまでくるとほとんどゴールで、今のgcdをGとすると何回か進めてgcdになる可能性があるものは、B-Aの約数&Ｇで割り切れるもののうち最も到達時間が早いものになります
到達するまでの時間は、(A%d)/gで求めることができます (d = 約数の候補)
ここで算数をさぼろうとしてmodintを使ったら謎のREを踏んでハマりました...
到達時間が分かれば、それまでの回数をまとめて遷移することで操作を高速化することができるので、実行時間に間に合わせることができます
(AC 48:45)
C Permutation Addition
制約が小さいのでなにかうまくできるかな～と思っていたが、何もわからず...
N≦50にとらわれすぎてしまった感があって、ナップサックとかを考えてしまって進捗が無だったので、特に構築だと気にしすぎないようにしないと
(AC --:--)
D LIS 2
Cがきつくて見に来たら、いかにも得意そうな見た目をしているので突撃することに
まず単純な考察として、もし[li,ri]を最後に採用するならば途中で止める必要はなく、最後まで追加するのが最善になります
ここから、dp[i] := i番目の区間でriまで使った時のLISの最大値 と定義したくなります
では、遷移を考えていきます
[1,3] [6,8]のようにかぶっていない場合ではすごく簡単で dp[j] = max(dp[i]) + r - l + 1になります
[6,8] [1,3]のようにかぶっていなくても大小が逆の場合は遷移することができません
[1,3] [2,5]のようにかぶっている場合がすこし面倒です
dp[i] := i番目の区間でriまで使った時のLISの最大値 と定義すると、[1,3]から遷移するとかぶっている[2,3]のところが余分に数えてしまいます
どうすればよいか考えると、おきもちとしては
「3まで伸ばしていたのを5まで延長したい」
より抽象的にすると
「riまで伸ばしていたのをrjまで延長したい」
ということになります
これを解決するために新たなdp配列を定義します
dp2[i] := i番目の区間でriまで使った時のLISの最大値 - ri
とします
こうすると「riまで伸ばしていたのをrjまで延長したい」というおきもちに対処できます
dp2[i] + rjとすると、
「i番目の区間でriまで使った時のLISの最大値」 + rj - ri
となるためです
よって、かぶっている場合の遷移は dp[j] = max(dp2[i]) + rjとすればよいです
これらをまとめると、あらかじめ[li,ri]をriを基準にソートした位置を特定しておき、
自分より左でかぶっていないなら dp[j] = max(dp[i]) + r-l+1
自分より左でかぶっているなら dp[j] = max(dp2[i]) + r
で更新することができます(dp[j]は上の2つのmaxをとります)
(AC 74:43)
総括
C通したかったけどレート増えてうれしい
