AtCoder Grand Contest 012E: Camel and Oases

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

DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦,D: シャツの部屋

DP

https://ddcc2016-final.contest.atcoder.jp/tasks/ddcc_2016_final_dこれは本当に良問だと思います。まずi-1回洗濯するとすると、i+k回洗濯すると破れる服は全部i回とみなせます。 Mが小さければdp[i][j]:=i回洗濯する服まで見てj日シャツを着られる方法で…

CODE FESTIVAL 2016 Grand Final,E: Water Distribution

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_e初手が難しい…。グラフの水の容量がB,水をやり取りする辺の距離の合計をA,都市の数をKとすると、なんと最大値は(B-A)/Kであることが証明できます。 Aは都市K個の最小全…

CODE FESTIVAL 2017 Final,E: Combination Lock

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_eまず区間の真ん中をまたぐ部分は考えなくていいです。 すると区間は左or右に寄った形になりますが、右にある区間を左に移しても問題ありません。 よって左半分に操作を行って右半分の文字列に…

「みんなのプロコン 2018」E: グラフの問題

https://yahoo-procon2018-qual.contest.atcoder.jp/tasks/yahoo_procon2018_qual_e検索するとこんなのが出てきます。次数 (グラフ理論) - Wikipediaここにある式をそのまま使えばいいです。1を足す時でも式で考えれば一番小さい次数を1上げれば良いことがわ…

CODE FESTIVAL 2017 Final,F: Distribute Numbers

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_fなんでこれ結構解かれているんだろう…editorialそのままです。違う構成法を考えてハマっていたので、いろいろ試してみようくらいしかこの問題から学べないと思うんですがね…あと見通しのいい…

CODE FESTIVAL 2017 Final,G: Mancala

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_g答えは(f(a)の期待値)*(K+1)^Nなのでf(a)の期待値を求めることにします。まず最小値を達成する操作とはどのようなものなのか考えます。 i番目の値Aiについて最初からAi>iであれば何も操作を行…

AOJ2405: 姉妹港

DP

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405解法をyosupoさんのブログとか見て理解したのでメモしておきます。とりあえずどっかで多角形を切り開いて区間の問題にします。 普通に考えるとO(N^2)のDPになって、更新式は [l r]に区間が張…

CODE FESTIVAL 2016 Grand Final,G: FESTIVAL

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_g昇順に並んでいる数列S{1,a,b,c,...X}があって、隣り合っている数の比がa(自然数)より小さいとします。 するとX以下の自然数NはSの線形結合で表されて、係数の和はO(a*…

CODE FESTIVAL 2016 Grand Final,D: Dice Game

https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_d面白い。petrが赤のサイコロを選ぶ確率をX,touristがiが出た時に赤という確率をxiとします。するとtouristが勝つ確率は f(X,x1...x6)=1-X+Σ((pi+qi)X-qi)xiとな…

AGC012C: Tautonym Puzzle

https://agc012.contest.atcoder.jp/tasks/agc012_c12345...12345...みたいに並べて2^n関連でやることは見えたけどそこからが思いつかなかった。 要素入れ替えたりを考えたけど、想定解は挿入でした。やっぱり秩序なくやるよりも、定式化できそうな良い構造…

CODE FESTIVAL 2017 Exhibition,A: Awkward

https://cf17-exhibition-open.contest.atcoder.jp/tasks/cf17_exhibition_a包除原理してpathを何本含むかでdpすれば良いということはわかりました。 ただ自信がなく解法見てやっぱり合ってたってなりました。 これ絶対debug時間かかるやつだと思いましたが…

CODE FESTIVAL 2017 Elimination Tournament Round 3,F: Unicyclic Graph Counting

DP

https://cf17-tournament-round3-open.contest.atcoder.jp/submissions/2045180こんなのサイクルが1つあるだけのグラフ以外に考察の余地無いだろで、DPに行けたのは良かったです。dp[i][j][k]:=i番目まで見て、j点サイクルに使って、サイクルの次数がkの時…

CODE FESTIVAL 2016 Grand Final,F: Intervals

https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_fまず真ん中の区間を動かさないで最小を達成する方法があることが示せます。 なので右左にそれぞれN/2個の区間を割り振ればいいです。 そして貪欲が厳しそうだと思える…

CODE FESTIVAL 2016 Final,F: Road of the King

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_fこれは簡単だった。どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。 なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含…

AGC007C: Pushing Balls

https://agc007.contest.atcoder.jp/assignments期待値ってこんなこともできるのか…まずf(d1,d2,....d2n)を距離の間隔がそれぞれd1...d2nの時の期待値と定義します。 簡単な例でf(1,2,3,4,5,6)を取り上げます。 1手進めてみましょう。すると f(1,2,3,4,5,6)=…

CODE FESTIVAL 2016 Final,E: Cookies

https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_eまずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。クッキーを食べるまでA+si秒待ったとすると、 クッキーの総和はΠ(1 Σsiを固定してΠsiを最大化する…

CODE FESTIVAL 2016 Elimination Tournament Round 1,B: 数字列をカンマで分ける問題

https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasksにぶたんします。結局任意のi,jに対してS[i...i+M]とS[j...j+M]が高速に比較できればいいんですが、これはsuffix arrayでできます。suffix array知っていれば一瞬の問題なのかぁ。部分列…

ARC012D: Colorful Balls

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d最初の提出で3ケースだけWAだったのでオーバーフローとかどうでもいいミスでしょと思いましたが違いました… 同じ色内だったら1番小さいやつから辺を張ればいいです。 でも違う色だったら色の中で一番…

AGC010D: Decrementing

https://beta.atcoder.jp/contests/agc010/tasks/agc010_dやっぱこういうのは偶奇ですね…。操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecremen…

AGC002D: Stamp Rally

https://agc002.contest.atcoder.jp/tasks/agc002_d永続unionfindかぁと思ってたけど、想定解は並列二分探索というものらしいです。同じような二分探索を大量にしないと行けない時に、まとめてやる感じです。辺の数と点の数をswapしていて無限にバグらせた… …

AGC001D: Arrays and Palindrome

https://agc001.contest.atcoder.jp/tasks/agc001_dこれ知識的には誰でも解けるけど結構思考しないといけなくて面白い。同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。 なので…

ARC064F: Rotated Palindromes

https://arc064.contest.atcoder.jp/tasks/arc064_df(l)=周期がちょうどlの条件を満たす数列の数とすると、f(l)=K^[(l+1)/2]-Σf(l/p)となって、求める値はΣ(lは奇数)f(l)*l+Σ(lは偶数)f(l)*(l/2)です。f(l)の式は高速メビウス変換の式に良く似ています。http…

COLOCON -Colopl programming contest 2018- Final

https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…

AGC020

DP

https://beta.atcoder.jp/contests/agc020A A-Bの偶奇ですB 条件を満たすものは区間で表せるので端の値を持てばいいです。C 和をSとしてS/2以上で一番小さいものを選べばいいです。証明はSの部分列をA、B=S/Aとするとsum(A)=S/2となることからです。 bitのdp…

行く年来る年

2017年重要なアルゴリズムはだいたい抑えられた。(特にflow)問題の解き方が少しわかってきた。(前まではひらめくまで途方に暮れていた)年末はコンテスト結構出れた。AtCoderのみだけど。2018年目標AtCoder Rate2600CodeForces Rate2200AtCoder精進(AGC,ARC)…

Codeforces Round #455 (Div. 2)

http://codeforces.com/contest/909/problem/E全体的に問題文の把握に手間がかかっていますね…A はい。 B 親の顔より見た問題。一番重なっているところを累積和で求めます。 C 勘違いした… D 削除は奈良市計算量チャンスです。 E 問題を理解するのに無限に時…

ARC068

https://beta.atcoder.jp/contests/arc068C はい。D 結局2枚捨てるという操作なので。E 解法2つあります。dの倍数のdを小さくすると、r - l 区間、つまりl区間の数は増えていきます。 これを利用する方法が1つです。もうひとつは区間(l,r)を二次元plotすると…

ARC088

https://beta.atcoder.jp/contests/arc088C A*2^nD 結構詰まった人もいるっぽい。端は好き勝手変えられるので真ん中だけ考えればいいです。AtCoder Regular Contest 080F: Prime Flip - omochan's diaryのように区間→2点更新の問題に言い換えられますが、今…

ARC067

C はい。 D min(B, A * dist)で移動すればいいです。 E 普通にdpするとO(N^3)と見せかけてO(N^2logN)なので間に合います。速く書けてよかった。 void solve() { cin >> N >> A >> B >> C >> D; C_init(N + 50); dp[A][N] = 1; for(int i = A; i <= B; i++) {…