ABC177の解答
AtCoder Beginner Contest177のアウトプットを書いていきます。
問題はこちらから。
https://atcoder.jp/contests/abc177/tasks
A Don't be late
待ち合わせに間に合うかどうかの問題。「みはじ」の問題なため、
d / s <= t
で良いのですが、int型だと値を切り捨てるため、両辺にsをかけて掛け算の形にします。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
int main()
{
int d, t, s;
cin >> d >> t >> s;
string ans;
if(s*t >= d) ans = "Yes";
else ans = "No";
cout << ans << endl;
return 0;
}B Substring
2つの文字列S, Tが与えられるときに、TがSの部分文字列となるのためには、最低何回書き換える必要があるか。という問題。
部分文字列というのは連続する部分列のことを指し、S = "abcde", T ="cde"の場合、”abcde”は"cde"を含みますので、TはSの部分文字列になります。
この問題は任意の点から開始してTがSと何文字異なっているかが答えとなります。そのため、文字列Sを開始位置をずらしながら全部探索していけば答えが出ます。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
int main()
{
string s, t;
cin >> s >> t;
int ls = s.length();
int lt = t.length();
int ans = 0;
rep(i,ls-lt+1){
int cnt = 0;
rep(j,lt){
if(s[j+i] == t[j]) ++cnt;
}
ans = max(cnt,ans);
}
ans = lt - ans;
cout << ans << endl;
return 0;
}探索回数は（Sのサイズ）ー（Tのサイズ）に１を足した数になるので、忘れないようにしましょう。
C Sum of product of pairs
n個の整数A1, ... ,Anが与えられます。そのうち2つを数字を取り出した全ての組み合わせに関して、2つの積の総和を求める問題。ただし、答えは、10^9+7のあまりで求めます。
愚直に書けば簡単ですが、nの条件が n <= 2*10^5 で n_C_2 程度の計算量となるので、TLEします。そのため計算の工夫が必要です。
様々な手法があるようですが、今回は部分和を用います。｛1,2,3,4｝という数列を例にとります。愚直にやると
1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4
となります。これを括ってあげると、
4 * (1+2+3) + 3 * (1+2) + 2 * 1
となります。計算の都合上大きい方から括りました。となるので、i 項目は
(i +1) * (iまでの総和)
となります。右の項から加算をしていけば総和は都度計算できるので、これをプログラムに起こします。例では数値とインデックス番号を一致させていますが、これを配列のインデックスと対応させれば大丈夫です。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
#define div 1000000007
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> b;
int sum = 0;
rep(i,n){
cin >> a[i];
sum = (sum + a[i]) % div;;
b.emplace_back(sum);
}
int ans = 0;
rep(i,n-1){
ans = (ans + (ll)a[i+1]*b[i]) % div;
}
cout << ans << endl;
return 0;
}計算のたびに、modの計算をしてオーバーフローを防いでします。
また、Atcoderの公式のYoutube解説にて、幾何的な説明があるので、さらにわかりやすいと思います。
D Friends
友達の縁を何とか切ろうとする問題。n人の人がいて、aとbは友達という情報がm個与えられます。また、この情報以外にも友達の友達は友達とみなすことができます。aとb、bとcが友達なら、bを仲介としてaとcも友達になります。
このn人を複数のグループに分けることで、同一グループに知り合いが存在しないという状況を作りたいです。そのためには、最低何個のグループに分ける必要があるかを求めます。
友達の友達は友達となるためその関係を辿っていくとn人はm個のグループに分けることができます。このとき、同一グループは全員友達で、別のグループに友達は存在しません。
これらのグループを解体して新しいグループにするのですが、その際に
別グループだった人とは同じグループになっても良い
同じグループだった人とは別れる必要がある
という条件を満たす必要があります。
長々と書きましたが、この条件より最も人数の多いグループの人数分だけ新しいグループを用意すれば良いことがわかります。そのため、求める答えは最大グループの人数となります。
さて、次に人数を求めるのですが、今回はUnionFindという手法？データ構造？を用います。詳しくは別に書きます。
端的に言うと、関係データのツリーを作成し、aとｂは友人であるかということを簡単に取得できる構造です。友人関係を枝として追加し、同じ根（root）から生えているかどうかをチェックします。このときに、同じ根を持つものは同じグループに所属しているとみなすことができます。
今回は同じグループに所属している要素の数を取得する必要があるため、単純なUnionFindに少し機能を追加します。
要素数の取得のため、ルートとなる場所にはそのルートから派生する全ての枝の数を保存しておきます。
UnionFindが実装できたら、あとは全部の関係を投げて、その後最も大きいグループのサイズを取得すればおしまいです。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
//UnionFind
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)); }
};
int main()
{
int n, m;
cin >> n >> m;
UnionFind uf(n);
rep(i,m){
int a,b;
cin >> a >> b;
--a, --b;
uf.unite(a,b);
}
int ans = 0;
rep(i,n) ans = max(ans, uf.size(i));
cout << ans << endl;
return 0;
}要素数を入れる関係上、UnionFindは-1で初期化しています。負値のものを根、正値のものを枝としています。
最低限の機能のみを持つUnionFindも実装したので、以下にコードと時間の比較を示します。こちらの方がシンプルでUnionFind自体の理解には向いていると思います。
struct UnionFindBase{
vector<int> d;
//コンストラクタ
UnionFindBase(int n=0){
rep(i,n) d.emplace_back(i);
}
//根の探索と張り替え
int find(int x){
if(d[x] == x) return x;
//根のはりかえ
return d[x] = find(d[x]);
}
//根の結合
void unite(int x, int y){
x = find(x);
y = find(y);
if(x != y) d[y] = x;
}
bool same(int x,int y){ return (find(x) == find(y));}
/*実行の前に、
rep(i,n) int hoge = find(i);
のようにfindにて更新をする。
これをしないとuniteにて最後に結合した関係の枝が更新されない。*/
int size(int x){
int cnt = 0;
rep(i,d.size()) if(x == d[i]) cnt++;
return cnt;
}
};
こうみると全然違いますね。計算時間のネックとなっているのはサイズの取得なので、同じグループかどうかを見るだけなこちらでも良いと思います。
E Coprime
n個の整数からなる集合Aが与えられ、約数に関してAnを場合分けする問題。場合分けの種類として、
１、全ての組み合わせに関して互いに素である。(pairwise coprime)
２、pairwise coprime ではなく全ての約数が互いに素である。(setwise coprime)
３、それ以外
がある。
例えば 5, 10, 13が与えられた場合、5と10は5を約数に持つから１を満たさない。5, 10 ,13の公約数は1だけであるので、条件２を満たす。よって、setwise coprimeを出力する。
方針は条件を１つずつチェックしていって分類するといったシンプルなやり方です。
まず条件１です。愚直に要素を2つ取り出して判定する、とやるとn_C_2通りとなり、計算量がO(n^2)です。nの条件は 2 <= n <= 10^6なので、この方法では厳しそうです。
そのため、各素因数に注目をします。5, 10 ,13であれば、まず5の素因数は5であるので、残りの要素が5を持っているかを判定します。13は大丈夫なのですが、10は2*5なのでアウトです。
これはAiの最大値(10^6)の長さの配列を用いて実装します。そして、要素のインデックスに1を立てます。今回は以下の通りです。
i 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Ai 0 0 0 0 1 0 0 0 0 1 0 0 1 ...
5に関して調べたいので i = 5 * k のインデックスの和を取ります。これが1であれば5を公約数とする組み合わせは存在しないことがわかります。もちろん和が0でも大丈夫です。(今回は2ですのでダメです。)
本来であれば素数に関して10^6まで上記操作を行い、全て条件を満たすかをチェックするのですが、今回は10^6までの自然数に関して行います。それでも、計算量はO(n log n)に収まるそうです。
条件２に関しては最大公約数を求めるgcd関数を用います。内部ではユークリッドの互除法が動いているらしいです。ただし、c++17で追加された関数なのでご注意を。
また複数の最大公約数は再帰的にgcdを使えば求めることができます。
gcd(a, b, c) = gcd(a, gcd(c, d))
これで条件を判定したので残りをその他として終わりです。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
const int A = 1000005;
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> b(A);
rep(i,n){
cin >> a[i];
++b[a[i]];
}
bool ispw = true;
//pairwise coprimeの判定
for(int i=2; i<A; ++i){
int cnt = 0;
for(int j=i; j<A; j+=i){
cnt += b[j];
}
if(cnt < 2) continue;
ispw = false;
break;
}
if(ispw){
cout << "pairwise coprime" << endl;
return 0;
}
//setwise coprimeの判定
int g = 0;
rep(i,n) g = gcd(g,a[i]);
if(g == 1){
cout << "setwise coprime" << endl;
return 0;
}
cout << "not coprime" << endl;
return 0;
}０とnの最大公約数はnとなります。g=１としていて詰まりました。
また、先に計算量について述べましたが、それについて軽く書きます。
2を探索する場合、2n の要素だけを参照するので A / 2 回の計算になります。いっこ飛ばしで見ていく感じです。同様に3は A / 3 回です。
そのため、全自然数に対して探索した場合、その計算量は
Σ A / i (iは i = 2 から A まで)
= A (1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + ...)
< A (1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + ...)
= A (1/2 + 1/2 + 1/2 + ...)
と上から押さえつけることができるので、A log Aのスケールに収まります。解説を聞いていて、感心しました。
F I hate Shortest Path Problem
最短経路問題を憎む問題です。
(h+1)*wのマス目があります。一番上のマスから初めて、右か下に1マス移動することを繰り返します。ただし、i行目とi+1行目の間のa列目からb列目までは壁が存在して、壁がある地点では下に移動することができません。
2行目、3行目、... 、h行目、h+1行目のそれぞれのいずれかのマスに到達するための最小の移動回数を求めます。このとき、各場合について一行目の中の出発位置（列番号）は個別に選ぶことが可能です。また、どうやっても到達できない場合は-1を出力します。
今回は右と下にのみ移動が可能なので、壁にぶつかるまでは下に移動、ぶつかったら右に逸れていけば最小の移動回数で到達できます。そのため、まずは壁にぶつかって右に逸れる挙動を考えます。
もしw=5でiとi+1の2~4の間に壁があるとします。この壁を超えるときに、壁の上にいる2~4の要素が壁+1の要素となり統合されることがわかります。
もう少し拡張します。i+1とi+2の間に1~2の壁があります。1の要素が壁+1の3の要素となることがわかります。
もう一つだけ考えます。5の壁があるとどうでしょうか。5の要素がこれ以上進行不可となります。
さて、このときの最小経路を求めます。まず、i+3に到達したのは1から出発した要素だけで、到達地点は3です。その時の経路長は横移動を2回、縦移動3回の5回です。これは、横移動 = 到達地点 - 開始地点、縦移動 = 列番目-1です。
i+2の時です。i+1に到達したのは開始点1と2,3,4,5です。1は経路4、2も4、３は３、4は2、5は1です。1が最短経路ですね。
このときに大切なのが、2,3,4,5の統合した要素です。同じ到着点持つ場合、開始地点が最も右にある要素のほうが経路が小さくなります。そのため、プログラムに実装する際には統合した時点で、開始地点の最大値以外の要素を削除することができます。これにより計算量を削減できます。
さて、動かし方を考えたので、次にどのように実装するかを考えます。
必要な要素は
１、現在地と開始点を保持しておく箱
２、経路長を保持しておく箱
この2つです。実装では1にmap、2にmultisetを用いました。
mapはkeyをもつ配列で、連想配列とも呼ばれます。たとえば、"december"というキーに12を仕込んでおけば、map["december"]で12が出力されます。
今回はmap<int,int> nsで、
ns[到達地（現在地）] = 開始地点の最大値
という形で用います。初期状態はns[i] = i で現在地と開始点は同じです
また、mapの機能にns.lower_bound(x)があります。これは、x以上の要素を持つもののイテレータを取得してくれます。そのため、 ns.lower_bound(壁の開始点)とすれば、現在地が壁よりも小さい要素を無視して、壁にぶつかった要素を取り出せます。もしなければ、終点のイテレータを返します。
要素の取り出し方として、lower_bound（）などでいずれかのイテレータを取得して、iterator -> firstでキー、 iterator -> secondで要素が取り出せます。
次にmultisetです。これは、setのmulti版です。setは順序付き集合と呼ばれており、各要素を昇順にソートしてくれいます。また、同じ要素は1つしか存在しません。
このmulti版なので、同じ要素の出現を許しています。解候補となる（現在地ー開始地点の最大値）を保存しているので、multisetの一番目を取り列番号を足せば答えが求まります。
初期状態は全部0ですね。
説明は以上です。実装します。
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
int main(){
int h, w;
cin >> h >> w;
map<int,int> ns; //（現在地、スタート地点の最大値）
multiset<int> dist; //現在地ースタート地点の最大値
rep(i,w) ns[i] = i; //キーiにiを代入
rep(i,w) dist.insert(0); //はじめは距離0
rep(i,h){
int a, b;
cin >> a >> b;
--a; --b;
auto it = ns.lower_bound(a);
int ms = -1; //最も右にある開始点を保持
while(1){
//壁を1だけ超える点のスタート地点を取得（b+1）
if(it == ns.end() || it -> first > b+1) break;
ms = max(ms, it -> second);
dist.erase(dist.find(it->first - it->second));
ns.erase(it++);
}
//要素が見つからない、wを超えてしまう時を除く。
if(ms != -1 && b+1 != w){
dist.insert(b+1 - ms);
ns[b+1] = ms;
}
int ans = -1;
if(dist.size() > 0){
ans = *dist.begin();
ans += i+1;
}
cout << ans << endl;
}
return 0;
}erase(it++);は後置インクリメント演算子（it++）によって、イテレータを回しています。++itとは処理が違うので注意です。
本題とは関係ないのですが、いつもプログラムの初めで入力をvectorなどで取得して、処理の際に取り出すということをしています。ただし、本問題でそれをやったら、その取り出し操作が重くてTLEになりました。
これだけで誤答ペナルティーをもらうのは嫌なので、計算量の感覚に慣れて、節約できるところはしたいですね。
この記事が気に入ったらサポートをしてみませんか？