http://codeforces.com/contest/1019/problem/AN人の有権者とM種類の政党がある。 i番目の人はもともとP[i]番目の政党に投票しているが、C[i]円支払うことで別の政党に投票してくれる。 1番目の政党が選挙で勝つには最小でいくら必要か。 ※選挙で勝つには他…

https://beta.atcoder.jp/contests/abc105/tasks/abc105_d 考察過程 1. よくあるテクを使う 2. 「右側を固定して、条件を満たす左端を高速に数え上げる」 3. 区間和に関する問題なので、先頭からの累積和を使って条件を考える 4. [l,r]の区間和がMの倍数 ↔ […

https://beta.atcoder.jp/contests/abc105/tasks/abc105_b 解法 https://beta.atcoder.jp/contests/abc105/submissions/29947624ドルと7ドルで支払うパターンを全探索する。 合計が100ドル以下なので、4,7ドルも100個を上限として良い。 yes,no問題は関数を…

https://beta.atcoder.jp/contests/abc105/tasks/abc105_a 解法 https://beta.atcoder.jp/contests/abc105/submissions/2994729なるべく均等に配っていくと、最大と最小の差が2つ以上離れることはない。 差が0になるのは、N個をK個に均等に分けれる場合のみ…

https://beta.atcoder.jp/contests/abc104/tasks/abc104_d 解法 https://beta.atcoder.jp/contests/abc104/submissions/2955573配列から3要素順番にとって条件を満たす組合せ数というのは真ん中を固定して全探索というテクがある。 Bとなる要素を全探索する…

https://beta.atcoder.jp/contests/abc104/tasks/abc104_c 前提知識 動的計画法 解法 https://beta.atcoder.jp/contests/abc104/submissions/2956491点数は全て100の倍数なので、全て100分の1にして考えることにする。 Gの上限が書かれていないので、上限を…

https://beta.atcoder.jp/contests/abc104/tasks/abc104_b 解法 https://beta.atcoder.jp/contests/abc104/submissions/2953007実装をする。 複雑な条件のyes/noは関数を分けたほうがいい。 小文字であることを判定するには'a'～'z'の間に文字があることを使…

https://beta.atcoder.jp/contests/abc104/tasks/abc104_a 解法 https://beta.atcoder.jp/contests/abc104/submissions/2952324実装をする。 elseifでつなげていくのがオススメ。 int R; //---------------------------------------------------------------…

https://yukicoder.me/problems/no/719 前提知識 bitDP 解法 https://yukicoder.me/submissions/276962bitDPを使って解く。 [2,N]の素数がn個、[2,sqrt(N)]の素数がm個あるとする。 dp[i][msk] := m～i番目までの素数を使って、0～m-1番目までの素数の使用状…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f 解法 https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947875chokudaiさんの解説放送が良質すぎる 公式解説 以上の副読本としての解説。 DPで解く。 解説放送にあるよ…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e 前提知識 ダイクストラ 考察過程 1. ダイクストラの問題に見える 2. 状態を考えるとマスの数NMで時間がKなのでNMK=10^11なのでこれは無理 3. なんとか改善できないか 4. 最短時間から…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_d 考察過程 1. 制約を見ると割と小さいので、シミュレートできそう 2. 操作を見てみるとかなりやばい操作をしているので、更にシミュレートしながら何かする感じが伝わる 3. メモ化すれ…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_c 考察過程 1. 制約からO(NM)かなと思う 2. 移動が1回だけでまずは考えてみる。これはDPできそう。dp[y][x] := 1回目で(x,y)に止まる始点の組み合わせ数 3. 2回目の移動もDPできないか…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_b 解法 https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947184シミュレーションで解こう。 A=0がコーナーケース。 int A; string S; //-------------------------------…

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_a 解法 https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947174c++のsubstrを使うと楽。 substrのいいところは文字数超過したときにREとならずに、取れる分だけ取ってき…

https://kotamanegi.com/Problems/view/?page=66 前提知識 O(3^N)の部分集合の列挙を用いたbitDP 解法 https://kotamanegi.com/Submission/view/index.php?SubmissionID=2149間接的に問題を解く。 まずは、以下のbitDPをする。dp[gr][msk] := gr個のグループ…

https://kotamanegi.com/Problems/view/index.php?page=73 前提知識 ダイクストラ 考察過程 1. 観光できるホテルは「任意の快適度dのホテルが距離d以内に存在する」ことである 2. 思いつく解法が、全ての頂点から全てのホテルをチェックする解法だがO(NK)で…

https://kotamanegi.com/Problems/view/index.php?page=72 前提知識 http://hamayanhamayan.hatenablog.jp/entry/2017/08/21/102212:tile=「①最上位の数と桁数を決定する②上位桁から順番に数を決定していく」というテク 解法 1. この手の構築問題にはテクが…

https://kotamanegi.com/Problems/view/index.php?page=70 前提知識 bitDP 考察過程 1. N≦16の時点でbitDP感がある 2. 最短時間を聞かれてるのでbitDPで最小値のDPを考えると答えられる 解法 https://kotamanegi.com/Submission/view/index.php?SubmissionID…

https://kotamanegi.com/Problems/view/index.php?page=69 解法 https://kotamanegi.com/Submission/view/index.php?SubmissionID=1603実装問題。 机をどう配置すれば最適かという問題もあるが、これは詰めるようにして置いていけばいい。 縦1横iの机を配置…

https://kotamanegi.com/Problems/view/index.php?page=68 解説 https://kotamanegi.com/Submission/view/index.php?SubmissionID=1538受講の最適解を考える。 取得単位数が多い科目から順に使っていくのが最適。 取得単位数が多い順で取っていって、M単位以…

https://kotamanegi.com/Problems/view/?page=67 解法 https://kotamanegi.com/Submission/view/index.php?SubmissionID=1509ゲームの後退解析のように解いていく。 chk(f,s) := 5文字の単語がf個、7文字の単語がs個でターンが回ってきたときに勝てるか もし…

https://yukicoder.me/problems/no/723 解法 https://yukicoder.me/submissions/276742こういう数え上げ問題のよくある手法を使う。 ある条件を満たす項目数を前計算しておくというテク。 今回はcnt[a] := A[i]=aを満たす項目数を前計算しておく。 条件を満…

https://yukicoder.me/problems/no/722 解説 https://yukicoder.me/submissions/276740暗算をするかどうかの条件が結構複雑なため、check関数で別途行うことにしている。 check関数では条件に合うかのチェックのために、何回10で割れたかをカウントしている…

https://yukicoder.me/problems/no/721