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

https://agc020.contest.atcoder.jp/tasks/agc020_dお気持ちそのままが解法ですが、実装がめんどくさすぎる…。1発ACだけど詰めるのにすごい時間かかった。 A>Bとします。Bまず文字が何個まで連続できるかを求めます。これは少し考えればfloor( (A+B)/(B+1) )…

https://agc018.contest.atcoder.jp/tasks/agc018_dアイディア自体はそこまで難しくないけど、証明がややこしいやつ。重心をとって、各子の部分木を渡り歩けば良いのかなぁという予想は簡単につくので、それが最善であることを頑張って示せばいいです。 ポイ…

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://agc003.contest.atcoder.jp/tasks/agc003_d本質を勘違いした…まず素数のうちa個あるものはa%3個にしてよいです。それでvをcubeにする値uをつなげたグラフを考えると二部グラフになるので、max( (vの数),(uの数) )の合計を求める問題に帰着できます。…

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

https://yahoo-procon2017-qual.contest.atcoder.jp/assignmentshttps://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_di日目の最適な売り方をした時の商品の残りをBi個としてグラフを考えます。(D,A)はグラフをD日からAだけ下げ…

https://yahoo-procon2017-final-open.contest.atcoder.jp/tasks/yahoo_procon2017_final_c平方分割やるだけです。初期化の時にセグフォ起こしたのでそれだけ気をつけましょう。 const int BLOCK = 300; const int CNT = MAX_N / BLOCK + 10; int N, M; int …

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_eこれはそんなに難しくない。重心分解して、一番部分木が大きい頂点から列挙します。 重心がsだとして、子が{a, b, c, d, e}だったとします。 そしたら(a,b)をまず聞いてaだったらa…

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

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

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

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

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

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

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

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

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

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

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

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

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

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