94:25 7完
まさかの橙diffACで黄色復帰、ABCジャンプしたね
A Growth Record
問題文がちょっとややこしいかも、冷静になるとif文書くだけ
成長の比率が一定の人間、ちょっとこわい
(AC 3:34)
B Counterclockwise Rotation
前回難読ということで荒れてたけど、問題文「は」簡潔
こういう回転の仕方いっつも忘れるけど、調べると
x = xcosθ - ysinθ
y = xsinθ + ycosθ
でいいらしいので、そのまま書いて実装
θをradianに変換するのも調べました
(AC 9:42)
C XX to XXX
ランレングス圧縮(Run Length Encoding)久しぶりですね
RLEしたあとに、形が同じ＆ちゃんと増やせるかを確認していきます
長さ1のものは増やせないことに注意すればいい、サンプルにあって優しいね
(AC 14:30)
D Circumferences
また幾何～ってなった
冷静になるとそんなに複雑ではなくて、「円iから円jに他の円を通らずに移動できるか」がわかればよいです
これは、「円iと円jが交点を持つ」ことと同義です
「円 交わる条件」とかで検索すると公式が見つかるのでそれを使ってあげます
ここで注意なんですが、小数を使うと誤差で死ぬ可能性があります
「接する」みたいなギリギリの条件を扱う時は小数は怖いのでできるだけ避けましょう
(i,j)のペアについて到達可能かわかれば、あとは(sx,sy)(gx,gy)がどの円にあたるかわかればよく、これは円の方程式に当てはめて判定できます
複数の円にまたがることもありますが、結局そういう円には移動できるので適当に選んで問題ないです
(AC 22:21)
E LCM on Whiteboard
かの有名なGCD on Blackboardを彷彿とさせるタイトルですね
lcmはgcdと違って、すごく大きな値になるので[素数、個数]で情報を持つことが多いです(類題 : ABC152-E Flatten)
今回も同様に[素数、個数]で管理するようにしましょう
そもそも、1つも1にしなかった場合のことを考えると、すべての素数についてeはmaxをとることになります
その状態からどの素数の個数が変化したか考えます
Aiを1にして、lcmにおけるある素数pの個数が変化する条件は
Aiでのpの個数が最大であり、かつ他のAj(i≠j)ではそれよりも小さい場合に限定されます
なので、どの素数pが変化するか？をvectorで管理して、これをsetに入れるとsetのsizeが答えになります
setにvectorを入れるのたまに使うけど、うまく使うと便利です
(AC 33:09)
F Select Edges
最初に「大きいものから貪欲でしょ、なにこれ？」と思いますが、そもそもサンプル1で落ちます
(追記：と思ってましたが、2 4 10がそもそも選べないので貪欲でもサンプル通ったらしいです、たまたま勘違いして逆に救われました...)
あまりいい方法が思いつかないので、いったん方針のたったGを解きに行きました
帰ってくると、「なんで木なんだろう？」という風に思います
一般のグラフで解けるならそうすればよいので、木であることを使えないか考えます
そうすると木DPがうまくいきそうだと思えます
木DPの形で考えると、子に必要な情報は「1辺付け足せるか？」になります(根つき木だと思うと、親は高々1個なので)
よって、DPを
dp[i][j] = iの部分木で頂点iにさらに辺を付け足せない(j=0) / 付け足せる(j=1)ときの最大値
と定義します
あとはこれを更新していきます
まず、子とつなげないことにしても困らないのであらかじめつなげない場合の値を計算します
その後、つなげるなら得が大きいところからつなぎたいです
なので、つなげたときに増える値を計算してソートし、大きい順に貪欲に付け加えていくことで最適解を計算できます
ちょっとバグらせたけど、なんとか通せた
(AC 94:25)
G Grid Card Game
ABC-GでN < 100、だいたいフロー(ほんと？)
↑は半分冗談ですが、半分本気なのでその気持ちで見ると、今回もフローです
燃やす埋める問題の形をしているので、うまく落とし込むことを目的にします
燃やす埋めるで課題になりがちなのが、「最大化」をどうするかということです
一般的な燃やす埋めるでは「コストの最小化」をするので、どうにかして最小化問題に落とし込む必要があります
行iをあらかじめとったことにして、とらなければその値を取り逃すという「コスト」がかかることにしよう！という発想が出てきますが、「コスト」がそもそも負だったときに適用できず困ります(一般的に負の流量を扱えないので)
ただ、よくよく考えると行iを選んでスコアが増えないのであれば、そもそも選ぶ必要がありません
つまり、「行i もしくは 列j の和が負ならば、それを選ぶ選択肢はあらかじめないことにしてよい」ということがわかります
こうすることで、「コスト」をすべて正にすることができます
辺の貼り方はほぼ公式解説と同じですが、必ず選ぶ必要がないところには辺を貼っていません
あとはACLのmaxflowなどを用いて、最小カットを求めると解けます
橙もあるとは思ってなかった、びっくり
(AC 58:49)
総括
ABC得意芸人になってきたかも
