精進6/23

https://agc022.contest.atcoder.jp/tasks/agc022_c面白い。場合分け系と思ったけど違った。前処理した後、大きいkから使う必要があるか見ていく。

精進6/21

久しぶりですhttps://beta.atcoder.jp/contests/arc098/tasks/arc098_bえー思いつきませんでした。bitがかぶらないことが必要十分。 https://beta.atcoder.jp/contests/arc098/tasks/arc098_c最小値固定すれば、長さk以上の区間から数を取っていく問題になり…

codeFlyer (bitFlyer Programming Contest)

こういうセット辛すぎないか?AB はい C ちょっと詰まるよね。とりあえずjを固定して雑に数えて引くんだけど、引く時はしゃくとりが使えます。 D 累積和やるだけ。全然綺麗な方法思いつかなかった…。imos法もバグらせまくった… ll H, W; int N, M; int B[2010…

Codeforces Round #483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]

http://codeforces.com/contest/983A えーABCの中で一番手間取った。QとBの最大公約数gをとってQをgで割ることを繰り返す。こういうの苦手。 B dpしてまたdp C dp[i][j][k][l][m][n]:=i番目の人までみて、場所jにいる。エレベーターに乗っている人はk,l,m,n…

Codeforces Round #482 (Div. 2)

http://codeforces.com/contest/979順位はそんな悪くないんですが…A n=0〜 B 奇数偶数やろ…となるんですが違います C えぇ… D 追加は約数個のオーダーだし、答える時は、segtreeっぽく範囲を狭めていきます。問題文が無駄に複雑。やめて。 考察は一瞬でした…

ARC097

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

Google Code Jam Round 1C 2018

DP

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

精進GW

随時更新していきます。https://beta.atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_c xを抜いてまず成立するか確認します。あとはxを適切に挿入していくだけです。https://beta.atcoder.jp/contests/ddcc2016-qual/tasks/d…

Codeforces Round #477 (rated, Div. 1, based on VK Cup 2018 Round 3)

http://codeforces.com/contest/925Virtualで参加しました。A エレベーターと階段の8箇所試せばよいです。いろいろ勘違いしてめっちゃWAした。 B 後ろの方から愚直に使うのが良いです。 C 順列の存在判定ってめちゃくちゃ難しいのはわかりますね。だからおそ…

Combination

Combinationが肝となる問題って数学ゲーとか言われて結構難しくないですかってことでいろいろ考察してみました。(a+b)Caはa+b人いる中でa人を選び、b人を除外するときの場合の数です。 これは経路数にも言い換えられて、タテaマスヨコbマスのgridで左下から…

IMO

解けそうなやつ解いてみました。2017 5番 N+1要素以上の単調増加列を使って構成する方法をまず考えましたが、うまく行かず。 そのときに数の区間で考える発想が浮かんだので、1-N+1,N+2-2(N+1),...,(N-1)(N+1)+1-N(N-1)のN個に分割してみました。 そうすると…

AGC023

https://agc023.contest.atcoder.jp/A map B (i,j)と同じでなければならないのは(j+B-A,i+A-B)です。よってB-Aの値だけが重要なのでO(N^3)です。 C あーなるほどなぁ。自分の中で全ての問題は貪欲orDPに落とせるって考えていたのが間違えでした。 なのでDPし…

CSA Round #78

https://csacademy.com/contest/round-78/summary/A はい B set C dp[桁][Nより小さいか][桁を始めたか]の桁dp。典型らしい。 D 結合性( (a+b)+c=a+(b+c) )が成り立てばsegtreeにできるというやつ。例えば https://yahoo-procon2017-qual.contest.atcoder.jp…

AOJ-ICPC埋め

国内予選出るので精進します。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…

ARC096

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…

AGC015E: Nuske vs Phantom Thnook

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

CODE THANKS FESTIVAL 2017,F: Limited Xor Subset

DP

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)になってとても間…

ARC092E: Both Sides Merger

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

AGC014C: Closed Rooms

DFS

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

CODE FESTIVAL 2017 Elimination Tournament Round 1,C: Paired Parentheses

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

ARC094D: Worst Case

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 となります。こ…

ARC095

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

CSAcademy: Round #76

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

精進4/11

DP

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

精進4/8

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

ARC094

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

CSA Round#75

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

精進4/4

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

精進3/29

DP

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…

ARC085E: MUL

https://arc085.contest.atcoder.jp/tasks/arc085_cmaximum closure problemという問題なんですが、集合を2つに分ける+DPでできない場合は疑ったほうがいいです。 さて今回最大化したいのは、 S-min(Σbi+Σci)です。ここでbiは破壊する宝石のうち値が正のもの…