Chokudai SpeedRun 002
簡易的な解説を書いておきます。
200点問題は飛ばします。
F - 種類数 α
$ A>B なら swap して、 set<pair<int,int>> に突っ込む
G - GCD α
int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
H - あまり β
abs(A-B) が答えです。($ A=B なら -1 )
ちゃんと言うなら数式を書いてみると良いです。
$ X で割って $ r 余るとき、
・$ A = nX + r
・$ B = mX + r
と表すことが出来ます。$ A > B としたとき、2式を引くと、
・$ A-B = (n-m)X
となり、$ Xは$ A-Bの約数であることが分かります。
さらに $ n = m+1とすれば $ X = A-Bにすることができ、これが最大だと分かります。
I - カツサンドくん β
最強候補を1つ見つけ、それが本当に最強かどうかを判定すればよいです。
勝敗判定は、$ (A_i+B_j-1)/B_j > (A_j+B_i-1)/B_i とすれば出来ます。(倒れるまでのターン数の比較)
さて、最強候補の見つけ方ですが、2通りくらいあります。
$ A_i*B_i が最大のものを選ぶ
勝敗判定の式を移項するとそんな感じになるけど、切り捨てとかの扱いがよく分からなくてちゃんとは証明しにくい、が、多分正しい
トーナメント戦を行って優勝者を選ぶ(こちらが想定解)
最強の食べ物があるならば絶対に優勝するはず
トーナメントといっても、勝ち抜き戦みたいな感じにすれば実装が楽
J - GCD β
直接的に答えを求めるのは厳しいので、答えを決め打ちして可能かどうかを判定していきます。
GCDを $ x にできるかは、全ての $ i について $ A_i, B_i のいずれかが $ xで割り切れるかを判定すればよいです。
解の候補は $ A_1 の約数と $ B_1 の約数を見ることで網羅できます。
計算量は $ O(約数の個数 * N) です。(+約数列挙の $ O(\sqrt A_1 + \sqrt B_1) )
$ 10^9 以下の高度合成数には約数を 1344 個持つ 735,134,400 があります。 K - 種類数 β
まず、入力をグラフにします。
辺$ iが頂点$ A_iと頂点$ B_i をつないでいるグラフ
すると、各辺に向きをつけて有向辺にし、入次数が 1 以上の頂点の個数を最大化する問題になります。
連結成分ごとに見ると、min(頂点数, 辺数) が答えで、これらを足し合わせると良いです。
これが上界であることは明らかです。
下界であることは、以下のように示せます。
辺数 = 頂点数 -1 の場合
木です
根を適当に決めて、根から離れる方向に向きをつければ実現できます
https://gyazo.com/f6e412a607fc03bd4c880eb0afc832db
辺数 = 頂点数 の場合
サイクルに木がいくつかくっついたようなグラフです
サイクルに沿って向きをつけ、残った木の部分はサイクルから離れる方向に向きをつければ実現できます
https://gyazo.com/d08d3980f9880031f656ce018c4c7838
辺がもっとある場合は連結を保ったまま適当に辺を削除すればこのケースに出来ます
頂点の番号がめっちゃでかいので、適当に番号を振り直しましょう。(いわゆる座圧)
L - 長方形 β
長方形 i を長方形 j に重ねられる条件を考えてみます。
横長の上に縦長を重ねるより、回転させて横長どうしにして重ねる方が真に簡単です。
つまり、全ての長方形を$ A_i > B_iとなるように回転させておくと、
$ A_i < A_j かつ $ B_i < B_j
が条件となります。
このような2値の大小関係を満たすような最大の集合を求める問題は、ずばり LIS です。(Longest Increasing Subsequence)
ちなみに普段よく見る普通の LIS は以下のような条件式です。
$ i < j かつ $ X_i < X_j
$ A_iを$ i、$ B_iを$ X_iに対応させて LIS を解けば良いです。
気をつけないといけないのは同じ値がある点です。
$ A_iの昇順でソートし、$ A_iが等しいものは$ B_iの降順にソートすれば、楽に実装できます。
$ (A_i, -B_i)のペアでソートする、など