ferinの競プロ帳

競プロについてのメモ

競技プログラミング

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…

yukicoder No.685 Logical Operations

問題ページ No.685 Logical Operations - yukicoder 考えたこと bitだし2進数で考える x AND y, x XOR y, x OR y を書いてみる X 01001 Y 11101 & 01001 ^ 10100 | 11101 x,yのi桁目を(x_i,y_i)と表す AND < XOR を満たすためには1が出てくる最初の桁が(0,1)…

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)(…

GCJ 2018 round1 C - A Whole New Word

問題ページ Google Code Jam 考えたこと 全ての可能な単語パターンは何通りか i文字目の文字種をc[i]とするとc[i]の総積になる nがこれに等しければ何をつくっても一致するので不可能 とりあえず適当にケースをつくってみる j文字目が全て同じ文字→j文字目を…

AOJ2642 Dinner

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

AOJ2310 薔薇園の魔女

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

AGC023 B - Find Symmetries

問題ページ B - Find Symmetries 考えたこと とりあえずよい盤面を書いてみる 斜めにずらしたとしてもよい盤面であるのは絶対に変わらない したがってB=iとしたときによい盤面であれば斜めにずらしてもよい盤面 O(N^3)なので書くとサンプルが通らない 対称な…

AGC023 A - Zero-Sum Ranges

問題ページ A - Zero-Sum Ranges 考えたこと 問題を読むと200点に見えないので真面目に考える とりあえず累積和を取ってみる i番目を左端とする区間で部分和が0になる区間はa[i]=a[j]となる したがってiより右でa[i]と等しいものの数を数える mapで現れた頻…

ARC096 F - Sweet Alchemy

問題ページ F - Sweet Alchemy 解法 問題の整理 d[i] = c[i] - c[p[i]] とするとドーナツをつくれる個数の条件である c[p[i]] <= c[i] <= c[p[i]] + D を 0 <= d[i] <= D と言い換えることができる。ただし根に関してはdに制限はなく 0 <= d[0] となる。 頂…

ARC096 D - Static Sushi

問題ページ D - Static Sushi 考えたこと 何か既視感を感じる どうせ引き返すのは高々1回 時計回り or 反時計回りに一方向に回るだけならO(N)で簡単に求まる dp1[i] = ([0,i]で得られる最大のカロリー、時計回り) dp2[i] = ([i,n-1]で得られる最大のカロリー…

ARC096 C - Half and Half

問題ページ C - Half and Half 考えたこと 頑張って数学O(1)もありそうだけど絶対つらい 制約を見ると10^5なのでO(max(X,Y))できる ABピザを2i枚使ったとするとAピザ、Bピザの枚数は一意に定まる 全探索をする ソースコード #define __USE_MINGW_ANSI_STDIO …

ARC035 C - アットコーダー王国の交通事情

問題ページ C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder 考えたこと Sを求めるには全点対の最短距離が必要 ワーシャルフロイドをしたい 辺を追加するクエリの度にワーシャルフロイドしてO(N^3)かけていたらO(N^3K)でまず通ら…

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…

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…