ferinの競プロ帳

競プロについてのメモ

競技プログラミング

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をする。遷移に必…

tco2017 Pittsburgh Regional round med

概要 数列のどの要素の3つ組を取っても和が9の倍数とならないような最大の部分集合の大きさを求める。 考えたこと コンテスト中の誤った思考を書いてるだけ。 与えられる数列の要素は200以下なので3乗くらいまでできそう。試しに9の倍数になる3つ組を全列挙…

AOJ 0530 Pyon-Pyon River Crossing

問題ページ ぴょんぴょん川渡り | Aizu Online Judge 考えたこと 制約が色々小さくて最小コストを求めるので拡張dijkstraやDPを考える。 dp[i][j][k] = (i行目j列目まででk回一行飛ばしをしたときの最小滑りやすさ) としてDPを考えるとO(NMmax(k)^2)で計算量…

AOJ 0596 Taxis

問題ページ タクシー | Aizu Online Judge 考えたこと 最短距離と言われたのでdijkstraを考える。遷移先が距離r[i]以下の頂点であるdijkstraをすればよさそう。全頂点からそれぞれdijkstraをしてある頂点から距離がr[i]以下の点を全列挙しておけば、あとはdi…

AOJ 0580 Fish

問題ページ 魚の生息範囲 | Aizu Online Judge 考えたこと 3次元imosすればよさそうだけど制約的に無理。領域木とかを考えてもわからないので解説を見たらただの座圧ではい。O(N4)で解ける これくらいは思いつきたかった… //#define __USE_MINGW_ANSI_STDIO …

AOJ 0537 Bingo

問題ページ ビンゴ | Aizu Online Judge 考えたこと N2要素で要素の値は1以上M以下、要素の合計がSの狭義単調増加な数列が何通りあるか求めればいい。 dp[i][j][k] = (i番目までで最大の要素がjで合計がkの数列の通り数) としてDPしようとしたが遷移のうまい…

Codeforces Round #431 (Div. 2) D. Rooter's Song

問題ページ codeforces.com 解法 まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全…

Codeforces Round #431 (Div. 2) C. From Y to Y

問題ページ codeforces.com 考えたこと 構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。 まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら…

Codeforces Round #431 (Div. 2) B. Tell Your World

問題ページ Problem - B - Codeforces 考えたこと 頂点を二つに分類してそれぞれの頂点群が直線上に乗っていて各直線が平行であるかを判定すればよさそう。 まず、頂点1とiを2頂点として選ぶ。この2頂点を通る直線を一本目として考える。この直線上にない頂…

Codeforces Round #431 (Div. 2) A. Odds and Ends

問題ページ Problem - A - Codeforces 考えたこと 問題を読むと普通に思い浮かばない。奇数が連続してるところで切れる(奇数個の要素になるところでしか切れないので嘘)のでその数を数えればいいという謎の思考をする。 終了30分前にhackされる。ちゃんと…

summerFestivalContest EEEEndless gamEEEE

問題ページ Hamako Online Judge 考えたこと ゲーム系の問題でN個の石の山と言われればまあgrundy数を思い浮かべる。 0個の状態のgrundy数を0としてgrundy数を求められれば解けそう。神通力についてはXORを取った結果が0なら何もしない、XORを取った結果と等…

summerFestivalContest Treasure Hunt

問題ページ Hamako Online Judge 罠 n回加算すべき崖と崖の間の道を一回分しか加算していなかった。 学び 3分探索の分割でx1=x0+(x3-x0)/3, x2=x0+(x3-x0)*2/3と書いていたがx1=(x3+2*x0)/3, x2=(2*x3+x0)/3で書ける。 解法 橋がある座標をそれぞれx_1, x_2…

summerFestivalContest StringGuessing

問題ページ Hamako Online Judge 考えたこと 問題を開いたタイミングでコンテストが残り20分だったのでササっと部分点を拾えないか考える。 1文字目から順番に1文字ずつ二分探索で決定していくとすると、1文字あたり多くとも5回でできそうでだんだん必要な回…

summerFestivalContest Dragon Curve

問題ページ Hamako Online Judge 考えたこと 今年のICPC国内予選の問題を思い出す。Nが大きいし左右ににぶたんしていってO(logN)かなあと思う。 実際に折ったりしてN=4くらいまでどうなってるか書き出してみる。 今までに折ったもの + 谷 + 今までに追った…

summerFestivalContest TakoyakiPicking

問題ページ Hamako Online Judge 解法 左から順番に加算していって合計/2になれば可能、それ以外なら不可能

SRM 613 div1 easy TaroFriends

概要 太郎くんの友達がいる位置が1次元座標として与えられる。友達はそれぞれ1回、左か右にX動かなければならない。最長の友達の距離を最小化する。 考えたこと とりあえず入力をソートして考える。最初任意の回数移動できるのかと思い距離Dを達成できるかを…

SRM 612 div1 easy EmoticonsDiv1

考えたこと dp[i] = (i個をつくるのにかかる回数)としたO(n^2)のDPを投げたらシステスで落ちた。 解説読んで状態に(テキストの数、クリップボードの数)を取るdijkstraを書いた。

SRM 610 div1 easy TheMatrix

考えたこと この間のARC080Fとか最大長方形とかを思い出す 制約を見たらh,w 二次元累積和っぽく実装したら通った かなり簡単目だったのかO((HW)^2)が嘘解法だったのか…? 解法 (x, y)を左上、(w-1, h-1)を右下とする各長方形について、条件を満たす長方形を…

SRM 609 div1 easy MagicalStringDiv1

考えたこと ><><>'の数-' 罠 誤読 解法 i番目までの'>'の数を前から、i番目からn-1番目までの' ans = max(i番目までの'>'の数, i+1番目からn-1番目までの'

SRM 608 div1 Easy MysticAndCandies

考えたこと まず適当に箱を選んだ時その選び方が条件を満たしてるかの判定について考える 選んだ箱のlowの和をlsum、選んでない箱の和をhsumとする C-lsum-hsumが正ならその分選んだ箱のキャンディーの最低数が増える max(C-lsum-hsum, 0) + lsum >= X とな…

SRM 607 div1 easy PalindromicSubstringsDiv1

考えたこと 長さ5000以下なのでO(|S|^2)までいけそう dp[i][j] = (i番目までの文字列で長さjの回文がつくれる確率)を考える 区間[i+1, j)が回文かどうか前計算で求めておくのをとりあえず実装してみる この実装をしてたら幅が小さい方から埋めていくDPを最…

ARC 081 E - Don't Be a Subsequence

問題ページ arc081.contest.atcoder.jp 解法 まず、dp[i] = (区間[i, s.size())の部分文字列に含まれない最短の文字列の長さ)としたDPを考える。文字cがi番目以降ではじめて現れる位置をnext(i, c)と表記することにすると、このDPはdp[i] = min{dp[next(i, …

Codeforces Round #429 (Div. 2) 考察

コンテスト中に考えてたことをまとめてみることにした。解法解説とはちょっとちがうかも? 覚えてる範囲なので時間はずれてるかも? ~00:03 Aを読むと、各文字の出現頻度を数えてKと比べればよさそう。ささっと実装したらpretest通った~00:10 Bの読解が難…

Codeforces Round #429 (Div. 2) C. Leha and Function

問題ページ Problem - C - Codeforces 概要 関数 F(n, k)を次のように定める。 集合{1,2,…,n}からk要素を選んだ部分集合を全て列挙する。各部分集合の値をその部分集合の最小の要素の値とするとき、この値を平均をF(n, k)とする。 \sum F(a[i], b[i]) が最大…

Codeforces Round #429 (Div. 2) A. Generous Kefa

問題ページ Problem - A - Codeforces 概要 n個の風船をk人の子供に配る。同じ子供に同じ色の風船を二つ以上配らないように全部の風船を配ることが出来るか 解法 各色の出現数の最大がk以下ならYes, そうでないならNo

Codeforces Round #200 (Div. 1) D. Water Tree

問題ページ Problem - D - Codeforces 概要 頂点1が根のn頂点の木が与えられる。q個のクエリを処理する。 クエリ1 頂点vとvの子孫の頂点の値を1にする クエリ2 頂点vとvの先祖の頂点の値を0にする クエリ3 頂点vの値を出力する 解法 部分木に関するクエリな…

Educational Codeforces Round 6 E. New Year Tree

問題ページ Problem - E - Codeforces 概要 n要素の根が1の木が与えられる。m個のクエリを処理しろ。 クエリ1 頂点vの部分木の頂点の色をcに変更する。 クエリ2 頂点vの部分木に含まれる色の種類を求める 解法 部分木に関するクエリを処理するのにオイラーツ…

hackerrankのGame Theoryを解いたまとめ

ゲーム系問題があつまっている。 https://www.hackerrank.com/contests/5-days-of-game-theory/challengesgrundy数とかNimとかの勉強によかった。 Game of Stones 2人のプレイヤーがいて各ターンで2,3,5個の石を取り除く行動ができる。行動できなくなったら…

Croc Champ 2013 - Round 1 E. Copying Data

問題ページ Problem - E - Codeforces 問題概要 数列a, bが与えられる。次の2種類のクエリを処理する。 1. b[y+q] = a[x+q] ( 0 2. b[x]を表示する 解法 区間更新の遅延セグメントツリーを使う。遅延更新用の配列に更新する配列aのインデックスとの値の差を…

codeforces #261 div2 D. Pashmak and Parmida's problem

問題ページ Problem - D - Codeforces 概要 数列aが与えられる。f(l,r,x) を l 解法 まず、f(1, i, a[i])を計算する。それぞれの要素の個数を数える配列を用意して順に計算していけばよいが、a[i] b[i]>c[j]となるような(i,j)の組の個数を求めればいい。BIT…

codeforces #207 div1 A. Knight Tournament

問題ページ Problem - A - Codeforces 解法 [l_i, x_i)、(x_i、r_i]の区間でまだ誰にも負けていない兵士がいればその兵士はx_iに負けたとして更新していけばよさそう。すでに負けた、負けていないを管理するのが大変そうだったのでクエリを逆に読んで、管理…

cf #427 div2 D. Palindromic characteristics

問題ページ Problem - D - Codeforces 問題概要 k-palindromeを以下のように定義する。 文字列の左半分と右半分が空文字列ではなく一致している 左半分と右半分がともに(k-1)-palindromeである 1-palindromeは通常の回文と同様である。 文字列sが与えられる…

cf #427 div2 C. Star sky

問題ページ Problem - C - Codeforces 解法 t秒目での各星の明るさは(s[i]+t) % (c+1) で求められる。星の明るさは周期c+1で同じものが現れるのでc+1回分2次元累積和を取っておいて各クエリにO(1)で答える。同じ地点に複数の星が存在するケースがあることに…

cf #426 div2 C. The Meaningless Game

問題ページ Problem - C - Codeforces 考えたこと 色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。 gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。 立法数判定だけな…

cf #426 div2 B. The Festive Evening

問題ページ Problem - B - Codeforces 解法 各文字について最初に現れるタイミングと最後に現れるタイミングを調べてimosする。

cf #426 div2 A. The Useless Toy

問題ページ 解法 操作には周期4の周期性があるので周期性を使って判定する。

ARC079D Decrease (Contestant ver.)

問題ページ D - Decrease (Contestant ver.) 解法 n=50で考える。 k=0のとき 49 49 49 … 49 とする。 k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48 k=2でも同様に 98 98 47 47 … 47 これを繰り返していくと、 k = 50 で 50 50 50 … 50 k =…

ARC079 C Cat Snuke and a Voyage

問題ページ C - Cat Snuke and a Voyage dijkstraで殴った