E - Don't Be a Subsequence 解き方 部分列でない最小の文字列の、先頭の文字を決める→2文字目以降の文字列について考える、を繰り返すDP DPする時には、後ろから決めていかないといけない どの文字を先頭にするか決めるために、どの文字がどこに現れるかに…

D - Coloring Dominoes 解き方 左から順々に見ていく。直前のタイルの貼り方と、次のタイルの貼り方は2*2の4パターンなので、それぞれ場合分けしながら計算する ハマったところ 上下に見ようとしたり、DFSしようとしたり、迷走していた 高さ2と小さいのだか…

C - Make a Rectangle 解き方 2個以上存在する数字を大きい方から2つ選んで長方形を作る ハマったところ 正方形のケース（同じ数字が2回登場する）を忘れていた github.com

D - Transit Tree Path 解き方 aからKへの距離とKからbへの距離の和を出力する Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。 ハマったところ 0-indexと1-index混ぜてた 読み込み時に変えておくべきという話はありそう 最初全頂点から全頂…

C - Multiple Clocks 解き方 最小公倍数を求めるだけ。場合によってはオーバーフローに気をつけないといけないのかな。 github.com

B - Two Switches 解き方 区間[A:B]と[C:D]の重複区間を求める。[max(A, C):min(B, D)]。 github.com

A - Palindromic Number 解き方 先頭から確認するだけ github.com

arc080.contest.atcoder.jp 解き方 辞書順なので、先頭から埋める 最初の数列で、奇数番目が解答の先頭に、偶数番目が解答の2番目にくる 奇数番目の最小の数字が先頭に、それより後ろで最小の偶数番目が2番目にくる 3つの領域に分割されるので、それらについ…

arc080.contest.atcoder.jp 解き方 左端あたりからジグザグに指定個数ずつ埋めていく ハマったところ WをNと書き間違えた github.com

arc080.contest.atcoder.jp 解き方 すべての数字を4で割った余りに変えても同じ 2は全部連続させて良い（分けることでうまく行くパターンが増えることはない） 2の連続、1のとなりには0が来ないといけない（2...2, 0, 1, 0, 1, ...., 1, 0, 1など）ので、そ…

arc079.contest.atcoder.jp 解き方 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ 閉路とそれ以外にまず分ける 閉路以外の部分は、根を0、その上を…としていくと一意に定まる 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算…

arc079.contest.atcoder.jp 解き方 1回の操作で、数列の総和は-1される 操作回数は最低でも 回操作をすると、総和が0になるのでこれが操作回数の上限になる（多分） K回の操作後、条件を満たすかどうかは全体を+Kしたあと、K回どれかの要素を-N-1する操作と…

arc079.contest.atcoder.jp 解き方 Nは50に固定しておき、とりあえずN-1+K/NをN個並べる K%Nとかを使って数字を調整すれば構成できる ハマったところ 素直に構成できたが、自信を持てず時間を無駄にしたみたいなところがある github.com

arc079.contest.atcoder.jp 解き方 1から1回で行けるところ、Nに1回で行けるところを列挙し、重複があるかどうか調査 ハマったところ 順調に解けた気がする github.com

agc018.contest.atcoder.jp 解き方 全競技を実施すると仮定して、そこから参加人数が多いものを消していく貪欲 ハマったところ 実施競技0から増やしていく貪欲がWAになったあと諦めた 逆からの貪欲くらいは試してみるべきだった github.com

agc018.contest.atcoder.jp 解き方 すべての数の最大公約数を求めて、その倍数かどうかで判定 ハマったところ gcdの実装再確認に時間をかけた gcdを求めれば良いことに確信を持つまでに時間がかかった。 github.com

arc078.contest.atcoder.jp 解き方 1から｀N`へのパス上をまず塗り、その後残りを塗るのが最適解 1とNからの距離でそのマスが黒か白か決まる 1とNの2箇所から幅優先探索して、黒白それぞれの塗られる数を探索 ハマったところ Nヶ所から幅優先探索する方法を…

arc078.contest.atcoder.jp 解き方 カードに書かれている数字の和を求めるのはO(n) 上から1枚取る場合、2枚取る場合、と順々にxとyを求めるのは、それぞれO(1)でできる 全部計算してminを求める ハマったところ xをi32で宣言していてオーバーフロー 定数項を…

agc017.contest.atcoder.jp 解き方 一つ前のマスより小さくなるマスの数を固定して，その条件のもと達成できるか判定，これをN回繰り返す ハマった所 どれかの値を固定することで高速に判定し，それをn回繰り返す，って発想が出づらい

arc077.contest.atcoder.jp 解き方 重複を考えずに組み合わせを計算し，重複分を引く 条件より重複は必ず1個存在する 組み合わせの計算は，n!を事前に計算しておく事でO(1)で行う n!^{-1}もmodを取る場合は前計算できる ハマった所 組み合わせ計算の高速化方…

arc077.contest.atcoder.jp 解き方 自分の解法 偶奇で場合分けし，前半分と後ろ半分をそれぞれ表示 想定解 dequeあたりを使って，前後から要素を挿入→最後に表示 ハマった所 特に無かったと思う

http://arc076.contest.atcoder.jp/tasks/arc076_b 解き方 コストの定義を使って，辺の数をO(N)に削減 最小全域木をクラスカルなりプリムなりで求める プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない ハマった所 プリム，クラスカルの…

arc076.contest.atcoder.jp 解き方 abs(M-N)が2以上，1，0で場合分け． ハマった所 隣接してはいけないので，組み合わせ(nCr)はいらない テストケース通して気づいた M+1