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…

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のうち最大のものを取るのが最適だ…

https://agc009.contest.atcoder.jp/tasks/agc009_eまずK分木の葉に0や1を書き込んで、木の形状通りに平均を取っていく問題に言い換えます。するとK分木は葉が全て0の部分を除けば、縦1直線に繋げばいいことがわかります。 証明のアイディアとしては、葉が全…

https://agc020.contest.atcoder.jp/tasks/agc020_dお気持ちそのままが解法ですが、実装がめんどくさすぎる…。1発ACだけど詰めるのにすごい時間かかった。 A>Bとします。Bまず文字が何個まで連続できるかを求めます。これは少し考えればfloor( (A+B)/(B+1) )…

https://agc018.contest.atcoder.jp/tasks/agc018_dアイディア自体はそこまで難しくないけど、証明がややこしいやつ。重心をとって、各子の部分木を渡り歩けば良いのかなぁという予想は簡単につくので、それが最善であることを頑張って示せばいいです。 ポイ…