AtCoder Beginner Contest 174の解答
ABC174を解き終わって自分なりに理解できたのでアウトプットとして書いてきます。私自身、abc初心者のため、何も知らない私が見ても理解できるように少し冗長に書いてきます。いろいろな方のプログラムや解説を参考にしたため、同様の実装となっている部分があるかもしれません。ご容赦ください。
問題はこちらから。
https://atcoder.jp/contests/abc174/tasks
A Air Conditioner
室温が30℃以上なら、冷房のスイッチを入れる問題。
if文を1つ使えば完成。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin >> x;
string ans;
if(x >= 30) ans = "Yes";
else ans = "No";
cout << ans;
return 0;
}とくに問題なし、次行きましょう。
B Distance
題名の通り、
n個地点が与えられて距離d以下の点は何個ありますか？という問題。
ポイントとしては、dとか地点の座標(xi, yi)が2×10^5で与えられる点。
距離を求めるときに二乗するから10^10オーダーになる。int型だと10^9オーダーのため、オーバーフローで間違いになるから注意。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll = long long;
int main()
{
ll n, d;
cin >> n >> d;
vector<ll> x(n);
vector<ll> y(n);
rep(i, n) cin >> x[i] >> y[i];
int cnt = 0;
rep(i, n){
if(x[i]*x[i] + y[i]*y[i] <= d*d) cnt++;
}
cout << cnt;
return 0;
}補足をすると、距離の導出にはルート演算を用いるけど、sqrtの演算が少し重いため、dの方を2乗にして比較したほうがスマートです。
オーバーフローに気を付ければ簡単ですね。次。
C Repsept
kの倍数と7が好きな少し変わった高橋君の問題。
7, 77, 777, ... という数列の中に初めての倍数が登場するのは何項目か？
という問題。
まず初めに考え付いたのはanはa(n-1)を用いて、
an = 10 * a(n-1) + 7
で表現できるから、kで割った余りが0になるまでwhile文を回せばいけるんじゃないかと思いましたが、以下の2点で困りました。
・入力例3で「999983」の答えが「999982」となっていて、999982桁が必要になること。
・答えが見つからないときの終了条件がわからないこと。
1つ目としては合同式の性質を用います。
私が高校生のときには合同式というものを学校で習っていなく、あいにく大学でも扱わなかった気がします。今の高校生や私より上の年代の方はどうなのでしょう？私は数学検定の勉強をしてる時に何とか出会えました。そのため、なじみのない方もいるかもしれません。
合同式は割り算のあまりに関する式です。
例えば、10と4は3で割るとどちらも余りは1になります。このとき、
10 ≡ 4 mod 3
と表されます。10と4は3で割ると余りが同じだよ。という意味です。
さて、この式に操作を加えます。
一つ目は足し算です。例えば、10と4に4を足して14と8にしてみます。これらを3で割るとどちらも余りは2になるので
14 ≡ 8 mod 3
となります。考えてみれば当然ですね。これが合同式の和です。
次は掛け算なのですが、次のようにして成り立ちます。厳密ではないですが、感覚はわかると思います。
これで、準備ができました。これがわかると何が嬉しいかというと
7, 77, 777, ...で考えなくても、余りについて考えれば良いということになります。先に述べたan = 10 * a(n-1) + 7という、関係を関数として考えると、
f(x) = 10x + 7
になります。関数は入れた値がf(x)の操作をされて出てくる箱だよ、と考えるとわかりやすいかもしれません。今回は入れた数に10をかけて7を足す箱という感じです。先ほどの性質が使えますね。この関数と余りの関係は次のようになります。
こんな感じです。
後は終了の条件についてです。余りは割る数と同じ種類数しかない（3で割るなら0, 1, 2）ので、その分の配列を確保していて出現を監視します。同じ余りが出てきてしまったら、条件を満たす答えはない、問題に従うなら「-1」を返して終了します。
長々と書いてしまいましたが、実装に移ります。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < n; i++)
int main()
{
int rem = 0;
int k;
cin >> k;
vector<bool> app(k);
int cnt = 0;
while(1)
{
cnt++;
rem = (rem * 10 + 7) % k;
if(rem == 0) break;
else if(app[rem-1])
{
cnt = -1;
break;
}
else app[rem-1] = true;
}
cout << cnt << endl;
return 0;
}
なかなかに大変な内容でしたが、無事できました。次の問題はこれより易しいのでめげずに書きます。
D Alter Altar
災いを防ぐ問題です。
白と赤の石が並んでいて、赤の石の左に白の石があると災いが起こるのでそれを防ぎます。そのために、私たちは次の二つができます。
・2つの石を入れ替える。（隣り合ってなくてもよい）
・石の色を反転させる。
何回操作をすれば災いが止まりますか？という問題です。いろいろと条件や操作がありますが、どうなれば災いが止まるのかを落ち着いて考えます。結論を述べてしまえば、全ての赤の石を左に、白の石を右に寄せてしまえばよいです。
RRRRRWWWWWWWW (R : 赤、W：白)
こうなれば大丈夫です。
完成が見えたのでそこから考えます。本問題では操作回数を求めます。当たり前ですが、Rは左からRの個数分だけ並びます。そして、その中にあるWを追い出してしまえばよいのです。反転操作はしません。
そのため、まずRの数を数えて、次に左からRまでにあるWの数をカウントしてあげれば終了です。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main()
{
int stoneNum;
string stones;
cin >> stoneNum >> stones;
int iterW,iterR;
int cntR = 0;
int ans = 0;
rep(i,stoneNum)
{
if(stones[i] == 'R') ++cntR;
}
rep(i,cntR)
{
if(stones[i] == 'W') ++ans;
}
cout << ans << endl;
return 0;
}分かってしまえば簡単ですが、試験中には思いつきませんでした。初めは左からW、右からRを検索して、文字列を操作してましたが非常に計算量が増えるため諦めました。数えるだけのこの方法はスマートですね。
E Logs
n本の丸太（長さがa1, a2, ... ,an）をk回切る。
丸太の最大値が最小となるときの最小値を求める。
（小数点切り上げ）
という、最大値最小化の問題。本問題では、以前記事を書いた、2分探索法を用います。まず、どのように考えるかを書いていきます。
丸太をk回切ることができる点に注目をします。1回目にa1を半分にして、2回目に、、と考えていると日が暮れてしまうので、切れ端を除いて、全部を一定の長さLに切ることを考えます。
丸太が2本（20cm, 30cm）があり、5回まで切ることができるとします。ある長さLを30とした場合、一回も切らなくてもすべてが30以下になります。適当に13とした場合、20cmを13cmと7cmに1回切る。30cmを13cm,13cm,4cmと2回切ります。結果3回で達成できました。
次に設定を極度に小さくします。1としましょう。その場合、合計で48回切らないといけないのでkの条件を満たせません。2としてもダメです。
上端、下端から順にやっていくと、どこかの長さではぎりぎりOKで、それよりも短いとNGという境界が出現します。今回は小数点切り上げの結果を出力なので、LではOKなのに1増やすとNGという数字があります。
このときのL+1が答えになります。
この数の導出は「high or low」で数を当てる方法とまったく同じです。上限と下限の中間を言って、「高い」「低い」に従って、上限、下限を更新します。
以下実装です。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i,n) cin >> a[i];
int up = *max_element(a.begin(),a.end());
int low = 0;
int mid;
int cnt = 0;
while(up - low > 1)
{
cnt = 0;
mid = (up + low) / 2;
rep(i, n)
{
if(a[i] % mid == 0) cnt += a[i] / mid -1;
else cnt += a[i] / mid;
if(cnt > k)
{
low = mid;
break;
}
}
if(cnt <= k) up = mid;
}
cout << up;
return 0;
}初めはこの問題と2分探索の関係が理解できずに、なかなかに悩みました。自分なりにかみ砕くことができたと思います。
F Range Set Query
数列のある区間の中に何種類の数字がありますか？
という問題。ぱっとみたとき、for文を区間のインデックス分だけ回して、出た数字を配列に格納、1回目ならカウントを+1、2回目以降なら無視。で行けるじゃん、簡単じゃね、と高を括ってました。実装してみると、計算時間超過。甘くないですね。
この問題は複数の処理が必要なため、目標を更新しながらゆっくり一歩一歩進んでいきます。
現在の目標：区間内の数の種類を求める
まず、求められているのは区間[l~r]に含まれる数の種類です。これをどう求めるか考えます。例えば以下の数列があったとします。
番号 1 2 3 4 5 6 7 8 9 10
数字 2 5 6 5 2 1 7 9 7 2
l = 4, r = 10とすると、その中の数字は{1, 2, 5, 7, 9}の5種類あります。この5は次のように求められます。
区間内の数は10-4+1の植木算で7個ある。
そのうち2と5が1セット重複しているため、7-2で5個となる。
ということで、目標を更新します。
現在の目標：区間内の重複を求める。
重複を求めるために、直前に出現した同じ数字の位置を考えます。例の場合では4番目の5の前には2番目に5が出現しています。ということで、4番目から2番目に向かって矢印を書いてあげましょう。なぜと思うかもしれませんが、後程説明します。他の数に関しても、矢印を書いてあげます。5番目の2から1番目の2へ、9番目の7から7番目の7へ、10番目の2から5番目の2へ。
矢印がかけたら再び区間を考えます。l = 4, r = 10のとき、その区間に完全に含まれている矢印は2つあります。この2つが数の重複数と一致します。賢いことを考えますね。
そのため目標は次の通りになります。
現在の目標：区間の中に←が何個含まれているか。
矢印が書けたら、数列内の数字は意味がないので無視してしまいましょう。番号のインデックスと矢印の始点、終点に注目をします。矢印の始点のインデックスをt、終点のインデックスをsとすると、
(s, t) = (7, 9) ・・・重複する7を結ぶ矢印
のような感じで表せます。この矢印が区間に含まれる条件は次の通りです。
l ≦ s かつ t ≦ r
となります。例の矢印では、
l = 4 ≦ s = 7 かつ t = 9 ≦ r = 10
で条件を満たすので、含まれていることがわかります。(s, t) = (1, 5)はsの条件を満たさないので含まれてないです。
条件がわかったので、矢印を数えていきます。偶然にも矢印の要素(s, t)および、区間の要素(l, r)も2次元の座標にプロットできそうですね。プロットしていきます。
グラフの中で l ≦ s かつ t ≦ rの条件を満たすのは赤色で示した範囲となります。そのため、区間の座標をプロットした点よりも右下（境界を含む）にある点の個数が重複数と一致することになります。
ということで、
現在の目標：区間の点の右下にある点の個数を求める。
となります。これが最後の目標です。頑張ります。
どうやって2次元平面の点を効率よく数えるかを考えます。
２要素考えるのは難しいので1要素を固定して、次元を１次元に減らして考えます。数学の問題なんかを考えるときによく使う手です。平面走査と呼ばれます。
今回はx軸を固定します。ある区間の座標の右下の点を考えますが、右は無視して、下にある点だけを考えます。それならfor文とif文一つずつで簡単に数えることができます。for文を回して, t <= rなら+1していくだけです。
次に、無視したx軸を考えます。区間の座標よりも右にあるものを数えればいいので、右から順番に探索をして、矢印の座標にぶつかったらそのy座標の値(この場合は t)を保存していきます。区間の座標にぶつかったら、保存してある座標のなかから、r以下のものの数を数えれば良いです。
また、本問題では区間は複数与えられるので効率化のために一緒に処理していきます。このようにしないと時間が足りません。
平面走査を図で示します。
以上のアルゴリズムを実装すれば所望の出力が得られます。
ざっくりとまとめると
１ 重複を考える
２ 矢印を引く
３ 区間内の矢印の数を数える
４ グラフにプロットする
５ x軸に関して走査を行い、右下の点を数える
こんな感じです。
本当に長くなりましたが、実装に移ります。
といいたいのですが、このまま実装をすると計算時間が足りません。そのためBinary Indexed Tree(BIT) 、フェニック木(Fenwick Tree)と呼ばれる手法を導入します。これに関しては後日記事を書きたいと思います。端的に言うと、配列に要素をそのまま入れるんじゃなくて、いい感じに要素と要素の和を組み合わせて入れると、高速に加算と要素の和が計算できるよ、というものです。
書きました。
この手法の導入により1秒ほど高速化しました。たった1秒ですがこの差で正解と不正解が分かれます。恐ろしい世界です。
実装です。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using P = pair<int, int>;
//BITの実装
template<typename T>
struct BIT {
int n;
vector<T> bit;
BIT(int n=0):n(n),bit(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
bit[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += bit[i];
}
return x;
}
};
int main()
{
int n, q; cin >> n >> q;
vector<int> c(n);
rep(i,n){
cin >> c[i];
c[i]--;
}
//クエリを始点の大きさをもとに並べる---
vector<vector<P>> query(n);
rep(i,q){
int l, r;
cin >> l >> r;
l--; r--;
//番号も保持しておく
query[l].emplace_back(r,i);
}
//矢印の配列をつくる------------------
vector<vector<int>> arrow(n);
//既に現れた数字を格納する
vector<int> app(n,-1);
rep(i, n)
{
int num = app[c[i]];
if(num != -1)
{
arrow[num].emplace_back(i);
}
app[c[i]] = i;
}
//X軸に関して走査を行う-----------------
vector<int> ans(q);
BIT<int> bit(n);
//x軸の大きい順に調べる
for(int x = n-1; x >= 0; --x)
{
//矢印の座標と一致したら、bitのy座標番目を+1
for(int y : arrow[x]) bit.add(y, 1);
//クエリを調べる
for(P qu : query[x])
{
int r = qu.first, i = qu.second;
//bitのrまでの数字の合計が重複分
ans[i] = (r-x+1) - bit.sum(r);
}
}
rep(i, q) cout << ans[i] << endl;
return 0;
}問題もそうですが、BITの理解に時間がかかりました。時間は超過しますが、x走査をして、矢印座標の t を格納して、区間座標に来たら格納した t に関して t <= rとしても答えが出ます。私も初めはそうしてました。
問題を変換していくのも、BITを導入するのも、この問題を記事にまとめるのも大変でした。最終問題にふさわしい問題です。ただ、典型的な問題らしいので、しっかりと理解したいですね。
さいごに
この記事を書くにあたり、解説をしてくださっているブログや動画を何回も見ましたが、こんな賢い方法があるんやな、と感心しっぱなしでした。初回ということもあり、収穫の多い体験で大変満足です。
非常に長くなりましたが、この記事が誰かのお役に立てば幸いです。
この記事が気に入ったらサポートをしてみませんか？