問題 atcoder.jp 解法 これと同じ感じでやる。 atcoder.jp ある数が2番目に大きい区間はどういう特徴があるか考える。 よく考えるとはより大きい数をちょうど1つ含んでいる区間である事がわかる。 より大きく、かつより右側にあるもののうち一番左側にあるも…

このAGCは引越の疲れで参加できてなかった... 問題 atcoder.jp 解法 手で実験してみるとDPぽいな〜と思ったのでDPを考えます. に対する塗り方の個数 とします. 色が切り替わるときに注目します. いま，j+1番目の石を見ているとしましょう. さらにj+1番目の石…

問題 atcoder.jp 解法 連結無向グラフから枝を取り除いていったときに非連結な頂点のペアの個数を答える問題.一般に，グラフから枝や頂点を取り除くという操作は難しいです. 逆に枝や頂点を追加するという操作は比較的かんたんです.今回の場合，枝を後ろから…

問題 atcoder.jp 解法 まずT,S,Z型は使えません. また，O型はそれ単体で横の長さが2の長方形になので必ず求めたい長方形に含めることができます. 結局I,J,L型の組み合わせを考えればいいです.同じ型を２つ組み合わせることで横の長さが4の長方形ができます.(…

問題 atcoder.jp 解法 まずとの色は一致するので入力のをとしていいです.黒色の正方形の左下をどこにするかで平面の色の塗り方は決まります. 塗り方の周期性から黒色の正方形の左下の座標の候補はとしていいです.したがって個の塗り方全てに対して叶えられる…

問題 atcoder.jp 解法 最大クリークを求める問題 (無向グラフGのクリークとはGの完全部分グラフ(の頂点集合)のこと). 頂点数が少ないので全ての部分グラフを見てあげることができる. 全列挙にはbitを使うのが便利. #include <iostream> #include <vector> #include <set> using name</set></vector></iostream>…

問題 atcoder.jp 解法 根が空の文字列に対応していて、左の子には０を右の子には1を文字列に足したものを対応させる完全二分木を考えます。 そうすると良い文字列があったとき、この二分木上での先祖子孫に対応する文字列はに追加することはできません。 つ…

問題 beta.atcoder.jp 解放 DPを使いましょう。 dp[i][j] を上からicm目まで横棒を引いたとき左からj本目の縦棒に行くあみだくじの数とします。 こうするとdp[H][K]が答えになります。 最初は1本目の縦棒にいるのでdp[0][1] = 1です。 正しいあみだくじの条…

問題 beta.atcoder.jp 解法 前から順に見ていって...01...(または...10...)というように異なる文字に出会ったら"...0"か"1..."の長い方を反転すれば良い。反転したものの中で一番短いものが答えになる。 #include <iostream> #include <string> #include <algorithm> #include <cstdio> #include <vector> </vector></cstdio></algorithm></string></iostream>…

問題 beta.atcoder.jp 解法 回文は各アルファベットに対して左半分と右半分でそのアルファベットが出てくる回数が同じである。 以下の場合は回文にすることはできない。 Sにおいて奇数回現れる文字が2種類以上 Sにおいて奇数回現れる文字が1種類かつ|S|が偶…

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

問題 E - Tr/ee 解法 木という条件から、でないといけない事がわかります。 逆にこの条件が成り立っているとき条件を満たす木を構成できます。 まずという枝を用意します。とします。の2文字目から見ていき、番目の文字を見ているとき枝を追加します。ならと…

問題 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 - FT Robot 解法 中でが出て来るたびにロボットが動く方向が軸方向→軸方向→軸方向となる。ここで軸方向と軸方向の動きは独立に考えても良い。 軸方向について動いているときを考える。このときロボットが移動できる点は(1回前に軸方向について動いた…

問題 D - Median of Medians 解法 であり、数列の長さはなので数列を実際につくるとTLEになるので別の方法を考えないといけない。 editorialがめちゃめちゃ分かりやすいので特に書くことなし。 BITでの反転数の求め方はここ www.geeksforgeeks.org が分かり…

問題 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)。よって頂点とが同じ連結成分に含まれているような…