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

Factorization [AtCoder Beginner Contest 110 D]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_c 解法 https://beta.atcoder.jp/contests/abc110/submissions/3256344操作を考えてみると、自由度が高そうな感じがある。 任意の文字を別の文字に変えることはできそう。 しかし、ある文字を文字列中…

String Transformation [AtCoder Beginner Contest 110 C]

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,…

1 Dimensional World's Tale [AtCoder Beginner Contest 110 B]

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

Maximize the Formula [AtCoder Beginner Contest 110 A]

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

均衡な辺削除 (Balanced Edge Deletion) [Aizu Competitive Programming Camp 2018 Day 3 E]

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

ピボット (Pivots) [Aizu Competitive Programming Camp 2018 Day 3 B]

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

回文部分列 (Palindromic Subsequences) [Aizu Competitive Programming Camp 2018 Day 3 G]

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

しりとり圧縮 (Shiritori Compression) [Aizu Competitive Programming Camp 2018 Day 3 D]

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

な◯りカット (Namo.. Cut) [Aizu Competitive Programming Camp 2018 Day 3 C]

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

IPアドレス (Internet Protocol Address) [Aizu Competitive Programming Camp 2018 Day 3 A]

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

Donut Hole [Aizu Competitive Programming Camp 2018 Day 2 E]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/D 前提知識 ダイクストラ 考察過程 1. ダイクストラしながら経路数も数える例のやつ？ 2. ダイクストラしながら、新記録更新したら経路数も更新する 解法 https://onlinejudge.u-aiz…

Gridgedge [Aizu Competitive Programming Camp 2018 Day 2 D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/C 考察過程 1. サンプルを眺めて考えると、スワップというより回転のように見える 2. ちょっと例を出して考えても回転みたい 3. 先頭が何かを覚えておいて回転させよう 解法 https:/…

Round And Round　[Aizu Competitive Programming Camp 2018 Day 2 C]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/B 考察過程 1. まだBなのにむずかしめに見える（制約も大きいし） 2. 簡単な所が無いか探す 3. 最適戦略があるのではないか？ 4. UKUが勝つ時とうしが勝つ時で最適な方を選択？ 解法…

U&U [Aizu Competitive Programming Camp 2018 Day 2 B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/A 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day2/3149547 最適戦略を考えると、全て500点で渡したほうが良い。 なので、P/500で最大何回500ポイントを渡せ…

Special Chat [Aizu Competitive Programming Camp 2018 Day 2 A]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d 考察過程 1. これを思い出すので、似たようなDPを考える 2. dp[i] := i番目まで確定していて、i番目で給油をした場合の組み合わせ数 3. dp[i] += sum{i以下のj…

通勤 [CODE FESTIVAL 2018 qual A D]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c 考察過程 1. Nがあまりに小さいので気になるがbitdpできるような大きさではないので、何か特徴を考える 2. 各要素への操作は独立に行える 3. 2で割る操作は最…

半分 [CODE FESTIVAL 2018 qual A C]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_b 前提知識 imos法（無くても全然解ける） 考察過程 1. なるべくB房みかんを使ったほうが良い 2. A房みかんを使わなくてはいけないのは、M個の区間での話 3. 1つ…

みかん [CODE FESTIVAL 2018 qual A B]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_a 解法 https://beta.atcoder.jp/contests/code-festival-2018-quala/submissions/3242821問題で示されているパターンをすべて試そう。 三重ループで表現すると…

配点 [CODE FESTIVAL 2018 qual A A]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/D 解説 https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day1/3148892右手法を使って解く。 外周に沿って右手法で移動すれば、 必ず一周して戻ってくる 同じ形であれば…

遭難 [Aizu Competitive Programming Camp 2018 Day 1 D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/C 前提知識 素数列挙 考察過程 1. p,q,p+qが全て素数って条件が結構厳しい 2. 2+?に必ずなるな 3. N+2以下の素数を全列挙して、隣り合う素数の差が2であるペアを答えればいい？ 4. …

素数 [Aizu Competitive Programming Camp 2018 Day 1 C]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/B 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day1/3146209回転後の図形はmax(A,B)を半径とした球となる。 なので、球の体積を求めると答え。 const double P…

直角三角形 [Aizu Competitive Programming Camp 2018 Day 1 B]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day1/problems/A 解法 https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day1/3146184普通にシミュレーションしても間に合いそうだが、別の方法で解いた。 [1,M]で埋まってない個数分だ…

テスト [Aizu Competitive Programming Camp 2018 Day 1 A]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0323 前提知識 三分探索 幾何（といっても三平方） 考察過程 1. 全ての円が重なる部分での最大距離が求まればいい 2. 流石にその部分を作るのはヤバすぎて無理そう 3. だが、全ての円が重な…

ヒバラ海に沈む遺跡 [パソコン甲子園2015 予選 I]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0321?year=2015 前提知識 UnionFind 考察過程 1. 矛盾が発生するのは、ある生徒が2つ以上の部活動に属している可能性がある場合 2. a,bが同じ部活動に属しているということは、同じグループ…

部活動調査 [パソコン甲子園2015 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0320?year=2015 考察仮定 1. 差分を考えていく問題であるが、差分だけを再計算することで判定できないか考える 2. 現在の状態を打ち消して、更新して、現在の状態を考えなおすという典型テ…

品質管理 [パソコン甲子園2015 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0319?year=2015 考察仮定 1. 答えのAを全探索できるのでは？ 2. できる 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0319/judge/3140675/C++14答え…

プログラミングコンテスト [パソコン甲子園2015 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0318?year=2015 考察仮定 1. 問題のベン図を見ながら高校数学のように数えやすい物をつかって表現する 2. すると答えはn(C) - n(A∧C) + n(A∧B∧C)となる 3. これを各々数えて、計算すると答…

極秘調査 [パソコン甲子園2015 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0317?year=2015 考察仮定 1. 貪欲に行けそうか考えると、流石にいけそう 2. 最適戦略を考えるとなるべく大ジャンプを使うほうがよくて、使えなくなったら小ジャンプ 3. DPでも解ける制約に…

カエルはまっすぐ帰る [パソコン甲子園2015 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0316?year=2015 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0316/judge/3140614/C++14実装をする。 イワナをh1匹、ヤマメをh2匹釣った場合の合計点…

魚釣り競争 [パソコン甲子園2015 予選 B]