ferinの競プロ帳

競プロについてのメモ

2015 ICL, Finals, Div. 1 J. Ceizenpok’s formula (nCk mod m の求め方)

問題ページ Problem - J - Codeforces 概要 nCk mod m を求める。 1 <= n <= 10^18, 0 <= k <= n, 2 <= m <= 1000000 考えたこと JAG夏合宿で見た問題 パット見nCk mod m求めるいつものやつだ!と思って制約を見たら真顔になった n, kが大きすぎるのでn, kま…

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

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

SRM 636 div1 easy ChocolateDividingEasy

解法 二次元累積和を計算しておくと矩形の範囲の値の総和をO(1)で計算できる。あとは切る位置を全通り試すO(H^2W^2)をすればよい。 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typed</ll></vi></int></bits/stdc++.h>…

SRM635 div1 easy SimilarRatingGraph

解法 i,jから始まる部分列について同型である直線の長さを考える。各区間について傾きが等しく、比率が等しいならば同型であると判定できる。 i+k→i+k+1、j+k→j+k+1の線分について傾きが等しく、day[i+k+1]-day[i+k] と day[j+k+1] - day[j+k] の比率が等し…

SRM634 div1 easy ShoppingSurveyDiv1

概要 M種類の品物を売っている店でN人の人が買い物に来た。同じものを2つ以上買った人はいない。商品iが売れた数はS[i]である。このとき、K個以上の商品を買った人を大口顧客と呼ぶ。このとき、大口顧客の最少人数を求めろ。 解法 できるだけ大口顧客の数を…

SRM632 div1 easy PotentialArithmeticSequence

概要 正の整数列であるaがある。aは与えられず、d[i] = (a[i]の末尾の0が連続する数) である数列dが与えられる。この数列の部分列で、a[i]が1ずつ増加していく部分列はいくつ存在するか求めろ。 解法 2^6 = 64、n <= 50 から部分列においてd[i] = 6が二つ以…

SRM631 div1 easy TaroJiroGrid

概要 各マスが黒か白に塗られているn*nの二次元グリッドが与えられる。同じ色がN/2マスより長く連続している列が存在する時、そのグリッドはだめなグリッドである。操作を繰り返すことでだめなグリッドを解消したい。このとき最小の操作回数を求めろ。なお、…

SRM630 div1 easy Egalitarianism3

概要 n頂点の重み付きの木が与えられる。集合の任意の2頂点の距離が等しくなるような頂点集合のうち、集合の要素数の最大を求めろ。 解法 ある頂点を根とした木で根からの距離を考える。根からの距離が等しい2頂点a, bでaとbのLCAが根であるような頂点であれ…

SRM629 div1 easy RectangleCovering

概要 holeH、holeWの大きさの穴を複数の板を使って塞ぐ。板iの大きさはboardH[i]、boardW[i]である。板は重なっても良いが全ての角が穴の外に位置していなければならない。このとき塞ぐのに必要な最小枚数を答えろ。不可能なら-1を答える。 解法 holeH >= bo…

SRM628 div1 easy DivisorsPower

概要 d(n) = (nの正の約数の個数)、h(n) = n^d(n)とする。x = h^-1(n) を求めろ。複数存在する場合は最も小さいものを求めろ。 解法 d(x) として使われうる値は20程度までしか存在しない。d(x)を決め打って、そのd(x)のときh^-1(n)が存在するか考える。nのm…

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を…

AtCoder Regular Contest 088 E - Papple Sort

問題ページ E: Papple Sort - AtCoder Regular Contest 088 | AtCoder 解法 文字列Sに文字aが11個存在すれば左の5個は回文の左半分に属し、右の5個は回文の右半分、真ん中の1個は回分の中央に属する。同じ文字を入れ替えたとしても操作回数が減らせることは…

TopCoder MM96 GarlandOfLights

MMで初のratedコンテストの参加だった。 概要 ワイヤーと色が決められているタイルで構成されている2次元グリッドが与えられている。タイルを並べ替えてワイヤーが閉路を構成するようにする。ただし同じ色が隣接しないように配置する。できるだけ閉路を長く…

SRM626 div1 Easy FixedDiceGameDiv1

概要 Aliceはa個のb面ダイス、Bobはc個のd面ダイスを投げる。このとき、ダイスの目の合計が大きい方を勝ちとする(引き分けはどちらの勝ちでもない)。Aliceが勝つことがありえないときは-1を出力しろ。そうでないときはAliceが勝った条件下でAliceのダイスの…

SRM726 div2 med TurtleGame

概要 2次元グリッド上で亀が左上のセルから右下のセルに右か下への移動を繰り返して移動する。グリッド上には障害物があり亀は通ることができない。このグリッドを用いて2人でゲームを行う。各プレイヤーはそれぞれの手番でグリッド上に障害物を配置する。こ…

SRM726 div2 easy StringHalving

概要 英アルファベットから成る文字列Sが与えられる。文字列Sは同じ種類の文字を2個ずつ含んでいる。この文字列Sを同じ種類の文字が1個ずつになるように文字を消去する。辞書順最小になるときに文字を消去したとき、文字列の最初の文字を出力しろ。 解法 辞…

CODE FESTIVAL 2016 Grand Final A - 1D Matching

問題ページ A - 1D Matching 考えたこと とりあえずNが小さいパターンを実験してみる。PCと電源をつなぐのをPCから電源への有向辺で表すとする。 下の図でオレンジ色のつなぎ方は最短なつなげ方ではない。最短なつなげ方にならないパターンを他にも試してみ…

競プロはじめて1年が経った

技術的なことは書けないのでポエムを書きます。ferinという名前で競プロをやっていてAtcoderとcodeforcesで青の下の方、topcoderで緑の人です。 2016年11月 ミーハーなので流行りのディープラーニングに手を出してみる。どうやらPythonという言語がメジャー…

AOJ 2152 Restrictive Filesystem

問題ページ Restrictive Filesystem | Aizu Online Judge 考えたこと 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリ…

AtCoder Regular Contest 087 E - Prefix-free Game

問題ページ E - Prefix-free Game 考えたこと ゲームと言われたのでサンプルについてWin-Loseの探索木を書いてみるがよくわからない 01文字列なのでtrie木を書いてみると葉を通らないような位置に頂点を追加する問題に言い換えられることがわかった 木上のゲ…

AOJ 2536 Median Tree

問題ページ Median Tree | Aizu Online Judge 考えたこと コストが小さい辺をなるべく使っていきたい 最小全域木を思い浮かべるけどコストが1の辺を使わずに2と3の辺を繋いだほうがいい場合があるのではみたいな気持ちになって捨てる(は?) 謎の貪欲を投げ…

AOJ 1602 ICPC計算機

問題ページ ICPC Calculator | Aizu Online Judge 解法 +か*が来たらその演算子で計算する範囲の数式を全部計算して返すような関数をつくってその関数を再帰的に呼び出していくことで計算する。ある演算子で計算する対象はその演算子より高さが1段高いものな…