B - Addition and Multiplication github.com

A - Rating Goal github.com

code-festival-2017-qualc.contest.atcoder.jp 解き方 O(n)の前計算で、s[i:j]が入れ替えて回文になるかどうかを計算できるようにする s[0:i]の最小の分割数でDPを構成する（O(n^2)) hash値に対するDPとすることでO(n)に高速化 ハマったところ 前計算→DPの流…

code-festival-2017-qualc.contest.atcoder.jp 解き方 両端から調査していく（xが片方に見つかったらxをもう一方に足す） ハマったところ 最初、奇数回出現する文字があるかないかで場合分けなど不要に複雑にしていた github.com

code-festival-2017-qualc.contest.atcoder.jp 解き方 a_m...a_nと似ていて、積が偶数である数列b_m...b_nとしてあり得る数列の個数を、m=n, n-1, ..., 1の順序で考える |a_i - b_i| <= 1より、b_iとして考えられる数字は3つ github.com

code-festival-2017-qualc.contest.atcoder.jp github.com

D - Four Coloring 解き方 45度回転してマンハッタン距離の代わりにチェビシェフ距離を使えるようにして、d*dの正方形ごとに色をかえる ハマったところ 45度回転する考えがそもそもなかった 要するにチェビシェフ距離が扱いやすいので、できるだけこれに変換…

D - Axis-Parallel Rectangle 解き方 長方形の頂点のx座標、y座標はいずれかの点のx座標、y座標と等しいと考えて問題ないので全探索 ハマったところ 全体でO(N^5)だったのでいけるか不安だったが、TLEはしなかった。 github.com

C - Bridge 解き方 DFSして橋を数える ハマったところ bridgeを見つけるアルゴリズムを忘れていたので、一から書いてたらデバッグに時間かかった github.com

B - Minesweeper github.com

A - One out of Three github.com

ddcc2017-qual.contest.atcoder.jp 解き方 最長の鉛筆をまず箱に入れて、もし入るなら最短の鉛筆も入れる。これを繰り返して個数を求める ハマったところ 最長の鉛筆と入れられる最長の鉛筆を入れるようにしたら、TLEした 後者を求める時に、配列の要素削除…

ddcc2017-qual.contest.atcoder.jp github.com

ddcc2017-qual.contest.atcoder.jp github.com

tenka1-2017.contest.atcoder.jp 解き方 h,nを1から3500の範囲で全探索する。h, nが決まればwは求まる github.com

code-festival-2017-quala.contest.atcoder.jp 解き方 回文を作るのに必要な同じ文字の数を計算 各アルファベットの出現回数を計算 必要な文字数が多い場所から順に、条件を満たす最小のアルファベットを入れる貪欲 ここが嘘解法っぽさがある github.com

code-festival-2017-quala.contest.atcoder.jp 解き方 行、列を入れ替える順番は無視して良いので、何列、何行入れ替えるかで全探索 ハマったところ +=の副作用を見逃してた github.com

code-festival-2017-quala.contest.atcoder.jp github.com

E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…

D - Restoring Road Network 解き方 これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(d[i][j])を保持、更新する 距離が小さい方から順に考えていく。 町i, j間の最短距離がcの時、 もし、d[i][j] == cならば、もう辺を追加する必要は…

C - Sugar Water 解き方 A, B, C, Dそれぞれの操作を何回するか、全探索 A, Bについては、100A <= F <= 30 * 100より、たかだか30回 C, Dについては、最大でF/2g溶ける（E=100の時）ので、たかだか1500回 合計で[tex:O(109)]なので、ダメでは？という気もす…

F - Sandglass 解き方 ある時刻におけるAの砂の量は、max(E1+C, min(E2+C, a+C))の形で表せる（aは最初にAに入っている砂の量） 各r_iについて、E1, E2, Cを前計算しておき、クエリに対しては二分探索→最後だけ計算 r_{i-1}のときの関数が求まれば、そこから…

D - joisino's travel 解き方 すべての町の間の最短経路の距離を事前にWarshall Floyd等で前計算 町の回り方をR!通りすべて試す（R<=8なので間に合う） github.com

C - Write and Erase 解き方 unordered_setを使えば良い github.com

B - Theater やるだけ github.com

A - September 9 数字として扱ったが、文字列のほうが簡単だった。 github.com

D - Derangement 解き方 となるiの個数を数える ただし、上記のようなiが連続している場合、その2つを入れ替えれば良いので差し引く ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/d.ccgithub…

C - Together 解き方 差が2以下であれば、同じ数字にできる 差が2以下となる数字の個数の最大値を求める ソートして、尺取り法すれば良い ハマったところ 特になし https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/arc082/c.ccg…

agc019.contest.atcoder.jp 解き方 A[i] == A[j]を満たすA[i..j]を反転させる時、A[i+1..j-1]を反転させた時と同じになるので、それを引く ハマったところ 最初回文を除かないといけないと考え、実装はしたもののO(N^2)から落ちなかった 回文を除く方針は、…

agc019.contest.atcoder.jp 解き方 ただの貪欲 ハマったところ なんか貪欲法の実装に手間取ってしまった記憶がある https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc019/a.ccgithub.com