3/28精進

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…

3/27精進

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

COLOCON -Colopl programming contest 2018- Final,E: キャプテン・タカハシ

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辺…

AGC006C: Rabbit Exercise

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となることがわかります。 次の…

3/26精進

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…

3/25精進

DP

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 えー結…

3/24精進

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する辺の本…

3/23精進

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

精進3/22

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…

3/21精進

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

ARC091

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"; }…

AGC005F: Many Easy Problems

FFT

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…

CODE FESTIVAL 2017 qual A,F: Squeezing Slimes

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…

CODE FESTIVAL 2017 Final,H: Poor Penguin

DP

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

CODE FESTIVAL 2016 Final,H: Tokaido

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です。よくある添字を1つ減らすテクニ…

CODE FESTIVAL 2017 Final,I: Full Tournament

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

AGC016F: Games on DAG

DP

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

AGC013E: Placing Squares

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

AGC010F: Tree Game

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

AGC010E: Rearranging

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

AGC009E: Eternal Average

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

AtCoder Grand Contest 020D: Min Max Repetition

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

AGC018D: Tree and Hamilton Path

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

AtCoder Grand Contest 009C: Division into Two

https://agc009.contest.atcoder.jp/tasks/agc009_c実家やるだけのはずなんですが通らないので後回しにします…。 int N; ll A, B; BIT bitx, bity; ll D[MAX_N]; const ll UB = 1e18; int cd(ll a) { return lower_bound(D, D + N, a) - D; } void solve() {…

AGC003E: Anticube

https://agc003.contest.atcoder.jp/tasks/agc003_d本質を勘違いした…まず素数のうちa個あるものはa%3個にしてよいです。それでvをcubeにする値uをつなげたグラフを考えると二部グラフになるので、max( (vの数),(uの数) )の合計を求める問題に帰着できます。…

AtCoder Petrozavodsk Contest 001F: XOR Tree

DP

https://apc001.contest.atcoder.jp/tasks/apc001_f 最近同じような問題を解いたのでわかったんですけども、O(3^N)DPをバグらせて悲しくなりました…。頂点に隣接しているすべての辺のXORを書き込みます。すると、2つの頂点についてある値XでのXORを行い、す…

「みんなのプロコン」D: 工場

https://yahoo-procon2017-qual.contest.atcoder.jp/assignmentshttps://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_di日目の最適な売り方をした時の商品の残りをBi個としてグラフを考えます。(D,A)はグラフをD日からAだけ下げ…

「みんなのプロコン」本選C: 倍数クエリ

https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c平方分割やるだけです。初期化の時にセグフォ起こしたのでそれだけ気をつけましょう。 const int BLOCK = 300; const int CNT = MAX_N / BLOCK + 10; int N, M; int …

第4回 ドワンゴからの挑戦状 予選,E: ニワンゴくんの家探し

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_eこれはそんなに難しくない。重心分解して、一番部分木が大きい頂点から列挙します。 重心がsだとして、子が{a, b, c, d, e}だったとします。 そしたら(a,b)をまず聞いてaだったらa…

AtCoder Grand Contest 012E: Camel and Oases

https://agc012.contest.atcoder.jp/tasks/agc012_eアイディア自体はすんなりいけたけどいろいろ勘違い+バグで無限に時間がかかった…。とり方を見てみると、容量Vでジャンプしないで取るオアシスの区間,V/2で取る区間、(V/2)/2で取る区間…があって、それぞれ…