ABC C問題埋め1

投稿者: | 2020年5月23日
0件のコメント

VScodeの環境が整ったので、またC問題埋めを再開していました。

Atcoder ProblemsのTraining(beta)のEasyにあるC問題から埋めています。今日解いた問題はABC127,134,152,149,150とABC153D問題です。

1.ABC149

問題:C-Next Prime

2以上の整数Xが与えられるので、それより大きい最小の素数を求めよという問題です。

最初は、エラトステネスの篩実装して素数リストを作ってやろうと思いましたが、制約条件を見てやめました。

その後、制約条件内の整数で素数でない部分が1000個も連続する部分がないので(素数階段)、整数Xに0から1000まで足して最初に素数になったところを出力すればいい、と思いつきました。この付近の階段の間隔なら50でも大丈夫だと思いますが、一応大きめの値を取っています。

また、素数判定が遅くても最大1000回判定するだけなのでTLEはしないはずです。

書いたコードは次の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
bool isprime(int n){
if(n<2)return false;
else if(n==2)
return true;
else if(n%2==0)
return false;
double sqrt_n = sqrt(n);
for(int i = 3; i < sqrt_n; i+=2){
if(n%i==0)
return false;
}
return true;
}
int main(){
int n;
cin >> n;
vector<int> num;
rep(i,1000){
int num = n+i;
if(isprime(num)){
cout << num << endl;
break;
}
}
return 0;
}
view raw ABC149c.cpp hosted with ❤ by GitHub

解説はwhile文で実装しています。そっちのほうが実装はシンプルだったか・・・。

素数判定については以下のコードを参考にさせてもらいました。

最速の素数判定プログラム C# Java C++

2.ABC150

問題:C-Count Order

辞書順順列という典型問題らしいです。私は知らなかったです。

そして、この問題だけ苦戦したので、自力で考えるのを諦めて解説を見ました。すると、"next_permutation"を使って比較するとありました。

std::next_permutation

与えられた時点の[first, last)の範囲を起点の順列として、辞書順によるその次の順列を生成する。

(C++日本語レファレンス std::next_permutation)

こんなのあったんですね、全く知らなかった。

使うときの注意点としては、関数に最初に与える範囲が昇順にソート済みである必要があります。

そういうわけで、N!通りの順列を出力させ、それぞれの順列と比較して何番目かを出せばよさそうです。

書いたコードは次の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n], p[n], q[n];
rep2(i, 1, n + 1) a[i - 1] = i;
rep(i, n) cin >> p[i];
rep(i, n) cin >> q[i];
int count = 0;
int num_p, num_q;
do {
count++;
bool flag = true;
rep(i, n) {
if(a[i]!=p[i]){
flag = false;
break;
}
}
if(flag)
num_p = count;
flag = true;
rep(i, n) {
if(a[i]!=q[i]){
flag = false;
break;
}
}
if(flag)
num_q = count;
} while(next_permutation(a, a + n));
cout << abs(num_p - num_q) << endl;
return 0;
}
view raw ABC_150c.cpp hosted with ❤ by GitHub

多分人生で初めてdo~while文を使いました。これは、while文で書くと一番最初の順列がでてこないことを防ぐためです。

do~while文ならば一回は文を実行されるので、一番最初の順列を出すことができます。

3.ABC153D

問題:D-Caracal vs Monster

ちょっと問題の理解に戸惑いました。問題設定としては、

1体のモンスターを攻撃する→モンスターのHPが1ならば撃破できる。それ以外なら体力を半分にした(端数切捨て)モンスターが2体出現する。→それぞれのモンスターについて同様のことを行う→最終的に攻撃した回数を出力

となっています。樹形図みたいなのを書くと理解しやすいんじゃないかと思います。

さて、どのように実装するか考えていきます。

結局モンスターはHPが1にならないと倒せません。つまり、モンスターの体力を半分にし続け1にすれば倒せます。このときの攻撃回数は、モンスターの体力を2で割った回数です。

つまり、モンスターが分裂しない場合の攻撃回数は、モンスターの体力が1になるまで2で割り続けた(端数が出た場合は切り捨てる)回数と等しくなります。この回数は制約条件では高々40回となります。

また、モンスターは攻撃すると2倍に数が増えるので、モンスターの数は1,2,4,8,…という初項1、公比2の等比数列となります。

あとは等比数列の和の公式から答えを出すことができます。

そういうわけで、書いたコードは次のとおりになりました。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
ll h;
cin >> h;
int count = 0;
while(h != 1) {
count++;
h /= 2;
}
count++;
cout << setprecision(13) << pow(2, count) - 1 << endl;
return 0;
}
view raw ABC153d.cpp hosted with ❤ by GitHub

4.ABC127

問題:C-Prison

N枚のIDカードとM個のゲートがあり、各ゲートはある範囲で連続する番目のIDカードならば通過できます。1枚のカードのみですべてのゲートを通過できるカードは何枚あるかという問題です。

要するに、すべての範囲に対して共通範囲を更新し続けて、その共通範囲の幅を出力すればよさそうです。

書いたコードは次のとおりです。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n, m;
cin >> n >> m;
int ans_r = 1, ans_l = n+1;
rep(i, m) {
int r,l;
cin >> r >> l;
if(r > ans_l || l < ans_r) {
cout << 0 << endl;
return 0;
}
if(ans_r < r && r <= ans_l)
ans_r = r;
if(ans_r <= l && l < ans_l)
ans_l = l;
}
cout << ans_l - ans_r + 1 << endl;
return 0;
}
view raw ABC127c.cpp hosted with ❤ by GitHub

最初0になるパターンを見逃していて3回ぐらいWA出しました。また、そうなる場合をflagで管理(共通範囲の右端、左端の値どちらとも更新しない場合は0にすると考えてた)した場合、なぜかバグったのでやめました。

ちなみに、bool型の配列にそれぞれの範囲を入れて共通範囲を出そうとするとTLEします。

5.ABC134

問題:C-Exception Handling

数列内のある番目に対して、それ自身以外の値の中から最大値を出す問題です。

めっちゃくちゃ簡単。

最大値を出せばいいので、数列内の最大値と2番目に大きい値を出せば準備は完了。あとは、ある番目の値が最大値と一致するなら2番目に大きい値、それ以外は最大値を出力すればよさそうです。

書いたコードは次の通り。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n];
int max = 0, sub_max = 0;
rep(i, n) {
cin >> a[i];
if(a[i] > max){
max = a[i];
} else if(a[i] > sub_max){
sub_max = a[i];
}
}
rep(i,n){
if(a[i]==max)cout<< sub_max << endl;
else cout<< max << endl;
}
return 0;
}
view raw ABC134c.cpp hosted with ❤ by GitHub

思ったより遅かったので他の人の解答を見ましたが、速度はこんなもんらしいです。また、最大値と2番目の値に関しては、数列をソートして出しています。こっちのほうが実装が簡単だし、速度もあまり変わらないっぽいので大人しく数列をソートする方法にすればよかった。

6.ABC152

問題:C-Low Elements

順列が与えられて、ある番目の値が、それより前の全ての値よりも小さくなる個数を出力せよという問題です。

こういうのを見ると、一番最初に考えつくのは、ある番目の値とそれより前の値を全て比較していく方法です。しかし、制約条件からそれは流石にTLEしそう。通してないのでわからないですけど・・・。

そうなるともっといい方法を考えなければなりません。

先程の方法は全部見るから時間がかかりすぎます。ならば、以前の情報を更新し続けて、それと比較すれば計算量は減りそうです。

そういうわけで、用意する情報がそれ以前までの最小値です。それ以前の最小値より、比較する値が小さければ条件は満たしていると言えます。

そういうことで書いたコードは次のとおりになりました。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i,s,n) for(int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
int n;
cin >> n;
int a[n];
rep(i, n) cin >> a[i];
int m = a[0], count = 0;
rep(i, n) {
if(a[i] <= m)
count++;
m = min(m, a[i]);
}
cout<< count << endl;
return 0;
}
view raw ABC152c.cpp hosted with ❤ by GitHub

7.終わりに

6問解いて約4時間・・・流石に時間がかかりすぎです。途中でtwitterみたり、VScodeのclang-formatいじてったりしてたのでこうなったわけですが。やっぱ問題解いてるときにtwitter見るのはダメ。

8.参考文献

ゼータへ続く素数の階段物語 第13回 数学カフェ「素数！！」

最速の素数判定プログラム C# Java C++

C++日本語レファレンス std::next_permutation

6-4. do~while文

ABC150解説PDF

AtCoder ChokudaiSpeedRun001の解説

コメントを残す

This site uses Akismet to reduce spam. Learn how your comment data is processed.