AtCoder Beginner Contest 302
結果
A - Attack : AC(1:48)
B - Find snuke : 提出無し
C - Almost Equal : AC(36:51)
D - Impartial Gift : 提出無し
A - Attack
体力$${A}$$の敵に対して$${1}$$回攻撃をすると体力を$${B}$$減らす
最低何回攻撃すれば体力を$${0}$$以下にできるか求める問題
自分の回答
int main(){
int64_t A, B;
cin >> A >> B;
printf("%ld\n", A / B + (A % B == 0 ? 0 : 1));
}AをBで割った余りが無いならそのまま、あるなら+1
そういえばこの手のは(A-1)/B+1でよかったな
公式解説
省略
B - Find snuke
縦$${H}$$マス横$${W}$$マスがあり、$${1}$$マスに$${1}$$文字英小文字が入っている
この中に$${1}$$つだけ存在する「s」「n」「u」「k」「e」がこの順で一列に並んでいる場所の座標を求める問題
自分の回答
書き始めたら各座標から全8方向見ないといけないからとんでもなく時間かかるなと思って後回し
D問題に行き詰って戻ってきたけど書ききれなかった
探索して座標が一直線かを見るのが良かったのかな…
どのみちB問題で要求されるものではねぇ…
公式解説
int main() {
int n,m,x,y;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
string str;
cin>>n>>m;
vector<string> s(n);
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<8;k++){
str="";
for(int t=0;t<5;t++){
x=i+t*dx[k],y=j+t*dy[k];
if((x<0)||(x>=n)||(y<0)||(y>=m))break;
str+=s[x][y];
}
if(str=="snuke"){
for(int t=0;t<5;t++){
x=i+t*dx[k]+1,y=j+t*dy[k]+1;
cout<<x<<" "<<y<<endl;
}
return 0;
}
}
}
}
return 0;
}https://atcoder.jp/contests/abc302/editorial/6404より
どの方向に見るかを配列で事前に用意するのか
なるほど
C - Almost Equal
英小文字からなる長さ$${M}$$の文字列が$${N}$$個与えられ、全ての文字列において自身と次の文字列が$${1}$$文字違いであるように並べることができるか判定する問題
自分の回答
int main(){
int N, M;
cin >> N >> M;
vector<string> S(N);
for(int i = 0; i < N; i++){
cin >> S[i];
}
sort(S.begin(), S.end());
do{
bool t = true;
for(int i = 0; i < N - 1; i++){
int miss = 0;
for(int j = 0; j < M; j++){
if(S[i][j] != S[i + 1][j]){
miss++;
}
}
if(miss > 1){
t = false;
break;
}
}
if(t){
printf("Yes\n");
return 0;
}
}while(next_permutation(S.begin(), S.end()));
printf("No\n");
}Nが最大8なためnext_permutationで総当たり
公式解説
省略
D - Impartial Gift
高橋君が青木君とすぬけ君に$${1}$$つづつプレゼントを贈る
青木君への候補は$${N}$$個、すぬけ君への候補は$${M}$$個あり、それぞれ価値が決まっている
二人へ贈る物の価値の差が$${D}$$以下になる中で価値の和が最大となるようにするといくつになるか求める問題
自分の回答
総当たりはダメなのがすぐ分かったからA全てから二分探索で価値の差がD以下で最大となるものを探すようにしてみたけど二分探索がちゃんと書けなかった
これは経験積むしかない
公式解説
import bisect
N, M, D = map(int, input().split())
A = sorted(map(int, input().split()))
B = map(int, input().split())
ans = -1
for b in B:
i = bisect.bisect_right(A, b + D) - 1
if i >= 0 and A[i] >= b - D:
ans = max(ans, A[i] + b)
print(ans)https://atcoder.jp/contests/abc302/editorial/6412より
Pythonによるもの
b+D以下で最大の値を直接探すんじゃなくてb+Dがどの位置に入るのかを探すのか
なるほど