https://atcoder.jp/contests/dp/tasks/dp_y座標をpairに格納してソートしたものをPとする。訪れるマスのPのindexをa_1 a_2->a_3->...->a_mの順番でしか訪問できない。なので、最後に訪れる場所で場合分けできて包除できる。 包除の問題で集合ではなく個数で…

https://beta.atcoder.jp/contests/dwacon5th-prelimsアーA Nかけましょう。 B なぜかバグらせた…上からbit決めましょう。 C なんで思いつかなかったのかなぁ…ちゃんと順番決めて見ていかないからダメ。DとMの数もってしゃくとりすればいいです。 int N, Q; …

http://codeforces.com/contest/1043/problem/FAB うん C 前から塊になるようにやれば。 D SAつかって殴った。TLEめちゃくちゃギリギリ。解説は並び替えてやってますね。 E a-bでsortすれば。 F 良問。まず数え上げに帰着して、包除原理する。このタイプ久し…

https://snuke21.contest.atcoder.jp/tasks/snuke21_e懐かしの。ムズイ。 ->初手でいけそうなのが、強連結の条件を考えてみるだけだった。 ->強連結成分がL個以上ならまあまあできそう。これが求まればあと引き算するだけ。 -->N!Σ(n+m+...=N)(2^(n(n-1)/2) …

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d考えること多すぎ。 ->とりまどうやって数え上げるか考える。 -->colorfulな列を考えて、そこにAが何個あるか? -->i番目からAが始まる列がcolorfulな場合の数Fiを計算する? -->まあ後者だろう。 ->co…

https://soundhound2018-summer-final-open.contest.atcoder.jp/tasks/soundhound2018_summer_final_cわりとすっきり解けた気がする。思考プロセス書きます。N,D ->分割統治? ->直線にしてみる? ->とりあえず緩和して最短距離がD以上のグラフの個数を数えて…

https://beta.atcoder.jp/contests/code-festival-2018-quala通過です…A sortしたけど、要素が3つでなんかオーバーキルな気がしてしまう B 愚直にやった。sortもしてません C まあdpだよね。0にならないとKを減らせないので注意。 D まあdpだよね。BIT使った…

https://beta.atcoder.jp/contests/arc102/tasksC K/2が肝とわかれば。 D 2^nの辺を張って、適当に付け加えれば良さそうと思って実際そうでした。添字がめんどい。 int L; vector<pi> G[20]; void solve() { cin >> L; int N = 1; while(L >= (1 << N)) N++; rep</pi>…

https://beta.atcoder.jp/contests/arc101本番解けないと意味ないってそれ一番。 コンテスト中は1完です…C K個の連続した区間になるので適切に計算すればO(N)。 D 本番誤読してかなしぃ。中央値はやっぱりにぶたんなんだよなぁ。 https://agc006.contest.atc…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011&lang=jpは?むずくないか? DPできないと思ったので、貪欲でやりました。 うしろから見ます。k日間でできるとします。k日目スケジュールが入っている人の集合をSとします。k-1日目でSに全部の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383350なのに全然解けない…と思ったら誤読で悲しかったです。 でも誤読した問題も少しおもしろいので紹介したいと思います。今までプレイした最高難易度と同じもしくは簡単な問題を解くことがT回…

https://csacademy.com/contest/round-84/task/manhattan-center/ つら… A Nが小さいので何しても通ります B O(N)でやろうとしたんですがバグらせたので普通ににぶたん書いた… C まず奇数長の棒が奇数本だとできません。そうでなければ奇数長を2本ずつ組み合…

https://agc022.contest.atcoder.jp/tasks/agc022_c面白い。場合分け系と思ったけど違った。前処理した後、大きいkから使う必要があるか見ていく。 https://agc006.contest.atcoder.jp/tasks/agc006_dやっぱり難しく考え過ぎだよなぁ…1が使えない→2で置き換…

https://beta.atcoder.jp/contests/arc097/tasks思考法を自分の中で確立して初めてのコンテストだったんですがうまくいったので舞い上がってます。C グッと睨むと5文字ずつとってsortすれば良いことがわかる。 D グラフにすればわかる。 E 条件がO(N)個あっ…

A dfsっぽくやって途中でexitすれば速いです。 B InteractiveっぽかったのでSkip C なんでこれ解けないのかなぁ…。dp[at][count]:=atまで見た時count個stackしたとする。その時の重さの最小値でO(N^2)で、実はcountまず謎貪欲を考えてしまったのが原因。最初…

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

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

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

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() {…

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

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