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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314構文解析といえばこの問題みたいなところあるよね。まず左再帰を取り除きます。assignment ::= var "=" expr "." var ::= "A" | "B" | "C"expr ::= term expr' expr' ::= "+" term expr' | "-…

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=2255優先順位が低い演算子から再帰していく感じでやればいいです。例えば演算子の優先順位が(),/,*,-,+だったら、expr0::=expr0 + expr0 | expr1 expr1::=expr1 - expr1 | expr2 expr2::=expr2 * …

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp構文解析おもしろいじゃーん。関数の返し値をpair ( (値),(どこまで解析したか) )にして、引数を(どこから解析するか)にすれば簡単に実装できます。 今回は formula:=-formula|(formu…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jpは?これも難しくないか? 普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。Aから中継点を数カ所挟…

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

https://codeforces.com/contest/1019Aで無限に時間を使ってしまい、絶望的だったので撤退…いやでも今後のためにも提出したほうがよかったかなぁ…A 普通に勝たせる人に何票入れるかで全探索すれば良いんですが、いろいろこんがらがってしまいだめでした… B …

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

https://codeforces.com/contest/949ABしか解けないよぉ助けてくれA 最大のzebraを取っていけばいいことはわかりますが、実装にてこずりました。こういうのはsetって一番言われてる。 B 再帰的に求めていけばいいです。 C 最近有向グラフの問題といてなくて…

https://codeforces.com/contest/986AB397位 A bfsします。 B 3nと7n+1で偶奇違うのに気づくのにすごい時間かかってしまった…。 C こういうグラフの問題は初手をミスるとなんにもできなくなりますね…。 補助グラフを使ってうまくまとめる感じです。https://c…

http://codeforces.com/contest/1016このコンテストで全完できるようになったらめちゃくちゃ気持ちよさそうですね… A 読んでないです。 B O(NQ)でゆるーくやりましょう。 C めんどくさい…横移動するとあとはコにしか動けません。 D 条件を連立方程式にして、…

https://codeforces.com/contest/1007A 普通にループ回しましょう。 B 包除原理で美しく書きましょう。 C やりたくない… D 2-SATだけど、普通にやったら間に合わないのでsegtreeっぽく構築するやつですね。HL分解すれば論理式がO(Nlog^2N)個になって多分解け…

A 作業の合計回数は一定です。 B 勉強になりました。数が埋まってる区間がありそうだからそれをずっと探そうと思っていたけど、冷静になるとこれは十分条件から攻めているのであまり良い戦略とは言えませんね。やっぱり「ありえない」ものを除去していって、…

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

https://beta.atcoder.jp/contests/agc026/tasks/agc026_b BとDの最大公約数が肝になることがわかればほとんど解けたようなもんですが、他の自明な条件も忘れないように。 https://beta.atcoder.jp/contests/agc026/tasks/agc026_c 文字列の前N字について割…

https://beta.atcoder.jp/contests/arc100/tasks/arc100_a目AC。中間値でもいいし、普通に全通り試すのもよし。 https://beta.atcoder.jp/contests/arc100/tasks/arc100_b目AC。にぶたんしなくても、しゃくとりしながらdpすれば解けます。K区間ならO(NK)です…

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

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

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

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…

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

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/code-festival-2017-qualc/tasks/code_festival_2017_qualc_c xを抜いてまず成立するか確認します。あとはxを適切に挿入していくだけです。https://beta.atcoder.jp/contests/ddcc2016-qual/tasks/d…

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

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

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

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

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…