https://beta.atcoder.jp/contests/abc110/tasks/abc110_d 前提知識 素因数分解 nHk mod 素数 解法 https://beta.atcoder.jp/contests/abc110/submissions/3260162数列aにすべて1を入れておく。 すべてかけてMになるためには、Mを素因数分解して、できた素因…

https://beta.atcoder.jp/contests/abc110/tasks/abc110_c最初に載せた自分の解法が嘘解法でした！（一応下に残してあります） 解法 https://beta.atcoder.jp/contests/abc110/submissions/3261715操作を考えてみると、自由度が高そうな感じがある。 任意の…

https://beta.atcoder.jp/contests/abc110/tasks/abc110_b 解法 https://beta.atcoder.jp/contests/abc110/submissions/3256117Zを全探索する。 ZはX＜Z≦Yであるため、最大200通りしか無い。 他の2つの条件のチェックもO(100)位なので、間に合う。 int N, M,…

https://beta.atcoder.jp/contests/abc110/tasks/abc110_a 解法 https://beta.atcoder.jp/contests/abc110/submissions/3255620xy+zという風に配置した場合、10x+y+zという結果になる。 つまり、10倍をどこにかけて足すかという問題にすることができる。 下…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/E 前提知識 二重辺連結成分分解 考察過程 1. 橋である辺と橋でない辺で挙動が分かれるのは見て分かる 2. 橋である辺を削除した場合の連結成分のコストを求めたい 3. 二重辺連結成分…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/B 前提知識 双方向リスト 考察過程 1. 全然分からない 2. 参加記でリストという単語を発見 3. なるほどー 4. 双方向リスト作るんね 実装 https://onlinejudge.u-aizu.ac.jp/beta/rev…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/G 前提知識 区間DP greedyからの帰着 考察過程 1. 似たような問題設定を見たことあった 2. DEGwerさんのgreedyからの帰着で解ける 3. それで区間DPすればいけそう 解法 https://onli…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/D 前提知識 動的計画法 考察過程 1. 難しく見えるし、最小値を求めているし、DAGっぽくもあるので、DP方針で考える 2. 「dp[i] := i番目まで到達するための単語の最小個数」がぱっと…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/C 前提知識 なもりグラフ 考察過程 1. なもりグラフというのがあり、1つだけ閉路がある 2. aもbも閉路上にあれば2本の削除が必要 3. それ以外なら1本で十分 解法 https://onlinejudg…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/A 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149687区切り線を全探索しよう。 各領域について条件を満たすかチェックする。 check関数で領域が条件を…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/E 考察過程 1. 食べる中心の座標に向かって直線引くだけでは？ 2. WA 3. サンプル2をみるとはみ出している 4. 食べれた部分の中心を計算し直して、直線を引くと通る 解法 https://on…