前回の記事
AtCoder164に参加した私の結果を報告しました。
今回は私が実際に解答できたABC３つの問題について解説を行いたいと思います。
【ABC164へ参加してみた】在宅勤務になったのでマネジメント系SEが競技プログラミング始めてみた。#3
Ａ問題：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
問題文抜粋
問題を読むとこんなイメージが湧くのかなと思います。
カードゲームとかした人は多分イメージができるとは思いますが、
イメージできない人はこんな流れでモンスターの闘いが繰り返されます。
闘いのイメージ
図をみていただいた方は流れを理解できたでしょうか。
図に記載したようにざくっとこんな流れです。
1.高橋君のモンスターが青木君のモンスターに攻撃し、体力を減らす(C-B)
2.青木君のモンスターが高橋君のモンスターに攻撃し、体力を減らす(A-D)
3.この操作をどちらかのモンスターの体力(AもしくはC)がゼロになるまで繰り返す
4.繰り返した結果、高橋君が勝った場合(つまりCがゼロになった場合)はYesを、そうでなければNoを出力する
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;
}
最後に
いかがだったでしょうか？
見ても解らないやもう少しこうすると良いのではないか？といった暖かい言葉ドシドシお待ちしています。