問題 beta.atcoder.jp 解法 とすると操作2のみでソートしようとする場合、それぞれの中でバブルソートをしていることになる。つまり操作1を行う必要があるのはの要素との要素を入れ替えたいときだけである。 操作1を行う回数を求めるにはをソートしたものを…

問題 C - /\/\/\/ 解法 偶数番目の要素からなる数列をeven、奇数番目の要素からなる数列をoddとすればそれぞれの数列での最頻値even_1、odd_1に書き換えれば良さそうなことに気がつく。しかし問題の制約からeven_1 ≠ odd_1でないといけない。そこで、それぞ…

問題 B - RGB Coloring 解法 緑色で塗られたマスは点もらえることから、緑色のマス目は赤色と青色の両方が塗られたマス目だと思うことができる。赤色、青色、緑色に塗られたマス目の個数をそれぞれとすると、このときの得点は点である。ここで であることに…

問題 B - Find Symmetries 解法 2つ目の盤面が良い盤面であるかどうかチェックするには愚直にやるとの計算量時間がかかる。考えられるの個数は個なので全てのに対して2つ目の盤面をチェックする方法ではの計算量時間がかかってTLEになる。 なので盤面チェッ…

問題 D - Good Grid 解法 色の塗替えの候補は30×29×28通り。 すべての色の塗り替え方について各マス目を見て違和感を計算する方法ではの時間計算量がかかりTLEになってしまう。 そこでに対してとなるマス目にどの色が何個あるかを事前に計算しておけば、色の…

問題 D - Grid Components 解法 まず100×100のグリッドを用意します。 上半分を白、下半分を黒で塗ります。 上半分のうち奇数行目を見ていき各行について1個おきにマス目を黒くします。個のマスを黒く塗ったら終了。 こうすることで白の連結成分の数を変えず…

問題 D - Menagerie 解法 最初の2人の動物の種類が決まれば、3番目以降の動物の種類は順番に決まっていく、ということに気がつけば後は実装するだけ。 最初の2人の動物の種類の組合せは4通りなので、全部試してそれぞれ条件に矛盾しないかどうかを調べる。 …

問題 B - Median Pyramid Easy 解法 実際にピラミッドを作るにはの時間計算量がかかるため無理。なので入力から直接数列を作ることを考えないといけない。 のときは無理である(中央値になりえないため)。のときはを出力すれば良い。他の場合は解説pdfにある…

問題 C - 二人のアルピニスト / Two Alpinists 解法 まずのとき答えはになる。そうでないときを考える。のときである事がわかる。このとき、でないと条件に矛盾する。同じようにのときであり、このときでないと条件に矛盾する。かつのとき山の高さはであれば…

問題 B - Moderate Differences 解法 とするととなる。ここでに関して、またはが成立する。個のうち前者の個数が個だったとするとこのとき条件を満たすにはである必要がある。逆にこれが成立する時、条件を満たすように数列を作ることができる。であるかどう…

問題 D - いろはちゃんとマス目 / Iroha and a Grid 解法 高校の数Aでよくあった問題。 (は素数)を求めるライブラリがあるとすぐ書ける。 #include <iostream> #include <vector> using namespace std; typedef long long int ll; const ll mod = 1e9+7; const ll INF = 1e9; c</vector></iostream>…

問題 B - Simplified mahjong 解法 先頭から順に見ていく。ペアを作れるだけ作って、カードが余るなら(1枚だけ余る)そのカードを次の値のカード1枚と組み合わせる。これを繰り返す。 #include <iostream> #include <string> #include <algorithm> #include <cstdio> #include <vector> #include <queue> #include <set></set></queue></vector></cstdio></algorithm></string></iostream>…

問題 B - Box and Ball 解法 シュミレーションで間に合う。 各箱に赤のボールが入っているかどうかということと、各箱のボールの数を記憶すればよい。 に赤いボールが入っている時に操作を行えば、に赤いボールが入っている可能性があることになる。操作をお…

問題 C - 次のアルファベット / Next Letter 解法 文字列を先頭から見ていく。今見ている文字がをaに変更できる場合、操作を何回か行ってaにしたほうが文字列は辞書式順序で小さくなる。変更できない場合そのままにしておくのが良い。 最後まで見て操作回数…

問題 D - 連結 / Connectivity 解法 鉄道が枝であるグラフと道路が枝であるグラフそれぞれでUnion-Findを行う。 頂点が鉄道と道路両方で連結であることは、がの同じ連結成分に含まれているかつの同じ連結成分に含まれている、ということと同値である。同じ連…

問題 C - Chocolate Bar 解法 分割の方法は4パターンある(解説pdf)。4パターンそれぞれを全探索して調べる。1つの長方形を決めると残りの2つは余っている長方形を均等に分けるのが良い。 結局の時間計算量で解ける。 #include <iostream> using namespace std; typedef</iostream>…

問題 D - Equals 解法 頂点集合が、枝集合がである無向グラフを考える。このときGの2つの頂点が同じ連結成分に含まれるならはスワップを何回か繰り返すことで値を入れ替える事ができる事がわかる(解説pdf)。よって頂点とが同じ連結成分に含まれているような…

問題 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>…