ferinの競プロ帳

競プロについてのメモ

AtCoder

AGC021 B - Holes

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

KUPC2012 J - 刺身

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

「みんなのプロコン」本選 2017 C - 倍数クエリ

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

COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君

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

square869120Contest #4 D - Driving on a Tree

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

NJPC2017 E - 限界集落

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

第4回 ドワンゴからの挑戦状 本選 A - アナログ時計

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

APC001 E - Antennas on Tree

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

APC001 D - Forest

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

APC001 C - Vacant Seat

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

APC001 B - Two Arrays

問題ページ 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]) とする必要がある…

Code Festival Team Relay G - Coinage

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

Code Festival Team Relay F - Capture

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

Code Festival Team Relay E - White and Blue

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

Code Festival Team Relay D - Shock

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

Code Festival Team Relay C - Garden

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

Code Festival Team Relay B - Evergrowing Tree

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

ARC090 E - Avoiding Collision

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

ABC 087 ARC 090 D - People on a Line

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

SoundHound Inc. Programming Contest 2018 (春) C - 広告

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

第4回 ドワンゴからの挑戦状 予選 C - Kill/Death

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

SRM627 div1 Easy HappyLetterDiv1

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

ARC055 C - ABCAC

問題ページ 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…

ARC056 C - 部門分け

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

ABC084 D - 2017-like Number

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

ABC084 C - Special Trains

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

AtCoder Regular Contest 007 C - 節約生活

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

ARC005 C - 器物損壊!高橋君

問題ページ C - 器物損壊!高橋君 考えたこと N回見た拡張dijkstra d[y][x][何回壊したか] = (最短距離) でdijkstraをする #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; #define FOR(i, a,</vi></int></bits/stdc++.h>…

ARC004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題ページ C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi ) 考えたこと 数式を書いてみると X/Y = (N(N+1)/2 - M) / N N = Y/2, M = (Y^2+2Y-4X)/8 N,Mが整数かつN < Mの条件を満たすような(X, Y)の組を探す N<Mの条件を満たす間(X, Y) (2X, 2Y) (3X, 3Y) … について探索していく これで出すとTLEしたのでMがマイナスになる部分を枝刈りする (kY)^2 + 2kY - 4kX > 0 を満たすように整数kを選ぶ k =</mの条件を満たす間(x,>…

ARC 003 C - 暗闇帰り道

問題ページ C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder 考えたこと 最小の最大化なので2分探索をする 経路の明るさvを達成できるかどうかをO(HW)くらいで判定できればよさそう d[y][x] = (座標(y,x)に到達できる最短の時刻t) としてdijkstraを…