AtCoder Regular Contest 072F: Dam

http://arc072.contest.atcoder.jp/submissions/1399394O(N)だからqueueとか使うのかな?と一瞬思ったが、水なんて独立に考えることが出来ないだろ!と思い、O(NlogN)で何とかしようとしたが死亡。水を入れた順番から昇順にdequeで管理することを考える。i番目…

AtCoder Regular Contest 076E: Connected?

http://arc076.contest.atcoder.jp/tasks/arc076_cわかったと思ったけどWA。よく考えてると2つの曲線の点がすべて違う辺に乗っているケースを見逃していた。どっちの端点も長方形の辺に乗っている曲線についてのみ考えればよい。 曲線を適当に0,1,2...と名前…

AtCoder Regular Contest 077D: 11

http://arc077.contest.atcoder.jp/tasks/arc077_bARC077に参加。CとEは結構すぐわかった。D解けないのはさすがにまずい。 余事象で考えればすぐわかる。ずっと足し合わせで求めようとして頭がこんがらがった。 でも足し合わせても求められるくらい頭良くし…

AtCoder Regular Contest 070D: No Need

DP

http://arc070.contest.atcoder.jp/tasks/arc070_bなんとなくの解法ならすぐわかったけど、それを詰めるのがつらかった。0~i-1の和をsum[i]と表す。aをsortしてai~aNの要素のうちいくつかを選んで和を作る。その内、Kを超えないもので最大の値をJとする。 す…

AtCoder Regular Contest 072E: Alice in linear land

http://arc072.contest.atcoder.jp/tasks/arc072_c類題解いていたのでイケた。 i回目から行動を始めてたどり着くことが出来なかった座標の集合を考えて、その集合のうち目的地からの距離が最も小さいものだけを持っておけばよい。 これは行動を逆から見るこ…

解きたい問題

定期的にメモっときます。 http://codeforces.com/contest/815/problem/D http://codeforces.com/contest/813/problem/D http://codeforces.com/contest/813/problem/E http://codeforces.com/contest/814/problem/E http://arc076.contest.atcoder.jp/tasks…

AtCoder Grand Contest 016E: Poor Turkeys

単調減少してから単調増加するPathがキーになることは分かったけど…ループがどうなるかよくわからなくなった。http://agc016.contest.atcoder.jp/tasks/agc016_eまずある一つの頂点xに注目する。操作を後ろから見て、i番目の人の操作が終わった際、何が生き…

Codeforces Round #419B: Karen and Test

http://codeforces.com/contest/815/problem/B手を動かすのは大事ですね…実験すると4周期ごとにパスカルの三角形が出てくることに気づく。 int N; ll A[MAX_N]; ll F[MAX_N]; ll D[10][10]; bool sign[10][10]; ll mod_pow(ll a, ll n) { if(n == 0) return …

AGC_016D: XOR Replace

http://agc016.contest.atcoder.jp/tasks/agc016_d うーん。Union Find見えてからが遅かった。EFもようわからん連結成分を考えれば良くて、変更前の数列のxorの値と変更後の数列のxorの値が等しいか異なるかで場合分け。 答えは(連結成分の数)+(異なる値の数…

AtCoder Grand Contest 016C: +/- Rectangle

http://agc016.contest.atcoder.jp/submissions/1365887 まあわかれば大したことないんだけど。Hがhで割れて、Wがwで割れる時、h*wの長方形を左上から詰めていくと(H/h)*(W/w)個の長方形がきれいに収まる。 これらの長方形内のh*w個の数の和は負なのでH*W全…

AGC_016B: Colorful Hats

http://agc016.contest.atcoder.jp/tasks/agc016_b 最初1CaseだけWAだったからこれはいけると思ったけどそうでもなかった。A[i]の最大値と最小値(それぞれrv,lvとする)の差が1か0で場合分けする 1. 0のとき rv = N - 1なら全色違うものを置けばOK rv * 2 2. …

AOJ 2749: ぼくのかんがえたさいきょうのおふとん

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2749&lang=jp sortしてbit dp。 int N, M; int dp[(1 << 16) + 10][110]; int O[20]; int A[110]; void solve() { while(true) { cin >> N >> M; if(N == 0) break; rep(i, 0, N) cin >> O[i]; re…

AtCoder Regular Contest 074 E: RGB Sequence

DP

http://arc074.contest.atcoder.jp/tasks/arc074_cひたすらdp[i][j][k](i番目まで見たときRがj個あり、Gがk個ある場合の数)みたいな感じでやろうとしたけど、区間内にRGBがそれぞれ存在するかどうかだけわかればいいのでどう見ても情報を持ちすぎていた。 dp…

AtCoder Regular Contest 075 E: Meaningful Mean

http://arc075.contest.atcoder.jp/tasks/arc075_c条件を数式に落とし込むと ∑(i=0→r)Ai - rK という値について考えればいいことがわかる。数式を使うと独立性に気付ける問題だった。 あとは適当に座圧してBITで数え上げればよい。 int n; //BIT 1-origin ll…

Educational Codeforces Round 23D: Imbalanced Array

http://codeforces.com/contest/817/problem/D久しぶりにコンテストに参加してみたが、全く頭が動かなかった。これくらいの問題が解けないのは大問題。コンテスト中なぜかいろいろ勘違いして最小値最大値分離出来ねえなあと思っていた。 int N; ll A[MAX_N];…

初投稿です

競プロやっているomochanという人です。適当に解いた問題を載せていくのでよろしくお願いします。 JOI Kangaroo int N; ll dp[2][MAX_N][MAX_N]; pi P[MAX_N]; int C[MAX_N]; bool bigger(const pi& p1, const pi& p2) { return p1.second < p2.second; } vo…