ferinの競プロ帳

競プロについてのメモ

競技プログラミング

AGC005 C - Tree Restoring

問題ページ C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder 解法 まず、max(a[i]) = Xの距離のグラフをつくることを考える。このグラフをつくるのに * Xが偶数のとき 距離がX/2の頂点が1個、X/2+1~Xまでの頂点が2個ずつ必要 * Xが奇数のとき 距…

ARC069 E - Frequency

問題ページ E: Frequency - AtCoder Regular Contest 069 | AtCoder 解法 辞書順最小なのでその時点で追加できる最小のものを追加していくようにする。 0 1 2 3 4 5 6 7 8 9 1 2 1 3 2 4 2 5 8 1 -> 8が3(=(8-5)*(8以上の数の個数))回追加 (最大の石の数は8)…

SRM625 div1 easy PalindromePermutations

解法 まず、回文が存在する条件として * それぞれの文字種の個数が全て偶数 * 一つの文字種だけ奇数でそれ以外は偶数 のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。 cnt[i]…

SRM624 div1easy BuildingHeights

考えたこと 題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。 dp…

SRM623 div1easy UniformBoard

考えたこと PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。 ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換える…

SRM621 div1 easy RadioRange

考えたこと 中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが (2円が外接する半径r_1)<= r < (2円が内接する半径r_2)の条件を満たすときと言い換えられる。 r_1 = max(0, sqrt(XX+YY)) (円の中に(…

SRM619 div1easy SplitStoneGame

考えたこと ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに…

SRM618 div1 easy Family

考えたこと サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。…

SRM617 div1 easy MyLongCake

概要 長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ…

Tenka1 Programmer Contest C - 4/N

問題ページ C - 4/N 考えたこと 何かうまい構成方法でO(1)?と思ったがよくよく考えると全探索できる。誤差死とオーバーフローに気をつけつつ算数をすると通った。 時間かけすぎで反省。 解法 hとnを決めるとwは一意に決まるのでO(35002)の探索をする #inclu…

Tenka1 Programmer Contest D - IntegerotS

問題ページ D - IntegerotS 考えたこと ナップザック問題っぽさを感じる。Kをそのまま配列に持つのは無理なのでbitが立ってる本数を配列に持つのかなあと考えるがうまくいきそうにない。 いろいろ実験してるとKのある桁を1から0にしたとき、それ以下の桁は全…

Tenka1 Programmer Contest E - CARtesian Coodinate

問題ページ E - CARtesian Coodinate 解法 解説を見た。 https://img.atcoder.jp/tenka1-2017/editorial.pdf www.youtube.com まず、N点からのマンハッタン距離の和が最小になる点について考える。マンハッタン距離はx座標、y座標それぞれ独立に足すことがで…

ARC039 C - 幼稚園児高橋君

問題ページ C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder 考えたこと 解説を見た。 4方向の近傍だけ持ってればよくて通ったところとその近傍しか情報いらないからmapでうまく持てばO(KlogK)で解ける。linked listを思い出しつつバグらせない…

AOJ 2429 marukaite

問題ページ marukaite | Aizu Online Judge 考えたこと 解説を見た。 最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)…

SRM 712 div2 med RememberWordsEasy

考えたこと O(max(d_1,d_2)max(w_1,w_2))で愚直にDPするのは無理。考察の方針が思い浮かばなかったのでとりあえず手で試してみる。区間の端を0単語とすると1~d1までの和の単語数までは全て実現することが可能そう。区間の端を決め打ってその区間で実現でき…

education week MM ConstrainedPermutation

問題ページ TopCoder MMはじめたいなーと思ってchokudai contest 001をやったりしていたらeducation week MMというなんともピッタリなものが開催されるらしいのでもちろん参加することに。 初日 16:00 問題を読み始める。日本語訳のmarkdownをつくって問題の…

JAG夏合宿2017参加記

初日 歩いていたらICPCの話をしている人がいておーとか思いながらオリセンに向かう。早く着いてしまって暇だったたのでtwitterリストを作りながらチームメンバーを待つ。周りの人々がみんなレッドコーダーに見えてこわい。 チームメンバーと合流した。2人し…

chokudai contest 001

問題ページ Tasks - Chokudai Contest 001 | AtCoder 唐突にマラソンがやりたくなったのでジャッジが公開されているマラソンのchokudai contest 001を試しにやってみることにした。 6:46 問題を読む グリッドゲーで操作にかかる手数をできるだけ小さくしたい…

ABC074 D Restoring Road Network

問題ページ D - Restoring Road Network 考えたこと 問題を読むとワーシャルフロイドの逆をやるらしい。それぞれの頂点間にA[i][j]の長さの辺があるのを初期状態として、どの辺を減らせるかといった方針で考える。i->k->jと移動した時、A[i][j]と同じコスト…

SRM616 div1 easy WakingUp

考えたこと とりあえず周期性がありそう。全てのアラームが鳴るタイミングまで進めばあとは周期lcmで繰り返されそう。10以下の整数のlcmは5*7*8*9=2520で計算量的には問題なさそう。周期の部分が負なら必ず起きそうなので-1を返すことにする。サンプル3で全…

SRM615 div1 easy AmebaDiv1

考えたこと Xに含まれないサイズはそのサイズを初期サイズとすれば最終サイズも等しくなるので必ずSに含まれる。Xに含まれるサイズを全て試せばいい。 実装したら通った。ものすごい簡単で逆に驚いた。 // BEGIN CUT HERE // END CUT HERE //#define __USE_M…

SRM614 div1 easy MinimumSquare

概要 xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。 考えたこと x座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせた…

AOJ0633 ぬいぐるみ

問題ページ Plush Toys | Aizu Online Judge 解法 bitDPをする。dp[S] = (集合Sの要素に含まれる種類を左から並べたときの最小の並べ替え回数) とする。dp[S|1<<i] = dp[S] + (並び替えに必要な回数) と遷移できる。並べ替えに必要な回数は並べる区間に含まれていない種類iの個数なので、種類別に累積和を取っておけばO(1)で求めることができる。したがってO(M2^M)で解ける。 //#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; t…</i]>

JOI2008 春合宿 Cheating

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf 考えたこと 最大の最小化と言われたので二分探索をする。幅Xで実現することができるかの判定について考える。x方向、y方向についてそれぞれ貪欲に決めていくと幅Xで必要な…

JOI2008 春合宿 sheet

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと 色iが色jの上に乗っていることをjからiへの有向辺が張られている状態と考えるとトポロジカルソートをすればよい。O(HWN)で辺を張ればよく、トポロジカルソート…

JOI2008 春合宿 Committee

問題ページ http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf 考えたこと N頂点の木で値の総和が最大になるような連結成分を求めればいい。dp[i] = (頂点iの部分木で最大の値の総和) とするとdp[i] = sum(dp[j], 頂点jが頂点iの子でdp…

AOJ0616 JOI公園

問題ページ JOI 公園 | Aizu Online Judge 考えたこと とりあえず広場1から各広場への最短距離はdijkstraで求まる。Xを決めれば各辺について両端の頂点への最短距離がX以下かどうかでその辺が撤去される辺か判断できるのでO(M)でできる。max(X) = 10^10 でま…

AOJ0600 バームクーヘン

問題ページ バームクーヘン | Aizu Online Judge 考えたこと 最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認す…

AOJ0562 JOI国のお買い物事情

問題ページ JOI 国の買い物事情 | Aizu Online Judge 解法 最短経路問題で始点が複数あるパターンなので始点をまとめる架空の頂点をつくってやればdijkstra一回で各頂点への最短距離がわかる。各頂点への最短距離がわかっていれば各辺のどの位置が最短距離が…

AOJ0550 お菓子の分割

問題ページ お菓子の分割 | Aizu Online Judge 解法 いかにもDPの雰囲気があるのでDPを考える。AくんとBくんでお菓子を分け合うとして dp[k][i][j] = (k番目まででAくんがi個取って最後に取ったのがAくんならj=0、Bくんならj=1) とおいてDPをする。遷移に必…