ABC181の解答
AtCoder Beginner Contest 181を解き終わったので解答を書いていきます。
問題はこちらから、
難易度はこんな感じでした。
A 0 （灰）
B 27 （灰）
C 212 （灰）
D 559 （茶）
E 1128 （緑）
F 1964 （青）
では、書いていきます。
A Heavy Rotation
白い服と黒い服を交互に着まわす人がいます。今日は白い服を着ています。n 日後には何色の服を着ているでしょうか？
という問題。
奇数日後と偶数日後で服の色が異なっているので、n の偶奇を判定してあげましょう。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
if (n & 1) cout << "Black" << endl;
else cout << "White" << endl;
return 0;
}最近、偶奇の判定を n&1 と書いています。処理が気持ち軽そうだなーって思うのですが、どうなんでしょう？
B Trapezoid Sum
ai 以上 bi 以下の整数の和を取得する、ということを n 回行った際の総和を求めましょう。
という問題。
ai から bi を一つずつ加算していけば答えが求まります。が、計算量が 10^11 ですので、少し工夫をします。
数学Bとかで学んだ、等差数列の総和の公式を使います。1 から n までの数（初項 1, 公差 1, 末項 n）の総和 Snは
Sn = n * (n+1) / 2
で求まります。今回は ai から bi までの和ですので、
S = Sbi - S(ai-1)
として、余分な1から ai-1 までの余分な部分を引いてあげましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
int main()
{
int n;
cin >> n;
ll ans = 0;
rep(i, n)
{
ll a, b; cin >> a >> b;
ll s1 = b * (b + 1) / 2;
ll s2 = a * (a + 1) / 2;
ans += s1 - s2 + a;
}
cout << ans << endl;
return 0;
}一応、ai から bi までの和を求める公式として、
S(初項~末項) = (初項 + 末項) * 項数 / 2
S(ai~bi) = (ai + bi) * (bi - ai +1) / 2
があります。結局、同じ式になりますのでどちらでもよいと思います。よりスムーズに書けて、ミスが少なくなる方を選びましょう。
C Collinearity
x,y平面にて複数点が与えられます。直線状に位置する3点の組み合わせが存在するかどうか求める問題です。
3点が同一直線状に位置する
という条件を考えます。様々あると思いますが、今回は浮動小数点誤差を防ぐために整数範囲で判定が可能な手法を用います。
3点(x1, y1), (x2, y2), (x3, y3) のうち、1,2を通る直線と、1,3を通る直線が一致しているかどうかを確かめましょう（どの点の組み合わせでも大丈夫です）。直線が共通の点（この場合（x2, y2））を通るので、あとは傾きをチェックします。
1,2の傾き = (y1 - y2) / (x1 - x2)
2,3の傾き = (y2 - y3) / (x2 - x3)
この2式が等しければ良いのですが、割り算をすると、小数点以下の切り捨てなり、浮動小数点誤差なりが生じるのでちょっと変形します。
(y1 - y2) * (x2 - x3) = (x1 - x2) * (y2 - y3)
こうすれば、桁を落とすことなく比較できます。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> x(n);
vector<int> y(n);
rep(i, n) cin >> x[i] >> y[i];
rep(i, n)rep(j, n)rep(k, n)
{
if (i >= j)continue;
if (j >= k)continue;
int x1 = x[i];
int x2 = x[j];
int x3 = x[k];
int y1 = y[i];
int y2 = y[j];
int y3 = y[k];
int l1 = (x1 - x2) * (y2 - y3);
int l2 = (x2 - x3) * (y1 - y2);
if (l1 == l2)
{
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}3点が直線状にあることの判定方法は様々ありますが、「誤差なく」という点がポイントだったと思います。
D Hachi
1 ~ 9の数字のみからなる数列が与えられます。その数列を並び替えて8の倍数が作れますか？という問題。
まず、8の倍数の判定方法について考えます。
8の倍数を8, 16, 24, ... と考えていくと、キリのいい数字に「1000」があります。この1000以降の8の倍数を考えると 1008, 1016, 1024, ...です。この場合でも、下3桁は依然と同様に出現します。つまり、
下3桁が8の倍数であればその数字は8の倍数である
ということが言えます。
今回は値を並び替えて8の倍数を作るので、入力された数字で「000」「008」「016」「024」「032」...「992」のいずれかが作れるかをチェックします（今回は"0"が入力されないので、もっと少ないです）。
そのために、まずは各数字が何回出現したかをカウントします。その出現テーブルをもとに、「000」～「992」のうちの一つでも作ることができたら、OKで、全部作れないのであればNGとなります。
試しに「112」を判定してみます。112は「1が2個」「2が1個」「3が0個」...「9が0個」あれば作ることができます。そのため、
もとの数字の出現テーブルの1の数 >= 2
2の数 >= 1
...
9の数 >= 0
として、すべて条件を満たせば「112」を作ることができます。
あとは、入力が3桁に満たない場合はコーナーケースとなり上記に従わないので個別に判定をしてあげることに気を付けましょう。
実装です。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
int main()
{
string s;
cin >> s;
int l = s.length();
if(l == 1)
{
if((s[0]-'0')%8==0) cout << "Yes"<< endl;
else cout << "No"<< endl;
return 0;
}
if(l == 2)
{
int s0 =s[0]-'0';
int s1 =s[1]-'0';
if((s0+s1*10)%8==0||(s1+s0*10)%8==0) cout << "Yes"<< endl;
else cout << "No"<< endl;
return 0;
}
vector<int> d(10);
rep(i,l) ++d[s[i]-'0'];
bool ans = true;
for(int i = 104;i<1000;i+=8)
{
int x = i;
vector<int> td(10,0);
rep(j,3)
{
++td[x%10];
x/=10;
}
ans = true;
rep(j,10) if(td[j] > d[j]) ans = false;
if(ans) break;
}
if(ans) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}試験後にtwitterがざわざわした問題です。みなさんそれぞれ異なった実装をしており、試験後も楽しむことができました。私もコンテスト中はなかなかに酷いプログラムを書き上げました。検索してみると面白いと思います。
E Transformable Teacher
身長が可変な先生がクラスに加わります。そのクラスで2人1組を作って、それぞれの身長の差を取ります。この差の合計の最小値を求める。
という問題です。
まず、ペアの組み方を考えます。といっても、クラスを背の順に並べて前から2人ずつペアを作っていく方法が最適な方法となります。これは、イメージ通りといいますか、自然なことだと思います。
また、先生の身長は m 種類あります。そのため先生の身長を一つ決めて、クラスの背の順の適切な位置に挿入する。その後、前後でペアを作って、その差の合計を求める。これを m 種類行って、その最小値を求める。
とやれば、答えを求めることができます。ただし、このように愚直にやると計算時間が間に合いません。
ということで工夫をしましょう。
まず、先生がいない場合の n 人のペアの取り方は、
(1, 2), (3, 4), (5, 6), (7, 8), ... ,(n-2, n-1), n
となります（n は奇数）。（奇数-偶数）でペアになっていることがわかりますね。次に適切な位置に先生を入れましょう。今回は 3, 4の間に入るとします。
(1, 2), (3, m), (4, 5), (6, 7), ... ,(n-3, n-2), (n-1,n)
ですね。先生が入ったことで、先生の前では変わらず（奇数-偶数）ですが、先生の後からは、(偶数-奇数)のペアになっていることがわかります。これは、4, 5のペアになっているところの間に入っても同じです。
(1, 2), (3, 4), (m, 5), (6, 7), ... ,(n-3, n-2), (n-1,n)
そのため、
(奇数-偶数)の差の累積和
(偶数-奇数)の差の累積和
を取得しておけば、先生の一つの身長に対して、
先生より前の(奇数-偶数）の差の累積和
先生とそのペアとなる生徒の差
先生より後の（偶数-奇数）の差の累積和
この3つを足し合わせることで、差の合計値を一発で求めることができます。3つ目の先生より後の(偶数-奇数)の差の累積和に関しては、先頭から(偶数-奇数)の差の累積和をとって、計算の際には
(偶数 - 奇数)の差の合計 ー 先生より前の（偶数- 奇数）の差の累積和
としてもよいですし、列の後ろから差の累積和を取ってもよいと思います。
あとは気合で配列の数字を合わせましょう。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;
const ll inf = 1e18;
int main()
{
int n, m;
cin >> n >> m;
int n2 = n / 2;
vector<int> h(n);
vector<int> w(m);
rep(i, n) cin >> h[i];
rep(i, m) cin >> w[i];
sort(h.begin(), h.end());
vector<int> d1((n+1)/2);
vector<int> d2((n+1)/2);
d1[0] = d2[0] = 0;
rep(i, n2)
{
int idx = i * 2;
d1[i+1] = d1[i]+ h[idx+1] - h[idx];
d2[i+1] = d2[i] + h[idx + 2] - h[idx + 1];
}
ll ans = inf;
rep(i, m)
{
int tw = w[i];
auto it = lower_bound(h.begin(), h.end(), tw) - h.begin();
if (it & 1) --it;
ll a = (ll)d1[it/2] + d2[n/2] - d2[it/2] + abs(h[it]- tw);
ans = min(ans,a);
}
cout << ans << endl;
return 0;
}プログラム中の
auto it = lower_bound(h.begin(), h.end(), tw) - h.begin();にて、先生の身長以下の直近の値を取るイテレータを取得できます。日本語が難しいですが、こうするといい感じの値になるということです。
あとは、最小値を取得したいので、はじめansには大きい値を入れておくのを忘れないようにしましょう。
F Silver Woods
半径 r の円が釘が打ってある道を通り抜けることができるかを判定する問題。説明が難しいので図の力を借ります。
この円が釘（黒点）を避けながら右端へ進んできます。釘にぶつからずに右端に到達できるような円の半径の最大値を求めます。ただし、釘に接する場合はセーフとします。
先に述べますが、今回は「二分探索法」と「Union-Find」の2つを用いて解きました。
まずは、考えやすいように問題文を読みかえます。丸を動かして考えていくのは大変なので、丸を大きさ0の点にして、釘の方を半径 r の円とします。
壁が r だけ縮まるのを忘れないようにしましょう。
こうやってみると、右に行けるかどうか一目瞭然ですね。
次は r を大きくしてみましょう。
この場合では右に行けませんね。
上記の例で分かる通り、r が極端に小さければ通り抜けられますし、 r が大変大きい場合には道が塞がってしまいます。
つまり、r を0から増加させていくと「OK」から「NG」へと移り変わるような「ある値」が存在することになります。その境界値となる値が今回求める答えとなりますので、それを二分探索法にて求めてあげます。
さて、次に「塞がっているか」をどのように判定するかを考えましょう。
「塞がっている」ということは「通る道がない」ということです。この点は〇の隙間の細い道を搔い潜って右端まで移動します。しかし、上の壁から下の壁まで〇で埋め尽くされていた場合には「通る隙間がない」、つまり「塞がっている」ということになります。
繰り返しになっていますが、要するに
「上の壁と下の壁が〇により接続されている」
際には「NG」となるわけです。言い換えると、〇を通って上から下まで移動できる際には「塞がってる」となります。
そのため、壁および〇をノードと見たてて、半径 r とした円周が重なっていたらリンクを伸ばすとしましょう（接するではダメです）。このようにすると本問題は
「上の壁のノードから、〇のノードを経由して下の壁のノードまで接続されているか」
というグラフの問題に言い換えることができます。グラフの接続といえば「Union-Find」ですね。条件を満たすものを片っ端から投げていきましょう。
塞がっている場合（左）と通り抜けられる場合（右）
必要なアルゴリズムは以上です。
最後にプログラムの流れを書いていきます。
１、OKとなる半径をlow = 0, NGとなる半径 up = 100とします。
（doubleの100だとどうなんでしょう？もう少し大きい値でも良いと思います。）
２、r = (low + up ) / 2とします。
３、半径 r にて重なる釘と壁、釘同士にリンクを伸ばします。
４、上と下の壁が繋がっていたら半径を小さく（up = r）、離れていたら半径を大きく(low = r)として、２に戻ります。
これを、終了条件まで繰り返します。今回は浮動小数点の計算なので、終了条件は一定回数の試行(80回)の終了時としました。この回数は、公式の放送で用いていた回数を採用しました。
実装です。
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
template<typename T>
struct UnionFind {
vector<int> d;
//コンストラクタ
UnionFind(int n = 0) : d(n, -1) {}
//根の探索と張り替え
int find(int x) {
if (d[x] < 0) return x;
//根のはりかえ
return d[x] = find(d[x]);
}
//根の結合
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
//大きい方に小さい方をくっつける
if (x < y) swap(x, y);
//サイズの更新
d[x] += d[y];
//結合
d[y] = x;
return true;
}
//サイズの取得
int size(int x) { return -d[find(x)]; }
//同じ集合に属しているか
bool same(int x, int y) { return (find(x) == find(y)); }
};
const int top = 100;
const int bottom = -100;
double dist(int x1, int x2, int y1, int y2)
{
double dx = (double) x1-x2;
double dy = (double) y1-y2;
return dx*dx+dy*dy;
}
int main()
{
int n; cin >> n;
vector<int> x(n);
vector<int> y(n);
rep(i,n) cin >> x[i] >> y[i];
double up = 200, low = 0;
rep(bi,80)
{
double mid = (up+low)/2;
UnionFind<int> uf(n+2);
//壁同士の判定
if(top-mid < bottom + mid) uf.unite(n,n+1);
//上下の壁との判定
rep(i,n)
{
if(y[i] + mid > top - mid) uf.unite(i,n);
if(y[i] - mid < bottom + mid) uf.unite(i,n+1);
}
//釘同士の判定
rep(i,n)rep(j,n)
{
if(i >= j) continue;
if(dist(x[i],x[j],y[i],y[j]) < 4*mid*mid) uf.unite(i,j);
}
if(uf.same(n,n+1)) up = mid;
else low = mid;
}
cout << setprecision(7) <<endl;
cout << low << endl;
}上の壁を n 番目、下の壁を n+1 番目のノードしています。また、距離の判定の際に、sqrtだと少し重いため、2乗のまま比較しています。
また、本問題では生じないですが、釘がないという意地悪なケースがあるかもしれないので、一応上の壁と下の壁の接触判定も計算しています。一応です。
数学といえば数学ですが、パズルみたいな面を持つ問題で非常に楽しく考えることができました。とはいいつつも、いくつかの数学アルゴリズムを用いて対処しなければなりません。勉強した成果が発揮されますね。
私は競技プログラミング歴3か月程のひよっこですが、本問題が一番お気に入りの問題かもしれません。
この記事が気に入ったらサポートをしてみませんか？