ferinの競プロ帳

競プロについてのメモ

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

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 座圧して…