国内予選出るので精進します。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2743&lang=jp4隅を必ず含む解が存在することが言える。それを元に丁寧に場合分けすればできる。面倒だけど一発AC。 int H, W, N; ll A[210][210]; ll S[210][210]; l…

https://beta.atcoder.jp/contests/arc096C. Cを全通り試します。 ll A, B, C, X, Y; void solve() { cin >> A >> B >> C >> X >> Y; ll ans = linf; for(int c = 0; c <= max(X, Y) * 2; c += 2) { ll res = 0; res += C * c; res += A * max(X - c / 2, 0l…

https://agc015.contest.atcoder.jp/tasks/agc015_cこの発想に至るまでが時間かかる気がする。森の数=木の頂点数-木の辺数と言い換えられれば勝ちです。 あとは累積和適当に取れば通ります。実装なんですがB,S,E,U,D,L,Rと7つも2010*2010の配列を作ってしま…

https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_fこういうの最近Codeforcesでも見た。とりあえずdpを書いてみます。 dp[i][a]:=要素iまで見た時xor sumがaになるものの場合の数。 これはO(NK)になってとても間…

https://arc092.contest.atcoder.jp/tasks/arc092_cこういう問題も冷静になればシンプルに書けるんやなって。結局、要素番号が偶数のやつから好きにとるか、奇数のやつから好きにとるかをすればいいとわかります。 構成法ですが、 1.数列を後から見て、使う…

https://agc014.contest.atcoder.jp/tasks/agc014_c結局1回目は開いているところをK回移動、2回目以降は壁を壊しながらK回移動と言い換えられます。 なので2回目以降は4方向のうち一番近い場外へ直線で行くのが最適です。変数がsx,x,nxと結構出てきてしまっ…

https://cf17-tournament-round1-open.contest.atcoder.jp/tasks/asaporo2_c考察よりも実装を重視して解いた。解法自体は良くありがちなやつ。 2つのカッコ列が成立するための必要条件が、最初がどちらも(、最後がどちらも)、真ん中で違うのが偶数個なのだが…

https://arc094.contest.atcoder.jp/tasks/arc094_b本質は構成ゲーです。A CをA*B>C^2を満たすうち最大の数とします。 A=A*Bのとき2*C-2、 C(C+1)=3であることがわかります。 なのでB-A B-A=0のとき2*A-2 B-A=1のとき2*A-2 B-A=2のとき2*A-1 となります。こ…

https://beta.atcoder.jp/contests/arc095こいついっつも同じような記事書いてるな。C はい。 D C(a,b) E 列と行の操作は入れ替えることができます。なので行を全探索した後、点対称にできるかどうか列を見ればよいです。 いえば簡単ですがめちゃくちゃバグ…

つら。ABC はい。D あーもうめちゃくちゃだよ。 queueっぽいものが見えてから発想が転換できなかったのが敗因。 やっぱり実装力ないし、考察時に実装量を見積もるのも下手ですね。 面倒な問題たくさん解いて精進したほうが良さそう… int N, M; ll Y[MAX_N], …

https://beta.atcoder.jp/contests/arc063/tasks/arc063_c 範囲求めて木の根から決めていけば良い。証明が少しあやふやで本番WAしたら自信無くして通せなさそう。 https://arc079.contest.atcoder.jp/tasks/arc079_d 丁寧丁寧丁寧にやったのでバグらせなかっ…

https://arc061.contest.atcoder.jp/tasks/arc061_c dijkstraを工夫しようと思って失敗した。グラフの方を工夫しましょう。 https://arc066.contest.atcoder.jp/tasks/arc066_b これ通せたのは成長感じる。桁DPなんですが、背反+遷移をちゃんと意識して解け…

https://beta.atcoder.jp/contests/arc094惨敗でした。C えーわかんないのでDPした。 D C(C+1)>=ABの式は出たんですが、方針が悪く詰めきることができず… 解説放送の二分探索のほうがわかりやすそう。 E 一回目の提出が1byte差で落ちたんですが、そこから冷…

https://csacademy.com/contest/round-75初参加です。A はい。 B 変なdfsした C sort and lower_bound D priority_queue E 平方分割でmodが小さい時はsegtreeで愚直に、大きい時は二分探索と思ったんですが通らず…。 F NTTやるんですが、式変形だけ書いてお…

実は引っ越しして一人暮らし始めたんですが、今日になってやっとwifi環境を用意出来たので、精進再開です。http://codeforces.com/contest/959/problem/C 真ん中に2つ点がある木と、rootに全ての点が隣接している木を出力する。 http://codeforces.com/conte…

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…