所見 想定された思考パスは前から順番に見ていって区間が閉じる直前にその区間が解決されていなければ処理すればいいよね->これをNlogNくらいでやりたい->開いてる区間を覚えておくのだとNMでつらそう->ソートしておけば貪欲に右端の橋を破壊すればよい くら…

Submission #2868393 - AtCoder Regular Contest 091 所見 さんすう 問題概要 aをbで割った余りがK以上になるN以下の整数の組(a,b)の個数を求めよ。 取った方針 bを固定すると、aをbで割った余りはaが1の場合から順番に1,2,...b-1,0,1,2...とループする。 1,…

所見 グラフに見えるかどうかゲー 問題がグラフに見える程度の能力は類題を解いた直後2週間程度は急上昇する(だがこれは罠でFalse Positiveも増える)ことが知られているので精進って感じだ 問題概要 x軸上にN人の人が居る。これらの人間の位置に関する情報が…

所見 中 学 入 試 (1) aab ccb (2) aabd ccbd (3) aabde ccbde (4) RvvttdWIyyPPQFFZZssffEEkka RLLwwdWIxxNNQUUXXVVMMooBBa を塗り分ける場合の数を求めなさい とかだとむちゃむちゃ中学入試っぽいと思います 問題概要 2*Nマスの範囲に1枚の面積が1マスのタ…

問題概要 1番が黒、N番が白く塗られた木に対し、自分の色に隣接しているノードに先手は黒、後手は白を塗っていくゲームをする、先に色が塗れなくなったほうが負けの時、両者が最適な動きをした場合勝つのはどちらかを求めよ。 取った方針 木はあるノードから…

所見 解説の方針頭良すぎワロタ 問題概要 N枚のカードに整数が書かれている。その中から任意の3枚を取り、最大の数と最小の数を食べ、カードの集合から同じ数がなくなることを目指す。最大で何枚残せるかを求めよ。 取った方針 同じ数が3枚以上あるとき、そ…

所見 グラフ上で連結かどうか->unionfind。そこから先で迷ったが、unionfindがどういうアルゴリズムかを考えると、同じ親を持つノードの数を数えればいいことがわかる。 高速な(経路圧縮した)unionfindを使えばO(K+L+NlogN)。 問題概要 N個の街が、K本の道路…

問題概要 N個の街におけるりんごの価格が与えられる。左から順に街を訪問し、りんごを売買し最大の利益を上げる人がいる。コストcでりんごの売買価格をcだけ変化させることができるとき、最大の利益を1以上下げるのに必要なコストを求めよ。 取った方針 最大…