AtCoder Beginner Contest 275
結果
A - Find Takahashi:AC(4:03)
B - ABC-DEF:提出無し
C - Counting Squares:WA
A - Find Takahashi
$${N}$$本の橋があり、$${i}$$番目の橋の高さは$${H_{i}}$$であり全ての橋の高さは相異なる
この中で最も高い橋は何番目かを求める問題
自分の回答
int main(){
int N, H = 0, B;
cin >> N;
for(int i = 0; i < N; i++){
int h;
cin >> h;
if(H < h){
H = h;
B = i + 1;
}
}
printf("%d\n", B);
}シンプルに1つづつ確認していき、これまでの最大より大きければそれが何番目の橋かを入れていく
公式解説
同じため省略
B - ABC-DEF
非負整数$${A,B,C,D,E,F}$$が与えられ、$${(A×B×C)-(D×E×F)}$$を998244353で割った余りを求める問題
自分の回答
オーバーフローの回避方法が思いつかなかった
最初に各値を998244353で割った余りにしても最悪$${998244352^3}$$になるからもう1つか他の方法で工夫しなきゃいけないんだろうけど…
公式解説
const int mod=998244353;
int main() {
long long a,b,c,d,e,f;
long long x,y,ans;
cin >> a >> b >> c >> d >> e >> f;
x=((a%mod)*(b%mod))%mod;
x=(x*(c%mod))%mod;
y=((d%mod)*(e%mod))%mod;
y=(y*(f%mod))%mod;
ans=(x+mod-y)%mod;
cout << ans <<endl;
return 0;
}https://atcoder.jp/contests/abc275/editorial/5129より
2乗までならオーバーフローしないからそこでさらに余りを求めればいいのか
なるほど
C - Counting Squares
二次元平面上の座標$${(r,c)\space\space (r,cは1以上9以下の整数)}$$上に「.」か「#」がある
この平面上で「#」を頂点とした正方形がいくつあるかを求める問題
自分の回答
int main(){
vector<int> X, Y;
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
char C;
cin >> C;
if(C == '#'){
X.push_back(j);
Y.push_back(i);
}
}
}
if(X.size() == 0){
printf("0\n");
return 0;
}
int count = 0;
for(int i = 0; i < X.size() - 3; i++){
for(int j = i + 1; j < X.size() - 2; j++){
for(int k = j + 1; k < X.size() - 1; k++){
for(int l = k + 1; l < X.size(); l++){
int x1=X[i], x2=X[j], x3=X[k], x4=X[l], y1=Y[i], y2=Y[j], y3=Y[k], y4=Y[l];
int s1 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
int s2 = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
int s3 = (x3 - x4) * (x3 - x4) + (y3 - y4) * (y3 - y4);
int s4 = (x2 - x4) * (x2 - x4) + (y2 - y4) * (y2 - y4);
if(s1 == s2 && s2 == s3 && s3 == s4){
int d1 = (x1 - x4) * (x1 - x4) + (y1 - y4) * (y1 - y4);
int d2 = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
if(d1 == d2){
count++;
}
}
}
}
}
}
printf("%d\n", count);
}コンテスト終了後にAC出せたもの
#を4つ選んでそれでできる四角形の辺の長さが全て等しく、対角線の長さも等しければ正方形であるため、それでチェックするのを総当たり
そもそも#が無いときにforが無限ループに入っちゃうのにあと10秒早く気づければ時間内に解けた…
あとそこ絡みでX.size()==0としてるけどこれそもそも四角形ができないなら0なんだからX.size()<4の方が確実だね
テストケースで四角形ができないパターンは#が無いのだけだったから通ったけど2つでもTLEする
(3つだとちゃんと動くから根本的な原因がわからん…)
公式解説
int main() {
vector<string> s(9);
for(auto &v : s) cin >> v;
auto valid = [&](int x, int y) {
return clamp(x, 0, 8) == x and clamp(y, 0, 8) == y and s[x][y] == '#';
};
set<set<pair<int, int>>> st;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
for(int dx = -8; dx < 9; dx++) {
for(int dy = -8; dy < 9; dy++) {
if(!dx and !dy) continue;
int i2 = i + dx, j2 = j + dy;
int i3 = i2 - dy, j3 = j2 + dx;
int i4 = i3 - dx, j4 = j3 - dy;
if(valid(i, j) and valid(i2, j2) and valid(i3, j3) and valid(i4, j4)) {
set<pair<int, int>> sq;
sq.insert({i, j});
sq.insert({i2, j2});
sq.insert({i3, j3});
sq.insert({i4, j4});
st.insert(sq);
}
}
}
}
}
cout << st.size() << endl;
}https://atcoder.jp/contests/abc275/editorial/5137より
これは1点を決めてそれを起点に正方形を作り、頂点全てに#があるならその座標をsetに入れるのを総当たりしてるのかな
この問題いろいろな解き方ありそうだなぁ