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個の区間を割り振ればいいです。 そして貪欲が厳しそうだと思える…
https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_fこれは簡単だった。どんなグラフになるかというと、連結成分を潰して1つの頂点と見れば直線になっています。 なので、dp[i][j][k]:=(i回目でまだとっていない点の数がj個、1を含…
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)=…
https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_eまずクッキーを食べる回数Tを固定します。これは40くらいまでやればいいです。クッキーを食べるまでA+si秒待ったとすると、 クッキーの総和はΠ(1 Σsiを固定してΠsiを最大化する…
https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasksにぶたんします。結局任意のi,jに対してS[i...i+M]とS[j...j+M]が高速に比較できればいいんですが、これはsuffix arrayでできます。suffix array知っていれば一瞬の問題なのかぁ。部分列…
https://beta.atcoder.jp/contests/agc012/tasks/agc012_d最初の提出で3ケースだけWAだったのでオーバーフローとかどうでもいいミスでしょと思いましたが違いました… 同じ色内だったら1番小さいやつから辺を張ればいいです。 でも違う色だったら色の中で一番…
https://beta.atcoder.jp/contests/agc010/tasks/agc010_dやっぱこういうのは偶奇ですね…。操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecremen…
https://agc002.contest.atcoder.jp/tasks/agc002_d永続unionfindかぁと思ってたけど、想定解は並列二分探索というものらしいです。同じような二分探索を大量にしないと行けない時に、まとめてやる感じです。辺の数と点の数をswapしていて無限にバグらせた… …
https://agc001.contest.atcoder.jp/tasks/agc001_dこれ知識的には誰でも解けるけど結構思考しないといけなくて面白い。同じにならないといけない文字同士を結ぶグラフを考えると、直線+ループになる。これは各点の次数が2以下であることから示せる。 なので…
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…
https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…
