主食は米

主に競プロ備忘録

AtCoder

CODE FESTIVAL 2018 qual A C - 半分

問題 解法 関連した以下のような簡単な問題について考える. n個の0があり,K回だけ 0<=i < n なるa_i を+1 する操作を行う. 数列は何通りできるか. これは以下のようなO(NK) の DPで解くことができる.(普通にコンビネーションでも解ける) def : dp[i][j] := (…

AGC 027 B - Garbage Collector

問題 解法 本番中の考察 何回原点に戻ってくるかでXの係数が変わるのでこの回数を決めうちして1回O(N)でやったら部分点取れそう 部分最適構造( [l,r) 間のごみの最適なとり方が x=l,..,r として [l,x),[x,r) の最適なとり方を各々やってきたうちコスト最小の…

codeFlyer 2018 final C - 部分文字列と括弧

問題 問題概要 '(' と ')' のみからなる文字列Sがある. 1 <=i < j <=|S| で, S[i :j] が対応が取れているのは何組あるか. 1 <= |S| <= 105 思考と反省 考えたこと 構文木作れば k 個の子を持つ親を見つける度に kC2 足していけば出来る -> 再帰で実装しよう …

みんなのプロコン2018 決勝 A - Uncommon

問題 問題概要 自然数N,M と 数列 {a_i} (0 <= i < N) が与えられる. 各 j = 1, ... ,M について, jと互いに素なa_iの要素の数を求めよ. 1 <= N,M,a_i <= 105 解法 各jについて, 互いに素でない <-> 共通因数を持つ a_i の数を考えることにしよう. j = 5 の…

ARC 098 E - Range Minimum Queries

問題 問題概要 サイズNの数列からサイズKのsubarrayを選び,subarrayのminを取り除く試行をQ回行う. 取り除いたminのうちの max - min をminimizeするように試行を行った時のminを求めよ. 1 <= N <= 2000, 1 <= a_i <= 109 解法 思考箇条書き 単純に小さい順…

codeFlyer 2018 予選 D - ハンコ

問題 問題概要 NM のハンコをハンコがマスに収まるような範囲の全ての場所でHW のマスに押す. ハンコで黒く塗られるのは何箇所か求めよ. 1 <= N,M <= 103 ,1 <= H,W <= 109 解法 まず for(ハンコを押した回数) for(ハンコの全てのマス)のループの順序を入れ…

codeFlyer 2018 予選 C - 徒歩圏内

問題 問題概要 昇順に並んでいる数列{x_i} (1<=i<=N) が与えられる. (i, j, k) , (i < j < k) の組で, x_j - x_i <= D x_k - x_j <= D x_k - x_i > D を満たす組の総数を求めよ. 3 <= N <= 105 解法 補集合を考える. x_j - x_i <= D, x_k - x_j <= D を満た…

AGC 025 B - RGB Coloring

問題 問題概要 ブロックに0,A,B,A+Bのいずれかの得点をつけることができる 合計Kの得点をつける塗り方をmod 998244353で求めよ. 1 <= N,A,B <= 3105, 0 <= K <= 181010 解法 単純にDPを立てると,状態がO(NK)とかになってしまうので間に合わない. ここで問題…

ARC 097 E - Sorted and Sorted

問題 問題概要 1~Nの数字が書かれた白のボールと黒のボールがN個ずつ,合計2N個ある. 白と黒それぞれに注目した時,どちらも順番通りに並んでいるようにするには最低何回のswapが必要か. 1 <= N <= 2*103 解法 考察段階から箇条書き 最終状態が決まるとそのswa…

ARC 081 F - Flip and Rectangles

問題 問題概要 0,1が書かれているh*wの盤面がある. 行または列を全て反転する操作が何回でもできるとして, その中の要素が全て1であるような長方形の最大の面積を求めよ. 解法 ここの方法がわかりやすかったのでこれでやった. ex. 盤面 1 0 1 0 1 0 1 0 1 1 …

ARC 092 D - Two Sequences

問題 問題概要 N要素の数列{a_i}, {b_i} が与えられる. Xor_(1<=i,j<=N) (a_i + b_i) を求めよ. 解法 a_i + b_j のkビット目の1の数の偶奇を考える. x + y = ( x & y ) << 1 + ( x xor y ) から, (a_i , b_j のkビット目の立っている数) * N + (k-1ビット以…

AGC 022 C - Remainder Game

問題 問題概要 N要素の整数列{a_i}を以下の作業を繰り返して{b_i}に一致させる. - いくつかの要素を選び, a_i をa_i % k に変化させる. その際いくつ選んだかに関わらず コスト2kを払う 必要な最小コストはいくらか. 1 <= a_i, b_i, N <= 50 解法 a_i から a…

AGC 022 B - GCD Sequence

問題 問題概要 サイズN, 各要素が30000以下の次の条件を満たす数列を求めよ. - 全ての要素のgcdは1である(全ての要素が互いに素ということではない) - 全要素の和をSとして,全てのiに対して gcd(a_i, S-a_i) != 1 解法 gcd(a_i, S-a_i) != 1 <-> gcd(a_i, S)…

ARC 073 E - Ball Coloring

問題 問題概要 N組の計2N個の整数x_i,y_iを赤/青に分けていく. (Rmax - Rmin) * (Bmax - Bmin) を求めよ. 1 <= N <= 2*105, 1 <= x_i,y_i <= 109 解法 全体のmax,minであるma = max_i(max(x_i,y_i)), mi = min_i(min(x_i,y_i) は必ずR/Bに塗られているため, …

ARC 093 E - Bichrome Spanning Tree

問題 問題概要 N頂点M辺の重み付き無向グラフと整数Xが与えられる. この辺を2色に塗っていく. 次の条件を満たす辺の塗り方の数をmod 1e9+7で求めよ. - 2色どちらの色も含む全域木が存在して,そのような全域木の最小コストがXである. 1 <= N <= 103, 1 <= M <…

ARC 083 E - Bichrome Tree

問題 問題概要 1が根であるN頂点の根付き木が与えられる. また数列{x_i} (i=1..N) が与えられる. 木に白/黒と非負整数を割り振り,自身を含めた子に含まれる自身と同じ色の頂点の数の総和がx[i]であるようにしたい. そのように割り振ることはできるか. 解法 …

UTPC2014 D - ラボライブ タフグローバルフェスティバル

問題 解法 M=1,2 の場合は容易に解ける. 以降ではM=3とする. まず下準備として押す場所で同じ場所が連続して来る場合は結合して一つの区間にしておこう. とりあえず一番近い指を使う貪欲を考えてみると, p1 <--> 指1 <-> p2 <--> 指2 <-> 指3 , s1=2, t1 = s…

AGC 021 B - Holes

問題 解法 前提知識: 凸包 (ググればいっぱい出てくる) Rが十分に大きいので数学的にINFだとして考察していく. 各点に落ちるような領域は与えられた二点の全ての組を取った垂直二等分線で区切られる(ボロノイ図と言うらしい) R=INFなので,この領域が有限領域…

ARC 068 E - Snuke Line

問題 問題概要 N個の区間[l_i,r_i],自然数Mが与えられる. 1 <= d <= Mについて,dの倍数を含む区間はいくつあるかそれぞれ答えよ. 1 <= N <= 3*105, 1 <= M <=105 解法 まず,各dについてr_i - l_i >= d-1 となる区間は必ず倍数を含む. よって r_i - l_i でソ…

ARC 060 E 高橋君とホテル

問題 問題概要 直線上のN個の点x_iが与えられる. 1回に合計距離Lまでの点から点への移動が可能として, 以下のQ個のクエリを処理せよ. - a,b間の移動には何回移動が必要か 1 <= N <= 105, 1 <= Q <= 105 解法 r[i][k] := (iから2k回正方向に移動してたどり着…

Typical DP Contest H - ナップザック

問題 問題概要 N個の荷物の重さwi,価値vi,色ciが与えられる. 重さW以下,色C色以下で達成できる最大価値を求めよ. 1 <= N <= 100,1 <= W <= 105, 1 <= C <= 50 解法 dp(i,j) := (i色以下,重さj以下で持てる最大価値) としてdp(i,j)を更新していく. w,vは色ご…

ARC 058 E - 和風いろはちゃん / Iroha and Haiku

問題 問題概要 整数N,X,Y,Zが与えられる. 整数1〜10から成り,XYZを含む要素数Nの数列をmod1e9+7で求めよ. なお{a_i}がXYZを含むとは sum(x<=i

ARC 081 E - Don't Be a Subsequence

問題 問題概要 英小文字から成る文字列Sが与えられる. Sの部分列でないような最短の文字列を求めよ. ここでS'がSの部分列とは S'[i] = S[a_i] (1<=i<=|S'|) なる単調増加なa_iが存在するものとする. 解法 まず,S[i,N)で一番最初に出てくる文字j(j='a'〜'z')…

第3回ドワコン予選 D - ネタだけ食べたい寿司

問題 問題概要 {X_i},{Y_i} (0<=i<N, X_i > Y_i) と自然数Mが与えられる. 各i についてX_i,Y_i を選んでいく. ただし,X_iを選べるのはM回までで,i<N-1でM回選んでしまうとそれ以降のY_iは得られない. 得られる合計を最大化せよ. 1 <= N,M <= 105 解法 まず, M>=Nのケースは全てX[i]を選べば良い. その他のケースについて,Z[i] := [0,i) で得られるM-1個以下の和の最大値 とする. </n-1でm回選んでしまうとそれ以降のy_iは得られない.></n,>…

みんなのプロコン 2018 C - 駆引取引

問題 問題概要 Nターンのゲームをする. 値段x[i],価値v[i],費用c[i] が与えられる. 先手は前からx[i]を売るか,それまで得た値段を払ってmax_(i in {1..N})(v[i])を得てゲームを終了する. 後手は先手の価値を最小化するように価値を取り除く 先手の最大スコア…

天下一2016 予選B C - 天下一プログラマーコンテスト1999

問題 問題概要 N人で総当たり戦を行う. 勝ち数が同じ場合はindexで順位をつける. Pの確率で結果を間違う時,元どおりの順位となる確率を求めよ. 解法 solve(i,j) := [i,N)が正しい順位で,i人めがj勝の確率 としてメモ化再帰. 答えはsolve(0,N-1)になる. m勝n…

みんプロ2017 B - チーム決め

問題 問題概要 {a_i} (1 <= i <= N), {b_i} (1 <= i <= M)が与えられる. 各数列からK個選んで,昇順に並べた時のmax_(1 <= i <= K) (abs(a_i - b_i))を最小化せよ. 1 <= N,M,K <= 105, 1 <= a_i,b_i <= 109 解法 二分探索する. l = -1としないと X = 0とでき…

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

問題 問題概要 グリッドが与えられる. '.'には広告を置くことができる.また広告は隣り合わないようにしたい. 置ける最大数を求めよ. 1 <= H,W <= 40 解法 グリッドグラフは二部グラフとみなせる. すると二部グラフの最大独立集合を求める問題に帰着できる. …

SoundHound Inc. Programming Contest 2018 (春) D - 建物

問題 問題概要 HxWのグリッド,各グリッドに報酬p[i][j], コストc[i][j]が与えられる. 各グリッドに移動すると初回でp[i][j]が得られ, 毎回c[i][j]かかる. (i,j) -> (i+1,j), (i,j)+1, (i,j-1) への移動が可能であるとして(H,j) (1<=j<=W)に最終的にいる時の…

ABC 014 D - 閉路

問題 問題概要 N辺の木が与えられる. aとbを繋いだ時にできる閉路の長さを出力せよ,というQ個のクエリに答えよ. 1 <= N,Q <= 105 解法 典型的なLCAの練習問題. a,b間に閉路を作った時, depth[a] + depth[b] - 2 * depth[lca(a,b)] + 1 の長さとなる. メモ ab…