考えたこと 2倍の回数はlogオーダーになるので大した回数にならない 3回2倍するとき a +x[0] *2 +x[1] *2 +x[2] *2 + x[3] 8a + 8x[0] + 4x[1] + 2x[2] + x[3] = newA になるようなxを見つける 最小回数なら2進法みたいな感じで貪欲にやれば求まる 適当な実…

考えたこと 最大の最小化なのでにぶたんをする Rを決め打つとO(n)で可能かどうかの判定ができそう 出すと通る THE典型みたいなにぶたん #include <bits/stdc++.h> using namespace std; using ll = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #d</int,></vi></int></bits/stdc++.h>…

考えたこと 長さ3の経路ができないような木を考えるとウニしかない 葉が101個のウニをつくる ウニの葉に頂点をつなげると長さ3の経路が+100される これで100,200,300,400,…,10000までつくれる ウニの中心から長さ3の足を生やすと長さ3の経路が+1される これ…

考えたこと 子の数の和が頂点数-1なら木構造がつくれそう つくれるなら適当な木を構成して直径を求めればよさそう 木の構成で悩む トポソみたいに葉としてしか使えない頂点を子にした頂点をつくるを繰り返して構成したらいい気持ちになる 木が構成できたら直…

考えたこと とりあえずソートしない理由はなさそう 明らかに二部マッチング 完全二部マッチングの個数の数え上げ NPなので無理です ソートしてあるとwarriors[i]とマッチングできるhorse[j]についてjの区間は[0,x]になって単調増加する warriors[i]がマッチ…

考えたこと 操作回数が多いのでうまくまとめる系の問題 時刻hで従業員nがtaskを持っているとき交換が起きるのはn-1,nの約数でh+1以上の最小の時刻 約数の列挙はO(sqrt(n))でO(n)個分やってたら当然TLE 交換回数がO(logn)とかO(sqrt(n))になってくれるとうれ…

考えたこと _の配置の組み合わせ数を無視してとりあえず;の方だけ数えてみようとする ;でペアを組めるのは_を挟んでるやつだけ i番目を始点, j番目を終点とできるなら辺i→jを張るみたいなグラフを考える DAGのマッチングに落ちたと思ったけどマッチングが何…

考えたこと 括弧列で定番の+1/-1の累積和とか考えるけどよくわからないので実験する 括弧列の長さがnのとき、LCSがn-1の括弧列が絶対につくれる気がする 1文字をずらしていったような括弧列はLCSがn-1になるはず 括弧を飛び越すようなずらし方をすれば異なる…

考えたこと 全てのマスを一回ずつ通って始点に戻るような経路(ハミルトン閉路)があればその経路をぐるぐる回ればいいのでどんなKでも必ずできる 実験してるとRかCの片方でも偶数であればハミルトン閉路が絶対にあることがわかる 奇数 * 奇数のときにハミルト…

考えたこと bitDPをしてくださいみたいな雰囲気をしている 制約的に考えると dp[S] = (集合Sのセルを実行しているときの最小コスト) みたいな持ち方になりそう n個全部を実行したことについての判定をどうするかちょっと悩んだけど命令s[i]の和集合が全て実…

考えたこと この間勉強した全方位木DPを思い出す 頂点数n<=50なのでただの木DPでO(n^2)でいい 頂点iの部分木の頂点を全部訪れるのにかかる手数は一番深いところを後回しにすればいいので簡単に求まる 頂点iの部分木の頂点を全部訪れるわけではないので dp[i]…

考えたこと 操作回数KでO(K)はできないならどうせ周期性という気持ちになる 周期性で O(min(A+B, K)) くらいにはなりそうという気持ちになるが足りない 適当に実験したら実は周期が短いのがわかるのでは？と思い実験する 3*10^6回実行しても周期性がないのが…

考えたこと とりあえずinitial→targetじゃなくて逆に戻していく動作を考える 先頭にBなら取り除いて残りを反転、末尾にAなら取り除くの2パターンがある 愚直にやると2Nくらいかかりそうだけど冷静に考えるとそこまでパターン数は多くない気がしてくる 2通り…

問題ページ B - Holes 考えたこと Rがめっちゃでかいのは別に気にしなくてよさそう 穴pに落ちる範囲の面積を求めて面積比を確率として求めるみたいなのを考える 穴pと他の穴qの垂直二等分線を引き、穴pが属する領域の凸多角形を求めるみたいなのをやりたくな…

問題ページ Shopping | Aizu Online Judge 概要 n個の店が並んだ商店街がありi番目の店は位置iにある。ある店dを訪れてからある店cを訪れなければならないというm個の制約の元で位置0から位置n+1まで歩くときの最小距離を求めろ。 n <= 10000, m <= 500 考え…

dp[i][j] = min(dp[i][k] + cost[k]) みたいなdpの遷移がうまくやると高速にできるみたいなテクのまとめ ConvexHullTrick 以下の二つのクエリに答えられるというテク 直線y=ax+bを追加する x=iのときの最小(最大)のyを求める 追加する直線の傾きが単調、最小…

問題ページ Problem - F - Codeforces 解法 dp[i][j] = (i個目の部分列でj番目までをカバーしたときの最小コスト) としたDPを考える。DPの漸化式は dp[i][j] = min_{k

問題ページ Problem - E - Codeforces 解法 dp[i][j] = (i番目のゴンドラでj人目までを乗せたときの最小値) としたDPを考える。漸化式はdp[i][j] = min_{k

問題ページ J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder 概要 魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り…

問題ページ Problem - C - Codeforces 解法 n本目の木を切ったあとはチャージし放題なのでコスト0で全ての木を切れる。したがってn本目の木を切るのに必要なコストを求めればよい。また、j本目の木を切った後にj本目より前の木を切ったとしてもチャージに使…

問題ページ Problem - B - Codeforces 解法 猫が止まる時間や丘までの距離など色々あって扱いにくいのでまずは処理しやすいように言い換える。丘に到達してから猫が待つ時間は猫と飼育員が丘0を出発する時間の差に等しい。したがって各猫が丘0を出発する時間…

概要 1~nまでの数からx個をランダムに選ぶ。このとき選んだx個のうち最小のものをSとし2Sをその集合のスコアとする。スコアの期待値を求めろ。 考えたこと 数mが最小の数Sになるのはどんなときか x個にmが含まれていてm未満の数が含まれていない したがってm…

概要 区間[x1,y1]、[x2,y2]が与えられる。この区間どちらとも共通部分を持つような最小の区間の長さを求めろ。 考えたこと 間の区間を取るかそもそも区間が被っているかのどっちか x1 < x2 と x2 > x1 で場合分けすればいいね x1の方が右ならx1-y2かすでに区…

概要 各頂点iに重みw[i]が設定されているn頂点の木が与えられる。 ある頂点に1つ石を置くか、石を一つ取り除く操作を繰り返すゲームをする。ある頂点に石を置くとき、その頂点の子全てに石が置かれている必要がある。 ゲーム中に取りうる、石が置かれている…

問題ページ C - 倍数クエリ 平方分割はじめてだったので練習として書いた 考えたこと mod m で考えてよさそう 平方分割なことは知ってたので考察をすると各バケツが数字が現れる頻度をもっておくとよさそう まとめてバケツに加算する配列lazを用意しておけば…

問題ページ C - スペースエクスプローラー高橋君 CHTで解いてたけどmonotone minimaで解けるらしいので解くことにした 考えたこと f(i,j) = (i番のキャノンで区画jを破壊するエネルギー) 最小値がどんどん右下に移動していくのはそれはそう monotone minima…

問題ページ SPOJ.com - Problem BRKSTRNG Mongeを使ったDP高速化の練習で解いた 考えたこと 解説を読む X(i,j) = ([i,j)のコスト) みたいな感じで持ちたい W(i,j)は[i,j)を分割するのにかかるコストだから区間の幅でよさげ DP漸化式がKnuth-Yao speedupの形…

考えたこと 問題文を理解するのに時間がかかる i番目をりんごにできるならりんごにせずに後ろに回した方がいい場合はなさそう 貪欲に前からりんごにできるならりんごにするみたいなのを書く O(K)で区間のりんごの数を数えられるので合計O(NK)で解けそう 区間…

考えたこと よくわからないので実験をする ある頂点からOな頂点ならEOの列を反転した列になる 距離が1ずれるんだからそれはそう この条件で可能どうかの判定はできそうな気持ちになる 条件を満たしていれば適当に構築してえい サンプルが弱すぎるだろ サンプ…

考えたこと EMでEとして使う問題数をw、Mとして使う問題数をx、MHでMとして使う問題をy、Hとして使う問題数をzとする min(E+w, M+x+y, H+z)を最大化すればよい 最小の最大化はにぶたんをしたくなる 問題セットの数cntを作れるかの判定をしたい Eがcntより小…