#前回の記事
AtCoder164に参加した私の結果を報告しました。
今回は私が実際に解答できたABC3つの問題について解説を行いたいと思います。
【ABC164へ参加してみた】在宅勤務になったのでマネジメント系SEが競技プログラミング始めてみた。#3
#A問題:Sheep and Wolves
###解説 二つの数を比較する問題です。 羊がS匹、狼がW匹いる場合に、「狼の数が羊の数以上」つまり「S<=W」となる場合を「unsafe」とします。problemA.cpp
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int s,w;
cin >> s >> w;
if(s<=w)
cout << "unsafe" << endl;
else
cout << "safe" << endl;
return 0;
}
#B問題:Battle
カードゲームとかした人は多分イメージができるとは思いますが、
イメージできない人はこんな流れでモンスターの闘いが繰り返されます。
problemB.cpp
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int a,b,c,d ;
cin >> a >> b >> c >> d;
while(a>=0 || c>=0){ //それぞれのモンスターの体力がゼロになるまで
c = c-b; //高橋君の攻撃のターン
if(c<=0){
cout << "Yes" << endl;
break; //勝敗が決まったのでループを抜ける
}
a = a-d; //青木君の攻撃のターン
if(a<=0){
cout << "No" << endl;
break; //勝敗が決まったのでループを抜ける
}
}
return 0;
}
#C問題:gacha
C問題については都度文字列を全探索でマッチングすると計算量の関係で実行時間エラーになるようです。
そのため以下のようにソートなどで計算量を減らす工夫が必要になります。
計算量については私もどこまでだったら減らせばいいとか正直まだ理解できていないので、
詳細な解説は控えます。
※ちなみに私は計算量とかあまり気にせず、こっちが簡単だなーと思ってやったら結果うまく行った感じでした。。。勉強します。
problemC.cpp
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
int n;
cin >> n;
string a[n+1];
a[0] ="";
for(int i=1; i<=n; i++)
cin >> a[i];
sort(a,a+n+1); //配列の内容をソートして辞書順にする
int cnt=0;
for(int i=1; i<=n; i++){
if(a[i-1]==a[i]) //同じものの場合にcntをインクリメントする
cnt++;
}
cout << n-cnt << endl; //違うものの数を数えたいのでnからcntを引く
return 0;
}
#最後に
いかがだったでしょうか?
見ても解らないやもう少しこうすると良いのではないか?といった暖かい言葉ドシドシお待ちしています。