問題 D - アンバランス / Unbalanced 解法 sの部分文字列のうち同じ文字が2つ連続しているところはアンバランスな文字列である。 同じ文字が2つ連続しているところがない場合、過半数を占める文字をAとしたとき、AXAの形の3文字を見つければ良い。なぜなら、…

問題 C - 4-adjacent 解法 条件から数列内に奇数があった場合その数の隣は4の倍数でないといけないことが分かる。 4の倍数と4の倍数以外の偶数と奇数の数を数える。 4の倍数と4の倍数以外の偶数と奇数をそれぞれ4、2、1と書くことにすると、2がない場合14141…

問題 A - STring 解法 文字列の先頭からSとTの個数を数えていく。先頭からSを集めていってTに出会ったらSを1つ捨てるイメージ。1つもSを持ってない状態でTに出会ったらそのTは最後まで残る。 #include <iostream> #include <string> using namespace std; int main() { string </string></iostream>…

問題 C - Sugar Water 解法 水の重さは非負整数を用いて、砂糖の重さは非負整数を用いてと書ける。 したがって次の2つの式を満たす非負整数のうちを最大にするもの全探索する。一応間に合う。 濃度が0%のときは水の重さを適当に出力する。 感想 pythonとかだ…

問題 D - Mixing Experiment 解法 どれを買ってどれを買わないかという組み合わせは2^40通りなので全探索は無理。このタイプの問題は01ナップサックに似ている。DPを考える。2つの物質の比を考えないといけないが比を見るには物質AとBをどれだけ購入したか分…

問題 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report 解法 回目に見たときの得票数をとする。回目にテレビを見た時、得票数の比がなら、二人の得票数はあるに対して、になっており、さらに、となっている。このようなで最小なものはで求められ…

問題 C - こだわり者いろはちゃん / Iroha's Obsession 解法 条件から必ず解は存在し、なので解は5桁以下の数字となることが分かる。 したがってからまでの数字を順番に条件を満たすかどうかを調べる。 感想 この時期の300点問題に比べると最近の300点は難し…

問題 C - Bridge 解法 連結成分の数を数えればいいのでUnion-Findを使った。これでもACできるが、単に連結かどうか調べるだけなのでDFSで十分だしDFSのほうがやや計算量が小さい。 全ての枝に対して、元のグラフからその枝を取り除いたグラフが連結であるか…

問題 C - Shopping Street 解法 josinoがお店を開ける時間帯の組み合わせは通りなので全部調べる。bit全探索というやつ。bit操作は慣れないと難しい。(bit>>j&1)でbitのj番目に1が立っているか(j番目の時間帯に店を開けているかどうか)を判別している。 #inc…

問題 A - AtCoder Group Contest 解法 ぱっと見て、参加者を弱い順にソートしたとき最初の人をバラバラのチームに入れれば良いことが分かる。 チームの強さになる人のうち1番強い人は全体で2番目に強い人である。この人と全体で1番強い人と全体で1番弱い人を…

問題はこちら。AtCoder Beginner Contest 101 - AtCoder A - Eating Symbols Easy ans = 0から始めて、Sの各文字が+なら+1、-なら-1する。 #include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; int ans = 0; for(int i = 0; i < 4; </string></iostream>…

競技プログラミングで解いた問題の記録かつAtCoder赤色になるまでの記録のブログ。