ABC160の復習
初めに
ABC160に参加した時の復習です。その時はC問題が解けずに終わってしまい、
解説を見て解き直しましたが、今まで使ったことが無い考え方が必要な問題だったので
忘れないように復習しようと思います。
https://atcoder.jp/contests/abc160
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Traveling Salesman around Lake
1周Kメートルの湖がありその周りにN軒の家があります。それぞれの家はAiメートル離れていて、 湖に沿ってN軒すべての家に訪問する際の最短距離を求める問題です。
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;
int main(){
long long K,N;
long long ans = INF;
long long total = 0;
cin >> K >> N;
vector<long long> A(N);
for(long long i = 0; i < N; ++i) cin >> A[i];
//
A.push_back(A[0]+K);
long long l = 0;
for(long long i = 0; i < A.size(); ++i){
// それぞれの家と家との間の距離の最大値を求める
l = max(l,A[i+1] - A[i]);
}
// 一周の長さから家間の距離の最大値を削除する。
cout << K - l << endl;
return 0;
}
これは円環の問題と言われるらしく、下記イメージのように輪っか上の何かを扱う問題です。
グラフで表すと以下イメージのようになります。
この問題は一直線ですべての家に回る経路が最短になるため、
各家への道のうち最も長い道を削除すると最短経路が求まります。
(一度通った点を折り返すパターンでは無い)
上記のイメージは解いている途中に何となく浮かんだんですが、
0を跨ぐパターンをどうやって計算するかが思い浮かびませんでした。
解説を見たところ円環の問題でよく使わるやり方としては
上記のグラフを切り開いて0を跨ぐ場合はK+A1の形で表す事で
それぞれの家との距離を求める事が可能になります。
(以下のように切り開いていて2周分の距離の中で計算を行う。)
あと、それぞれの家との距離の最大値を求めてKから引けば答えが求まります。
最後に
この記事を書いていて感じたが、やっぱり時間が立つと結構抜けてしまいますね。
ずっと覚えている事は難しいのでこのような形ですぐに思い出せるように残しておきたいですね。
ABC168に参加してみました
初めに
ABC168に参加しました。今回は久しぶりにA・B・Cが解けました。
D問題に関してはBFS(幅優先探索)すれば行けるだろうなと思ってコーティングしている途中で終わってしまいました。
もうちょっとC問題が早く解ければ行けそうだったんですよね～。。。
なので、今回はD問題について書いて行きます！
https://atcoder.jp/contests/abc168
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
D - .. (Double Dots)
N個の部屋と、部屋と部屋を繋ぐ通路がM本あります。各部屋には繋がっている部屋を
指す道しるべを一つ配置することができます。
部屋と部屋との通路の情報が与えるのでその情報を元に、ある部屋から出口に繋がっている部屋1に
最小の移動回数で移動できるような道しるべの配置が存在するか判定する問題です。
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N,M;
vector<ll> load[100005];
cin >> N >> M;
for(ll i = 0;i < M;++i){
ll A,B;
cin >> A >> B;
// ①隣接リストを作成
A--;B--;
load[A].push_back(B);
load[B].push_back(A);
}
// ②BFS のためのデータ構造
vector<ll> dist(N, -1); // 全頂点を「未訪問」に初期化
vector<ll> pre(N,-1);
queue<ll> que;
// 初期条件 (頂点 0 を初期ノードとする)
dist[0] = 0;
que.push(0); // 0 を頂点にする
while (!que.empty()) {
// ③キューから先頭頂点を取り出す
ll v = que.front();
que.pop();
// ④v から辿れる頂点をすべて調べる
for (int nv : load[v]) {
// ⑤すでに発見済みの頂点は探索しない
if (dist[nv] != -1) continue;
// ⑥新たな頂点 nv について距離情報・辿ってきた頂点情報を更新してキューに追加する
dist[nv] = dist[v] + 1;
//道しるべの配置を記録
pre[nv] = v;
que.push(nv);
}
}
bool flg = true;
// 未到達の頂点が無いか確認
for(ll i = 0;i < N;++i) if(dist[i] == -1) flg = false;
// すべての頂点に到達していた場合
if(flg){
cout << "Yes" << endl;
// 結果出力 (各頂点の頂点 0 からの距離を見る)
for (ll v = 0; v < N; ++v){
if(v == 0) continue;
ll ans = pre[v];
ans++;
cout << ans << endl;
}
}
// 到達していない頂点があった場合
else{
cout << "No" << endl;
}
return 0;
}
与えられた通路情報を元に出口に繋がっている部屋1から、それぞれの部屋への最短経路を求めれば良いので以下①～⑥にてBFSを行います。
①まずは、入力された通路の情報を隣接リストに格納します。
(隣接リストのイメージは以下のような感じ赤枠が隣接している要素のリスト)
②距離を格納するdist、辿った部屋番号を格納するpre、
ある点から辿れる頂点情報を格納するqueueを宣言します。
※今回の問題は最短経路の距離を求める分けでは無いので、実はdistは要りません。
③先頭に格納されている頂点情報を変数vに格納し、queueから取り出します。
④取り出した頂点から辿れる頂点をすべて調べます。
⑤既に調べていた頂点だった場合はスキップします。
⑥辿ってきた頂点情報の更新およびqueueへの頂点情報の追加を行います。
③～⑥をqueueが空になるまで行い、最後にすべての頂点に到達したか否かを判定し
「Yes」,「No」を出力します。
「Yes」の場合は、配列preに格納されている経路情報も併せて表示します。(queueで行っている事のイメージは以下です。)
幅優先探索については@drken1215さんの記事が非常にわかりやすかったので、
↓の記事も見ていただければより理解が深まると思います。
最後に
問題を解くためのアルゴリズムは分かったのですが、如何せんC問題を解くのが遅かったのと
過去に何度か書いた程度だったのでコーディングの時間が足りませんでした。
まぁでも今回はA～C問題まで解けて良かったです。
今回のコンテストでやっとレーティング200に到達したのでこの調子で茶色に行きたいですね!
ABC167に参加してみました
初めに
今回はABC167に参加しましたが、今回もCを解いている途中でタイムアップしました。。。
（全探索すれば解けるとは思ったんですがTLEになっていまいました。）
なので、今回もC問題について書いて行こうと思います。
https://atcoder.jp/contests/abc167
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Skill Up
この問題は、本屋でそれぞれCi円で売られているN冊の参考書よりM個のアルゴリズムを学び、
それぞれの理解度(Aij)をX以上にするために必要な金額の最小値を出力する問題です。
初めの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,bool> Pair;
int main(){
ll N,M,X;
ll tot = 0;
ll ans = INF;
cin >> N >> M >> X;
vector<ll> a(M);
vector<ll> C(N);
vector<vector<ll>> A(N,vector<ll>(M));
for(ll i = 0;i < N;++i){
cin >> C[i];
for(ll j = 0;j < M;++j) cin >> A[i][j];
}
//順列の生成用配列
vector<ll> v;
//順列の生成用配列に0～Nの値を格納
for(ll i = 0; i < N;++i) v.push_back(i);
do{
// 初期化します
tot = 0;
for(ll i = 0; i < M;++i) a[i] = 0;
for(ll i = 0; i < N;++i){
// 各アルゴリズムの理解度が条件を満たしているか否かを判断するフラグ
bool flg = true;
//購入費を加算します
tot = tot + C[v[i]];
for(ll j = 0; j < M;++j){
// 理解度を加算します
a[j] += A[v[i]][j];
// 各アルゴリズムの理解度がXより小さい場合はflgをfalseにします
if(a[j] < X) flg = false;
}
// 各アルゴリズムの理解度がX以上である場合は購入費の更新をします
if(flg){
ans = std::min(ans,tot);
break;
}
}
// 順列を列挙
}while(next_permutation(v.begin(),v.end()));
// 購入費が初期値から購入されているか判定
if(ans == INF) cout << "-1" << endl;
else cout << ans << endl;
return 0;
}
本を選択するパターンを順列で列挙(next_permutation)しています。
N冊の本をすべて購入しなくても理解度がX以上になるパターンが存在するため、
すべてのアルゴリズムの理解度がX以上になった際に購入費(ans)を更新しループを抜けるようにしています。
そして、最後に購入費が初期値から更新されているかを判定し計算結果を出力しています。
このプログラムだとNの最大値である12が入力された場合は12!通りのパターンに対して、
条件を満たすか確認が必要があるため、TLEになっていたものと思います。
(TLEになるだろうなとは思いつつこの方法しか浮かばなかった、、、)
next_permutation - cpprefjp C++日本語リファレンス
解説を見てからの回答
順列でもすべてのパターンを列挙可能ですが、そもそも順番は気にする必要が無いため
組み合わせのパターンを列挙すれば良いので、下記のように書くことが出来ます。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
int main(){
ll N,M,X;
ll tot = 0;
ll ans = INF;
cin >> N >> M >> X;
vector<vector<ll>> A(N,vector<ll>(M));
vector<ll> C(N);
for(ll i = 0;i < N;++i){
cin >> C[i];
for(ll j = 0;j < M;++j) cin >> A[i][j];
}
// (1<<N)で1を左にNビットシフトする(N=3だった場合：0001(1) → 1000(8))
for(ll i = 0;i < (1<<N);++i){
tot = 0;
vector<ll> a(M);
for(ll j = 0;j < N;++j){
// (i>>j)でiを右にjビットシフトする(i=6,j=1だった場合：0110(5) → 0011(3) ＆ 0001(1) = 0001)
if((i>>j)&1){
tot = tot + C[j];
for(ll k = 0;k < M;++k) a[k] += A[j][k];
}
}
bool flg = true;
for(ll j = 0;j < M;++j) if(a[j] < X) flg = false;
if(flg) ans = std::min(ans,tot);
}
if(ans == INF) cout << "-1" << endl;
else cout << ans << endl;
return 0;
}
10進数の数字を2進数で表すと以下のように1と0で表すことが出来ます。
1 → 0001
2 → 0010
3 → 0011
4 → 0100
・
・
・
1を「購入する」、0を「購入しない」とし、さらに下記のイメージのように2進数のそれぞれの桁を本のN番目と見立てます。
下記のように見立てることで、それぞれの桁数の値を確認することで、
本を購入する組み合わせを列挙することが出来ます。
それぞれ桁の値を確認する際は、確認する桁数分だけ右にビットシフトし1との論理和を
計算することで確認することが出来ます。
例 ) 0110(5)の3桁目の値を確認する場合
0110(5)を2ビットずらし、0001(1)との論理和を計算します。
0001(1) & 0001(1) = 0001
この方法であれば、最大で212通りのパターンを列挙して条件を満たすか確認すれば良いので、
最初に考えて方法より計算量がかなり少なく計算できますね。
最後に
今回の問題は、解釈を間違えて効率的な全探索を行う事ができませんでしたが、
bit全探索という新たな探索方法の知識を得られたのは良かったかなと思います。
まだまだ勉強が必要ですね。。。
ABC165に参加してみました
初めに
今回はABC165に参加しました。A・BはACして、Cは解いている途中でタイムアップしました。
Twitterを見た限りだとDよりCが難しかったようで、「Cを飛ばせば良かったなぁ」と思いました。
(まぁ、CよりDの方が簡単だからと言って私が解けるかは別な話ですがw、、、)
では早速、解いている途中で終わってしまったC問題について書いて行こうと思います。
https://atcoder.jp/contests/abc165
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Many Requirements
正整数 と、4 つの整数の組
組が与えられます。
はそれぞれ以下を表しています。
そして、 を満たすような
についての
の総和を計算し、
与えれらた組の整数の組を利用して得られる数列
の得点の最大値を求める問題です。
初めの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll N,M,Q;
ll sum = 0,ans = 0;
vector<ll> a(50);
vector<ll> b(50);
vector<ll> c(50);
vector<ll> d(50);
vector<ll> A(10);
//深さ優先探索を行っている関数です。
void dfs(ll NN){
//樹形図の一番下の頂点の位置です。
if(NN == 0){
sum = 0;
for(ll i = 0;i < Q;++i){
//条件を満たすか確認します。条件を満たしている場合はsumにdiを加算します。
if(A[b[i]-1]-A[a[i]-1] == c[i]){
sum = sum + d[i];
}
}
//最大値ansに格納されている値よりsumの値が大きかった場合、最大値ansをsumの値で更新します。
if(ans < sum) ans = sum;
}
else{
for(ll i = 0;i < M;++i){
// 樹形図の各頂点の数値を格納しています。
A[NN-1] = i + 1;
// 樹形図の下の頂点に向かう操作をしています。
dfs(NN-1);
}
}
}
int main(){
cin >> N >> M >> Q;
for(ll i = 0;i < Q;++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
dfs(N);
cout << ans << endl;
return 0;
}
再帰関数を利用しDFS(深さ優先探索)を行って数列の全列挙を行います。
以下はDFSのイメージになりますが、樹形図の一番の下の頂点にぶつかるまで探索(赤矢印)したら、
一歩戻って(青矢印)また一番下の頂点まで探索を行う操作を繰り返し行う探索方法になります。
全列挙したそれぞれの数列に対して の条件に合うか確認し、数列
の得点を計算を求め、
得点の最大値が格納されている変数ansの更新を行い、DFS完了後に最終的な変数ansの値を出力しています。
提出結果としては、実行時間が掛かり過ぎてしまいAC出来ませんでした。
(最大で1010の計算をする場合があるから、まぁTLEになっちゃいますよねぇ。。。)
そして、探索の中で枝刈りが行る場所は無いか考えている最中にタイムアップになりました。
(そもそも問題文の理解に時間が掛かり過ぎて、あまり実装に時間を掛けられませんでしたorz)
解説を見てからの回答
下記のコードは最初に書いたコードから少し変わっていますが、
解説を見た上で変更したのは樹形図の下の頂点に向かう操作の条件のみです。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll N,M,Q;
ll sum = 0,ans = 0;
vector<ll> a(50);
vector<ll> b(50);
vector<ll> c(50);
vector<ll> d(50);
vector<ll> A(11,1);
void dfs(ll NN){
if(N == NN){
sum = 0;
for(ll i = 0;i < Q;++i){
if(A[b[i]-1]-A[a[i]-1] == c[i]){
sum = sum + d[i];
}
}
if(ans < sum) ans = sum;
}
else{
for(ll i = 1;i <= M;++i){
A[NN] = i;
// 一つ前の頂点の数字以上であった場合のみ樹形図の下に向かう操作をします。
if(A[NN-1] <= A[NN]) dfs(NN+1);
}
}
}
int main(){
cin >> N >> M >> Q;
for(ll i = 0;i < Q;++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
dfs(1);
cout << ans << endl;
return 0;
}
数列の条件(
)より、広義単調増加しているため、
は、
以上の数字しか取りません。
そのため、以下のイメージのように一つ前の数字以上の場合のみ樹形図の下に向かう操作(緑枠)を
行うことで実行時間が削減でき、ACすることが出来ました。
最後に
Cはよく問題を理解していれば解けていたと思うので悔しいですね。最近はA～C問題は解けていたので、 解けなくてちょっと焦ってしまいました。次回からは落ち着いて解こうと思います。。。
ABC164に参加してみました
初めに
参加してから時間が立ってしまいましたが、ABC164に参加したので書いて行こうと思います。
今までは自分が解けた問題のみを記載していたのですが、今回からはコンテスト中に解いている
途中でタイムアップして後日解いた問題や、解説を見て気づきがあった問題のみ書いて行きます。
(なので更新がコンテスト参加日から結構空いてしまいました、、、)
https://atcoder.jp/contests/abc164
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - gacha
この問題は、くじ引きをN回行い何種類の景品を得ることが出来るか求める問題です。
景品は文字列Sで与えられます。
最初の回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N;
cin >> N;
vector<string> S(N);
for(ll i = 0;i < N;++i) cin >> S[i];
// ①文字列を並び変える
sort(S.begin(), S.end());
// ②・③重複要素を纏めた後に、不要な要素の削除(uniqueは実行後に重複を纏めた範囲の末尾の次のイテレータを返します)
S.erase(unique(S.begin(), S.end()), S.end());
ll ans = S.size();
cout << ans << endl;
return 0;
}
入力されたくじ引き回数より、N個の文字列型の要素を格納可能な配列Sを宣言し、
その配列に景品の文字列を格納していきます。
景品の文字列は重複して入力される場合があり、重複している文字列については種類が
被ってしまうので手に入れた景品の種類としては数えてはいけません。
そのため、景品の文字列を入力した配列に以下の操作①～③を行う必要があり、
その操作の完了後に配列Sの長さを出力することでACすることが出来ます。
①sortを用いて、文字列を並び替えます。
→重複している文字列が隣通しになります。
②unique(下記リンク参照)にて重複している文字列があった場合は1つにまとめます。
→ ex )：aabbbcddaaa ⇒ abcda??????
配列の要素自体が削除されるわけではないので?の部分は何かしらの値が格納されています。
③uniqueを実行後に残った?の部分をeraseで削除します。
→uniqueを行っても配列の要素数自体は変わらないため、不要な部分を削除しています
unique - cpprefjp C++日本語リファレンス
解説を見てからの回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll N;
string S;
cin >> N;
set<string> setS;
for(ll i = 0;i < N;++i){
cin >> S;
setS.insert(S);
}
ll ans = setS.size();
cout << ans << endl;
return 0;
}
最初に記載した方法でもACになるのですが、解説にもっとスマートな書き方が記載されていたので
上記のように書き直しました。
setを使用することでユニークな要素の格納が行えます。重複するような値が入力された場合でもsetに格納されることはありません。
そのため、入力された値を格納し、格納した要素数を出力するだけで回答することが出来ます。
※setの詳細は下記リンクを参照。集合を表す時に活用することも出来そうです。
https://cpprefjp.github.io/reference/set/set.html
setを使用して思ったこと
最初の回答と比べてメモリ使用量や実行時間が増えており、上記サイトの記載にもある通りvectorのinsertやsortの処理に比べて
遅いようなので使用するにあたり、そのへんも頭に入れておいた方が良さそうですね。(入力がやたら多い問題とかだったらTLEになるかも？)
実際に最初に書いたプログラムの実行時間とメモリを比較すると処理速度の違いがわかりますね。
※上がsetを使って解いた時の結果、下がvectorを使って解いた時の結果
D - Multiple of 2019
1 から 9 までの数字のみからなる文字列Sが与えられ、部分文字列の中に2019の倍数がいくつあるか求める問題です。
最初の回答
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
string S;
ll ans=0;
cin >> S;
for(ll i = 0;i < S.size();++i){
string subS = "";
//部分文字列の開始地点をずらすため、インクリメント変数iで初期化
for(ll j = i;j < S.size();++j){
//①文字列を長くしていく
subS = subS + S[j];
//②文字列から数値に変換
ll num = atoi(subS.c_str());
//③変換された数値が2019で割り切れる場合は総数ansを1つ増やす
if(num%2019 == 0) ++ans;
}
}
cout << ans << endl;
return 0;
}
for文の2重ループを用いて、部分文字列の開始地点をずらしながら以下の操作①～③を行い、
すべての部分文字列に対して2019で割り切れるか計算を行います。
①部分文字列格納用の変数subSにループ毎に文字列Sの文字を1つずつ格納していきます。
②部分文字列subSを数値(num)に変換します。
③numが2019で割り切れる場合は総数ansを1つ増やします。
で、これを提出するとTLEになります。
計算量O(n2)で文字列Sの入力の制約が 1≤|S|≤200000 だったので、「まぁ、たぶんTLEだろうなぁ」と思って提出したら案の定TLEでした。 これを提出してから実行時間を削れる方法が無いか悶々と考えているうちにタイムアップしてしまいました。
解説を見てからの回答
入力された文字列の右側から n 個分からなる数字を とおき以下のように記載します。
※以降、例として「1817181712114」が入力された想定で記載していきます。
・・・
例えば「1817181712114」より黒太文字で記載されている数字を取り出す場合は、
以下のような計算を行う事で取り出すことが出来ます。
で割っているのはBの長さが4桁で、Bの桁数分だけ0が続いているからです。
上記よりある区間]の数字は以下を満たせば2019で割り切れると言えます。
ここで、2019と10は互いに素(最大公約数が1のみ)であり、上記式を満たす上でが2019の倍数である必要があるため、
以下のように表すことが出来ます。
さらに以下のように式を変形することが出来ます。
このことから、文字列の右から個までの数字と
個までの数字を2019で割った余りが同様な場合、
2019の倍数であると言うことが出来ます。
つまり、右端から順々に数字を見ていき2019で割った余りが同様な数字の出現回数
(=余りが同様になる数字の個数)をそれぞれ集計し、集計した中から2組の数字を選ぶ方法()を
計算し、結果を足し合わせることで、文字列に含まれた2019の倍数の総数が求める事が出来ます。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
string S;
cin >> S;
ll x = 1;
ll tot = 0;
ll ans=0;
ll mod = 2019;
vector<ll> cnt(mod);
// 0桁の値を2019で割った余りは0なので、cnt[0]に1を代入します。
//<例>数字が21145で、5桁すべての数字を取得する場合は21145の後ろに(a0)位置に敷居(|)が来るのでそのパターンを表している→21145|
cnt[0] = 1;
// 入力された文字列は一番最後の要素に1桁目の数字が格納されているため、計算しやすくするために逆順にしています。
reverse(S.begin(),S.end());
for(ll i = 0;i < S.size();++i){
// ①i桁目の数字を取得しています。
ll num = S[i] - '0';
// ②「①」で求めたi桁目の数字を変数totに足します。
tot = (tot + (num*x)) % mod;
// ③配列の添え字として変数totを利用し、
cnt[tot] = cnt[tot] + 1;
// ④桁数を計算しています。
x = (10 * x) % mod;
}
//⑤「余りが同様になる数字」の中から2個を選択する方法([tex:_n C_2])をそれぞれ計算します。
for(ll n : cnt) ans += (n * (n - 1)) / 2;
cout << ans << endl;
return 0;
}
各桁の数字は下記の例のように、各桁の累積和で表すことができます。
累積和で表せることを利用して操作①～④を行い、右端からそれぞれの数字に対して余りを計算していきます。
①i桁目の数字を取得します。
→文字コード表で'0' ～ '9'は連番で対応しているため'0'を引くことで数値変換出来ます。)
②変数totにi桁目の数字に掛けた値を加算し、2019で割った余りを計算します。
→累積和の計算
③配列cntに2019で割った余りの数字の出現回数をカウントします。
→配列cntの添え字を2019で割った際のあまりの数字と対応させます。
④桁数を計算しています。
→桁数が大きいため別途modを取るようにしています。
最後に操作⑤を行い、配列cntで求めた「余りが同様になる数字」の中から
2個を選択する方法()をそれぞれ計算し、集計することで2019の倍数の総数が求められます。
⑤「余りが同様になる数字」の中から2個を選択する方法()をそれぞれ計算します。
→n個の中から2個選択する場合は以下のような式で求める事ができます。
最後に
いやぁ今回はD問題を理解するのにすごい時間が掛かりましたね、、、なんとなく理解していたことを整理して書き起こすのは
中々パワーが必要になりますね。今後も時間は掛かりそうですが今回のような内容で書いて行こうと思います。
ABC163に参加してみました
初めに
今回はABC163に参加したので回答出来たものに関して書いて行こうと思います。
因みに今回のコンテストはAtCoderのジャッジシステムの不具合？で画面閲覧が10分以上出来なかった
参加者が居たためUnrated(レーティング更新無し)のコンテストでした。
(私も21:00にサイトにアクセスしたら502が表示されたので、「ん？」となりました。)
https://atcoder.jp/contests/abc163
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
A - Circle Pond
この問題は円周を計算するだけですね。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
double R,PI = 3.14159265358979323846;
PI *= 2.0;
cin >> R;
cout << R*PI << endl;
return 0;
}
こちらは特にゆうことはないですね。ただ、この回答を提出した結果IE(Internal Error)が発生して焦りました。。。 最初は何を意味しているか分からなかったので、なんでACにならないのか少し考えてしまいました。(結果的にはジャッジシステムの問題でした)
解説動画を見たらacosでπの計算をしていたので、ちょっと書き直しました。
たしか大学時代に習った気がするんですけど結構忘れちゃってますね、、、
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
double R,PI = acos(-1);
cin >> R;
cout << 2.0*R*PI << endl;
return 0;
}
B - Homework
この問題は、N日の夏休みの間にM個の宿題を終わらせて何日遊べるかを出力する問題です。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
ll N,M,A;
cin >> N >> M;
for(long long i = 0;i < M;++i){
cin >> A;
N -= A;
}
cout << ( N >= 0 ? N : -1 ) << endl;
return 0;
}
与えられた夏休みの日数Nからそれぞれの宿題を終えるのに掛かる日数を減算していきます。
(わざわざ配列に格納する必要はありません。)
出力は三項演算子を利用して記載しており、Nが0以上かどうかで出力する値を変えています。
C - management
この問題は、N人の社員のそれぞれの社員に直属の部下が何人いるかを求める問題です。
各社員には1～Nの社員番号が与えられ、社員番号1以外のすべての社員には自分より社員番号が小さい直属の上司がいるという前提があります。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL<<60;
typedef pair<ll,ll> Pair;
int main(){
long long N,A;
cin >> N;
vector<ll> ans(N+1,0);
for(int i = 1;i < N;++i){
cin >> A;
ans[A]++;
}
for(int i = 1;i <= N;++i) cout << ans[i] << endl;
return 0;
}
配列の添え字を社員番号と対応させるため、Nの入力後にN+1個の配列を宣言しています。
(N+1としている理由は、N個の配列を宣言した場合は添え字が0～N-1となりますが、Aの入力は1～Nまでのため、
入力をそのまま配列の添え字として利用するために、N+1個の配列を宣言しています)
入力Aを配列の添え字として設定し、社員番号が入力されるたびインクリメントしていくと、
それぞれの社員に何名の部下がいるのか求まります。
最後に
今回もD問題が解けなくて悔しいですね。数学的な考察が必要な感じの問題だったんですが解説動画見てからコードを書いてみようと思います。 後はD問題だけ集中的に過去問を解いて勉強しようと思います。(ちょうど良さそうなサイトも見つけたので)
ABC162に参加してみました
初めに
こんにちわ！このご時世で家でやることが無かったのではてなブログを初めました。
今回は先週参加したAtCoderのABC 162で自分が回答出来たものについて書こうと思います。
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
A - Lucky 7
この問題は、3桁の整数Nが与えられた時に、Nのいずれかの桁に数字の7が含まれているか判定した結果を出力する問題です。
#include <bits/stdc++.h>
using namespace std;
int main(){
string N;
cin >> N;
if(N.find('7') != std::string::npos) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
入力を文字列として受け取り、文字列クラスstringのfind関数を使用して'7'が含まれているか判定をしています。 nposはfind関数で値が見つからなかった場合に戻り値として返す値が定義されており、その値を比較して判定結果を出力しています。
B - FizzBuzz Sum
この問題は、整数Nが入力として与えられ、N項までFizzBuzzを行った際に下記ルールに該当しなかった整数の和を出力する問題です。
①. 3 でも 5 でも割り切れるなら → FizzBuzz
②. そうではなく 3 で割り切れるなら → Fizz
③. そうではなく 5 で割り切れるなら → Buzz
#include <bits/stdc++.h>
using namespace std;
int main(){
long long N,ans = 0;
cin >> N;
for(long long i = 1;i <= N;++i){
if(i%3 == 0 && i%5 == 0) continue;
if(i%3 == 0) continue;
if(i%5 == 0) continue;
ans+=i;
}
cout << ans << endl;
return 0;
}
for文で1からN項までの整数をカウントしていき、上記ルールの①～③の何れかに該当した場合は処理をスキップします。
ルールに該当しなかった場合は変数ansにカウンタ変数iの値を加算し、その結果を出力しています。
・・・書いていて思いましたが、別に3つもif文を書く必要はないですね、、、 3か5で割り切れなかったら場合に変数ansにカウンタ変数iの値を加算すれば良いだけですね。 (コンテスト終わってから気付くことが多々あるんですよね、、、)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long N,ans = 0;
cin >> N;
for(long long i = 1;i <= N;++i) if(i%3 != 0 && i%5 != 0) ans+=i;
cout << ans << endl;
return 0;
}
C - Sum of gcd of Tuples (Easy)
この問題は、整数Kが与えれた時に下記の式の通り3つの整数に対するgcd(最大公約数)を求め、その総和を求める問題です。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long K,ans = 0;
cin >> K;
for(int i = 1;i <= K;++i){
for(int j = 1;j <= K;++j){
for(int k = 1;k <= K;++k){
ans += gcd(gcd(i,j),k);
}
}
}
cout << ans << endl;
return 0;
}
Σは総和を表す記号でforループで計算を行う事ができ、今回の場合は3重のΣの計算であったため3重のforループを書いています。
gcdはユークリッドの互除法というアルゴリズムで求められます。(C++ではgcd求める関数があるためそれを利用しています。)
3つの整数のgcdは何れかの2つの整数のgcdと残った1つとの整数とのgcdを計算すれば求める事が出来ます。
計算量がO(N3)でしたが、整数Kの制約が 1<=K<=200 であったためTLEは発生しませんでした。
最後に
今回はD問題の回答を考えているところでタイムアップしていました。D問題は解けたり解けなかったりというのが 続いているので、過去のD問題等を解いて安定的に解けるようになりたいですね。最終的にはA～F問題までの解いてブログに載せられればなぁと思っているので頑張ります。(いつになることやら、、、)
