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

問題ページ 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…

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

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

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

問題ページ 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>…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題ページ 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)…

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

問題ページ 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)(…

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

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

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

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

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

問題ページ 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] となる。 頂…

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