https://beta.atcoder.jp/contests/arc060/tasks/arc060_d 最小項数は1or2orNで、1とNの時は簡単。2はKMP法でできる。 [https://beta.atcoder.jp/contests/agc013/tasks/agc013_d DPにするのが難しいタイプの問題はホント苦手。でもこれはとりあえずdp[i][at…

https://arc085.contest.atcoder.jp/tasks/arc085_cmaximum closure problemという問題なんですが、集合を2つに分ける+DPでできない場合は疑ったほうがいいです。 さて今回最大化したいのは、 S-min(Σbi+Σci)です。ここでbiは破壊する宝石のうち値が正のもの…

https://beta.atcoder.jp/contests/agc004/tasks/agc004_c 赤と青を交互に並べる。 https://beta.atcoder.jp/contests/agc012/tasks/agc012_b うーんこういうのダメだよなぁ。dp的に考えるのが苦手。bellman-fordっぽくやる。 https://beta.atcoder.jp/conte…

https://arc081.contest.atcoder.jp/tasks/arc081_d まず2*2の正方形に注目して塗られているマスが奇数個だとその正方形を一色にすることはできないことに気づきます。そうしたらそのような正方形を全部含まないような長方形のうち最大のものを求めればいい…

https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e rep(i, H + 1) rep(W, M) AS[i] += min(i, A[j]); 通した人の多くがこのようなコードを書いているわけですが、これだけ解説します。 Bがsource側、Aがsink側だとします。 Bのうちi辺…

https://beta.atcoder.jp/contests/agc006/tasks/agc006_cおもしろかったので別に記事書きました。まず簡単な計算をすると、ai,ai+1,ai+2と場所の期待値が求まっており、ai+1が行動するとき、ai+1の期待値はai+1→ai+ai+2-ai+1となることがわかります。 次の…

https://beta.atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_c 二部グラフでdfs https://beta.atcoder.jp/contests/agc004/tasks/agc004_d 下からk-1番ごとに1に繋げれば良い。上から見るのではなく下から見るのが重要 https://beta.a…

https://beta.atcoder.jp/contests/arc093/tasks/arc093_a 3点を見比べる。 https://beta.atcoder.jp/contests/arc093/tasks/arc093_b 一面黒に塗って白をその中にちまちま塗る。逆も同じ。 https://beta.atcoder.jp/contests/arc064/tasks/arc064_b えー結…

https://beta.atcoder.jp/contests/arc060/tasks/arc060_c doublingするだけ。 https://beta.atcoder.jp/contests/agc005/tasks/agc005_c 一番長いパスを考えれば一瞬。 cout https://beta.atcoder.jp/contests/agc010/tasks/agc010_c 下からmergeする辺の本…

https://beta.atcoder.jp/contests/agc002/tasks/agc002_b DPっぽいことすればできます。でもあまり自分にはない発想なので解いてよかった。 https://beta.atcoder.jp/contests/agc003/tasks/agc003_b 小さいものからペアにしていけばいいです。0に注意。 ht…

https://beta.atcoder.jp/contests/arc058/tasks/arc058_b コンビネーションやるだけだけど、素早く通せてよかった。 https://beta.atcoder.jp/contests/abc088/tasks/abc088_d 幅優先久しぶりに書いた… https://beta.atcoder.jp/contests/arc065/tasks/arc0…

適当に簡単めの問題をたくさん解いたのでメモっときます。https://beta.atcoder.jp/contests/abc051/tasks/abc051_d ワーシャルフロイドして辺を通るルートは最適か見る。 https://beta.atcoder.jp/contests/abc054/tasks/abc054_d 混合液の量が小さいのでdp…

https://beta.atcoder.jp/contests/arc091/tasks/arc091_a速さが足りない。C はい。 ll N, M; void solve() { cin >> N >> M; if(N > M) swap(N, M); if(N == 1) { if(M == 1) cout << "1\n"; else if(M == 2) cout << "0\n"; else cout << M - 2 << "\n"; }…

https://beta.atcoder.jp/contests/agc005/tasks/agc005_fFMT初実装です。まず求めるものを式にすると ans[K]=1/(K!)Σ(i=K...N)cnt[i]*(i!)/(i-K)! となります。ただしcnt[i]はサイズがiである部分木の数です。 これを式変形すると、 ans[N-u]=1/((N-u)!)Σ(i…

https://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_fこれは特に言うことはなくて、合成する操作が木に見えて、木の高さが本質とわかれば解けますね。 int N; int B[MAX_N][2]; ll dp[MAX_N][2]; void solve() { cin >> N…

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_hお気持ちはわかるし、結構惜しいところまではいけるけど…氷山を消すと、4辺全てに氷山がある長方形領域に分断されることがわかります。なのでそれにしたがってDPすればいいです。といえば簡単…

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_h面白いです。良問。まずM=1の時を考えて普通にdpすると、 f(j)=max(Ai-sum(j,i)-f(i+1)|i>=j)となります。ただしsum(j,i)=Σ(k=j...i-1)Akです。よくある添字を１つ減らすテクニ…

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_iだいぶ時間使ったけどなんとか解けました。良問です。順位表が求められればトーナメント上の順番は簡単に求まります。順位表上でi番目がj番目よりも小さくならなければならない条件をi->jに辺…

https://agc016.contest.atcoder.jp/tasks/agc016_fやっぱりできることとできないことの差がまだわからない…。1と2のgrundy数が一致しないようなグラフを数え上げればいいです。 全ての頂点についてgrundy数を決めてしまえば、グラフを数え上げるのは多項式…

https://agc013.contest.atcoder.jp/tasks/agc013_e一応知ってるテクニックの組み合わせにはなるんだけど…難しいですね。Degwerさんの数え上げテクニック集で紹介されている問題です。とりあえず自明DPを考えると dp(x)=Σ(y=1...x)y^2dp(x-y)となります。こ…

https://agc010.contest.atcoder.jp/tasks/agc010_fO(N)で心配になった…。まずある頂点vに対して、隣接している全ての頂点piに対してA[v] なぜなら高橋君がvからどこに動かしても、青木くんがvに駒を戻せばいいです。そうすればA[v]がいずれ0となり高橋君は…

https://beta.atcoder.jp/contests/agc010/tasks/agc010_eO(N^4)からの高速化が思いつかなかった…。まずAiを頂点としたグラフを考えて、互いに素ではない頂点同士をつなげます。すると各連結成分で一番小さい要素をcとしてcのうち最大のものを取るのが最適だ…