問題ページ C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoder 考えたこと 最小全域木を求めたくなる 最小全域木で使わない辺はいらなさそう 根をcが最も小さい頂点とした根付き木を考えればよさそう 辺を使わないことにして別の頂点を使うみたいな…

問題ページ C - 高橋王国の分割統治 考えたこと 明らかに†全方位木DP†をしろという雰囲気をしている d[i] = (頂点iの部分木の頂点数) とする d_par は n-(進む頂点の部分木の頂点数) を渡せばよさそう テンプレに当てはめて書くと通った #include <bits/stdc++.h> using nam</bits/stdc++.h>…

問題ページ C - 高橋君、24歳 考えたこと 正しく手紙をいれた人のパターンはC(N,K)でO(K)で求まるので問題ない 問題は誤ったK人の方が何パターンあるか 組み合わせを頑張ってO(1)とか考えるけど思い浮かばない 樹形図を書いて小さいケースについて実験する k…

問題ページ B - Holes 考えたこと Rがめっちゃでかいのは別に気にしなくてよさそう 穴pに落ちる範囲の面積を求めて面積比を確率として求めるみたいなのを考える 穴pと他の穴qの垂直二等分線を引き、穴pが属する領域の凸多角形を求めるみたいなのをやりたくな…

問題ページ J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder 概要 魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り…

問題ページ C - 倍数クエリ 平方分割はじめてだったので練習として書いた 考えたこと mod m で考えてよさそう 平方分割なことは知ってたので考察をすると各バケツが数字が現れる頻度をもっておくとよさそう まとめてバケツに加算する配列lazを用意しておけば…

問題ページ C - スペースエクスプローラー高橋君 CHTで解いてたけどmonotone minimaで解けるらしいので解くことにした 考えたこと f(i,j) = (i番のキャノンで区画jを破壊するエネルギー) 最小値がどんどん右下に移動していくのはそれはそう monotone minima…

問題ページ D: Driving on a Tree - square869120Contest #4 | AtCoder 全方位木DPに慣れるために解いた 考えたこと 頂点vからどこかの子に移動したら他の頂点vの子には絶対に到達しない d[i] = iを根とする部分木でiからスタートしたときの動く回数の期待値…

問題ページ E: 限界集落 - NJPC2017 | AtCoder うしさんのブログを見て前半2問で全方位木DPを学んだので解説を見ずに解いた 考えたこと 各頂点から最も遠い頂点までの距離を求めて全てDより大きければ到達不可能なので-1 d[i] = 頂点iを根とする部分木で頂点…

問題ページ A - アナログ時計 考えたこと 重なるタイミングがどんなときかとりあえず列挙する 分針と秒針はxx:00:00、xx:01:01とxx:01:02の間、xx:02:02とxx:02:03の間… 時針と分針は00:00:00、01:05:00あたり… 時針と分針は明らかに面倒なのでコードを書い…

問題ページ E - Antennas on Tree 考えたこと 次数が大きい頂点にアンテナを置いても同じ距離の頂点が大量にできるだけなので次数が小さい頂点に置いた方がよさそう 次数が大きいウニみたいなグラフがあったときどうするか考える ウニの中央の頂点に置くのは…

問題ページ D - Forest 考えたこと グラフのつながれている形によってある頂点が使えなくなるといったことはないので形は関係なさそう 各連結成分についてa[i]の集合として考えられそう vectorをマージしていく感じに思えたのでマージテクを調べ始める 小さ…

問題ページ C - Vacant Seat 考えたこと 頂点数が奇数で円環状になっているグラフが2部グラフなわけはないので空席があるのはそれはそう クエリ回数が20回なのでlogオーダーの計算量しかありえなさそう 空席が絶対にある範囲をもって二分探索っぽいことをす…

問題ページ B - Two Arrays 考えたこと 考えるのはa[i]とb[i]の差だけでよい a[i] < b[i] だとすれば a[i]+2, b[i]+1とすれば差が1縮まるので周りの状況にかかわらず絶対に等しく出来る a[i] > b[i] のときは a[j]+2, b[i]+1 (a[j] < b[j]) とする必要がある…

問題ページ G - Coinage 考えたこと どちらか優先すべき文字列を連続して置いたあともう一方を連続して置くべきっぽいので優先すべき文字列を決定する sとtのうち辞書順で小さい方をできるだけ並べたあと残りを埋めればいい気持ちになって出すとWA s="bb", t…

問題ページ F - Capture 考えたこと 尺取りとかするのかと思ったがどこまでで区間を伸ばすのを止めるのかわからない iまで網をかけている状況で[i,i+1]に新たに網をかけたときの利益の増加はv[i] = s[i+1] + (x[i+1] - x[i])になる 数列vの累積和を取れば区…

問題ページ E - White and Blue 考えたこと 全員反対した状態から1人ずつ賛成にしていき条件を満たしたタイミングで判断する 白票が多い順に賛成にしていくコードを書いたらサンプル通ったので投げると落ちる 白が少なくても青が多い人の方を先に賛成にする…

問題ページ D - Shock 考えたこと 頂点1が含まれる連結成分V1と頂点2が含まれる連結成分V2とそれ以外の頂点集合V3に分割して考える V1とV2の頂点が繋がれることはありえない V1とV3をつなげばV2とV3をつなぐのは不可能で逆も同様 V1とV2で要素数が多い方をV3…

問題ページ C - Garden 考えたこと 位置Yがk番目に植えられる花の位置X以上かを判定する問題を考えるとO(N)で解ける 各iについて(Y-w[i])/d[i]+1が位置Yまでに植える花の個数になるのでこの合計がK以上かどうかを見ればよい 上の問題は単調性があるので二分…

問題ページ B - Evergrowing Tree 考えたこと 同じ頂点にたどり着くまで上にたどっていけばよさそう 完全N分木なのでダブリングしなくても上にたどるのは対数オーダー 根を0とすると頂点vの親は(v-1)/Nになる vとwの深さをそろえた後頂点が一致するまでたど…

問題ページ E - Avoiding Collision 解法 ある頂点uから頂点vへの最短経路が何通りあるか求めたい。ある辺(u,v)を最短経路に使う可能性が存在するかどうかは d[u] + cost = d[v] で判定できる。ある無向辺(u,v)が存在したとき最短経路にu→vとv→uの経路を両方…

問題ページ D - People on a Line 考えたこと r[i] と l[i] を繋いでいった連結成分ごとにバラバラに考えてよさそう 各連結成分について1つ値を決めれば残りの値が順番に決めていけそうなので連結成分ごとにDFS 各連結成分ごとに最も左にいる人の位置を0とし…

問題ページ C - 広告 考えたこと ドミノ敷き詰めみたいなbitDPかと思いながら読むと制約的に違う 各連結成分で2部グラフの大きい方を取る気持ちになる→WA よくよく考えると嘘なケースがある 各行ごとに考えると下の行のために看板を置く個数を減らす理由はな…

問題ページ C: Kill/Death - 第4回 ドワンゴからの挑戦状 予選 | AtCoder 考えたこと sample1を読むと5デスを4人に割り振るようなのを求められればよさそうでこれは分割数なのでできる sample2を読むとキル数が違う人ごとにまとめてそれぞれ計算していくとよ…

概要 文字列S(|S|<=50)が与えられる。この文字列から異なる文字の2つ組を取り除く処理を繰り返していき最後に残る可能性のある文字の集合を求めろ。 解法 文字cが最後に残る可能性があるかどうかについて考える。文字c以外を全て消せるかどうか判定できれば…

問題ページ C - ABCAC 公式解説のaとcを高速に求める方法について 解法 aとcをそれぞれ求めたあと a>0 && c>0 && a+c>=|y| を満たしていればABCACが構成できる文字列ABCの組み合わせは a+c-|y|+1 通りある。 SAとlcp配列とRMQ SAとlcp配列を構築する。rank[s…

問題ページ C - 部門分け 考えたこと O(N!)すれば部分点40点ははい 部門数とか何か条件を決め打てばスコアが一意に定まるみたいなのを考える 部門数M = N からはじめてもっともスコアが上がる方法で M = N-1 につなぐ貪欲→明らかにだめなパターンが存在 すで…

問題ページ D - 2017-like Number 考えたこと f(A) = (1からAのうち条件を満たす数) とすれば f(r) - f(l-1) として計算できるのでf(A)を前計算する 10^5までの素数をエラトステネスの篩で列挙して、条件を満たす数を1~10^5までで探せばよさそう 条件を満た…

問題ページ C - Special Trains 考えたこと 乗れる電車のうち一番はやい電車に貪欲に乗っていけばよさそう t秒目に駅に来た時 s + k*f >= t を満たす最小のkの電車に乗ればいい 変形すると k >= (t-s)/f k = max(0, ceil*1と決定できるのであとは貪欲にえい …

問題ページ C: 節約生活 - AtCoder Regular Contest 007 | AtCoder 考えたこと 愚直に全探索するとO(N^N)になりそう 多少枝刈りできそうだし10^10なら通るのでは？と思って投げるとTLEじゃなくてWA 全てのテレビが付くまでは視聴できない時間が合ってもいい…