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個でターンが回ってきたときに勝てるか もし…