ARC163 参加記
3完 97:23 506位
テスト勉強で出るつもりじゃなかったんですが、問題見てみたらC解きたかった＆思ったよりテスト勉強の進捗がよかったので15分くらい遅れて参加
C->A->Bで通したのでAC時間が変なことになってます
A Divide String
ARC-Aによくありがち
もし2個より多く分割できたときt1 < t2 < t3 ... となっていますが、そのようなときにt1 < (t2 + t3 + ... )が必ず成り立ちます
なぜなら t2に何を足しても辞書順でt2より小さくなることはないからです
よって、条件を満たすなら2つに分割する解が存在するので、切れ目をどこに入れるか全探索すればよいです
(AC 90:55)
B Favorite Game
問題名の由来、なんだろ
ある区間があって、その中に含まれるものの個数を増やしたいという問題です
どういう操作ができるか考えると
・区間を広げる(縮める意味はない)
・外にあるものを区間内に持ってくる
の2つになります
A = (1,3,5,5)のようなものを考えるとわかりやすいかなと思うんですが、区間の外にあるものを2個以上持ってくるなら、そもそも区間を広げてあげたほうがよいです
というかそもそも、外にあるものを1つ区間内に持ってくる操作回数と同じ操作回数で区間を広げることができるので、「区間を広げて損することはない」です
よって、A1, A2のみ動かせばいいということになります
ここまでくれば、A1,A2を除いたものをCとすると、Cをソートした配列で長さMの区間をすべて調べればよいです
区間を固定すると操作回数は max(0, A1 - C[i]) + max(0, C[i+M-1] - A2)で表されるので、この最大値を計算すればOKです
(AC 97:23)
C Harmonic Mean
判定込みの構築で、ちょっと苦手なタイプではありますが頑張ります
まず自明なところを処理すると、N=1 は A=(1)で満たします
N=2は無理です(1/3以下を2つだと1にたどりつかない & 1/2を使うともう一つも1/2)
N=3,5があるので少なくとも奇数はつくれるんだろうなと思います
いきなり大きなNのときの解をつくるのは難しそうなので、N=3,5の解をもとにして作ることを考えます
N=3を参考にすると、1/2 = 1/3 + 1/6になるのでこれを使ってみます
たとえば、1/3 = 1/6 + 1/12, 1/6 = 1/12 + 1/24のように分解していくと、1つの分解でNを2増やすことができます
ただ実際にこれでプログラムを動かしてみると、重複がない場合100個にも到底届かないようなものしか構築できません
よくよく考えると、これで表されるのは 1/2^a 3^bの形で表されるものですが、この個数を愚直に全探索で計算してみると(たぶん)276個になるので、制約的にどんなに天才でも達成できないことがわかってしまいます
解決策としてはもう少し複雑な形(1 / 2^a 3^b 5^c 7^d など？)を考えるか、ほかの手段を考えるかになりますが、前者でうまくいくビジョンがあまり見えなかった(tatyamさん解説に解法あり)ので他の手段を考えます
さっきの手法だと答えに使いたい数の分母が指数的に増えていって困ったので、あまり増えないようにしたいなと思ってみると、そういえば1/6 = 1/7 + 1/42にできたなとなります(え？)
こう考えると、1/k = 1/(k+1) + 1/k(k+1)に変換できるので、これを使えないかなと思います
直感的には小さいものを分解すると、すでにつくっていたものとかぶりやすいかな？と思うので、一番大きな値を分解していって、かぶらない＆10^9を超えないならば貪欲に分解することにします
実際にこれでプログラムを回すとN=500でも問題なく、1回の操作でNが1だけ増えるのでN=3~500で構築できることがわかります
(AC 88:20)
総括
Cこんなに通されるのか...みんな構築に強すぎる
ABC308 参加記
6完 33:42 388位
ライブラリをなにも理解していないことをさらしてしまった
A New Scheme
ABCの配点として正しいかどうかってことですね
言われたとおりにif文を書いて判定
(AC 2:35)
B Default Price
いつものBですね
それぞれの色について何円なのか保存しておけば、ループで調べれば解けます
map使った方が直感的なのでそうしたけど
(AC 5:49)
C Standings
これむずいと思う、茶色の僕は知らなかった
C++だとsort関数に比較する関数を渡してあげることができるので、これを定義します
Ai / (Ai + Bi) < Aj / (Aj + Bj)ですが、誤差が怖いので分母を払ってあげて
Ai * (Aj + Bj) < Aj * (Ai + Bi)とすればよいです
これに加えて、indexの比較も同じ関数内に入れておけばOKです
(解説のようなstable_sortではなく、indexの比較をいれたもの)
Submission #43100882 - AtCoder Beginner Contest 308
(AC 11:35)
D Snuke Maze
いつものD
s -> n -> u -> k -> e -> s ... と動いていくことになるので、それぞれ隣り合うものをみて辺を張れるか判定してあげて、張れるなら張ります
そうしてグラフを作ってあげれば、あとは(1,1)からBFSやDFSをして(H,W)に到達できるかみるとよいです
※陽にグラフをつくらなくても、「マスの上を動かしていって動ける＆まだ行ってない場所に行く」を繰り返せばよいです
(AC 19:18)
E MEX
典型：「3つのものは真ん中を固定」
何度も出題されていますが、こういうタイプの数え上げ・和の計算は真ん中を決めるとうまくいくことが多いです
類題
今回も真ん中のEの位置を決めます
そうすると、「自分より左にあるM」と「自分より右にあるX」しか考えなくてよくなります
これは左右からの累積和を使って簡単に個数をまとめられるのでうれしいです
この問題ではこれに＋αがあります
mexは0,1,2のうちどれがあって、どれがないか？がわかればよいので、「自分より左にあるM」のうち(0の個数、1の個数、2の個数)を求めて、Xについても同様に求めればよいです
あとは各Eについて、Mでどの数字を採用するか・Xでどの数字を採用するかを総当たりして個数を加算してあげれば解けます
(AC 27:43)
F Vouchers
貪欲っぽい問題は正しい貪欲を思いつくのが難しいものも多いですが、「制限の厳しいものから考える」というアプローチが有効なことがそれなりにあります
(この問題に限らず)おきもちとして、いきなりめちゃくちゃ選択肢があるものを考えるのは大変です
なので選択肢が少ないものを考えて、「この厳しい条件ではこうするのがベスト」という方法を見つけてみます
それが全体の問題を解くときに使えないか？と考えると解法が見えることがあります
あらためて今回の問題を考えると、高い商品にはたくさんクーポンを使えるが、安い商品には使えるクーポンが少ないことが分かります
また、安い商品に使えるクーポンは高い商品にも使えるので、使えるクーポンの集合はどんどん増えていくことになります(=あとで使えなくなるから最善ではないけど早めに使わないといけない、ということは起こりません)
よって、安い順にみていって「その時に使えるクーポンのうち最も割引額が大きいものを使う」として問題ありません
これはpriority_queueを使うと実装できます
類題
(AC 33:42)
G Minimum Xor Pair Query
想定解法が天才だった
これは思いつかなかったのでBinary Trie解法を書きます
まず、xorの典型考察として「桁ごとに考える」というものがあります
xorをできるだけ減らそうとすると、k桁目までいっしょでその部分が0になるとうれしいので、「k桁目まで同じものがある」かどうかを調べたくなります
これはBinary Trieでやっていることと同じなので、Binary Trieを使って解けそうだと思います
もう少し詳しく考えていきます
k桁目まで同じものが2つあるとすると、そのxorは答えの候補になります
Binary Trieでは各ノードに「あてはまる数字の個数」「あてはまる数字どれか1つ」を持つことにします
addクエリでは、そのノードの「あてはまる数字どれか1つ」がないならば、addする値で更新します
また、「該当する数字の個数」が2になったときに、2つの子ノードがあればそれぞれの「あてはまる数字どれか1つ」のxorをmultisetに加えます
もしくは、葉ノードの「該当する数字の個数」が2(=等しい値が存在する)のときに0をmultisetに加えます
3,4...など2より大きいときにもっと小さい値ができる可能性がありますが、それはもっと深いノードで2になるところがある or 葉ノードに2つ以上の値があり0になる、のどちらかなので考えなくてよいです
addクエリは比較的簡単ですが、eraseクエリはちょっと面倒かもしれません
大枠はaddクエリと同じですが、「あてはまる数字どれか1つ」を管理する必要があります
「あてはまる数字どれか1つ」が今消そうとしている数かもしれません
その場合は、子ノードの「あてはまる数字どれか1つ」を適当に選んで更新してあげればよいです
ただし、更新した場合はもともとmultisetにあったxorとは異なる可能性があるので、あらかじめそのノードで加えていたxorの値を取り除いてから、新しい値を加えることになります
とりあえず書いたんですが、文章だとかなり煩雑なので実装も置いておきます
(実装のadhocと書かれている部分がBinary Trieに書き加えた部分です)
(AC --:--)
総括
Binary Trieやっと実装がわかってきた
ARC109-E 1D Reversi Builder プチ解説
ARC109-E 1D Reversi Builder の解法が少し既存の解説と違ったので紹介します
備忘録的な感じ
参考リンク
問題概要・考察の初歩は上記のリンクをご覧ください
盤面を固定した結果はけんちょんさんのブログの「正攻法」欄に記載されています
以下の説明は、この「正攻法」の考察がなされていることを前提とします
まず、多項式時間で「正攻法」の数え上げができるか考えてみます
以下の考察は左端が黒・右端が白であることを仮定します
スタートの位置を固定します
ゲーム終了時の黒い石の個数は、左から何個黒が続くか、右から何個白が続くかの2つの情報でわかります
これらをそれぞれ ,
とします(けんちょんさんの記事と同様)
よって、,
,
の3つを定めればゲーム終了時の黒い石の個数がわかるので、
で数え上げることができます
ただし、今回の問題ではなので、
程度まで高速化する必要があります
ここでを
~
まで動かしながら計算していくことを考えます
まず、 =
のときは ゲーム終了時の黒い石の個数は
になります
を決め打って、そのときの値を計算しておきましょう
一番左が黒、右から個が白 = 右から
個目は黒になるので、自由に決められる色は
(
,
)個あり、この値を
とすると、(
) ×
を足し合わせればよいです
それでは、を1つずつ進めていきましょう
を1つずつ進めていくと、
では終了時に
個黒い石があったのに、
では終了時に
個しか黒い石がない盤面が出てきます
その一方で、左端を黒に固定しているので、よりも
で終了時の黒い石が多くなることはありません
そこで、では終了時に
個黒い石があったのに、
では終了時に
個しか黒い石がない盤面をまとめて数えることを考えます
そのような変化が起こるのは以下の2パターンになります
・
・
ほとんど考え方は同じなので、 の場合のみ説明します
とおきます (こちらの場合は条件より
は存在できないことに注意)
この条件を満たす盤面の個数を考えます
左から個は黒、左から
番目は白、右から
個は白、右から
番目は黒になることから、自由に決められるのは
個になります
※からの距離が
以上の場所はすでにきまっていると考えるのがわかりやすいかもしれません
よって、を固定した時、
から
になるタイミングで、(
) ×
だけ終了時の黒い石の個数が減少します
あるについて、とることのできる
の範囲は単一の区間になるので、あらかじめ各
のときの値を計算し、累積和を求めておくことで
から
に変わるときの差分を
(
)で計算できるので、全体を
(
)で求めることができます
実装例
ABC302 参加記
7完64:09 149位
Eで多少詰まったけどFGをまあまあの速度で通せてセーフ
A Attack
切り上げは (A + B - 1) / Bでできるやつ
Aでforが出るならlong long もでていいよね
(AC 2:54)
B Find snuke
250点はなんだと思ってみると重実装がおいてある
とはいっても、楽することはできて
dx = {-1, 0 , 1}
dy = {-1, 0, 1}
の全組み合わせを、すべてのマスを始点として試せばよいです
8方向書くときには↑のような定義おすすめです(dx = dy = 0は適切に省く)
(AC 8:12)
C Almost Equal
えー、地味にむずくない？と思ったら制約に答えが書いてありました
N ≦ 8なので順列全探索ができます
判定は1文字ずつみて素直にやるだけ
(AC 11:46)
D Impartial Gift
「2つ選びます」「3つ選びます」みたいな選ぶ個数が少ないタイプの問題は、とりあえず1つ選んでしまって、そこから最適なものを考えるとうまくいくことが多いです
今回も1つ決めてしまいましょう
Aiを1つ決めると、最適なのはBi ≦ Ai + D となるもののうち最大のBiです
(もしそのBiがAi-Dより小さいなら選べないことに注意)
これは二分探索で簡単に求めることができます
Biを1つ決めるものも試して最大値をとればよいです
(AC 19:33)
E Isolation
辺をくっつけて連結成分数 -> Union Findか？と思ったけどただの過学習でした
辺を頻繁につけたり外すのはUnionFindだとあまり得意ではないので、少し違うかなと思って普通に考察します
※1回だけ外すとかだと逆順にみるのが有効なことが多い？
2番目のクエリの辺を削除するというのが大変かな？と思うのですが、もともと辺がないし追加されるのもクエリにつき1辺なので、愚直に削除しても間に合いそうです
では、2番目のクエリの処理の仕方を詰めていきます
普通に隣接リスト(vector<vector<int>> G(N) のような形)で持つことを考えます
頂点iにつながっているものをすべて削除するクエリが与えられるとき、G[i]はすべて削除すればよいです
しかし、iとつながっている先の頂点でもiを削除しないといけません
これを普通にやるとvectorからiを探索して削除しないといけないので、最悪O(N)かかってしまいます
ここでsetを使うと「iを探索して削除」をO(logN)で行えるので、高速になります
よって、つながっている辺をsetで管理することでクエリの各処理がO(logN)で行えるので全体でO(QlogN)になり、十分間に合います
(AC 30:35)
F Merge Set
何で思いついたか説明しづらい...過去問演習の効果としか
同じ数字を含むものはつながっていてほしいという"おきもち"を抱くので、そうできるように考えます
左側に1~Nの番号、右側に1~Mの数字をあてはめた二部グラフを考えます
i番目の集合にjが含まれるなら、左側のi と 右側のj を結びます
(この時点では完全な解法は思いついていないですが、このようなグラフをつくって考察する価値があるだろうという読みでつくっています)
このグラフを使って考察すると、(当たり前ですが)右側の1から1回操作すると左側の「1を含む集合」にたどり着くことができます
同様にグラフを使って考察すると、「iとjを含むための回数」 = 「右側のiから右側のjまでの最短路 / 2 - 1」になることがわかります
(ここはサンプルをもとにいろいろ手を動かしてみるとわかりやすいと思います)
よって、このグラフで最短経路問題を解けばいいのでBFS, Dijkstraなどを使えばよいです
(AC 38:47)
G Sort from 1 to 4
めちゃめちゃ解かれていたのであせった...
まず広義単調増加となる列は一意に定まるので、それは求めておきます
そもそも、もとの列と広義単調増加の列で値が等しいものは動かすのが無駄なのでそのままにしておきます
そうでないものとして、以下の3パターンが考えられます
(i) 1 <-> 2 のように2点swapで解決する(=1回操作)
(ii) 1 -> 2 -> 3 -> 1のように3点をぐるっと回すと解決する(=2回操作)
(iii) 1 -> 2 -> 3 -> 4 -> 1のように4点をぐるっと回すと解決する(=3回操作)
まず、(i)はして損することがなさそうなので優先することにします
問題は(ii)と(iii)ですが、可能であれば(ii)が優先できたらいいですが、(ii)を優先した結果(iii)が増えるということがあると困ります
順位表をみるとよくわからない貪欲が落ちそうな割には、ペナが少なめです(嘘貪欲で落ちるならAC / Submit = 1 : 2~3になりそうですが、 160/200くらいでした)
こう考えると、適当な貪欲で通りそうなので(ii)を優先することにします
(ii)の中の優先順位もよくわからないんですが、普通に貪欲にしてみます
具体的な実装としては、3重ループで(1,2,3),(1,4,2)など組を列挙してそれがあれば処理するようにします
「組に該当するものがあるかどうか？」は
count[i][j] := 広義単調増加列だとiの位置に、jが存在する個数
をあらかじめ計算しておけばよいです
(i) -> (ii) -> (iii)の順に貪欲に処理していって提出すると通ります(証明AC)
(AC 64:09)
総括
Eの過学習よくないね
ABC301 参加記
5完45:27 125位
Cで詰まった＆Fが3分間に合わなかったのにこの順位なのびっくり
落ちたからやめた人多そう
A Overall Winner
素直にやります
A,Tの数を数えて片方が大きいならそれを出力、等しいなら後ろにないほうでOK
(AC 2:17)
B Fill the Gaps
これも素直にやる
とりあえず最初の数だけ入れておいて、あとは間の数を定義通りループで入れていく
(AC 5:07)
C AtCoder Cards
貪欲の自信がなかった...
とりあえず、"@atcoder" に含まれないもので数が異なるものがあるとどうしようもないのでNoです
あとはこれらをうまくそろえていけばよくて、足りてないものを@で補填していくのが最善になります
が、なぜか本番で最善かわからなかったのでフローで殴りました
スタート、ゴール、S,Tのa~z,@にあたるものを頂点とします
スタート -> Sの各文字：容量=Sにある文字の個数
Sの各文字->Tの各文字：容量=INF
"atcoder"でない小文字は同じ文字にだけ
"atcoder"にある小文字は同じ文字+@に
@は@,atcoderのすべてに
Tの各文字->ゴール：容量=Tにある文字の個数
として流量がNであればよいです
(AC 26:51)
D Bitmask
こっちのほうが簡単では？
まず1のところはどうしようもないので、加算しておきます
あとは?のところを変えていくのですが、1にできるなら変えるのが最善です
難易度C>>>Dと思ったけどそんなことなかった
(AC 29:47)
E Pac-Takahashi
やることわかるけど実装重め
まず問題文に「18個以下」と強調して書いてある＆最短距離的なので、bitDP使うんだろうな～と思います
お菓子を取る順番を決めてしまえば、それぞれの最短距離を求めればいいだけですがこれを愚直にやるとO(K!) [K=お菓子の個数]になります
こういう順列全探索の高速化はbitDPが相性がいいことが知られています
つまり、順番はそこまで大事でなくて「どこを通ったか/通っていないか」が重要なので、その情報をbitで持つことで計算量をO(2^K)に改善できます
それぞれの最短距離を求めればいいだけ、と書いたのですがここをちゃんと考えておきます
もう少しサイズが小さければワーシャルフロイドを使って全ペアの最短距離をO((HW)^3)で計算できますが、今回の制約では厳しいです
重要なのはお菓子のあるマス(+スタート・ゴール)への距離なので、このK+2マスについてわかればよいです
ということで、それぞれのマスを始点として最短経路を計算します(BFS, Dijkstraなど)
それぞれの最短距離がわかれば、あとはbitDP(巡回セールスマン問題と同じ)で解くことができます
(AC 45:27)
F Anti-DDoS
いかにも設定から作られてそうですが、適度な難易度でおもしろかった
「(連続でない)部分列としてTが存在するSの個数」の典型として、
dp[i][j] := Sのi文字目まで見てTのj文字目まで存在する通り数
と定義して計算するというものがあります
例：?を含むSを書き換えて、"atcoder"が含まれるのは何通りか？
今回も考え方としては同じです
dp[i][j] := Sのi文字目まで見て"DDoS"のj文字目まで存在する通り数、とします
3,4文字目のo,Sは小文字・大文字という条件しかないので簡単です
ただし、1,2文字目のDDは「1文字目と2文字目が等しい」という条件がついているので少し難しいです
DDの部分を解決することを考えましょう
愚直に考えるとアルファベットのi文字目があるか？という情報をもってbitDPができそうですが、これは2^26必要で計算量が厳しそうです
そのため具体的に「どの文字があるか？」と持つことは諦めて「文字が何種類あるか？」を持つことを考えます
dp[i][j][k] := Sのi文字目まで見て"DDoS"のj文字目まで存在して、今までに出現した大文字の種類数がkである通り数
と定義して計算していきます
もしS[i]=?であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます
かぶるときは、どの文字とかぶるかがk通りあるので、
dp[i][2][k] += dp[i][1][k] * k と遷移します
かぶらないときは、同様に考えて
dp[i][1][k+1] += dp[i][1][k] * (26 - k) と遷移します
もしS[i]=大文字であれば、今まで出現した文字とかぶるorかぶらないの2パターンを考えます
少しここが厄介なので状況を整理します
i-1文字目までで、すでに決まっている(=?でない)大文字がA種類
i-1文字目までで、?から大文字に変えた箇所がB個(これはどの大文字ともかぶらない)
とします
S[i]が今までに登場した大文字とかぶる確率を考えます
もし、すでに決まっているA種類のものと同じであれば確率は1です
そうでなければ、B / (26 - A)になります
この確率をかけてdpの遷移をしてあげればよいです
また、かぶらない確率は上の結果から容易に計算できます
最終的にはdp[N][0][k] + dp[N][1][k] + dp[N][2][k] + dp[N][3][k]を出力すればACとなります
(AC 108:37)
総括
Fちゃんと通したかった
ABC297 参加記
7完60:17 + 2ペナ 105位
FGをサクッと片付けたのがえらい、Eでハマったのはダメ...
A Double Click
forやるだけ、言われてみればダブルクリックの時間を快適にするの絶妙な調整だよね
(AC 1:50)
C chess960
元ネタを知らなかったので、1行でチェスするの何が面白いんだと思った
解くのは条件を丁寧に実装するだけ
2重ループ+3重ループで解きました
(AC 5:20)
C PC on the Table
PCTやりたいだけ
左から貪欲に詰めていけば問題ないので、一つ一つ変えていきましょう
(AC 7:33)
D Count Subtractions
直前のARC-Bっぽさを感じさせるけど、解法はちょっと違う
大小関係が入れ替わるまでは操作をまとめて繰り返してあげればよいです
やっていることはユークリッドの互除法とだいたい同じなはず(?)で、高速に終わります
(AC 11:35)
E Kth Takoyaki Set
Twitterで最近流れていた Ai + AjのうちK番目みたいな問題に思いをはせながら解いた
できる可能性がある候補としては現在の値をXとして、X+Ai(1≦i≦N)になるので、これをいい感じに調べていきます
具体的には、あまり大きいと調べる必要がないのでpriority_queueにつっこみながら小さい順に調べていくことにします
今までに出現した値をset, priority_queueで管理しておきます
もし今まで出現した値がK個を超えたら、K番目以上のものは調べる必要はありません
K番目の値以上になるものを加えないようにすると、計算量が抑えられて間に合います
(AC 24:36)
F Minumum Bounding Box 2
期待値を直接計算するのは難しそうなので、総和を求めることにします
解説と方針は違いますが、縦h、横wを固定して「最小長方形が縦h,横wになる通り数」を数え上げることにします
すごくざっくり考えるとh×wマスからK個のマスを選ぶので、二項係数を用いてhwCKになりそうですが、たとえば上一行にひとつもない場合など当てはまらないこともあります
ダメな条件を考えると
・上一行にない
・下一行にない
・左一列にない
・右一列にない
のうちどれか一つでもあるとダメであることが分かります
こうやって整理すると「A,B,C,Dのうち一つでも満たす通り数」を計算する問題になっているので、これは包除原理で解くことができます
bit演算を用いて縦・横の縮め方を管理すれば比較的楽に書けます
実装例
Submission #40507604 - AtCoder Beginner Contest 297
(AC 46:49)
G Constrained Nim 2
各ゲームが独立しているので、それぞれのGrundy数を求めてXORをとるのがよさそうだな～と思います
Grundy数を求めたいので、とりあえず手元で実験してみます
L=3, R=5とすると、Grundy数が0,0,0,1,1,1,2,2,0,0,0,1,1,1,2,2...となって
実験したときの遷移する先も考えると、0がL個、1がL個、2がL個 ...という風になっていくはずで、長さは(L+R)個でループしていることが分かります
変な例外があったら悲しいんですが、とりあえずあってそうなのでGrundy数をAi%(L+R)/Lとして実装します
サンプルが弱くて心配になりますが、投げるとAC
(AC 60:17)
総括
F黄色かと思ったらギリ青色だった
ARC159 参加記
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通したかったけどレート増えてうれしい
