ferinの競プロ帳

競プロについてのメモ

AOJ

AOJ1604 デッドロック検出

問題ページ Deadlock Detection | Aizu Online Judge 考えたこと とりあえずサンプルを読む あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック あるuから次のuまでに同じ数字が2回以上出てくる→デッド…

AOJ2585 一日乗車券

問題ページ 1 Day Passport | Aizu Online Judge 考えたこと とりあえず入力で何がくるのかちゃんと読む 会社の数の制約が小さい dp[S] = (会社の集合Sを乗り放題にするために必要な最小コスト) を求めておく これは簡単なbitDPでできてO(2^KP) 会社の集合S…

AOJ1330 Never Wait for Weights

問題ページ Never Wait for Weights | Aizu Online Judge 考えたこと bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる 重さの差を測るクエリ…

AOJ2200 Mr. Rito Post Office

問題ページ Mr. Rito Post Office | Aizu Online Judge 考えたこと 人がx、船がyにある状態を(x,y)と書くことにする ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(…

AOJ2642 Dinner

問題ページ Dinner | Aizu Online Judge 考えたこと すべての日で自炊するとする このときの幸福度は簡単に求まる ある日を自炊から外食に変えると変化する幸福度は(外食の幸福度)-(その日の自炊の分)-(その日以降で自炊する日数)*(定数) i日目以降で自炊をj…

AOJ2310 薔薇園の魔女

問題ページ Rose Garden Witch | Aizu Online Judge 考えたこと 左下からの線分の偏角を微小量dtごとに変化させて全部試すみたいな解法を考える 判定部分でdfsでO(HW)かかるのでとてもじゃないけど精度がたりなさそう 線分を引く位置はどうせ少ないとかがな…

AOJ2510 双子の読書感想文

問題ページ Twin book report | Aizu Online Judge 考えたこと まず本を読む時間を最小化することを考える 感想を書く時間を無視して読書にかかる時間の方だけ考える とりあえずソートしたい気持ちになる いろいろ試してると大体 sum(r) で読書が終わりそう …

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…

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)の個…

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通りの遷移がある。 分割し…

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…

RUPC2018 day3 F: 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths)

問題ページ Aizu Online Judge Arena 解法 s-t間の最短経路に使われない辺をいくら伸ばしたところで最短経路は伸びない。したがって最短経路に使われる辺だけを抜き出したグラフを考えればよい。辺を抜き出す部分の判定は dist[i][j] = (iからjの最短経路) …

RUPC2018 day3 E: ブロッコリー?カリフラワー? (Broccoli or Cauliflower)

問題ページ Aizu Online Judge Arena 解法 部分木についてのクエリなのでオイラーツアーをしたくなる。オイラーツアーをした列に対して遅延セグ木を使って更新するいつものをしたい。updateが区間xor、queryが区間和の遅延セグ木を使えばその木にGとWのどち…

RUPC2018 day3 D: 素因数分解の多様性 (The Diversity of Prime Factorization)

問題ページ Aizu Online Judge Arena 解法 dp[i][j] = (i番目までで今までに使った最大の素数がj) みたいなDPを書きたくなる。しかしこれでは状態数がO(N*(max(q)以下の素数の数))となり間に合わない。ここで連続した2数が指数の方になることはありえないこ…