はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

Awkward Pairs [CodeChef ProCon 2018 D]

Contest: https://www.codechef.com/PROC2018/problems/PROC18C Practice: https://www.codechef.com/problems/PROC18C1≦L≦R≦10^18が与えられる。 以下の条件を満たすペアの組み合わせ数mod(10^9+7)でを答えよ。ペア(x,y)が以下の条件を満たす xもyも[L,R]に…

Algebra Score [CodeChef ProCon 2018 C]

https://www.codechef.com/problems/PROC18DN(≦200)個の数とN-1個の+,-演算子が順番に並んでいる。 適切に括弧をつけることで計算結果を最大化せよ。 前提知識 区間DP 考察過程 1. そもそもyukicoderで似た問題を見た これ 2. この問題の解法のエッセンス…

DigitRotation [SRM 736 Div1 Easy]

http://community.topcoder.com/stat?c=problem_statement&pm=14958とても大きい数Xがある。 この数に対して、以下の操作を行う。 a<b<cを用意し、a桁目をb桁目に、b桁目をc桁目に、c桁目をa桁目に数を移動させる このとき、leading-zeroとなるのは不正な…

The hat [Codeforces Round #503 (by SIS, Div. 1) B]

http://codeforces.com/contest/1019/problem/Bインタラクティブ問題。 N要素(Nは偶数)の配列Aがある。 この配列は以下のような特徴がある。 隠されている 円状である。つまり、1番目とN番目は隣接していると考える 隣接している要素の数はちょうど1だけ離…

Elections [Codeforces Round #503 (by SIS, Div. 1) A]

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

Candy Distribution [AtCoder Beginner Contest 105 D]

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

Cakes and Donuts [AtCoder Beginner Contest 105 B]

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

AtCoder Crackers [AtCoder Beginner Contest 105 A]

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

We Love ABC [AtCoder Beginner Contest 104 D]

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

All Green [AtCoder Beginner Contest 104 C]

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

AcCepted [AtCoder Beginner Contest 104 B]

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

Rated for Me [AtCoder Beginner Contest 104 A]

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

Coprime [yukicoder No.719]

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番目までの素数の使用状…

チーム分け [Mujin Programming Challenge 2018 F]

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

迷路 [Mujin Programming Challenge 2018 E]

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

うほょじご [ Mujin Programming Challenge 2018 D]

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

右折 [Mujin Programming Challenge 2018 C]

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できないか…

セキュリティ [Mujin Programming Challenge 2018 B]

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; //-------------------------------…

コンテスト名 [Mujin Programming Challenge 2018 A]

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とならずに、取れる分だけ取ってき…

Cut onion [Kotamanegi Online Judge No.66]

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個のグループ…

観光計画 [Kotamanegi Online Judge No.73]

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

K-th DigitSum [Kotamanegi Online Judge No.72]

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

アルゴリズムのお勉強 [Kotamanegi Online Judge No.70]

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…

机の配置 [Kotamanegi Online Judge No.69]

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

単位 [Kotamanegi Online Judge No.68]

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

575ゲーム [Kotamanegi Online Judge No.67]

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

2つの数の和 [yukicoder No.723]

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

100×100=1000 [yukicoder No.722]

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

Die tertia (ディエ・テルツィア) [yukicoder No.721]

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

Propagating Edges [SoundHound Programming Contest 2018 Masters Tournament 本戦 D]

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d