ferinの競プロ帳

競プロについてのメモ

競技プログラミング

AOJ1318 long distance taxi

問題ページ Long Distance Taxi | Aizu Online Judge 解法 拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。 d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。 入力が面倒だっ…

AOJ0343 プログラミングコンテスト II

問題ページ Programming Contest II | Aizu Online Judge 解法 (点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧して…

AOJ0570 ジグザグ数

問題ページ ジグザグ数 | Aizu Online Judge 考えたこと 桁DPなのは知ってたので桁DPを考える dp[i桁目][B以下が確定か][mod M][最後に選んだ数][ジグザグ数になってないか上昇か下降か] を書く mod Mを上の桁から取るのが面倒そうだけどよくよく考えると mo…

ARC094 D - Worst Case

問題ページ D - Worst Case 考えたこと よくわからないのでとりあえず実験する A<=Bとか仮定しておくと便利そう 一回目、二回目に小さい順位を取った人が条件を満たすようにしたい A=8,B=9 みたいなのが来たら下のように構成できて14個 1,71 71,1 2,35 35,2 …

ARC095 E - Symmetric Grid

問題ページ E - Symmetric Grid 考えたこと 行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない 行と列独立に考えたくなる 行を交換する操作について考える ある行を二つ取り出してきたときにその二つの行の組み合わせで点…

ARC095 D - Binomial Coefficients

問題ページ D - Binomial Coefficients 考えたこと C(x,y)はxが大きければ大きいほどよさそう x = max(a) で固定 O(n)でC(a[n-1],a[i])を全部求めればいい気持ちになるがa<=10^9で無理 よくよく考えるとC(x,y)のyはx/2に近い方がいい パスカルの三角形を考え…

ARC095 C - Many Medians

問題ページ C - Many Medians 考えたこと 中央値を取りうるのはa[n/2-1]かa[n/2]の二択 n/2番目以降ならa[n/2-1]、それ以外ならa[n/2] ソートすればいいのになぜか座圧を書く 座圧を書いたあとsampleを見て気づいてソートに書き直す 出すと通る 無駄に時間か…

AOJ2304 Reverse Roads

問題ページ Reverse Roads | Aizu Online Judge 考えたこと 有向グラフの辺を反転することでs-tフローを最大化する 与えられた辺を無向辺のように扱って両方の向きに辺を張ってフローを流す 最大フローの値はこれで求まる 反転すべき辺を求めるのには残余グ…

AOJ2382 KingSlime

問題ページ King Slime | Aizu Online Judge 考えたこと 縦横で同じ軸にいるスライムは移動1回でくっつけられそう sample1を見ると縦横で同じ軸にいるスライムをつないでいってその連結成分にいるスライムは移動1回でまとめられそう つまり(連結成分の大きさ…

AOJ2297 Rectangular Stamps

問題ページ Rectangular Stamps | Aizu Online Judge 考えたこと 各マスについてempty,R,G,Bの4種類の状態を持ちたい これが持てると集合を持ちつつ探索していけそう 4^16は無理 考察するとそのマスで必要な情報は最終的な色に達しているかどうかの2種類しか…

AOJ2425 全探索お姉さんの休日

問題ページ A Holiday of Miss Brute Force | Aizu Online Judge 考えたこと 六角形のグリッド上を探索する 拡張dijkstraの要領で頂点に時間を増やせばいい気持ちになる 時間の上限ないしそのままつけるのは無理 時間が影響するのはabs(x*y*t)%6の指示される…

RUPC2018 day2 J Matrix

問題ページ 解法 ある矩形範囲(a,b,c,d)の最大値はその区間の max(A)*max(B), max(A)*min(B), min(A)*max(B), min(A)*min(B) のうちのどれかとなる。最小値についても同様にどれかになる。 最大値の個数については max(A)*max(B)が最大値であればmax(A)の個…

codeforces #212 div2 D. Fools and Foolproof Roads

問題ページ Problem - D - Codeforces 概要 n頂点m辺の重み付き無向グラフが与えられる。このグラフに辺を張る操作をp回行うことで連結成分数がq個になるようにしたい。 辺を張るときは 同じ連結成分内の頂点なら1000 違う連結成分の頂点ならばmin(10^9, 連…

codeforces #212 div2 C. Insertion Sort

問題ページ Problem - C - Codeforces 概要 n要素の順列が与えられる。この順列に挿入ソートを行う。 この順列のどこか2要素をswapすることで挿入ソートでの交換回数を最小化しろ。 考えたこと ようするに転倒数を最小化すればいい i,j (i

AOJ2441 FizzBuzz

問題ページ FizzBuzz | Aizu Online Judge 考えたこと 数xまでの文字数が何文字になるか Fizz,Buzzの部分は文字数が固定だからいいけど数字部分の文字数がずれるのがつらそう ずれないように桁ごとに分ける 1~9の中の3,5,15の倍数の数を数えると1~9のFizzBuz…

AOJ2009 Area Separation

問題ページ Area Separation | Aizu Online Judge 考えたこと ある線を引く時、既に引いている線分との(交点の数+1)個領域が増える ただし一つの交点に3本以上の線分が交差している場合、重複して数えてはいけない 正方形の辺上で交わる場合を交差に数えては…

AOJ1176 輪番停電計画

問題ページ Planning Rolling Blackouts | Aizu Online Judge 解法 func(sx,sy,gx,gy) = (指定範囲で実現できる最大のグループ数, グループの需要のうち最大) とする。その領域を分割しないか、縦に分割するか、横に分割するかの3通りの遷移がある。 分割し…

Maximum-Cup 2018 D

問題ページ D - Many Go Round 解法 普通に部分和を求めるDPをしようとするとsum(a)<=10^8で状態数が大きすぎて不可能。ここで考察をすると持っておくべき合計は高々Mであることがわかる。dp[i][j] = (i番目の燃料までで休憩所jにたどりつくのに必要な最小の…

Maximum-Cup 2018 C

問題ページ C - 嘘つきな天使たち 考えたこと とりあえずグラフを書きたくなる 天使に隣接しているのは悪魔、悪魔に隣接しているのは天使になる 隣り合う頂点を違う色で塗り分けられればいいのでこれは二部グラフをつかって判定できる 二部グラフでなければ-…

Maximum-Cup 2018 B

問題ページ B: 駆け抜けろ!埼大山車部!! - Maximum-Cup 2018 | AtCoder 考えたこと 制約が小さいし全探索 d[y][x][向き][右折した回数][左折した回数] = (通ったか) としてBFSをする 左折がa回、右折がb回なのに逆にしてたり曲がる回数の条件を達成する前…

Maximum-Cup 2018 A

問題ページ A: フィギュアスケート界の貴公子埼大選手 - Maximum-Cup 2018 | AtCoder 解法 距離dの位置にt+10秒のタイミングでm個投げ込まれる。距離dの位置はd秒で通過するのでd<=t+10であればその位置のぬいぐるみを取れる。 ソースコード #include <bits/stdc++.h> using</bits/stdc++.h>…

AOJ1182 鉄道乗り継ぎ

問題ページ 鉄道乗り継ぎ | Aizu Online Judge 解法 各鉄道会社について駅i->駅jに移動するときに必要な距離をワーシャルフロイドを用いて求める。各鉄道会社についてある距離を移動するために必要なコストは求めることが可能なので駅i->駅jへ移動するのにか…

AOJ2298 Starting Line

問題ページ Starting Line | Aizu Online Judge 考えたこと にんじんを使うべきタイミングはいつか? にんじんを食べていない && にんじんを持っている状況で食べずに持っているほうがいいときはなさそう 持ちきれないときも使ってしまった方がよさそう 上の…

AOJ2601 Evacuation Route

問題ページ Evacuation Route | Aizu Online Judge 考えたこと そのマスから各出口へ到達できる最後の時刻を求めたい その出口に右から入るとき、その出口よりも右にある防火扉が閉まる前に超えられればok dp[i] = (区画iから左へ進んだときに出口に到達可能…

AOJ1248 The Balance

問題ページ The Balance | Aizu Online Judge 考えたこと aグラムがi個、bグラムがj個のとき ai + bj = d, ai + d = bj, ai = bj + d を満たせばdグラムを測れる iを決め打てばjは自動的に決まる iは何通りくらいあるのか? a=1,b=2,d=50000みたいなときに5*…

AOJ2303 Marathon Match

問題ページ Marathon Match | Aizu Online Judge 考えたこと i人目が走るのにかかる時間は (休んだ回数)*T[i] + L/V[i] 休憩所M個中r個で休む確率は C(M,r) P(i)^r (1-P[i])^(M-r) になる したがってi人目がj回休む確率とそのときのタイムを求められる i人目…

AOJ2157 Dial Lock

問題ページ Dial Lock | Aizu Online Judge 考えたこと 状態数が最大10^10あるから愚直は無理 回転させる数だけ気にすればいい気持ちになる i桁目について (t[i]-s[i]+10)%10 回回せばいい +1 +2 +4 +2 みたいなのが来たときに+2から+2の区間をまとめて回せ…

AOJ1320 City Merger

問題ページ City Merger | Aizu Online Judge 概要 要素数がNの文字列集合Sが与えられる。連続した部分文字列にSの要素を全て含むような文字列のうち最短のものを求めろ。 N<=14、(文字列の長さ)<=20 考えたこと suffixとprefixが一致しているような文字列の…

AOJ 1161 覆面算

問題ページ Verbal Arithmetic | Aizu Online Judge 解法 アルファベット10種類について考えるのが面倒なのでとりあえず座圧をすることにする。したがって以降に出現するアルファベットは'A'~'J'までの範囲であるとして考える。 ACE + DBE = DCFC 100A + 10…

AOJ2182 Eleven Lover

問題ページ Eleven Lover | Aizu Online Judge 考えたこと ある数が11の倍数の条件を考える 算数を思い出しながら考えると a[1] + 10a[2] + 100a[3] + 1000a[4] + … = a[1] + 10a[2] + a[3] + 10a[4] + … + 11(9a[3] + 90a[4] + …) なので a[1] + 10a[2] + a…