AtCoder Beginner Contest 018
はい。
https://beta.atcoder.jp/contests/abc018
A - 豆まき
Python2
p,q=[],[] for i in range(1,4): x=int(raw_input()) p.append(x) q.append(x) p.sort() p=p[::-1] for i in q: print p.index(i)+1
ソートで順位つけて、indexでなんとか。
B - 文字列の反転
Python2
s=raw_input() n=int(raw_input()) def chg(w,x,y): k=w[x-1:y] p=w[:x-1]+k[::-1]+w[y:] return p for i in range(n): a,b=map(int, raw_input().split()) s=chg(s,a,b) print s
スライスと反転を頑張る。
C - 菱型カウント
C++14
#include<bits/stdc++.h> using namespace std; int main(){ int r,c,k,ans=0; scanf("%d %d %d",&r,&c,&k); int b[r][c][2]; char s[r][c]; for (int i=0;i<r;i++) for (int j=0;j<c;j++) { b[i][j][0]=0; b[i][j][1]=0; } for (int i=0;i<r;i++) { scanf("%s",s[i]); } for (int i=0;i<r;i++) for (int j=0;j<c;j++) { if (i==0) { if (s[i][j]=='o') b[i][j][0]=1; if (s[r-i-1][j]=='o') b[r-i-1][j][1]=1; } else { if (s[i][j]=='o') b[i][j][0]=b[i-1][j][0]+1; if (s[r-i-1][j]=='o') b[r-i-1][j][1]=b[r-i][j][1]+1; } } for (int i=k-1;i<r-(k-1);i++) for (int j=k-1;j<c-(k-1);j++) { bool f[2]={1,1}; for (int p=0;p<k;p++) { if (b[i][j+p][0]<k-p || b[i][j+p][1]<k-p) f[0]=0; if (b[i][j-p][0]<k-p || b[i][j-p][1]<k-p) f[1]=0; } if (f[0]==f[1] && f[0]==true) { ans+=1; } } printf("%d\n",ans); return 0; }
問題文がよくわかっておりません。。Kの制約はmin(r,c)/2でないと枠からはみ出る気がします。その時は0が解になってるはずですけど。解き方はわからなかったので解説スライド見ましたね。とある任意の座標(x,y)に上方向と下方向に連続した白マスが何個かを調べておいて、枠内のK個内側を全部調べました。中心が(x,y)で菱形を作るのに(x+1,y), (x-1,y)..とかで菱形が作れることを確認したあとに、中心が(x+1,y)で確認するのに(x+2,y)とかの方向だけみれば良くて負の方向には見に行く必要ないんですけど調べてもTLEにならないみたいですね。まぁC問題ですしね