ferinの競プロ帳

競プロについてのメモ

Codeforces Round #499 (Div. 2) E. Border

問題ページ Problem - E - Codeforces 考えたこと k進数の下一桁はkで割った余りに等しい a[i] mod k を取っておいてよさそう dp[i番目][金額]=(bool)とかしたいけど10^10なので無理 a[i]がkと互いに素なら0~k-1まで全て取りうる a[i]がkと互いに素でない場…

Codeforces Round #499 (Div. 2) D. Rocket

問題ページ Problem - D - Codeforces 考えたこと p[i]を把握しないといけない y=INFを出力しようと思ったけどだめなのでy=1を出力して確認する p[i]さえわかれば二分探索すればよい m<=10^9ならクエリ回数30回あれば足りる 二分探索を実装して出すと通る y=…

Codeforces Round #499 (Div. 2) C. Fly

問題ページ Problem - C - Codeforces 考えたこと 燃料xを積んだときに旅行を達成できるか?を考えると単調性がある 判定O(N)でできそうなのでにぶたんできそう 燃料を10^9までしか使わないことが保証されている -1の判定はこれを使えばできそう 不等号に=を…

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

問題ページ C - Cheating Nim 考えたこと Nimの勝利条件から問題文を言い換えたい 不正者が勝てるのは a[0] xor a[1] xor … xor a[n-1]=0 のときだけ 山の石の数を-1する操作で上の条件を達成する問題になった xorなのでビットごとにみたくなるので2進数の形…

yukicoder No.235 めぐるはめぐる (5)

問題ページ No.235 めぐるはめぐる (5) - yukicoder 解法 HL分解の練習として解いた。クエリ0は街Xから街Yに対してC[i]*Zを加算するクエリ、クエリ1は街Xから街Yの値の和を求めるクエリになる。区間に対しての加算と区間和を求めるものなので遅延セグメント…

NJPC2017 H - 白黒ツリー

問題ページ H - 白黒ツリー 解法 頂点に関する制約条件を扱うのは大変なので辺のコストの条件に置き換える。両端の頂点の色が違う辺のコストは0、両端の頂点の色が同じ辺のコストは1とする。こうするとクエリ2について頂点uとvの2頂点間の距離が0かどうかの…

Codeforces Round #500 (Div. 2) D. Chemical table

問題ページ Problem - D - Codeforces 考えたこと sampleを眺める 1列を埋めたあと1つもない列に1個ずつ配置すると最適な置き方な気がした 列iに要素がa[i]個あるときh-max(a[i])個で1列埋めたくなる 列iと列jに同じ行の要素があるとき、この2つの列はマージ…

SoundHound Programming Contest 2018 Masters Tournament 本戦 B - Neutralize

問題ページ B - Neutralize 解法 DPをする。dp[i] = (区間[0,i]の最大値) とする。遷移について考えると max(dp[j]) (0<=j<=i-k) dp[i-1] + b[i] 0 (k-1<=i) の3通りになる。上から順に区間[j,i]を0にする、i番目の薬について0にせず足す、区間[0,i]全体を0…

AOJ2236 Rabbit Plays Games!

問題ページ Rabbit Plays Games! | Aizu Online Judge 考えたこと 項目が多すぎるのでまとめたい まず敏捷sについて関係あるのは自分より早く動くか遅く動くかだけ 敏捷の差とか考えたくないので無視したい 戦闘前に自分より早く動くやつにダメージをもらう…

yukicoder 710 チーム戦

問題ページ No.710 チーム戦 - yukicoder 考えたこと 二人でスケジューリング問題をしましょうみたいな問題 どうせ貪欲かDP 制約小さいしとりあえずDPを考える dp[i問目][男がj秒][女がk秒] = (この条件が可能か) のDP 状態数が多すぎる dp[i問目][男がj秒] …

yukicoder 709 優勝可能性

問題ページ No.709 優勝可能性 - yukicoder 考えたこと 各パラメータで一番大きい値とその人を持てばいいだけでは?と思って書く サンプルで落ちる 冷静に読むと同じ値が複数出てくる 各パラメーターjで一番大きい値を取る人の集合cnt[j]を持っておきたくな…

ABC100 A - Happy Birthday!

問題ページ A: Happy Birthday! - AtCoder Beginner Contest 100 | AtCoder 解法 a <= 8 && b <= 8 なら条件を満たしているのでYay!、違うなら:(を出力する。 abs(a-b) <= 1 ならとか考えてたら2分かかってしまった。 ソースコード #include <bits/stdc++.h> using namespac</bits/stdc++.h>…

ABC100 B - Ringo's Favorite Numbers

問題ページ B: Ringo's Favorite Numbers - AtCoder Beginner Contest 100 | AtCoder 考えたこと ちょうど0回割り切れるって何だと思ってサンプルを見たら1回も割りきれないことっぽい nの後ろに'0'を2d個つければいいでしょと思って投げる 落ちてて何事かと…

ABC100 C - \*3 or /2

問題ページ C: *3 or /2 - AtCoder Beginner Contest 100 | AtCoder 考えたこと 全ての要素に対して2で割るか3倍するのどちらかをするのかと思う 全てのiに対して3倍するって何のことだと思って数分が経過する 操作1回につき各要素について2で割るか3倍する…

ABC100 D - Patisserie ABC

問題ページ D: Patisserie ABC - AtCoder Beginner Contest 100 | AtCoder 考えたこと 与えられる値が全て正だったらx[i]+y[i]+z[i]が大きい方から取ればいいだけ 最大化するのは絶対値で負がある それぞれ正負を試せばいいのでは? 正負を固定すればソート…

AOJ2596 Points and Lines

問題ページ Points and Lines | Aizu Online Judge 考えたこと BNFがパッと目に入って明らかに構文解析 幾何の操作がBNFの形で与えられるのでその結果を求める 幾何の操作は2点から直線を作る操作とreflectionと直線の交点 割と単純な操作でライブラリを貼れ…

AOJ2712 Escape

問題ページ Escape | Aizu Online Judge 考えたこと 閉路が存在すればそこでUターンできる つまり1->閉路->1みたいな移動ができる 閉路にたどり着くまでの頂点は必ず訪れることができる 閉路の先にある頂点の集合は最後に取ることしてどれか一箇所しか取れな…

AOJ2784 Similarity of Subtrees

問題ページ Similarity of Subtrees | Aizu Online Judge 考えたこと 各頂点xを根とした部分木について配列v_xを考える v_x[i]=(深さiの頂点数)とする v_xが等しければその部分木は等しい v_xが等しい頂点の数がa個であればa(a-1)/2個の条件を満たすペアがあ…

AOJ2447 A Two Floors Dungeon

問題ページ A Two Floors Dungeon | Aizu Online Judge 解法 制約を見るとSがかなり小さい。盤面の状態の変化を全て持つと2^(50*50)で明らかに持てないがスイッチのON/OFFの全通りの2^Sであれば十分持てる。こうすると d[スイッチの状態][x座標][y座標][何階…

AOJ2741 インビジブル

問題ページ インビジブル | Aizu Online Judge 考えたこと ゲーム系だけど制約が小さいので全探索系っぽい minmaxをする感じで考える 持ちたい状態を考えると山札の何枚目を見ているか、スタックに何枚あるか、どっちのターンかあたり スタックにある枚数を…

AOJ2606 Perm Query

問題ページ Perm Query | Aizu Online Judge 解法 各iについて周期が高々40以下といういかにも使えと言っている制約があるので使う。各iについて周期がcnt[i]、1周期でretに加算される合計をsum[i]とする。すると各iを繰り返す回数は区間[l,r]のcnt[i]のlcm…

AOJ1350 There is No Alternative

問題ページ There is No Alternative | Aizu Online Judge 解法 ある最小全域木Tの辺をひとつ交換して構成できる全域木が最小全域木であれば、その辺はno alternative bridgeではない。ある辺を除去したときに代わりに加えたときに全域木になる辺を列挙した…

AOJ1246 Concert Hall Scheduling

問題ページ Concert Hall Scheduling | Aizu Online Judge 考えたこと 区間が飛んでくるのでとりあえず終端でソートする 区間が3つ以上かぶるような日があるとだめ 今までに選んだ区間ですでに2つかぶっているような日が存在 その日よりも始点が前の区間を使…

AOJ 2306 Rabbit Party

問題ページ Rabbit Party | Aizu Online Judge 考えたこと 入力がグラフっぽい グラフとしてサンプルを書いてみるけどグラフの知ってるもの(最大安定集合とか)に帰着できない DPを考える dp[i匹目まで][j匹選んだ] みたいなの 今までに選んだうさぎの部分集…

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文字目を…