https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0315 解法 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0315/judge/3140590/C++14実装問題。 総和を答える。 int P, M, C; //--------------------------…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0343?year=2016 前提知識 二分探索 BIT 座標圧縮 考察過程 1. （平衝二分木でset作れば一発っぽいが…） 2. （パソコン甲子園で平衝二分木実装して通したらかっこいい） 3. クエリ先読みして…

未整理記事 最小全域木 辺に重みが付いている無向グラフが与えられて、ここからいくつかの辺を選んで木を作るとき、重みの総和の最小値は？という問い アルゴリズムは3種類ある 解説 プリム法 O(V^2) or O(ElogV) ある頂点を始点として、頂点を1つずつ増やし…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0342?year=2016 前提知識 凸包 最小全域木（実際には少し違うけど）のクラスカル法 UnionFind（最小全域木の構築で使用） 考察過程 1. 「幾何っぽさ」「村を構成するどの2つの集落を結んだ…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0341?year=2016 前提知識 動的計画法 考察過程 1. 典型問題として覚えてしまっているので、考察過程がなかった 2. 文字列の添字を持つDPを作る 3. 10^9+7での数え上げ、制約もどちらのindex…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0340?year=2016 前提知識 動的計画法 （想定解では貪欲で解けるので、必要不可欠ではない） 考察過程 1. pの上限が小さいのが気になる 2. 裏返しの操作は順番が逆になっても結果が変わらな…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0339?year=2016 考察過程 1. 集合として見た時に同様のものがあれば消すことができる 2. 集合として等しい判定をするにはいろいろな方法があるので、好きな方法を使おう 解法 https://onlin…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0338?year=2016 考察過程 1. 一見厄介そうな問題に見える 2. 問題を簡単にしているのが「全て同じ大きさの正方形」で埋めるという部分 3. とりあえず何かを全探索する方針で考えるが、正方…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0337?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0337/review/3140004/hamayanhamayan/C++14実装問題。 なるべく簡単に実装できるように実装方針をまず考えよう。…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0336?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0336/review/3139998/hamayanhamayan/C++14境界となる「日の出または日の入り」を考えてみる。 すると、H=-Rのと…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0335?year=2016 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0335/review/3137179/hamayanhamayan/C++14実装問題。 int W; //---------------------------------------------…

https://beta.atcoder.jp/contests/agc027/tasks/agc027_d 解法 https://beta.atcoder.jp/contests/agc027/submissions/3208300公式解説放送を見ましょう。 動画を見れば、考え方はそんなに難しくない。 実装方法について説明する。 まずN=2のときは数が被っ…

https://beta.atcoder.jp/contests/agc027/tasks/agc027_c 前提知識 後退解析 考察過程 1. ab...にできるということは関連する全ての頂点からa,bの辺に遷移可能ということである 2. abへ遷移できない頂点を消すと、更にabへ遷移できない頂点が増える 3. どん…

https://beta.atcoder.jp/contests/agc027/tasks/agc027_b 解法 https://beta.atcoder.jp/contests/agc027/submissions/3208323何かを全探索するが、「ゴミを回収してゴミ箱へ捨てに行く」という操作の回数を全探索する。 k回ゴミ箱へ捨てに行く場合に必要な…

https://beta.atcoder.jp/contests/agc027/tasks/agc027_a 解法 https://beta.atcoder.jp/contests/agc027/submissions/3198858最適分配は喜ぶお菓子の量が少ない子供から分けていくこと。 少ない方から分けていって、ピッタリ渡せる人数が答え。 コーナーケ…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0366?year=2017 前提知識 強連結成分分解 考察過程 1. 全体を強連結にせよという問題に言い換えられる 2. 強連結成分については内部で辺を貼る必要は無いので、強連結成分分解をしてDAGにし…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0365?year=2017 前提知識 BIT 考察過程 1. 辞書順最小の文字列を構築するテク「貪欲に先頭から決めていく」 2. ある文字をスワップして先頭にもってくるためには、その文字より前にある文字…

https://onlinejudge.u-aizu.ac.jp/problems/0364 考察過程 1. 一掃できる敵は、移動後の最大列xmax、最大行ymaxとすると、x≦xmax,または,y≦ymaxを満たす座標(x,y)にいる敵 2. これを考えると上や左に移動するのは無駄なので考えない 3. 加えて、右に何回移…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0363?year=2017 前提知識 bitDP 考察過程 1. 横幅4mというのが重要に見える 2. 今回は荷物が置かれているかどうかというのが重要なので、bitdpできそう 3. 丁度1つ上の行の状態だけ持てばい…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0362?year=2017 考察過程 1. 往復できるかという問題だが、「左端から右端へ移動できるか」の判定が作れれば、右端から左端への問題へすぐ変換できるので、片道できるかという問題について…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0361?year=2017 前提知識 最大公約数(GCD) 考察過程 1. 電線とパネルの継ぎ目の交点を全て求めれば答えが出そう 2. でも解法としてかなり大変に思える 3. なにかに着目して、問題をもっと単…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0360/review/3136426/hamayanhamayan/C++14この問題では半開区間で区間が表現されているが、閉区間に直して解く…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0359?year=2017 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0359/review/3136380/hamayanhamayan/C++149日が土曜日であると書いてあるので、土曜日になる日を考えてみる。 2…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0358?year=2017 解法 https://onlinejudge.u-aizu.ac.jp/solutions/problem/0358/review/3136378/hamayanhamayan/C++14条件分岐を使って処理を分けていこう。 d := 自分の持ち金で買った時…

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0357?year=2017 解法 初歩的な実装問題。 int A, B; //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >…

https://beta.atcoder.jp/contests/abc109/tasks/abc109_d 考察過程 1. 400点問題にしては難しい気がする 2. 点数の低い構築は機械的にやれる最適戦略があるイメージ 3. 特に今回は操作回数の最小化は求められてないので、簡単な機械化を目指す 4. すると、…

https://beta.atcoder.jp/contests/abc109/tasks/abc109_c 前提知識 GCD 考察過程 1. Dを固定すると、行ける座標と行けない座標が定まってしまう 2. 細かく言うと、X = y mod Dであるyしか行けなくなる 3. よって、X%D=x[0]%D=x[1]%D=...=x[N-1]%Dを満たす最…

https://beta.atcoder.jp/contests/abc109/tasks/abc109_b 解法 https://beta.atcoder.jp/contests/abc109/submissions/3160171実装する。 同じ単語が出たかどうかはsetを使って管理すると良い。 stringの場合はbackメソッドで最後の文字が取得できるので活…

https://beta.atcoder.jp/contests/abc109/tasks/abc109_a 解法 https://beta.atcoder.jp/contests/abc109/submissions/3159224実装をした。 A,Bがどちらも奇数の場合にYesであるといえるが、実装で行ける場合は自分は実装したい。 （考察に自信がない） int…

http://codeforces.com/contest/1036/problem/DN要素の配列A, M要素の配列Bがある。 2つの配列に対して、「配列内の任意の区間を消して、その場所にその区間の総和を入れる」操作をする。 以上の操作を好きなだけやって、配列Aと配列Bを全く同じものにする。…