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