A
link
2つの動物が常に中央に向かってジャンプする場合、中央の間隔が奇数であればもう一方の動物が勝利します（必ず2つの動物が隣り合う状況でアリスがジャンプするから）。偶数の場合、アリスが勝利します（必ず2つの動物が隣り合う状況で相手の動物がジャンプするから）。このように、動物たちは常に中央に向かってジャンプする傾向があります。なぜなら、端に向かってジャンプして戻ってくる場合、歩数は偶数になるため勝敗の奇偶性に影響を与えないからです。
コードを表示``` #include<bits/stdc++.h>
using namespace std;
int n, x, y;
void solve(){
cin >> n >> x >> y;
if(x%2 == y%2) cout << "YES\n";
else cout << "NO\n";
}
int main(){
int t;
cin >> t;
while(t--) solve();
return 0;
}
B
=
link
配列の要素iとjを同時に選択することは最適ではありません。なぜなら（i < jと仮定すると）、配列は以下のように変化します：
a_1-2, a_2-2,…,a_{i-1}-2, a_i, a_{i+1}-2,…,a_{j-1}-2, a_j, a_{j+1}-2,…,a_{n-1}-2, a_n-2（これは手で計算することで確認できます）。
したがって、我々は常に1つの要素だけを変更する必要があります。まず、変更が必要な要素の数を確認し、それが1つの場合、他の要素がその要求を満たすかどうかをチェックします。
コードを表示```
#include<bits/stdc++.h>
using namespace std;
int n;
int original[200005];
int target[200005];
int count, position;
void solve(){
cin >> n;
count = 0;
for(int i = 1; i <= n; ++i)
cin >> original[i];
for(int i = 1; i <= n; ++i){
cin >> target[i];
if(target[i] > original[i]) count++, position = i;
}
if(count >= 2) cout << "NO\n";
else if(count == 0) cout << "YES\n";
else{
for(int i = 1; i <= n; ++i){
if(i != position && original[i] - target[position] + original[position] < target[i]){
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
}
int main(){
int t;
cin >> t;
while(t--) solve();
return 0;
}
C
link
各行と各列の合計をxとすると、xn=xmという式が成り立ちます。n≠mのとき、xは0でなければ条件を満たせません。したがって、各行と各列の合計を0に設定し、空欄を求めていきます。具体的には、位置(x,y)にいるとき、右に進む場合、左側（1〜y列）はもう進まないため、それらの列の値は既に確定しています。このため、各列の合計が0になるようにその点を計算できます。下に進む場合も同様の処理を行います。
コードを表示``` #include<bits/stdc++.h>
#define int long long
using namespace std;
int rows, cols; char direction[2005]; int grid[1005][1005]; int row_sum[1005], col_sum[1005];
void solve(){
cin >> rows >> cols;
cin >> direction+1;
for(int i = 1; i <= rows; ++i){
for(int j = 1; j <= cols; ++j){
cin >> grid[i][j];
row_sum[i] += grid[i][j];
col_sum[j] += grid[i][j];
}
}
int x = 1, y = 1;
for(int i = 1; i <= rows+cols-2; ++i){
if(direction[i] == 'R'){
grid[x][y] = -col_sum[y];
row_sum[x] += grid[x][y];
col_sum[y] += grid[x][y];
y++;
}
else{
grid[x][y] = -row_sum[x];
row_sum[x] += grid[x][y];
col_sum[y] += grid[x][y];
x++;
}
}
grid[rows][cols] = -row_sum[rows];
row_sum[rows] += grid[rows][cols];
col_sum[cols] += grid[rows][cols];
for(int i = 1; i <= rows; ++i){
for(int j = 1; j <= cols; ++j)
cout << grid[i][j] << " ";
cout << endl;
}
}
int main(){
int t;
cin >> t;
while(t--) solve();
return 0;
}
D
=
link
この問題はかなり複雑なシミュレーションです。コード内のコメントを参照してください。
コメントの中には理解しにくい部分があるかもしれません。その場合は、括弧で上記の説明と対応させます。
（1）ここでtimに加減算しているのは、tim秒が経過したにもかかわらず、後の稲妻人形の移動を考慮していないように見えるかもしれません。しかし、実際にはそれらも移動しています。
（2）押している：烏が稲妻人形とkの距離を保つため、ちょうどk離れている人形が1歩進むと、烏も1歩進みます。これは、稲妻人形が烏を押し進んでいると考えることができます。前の人形は烏からkより近づくことはなく、アルゴリズムによってkより遠ざかることもありません。
コードを表示```
#include<bits/stdc++.h>
using namespace std;
int num, distance, limit;
int positions[200005];
void solve(){
cin >> num >> distance >> limit;
distance *= 2; limit *= 2;
for(int i = 1; i <= num; ++i)
cin >> positions[i], positions[i] *= 2;
//分母を避けるために時間関連のすべてを2倍に
int crow_pos = 0;
//烏の位置
int current_scarecrow = 1;
//烏の前の最近の稲妻人形のインデックス
int elapsed_time = 0;
//経過時間
while(current_scarecrow+1 <= num && positions[current_scarecrow+1] == 0) current_scarecrow++;
//先頭の0の稲妻人形をスキップ
if(positions[1] > 0){
elapsed_time += positions[1];
positions[1] = 0;
//最初の稲妻人形を烏と重ねる
//（後で説明）
}
while(1){
crow_pos = positions[current_scarecrow] + distance;
//重なると烏は現在位置＋distanceに到達
//（重なるため、現在位置はpositions[current_scarecrow]
if(crow_pos >= limit) break;
//limitに到達すれば終了
//目的：
//烏の後ろにある最近の稲妻人形と烏が重なるようにする
if(current_scarecrow+1 <= num){
//烏の後ろに稲妻人形が存在する
//(1)
if(positions[current_scarecrow+1] - elapsed_time > crow_pos){
//烏が進んでも稲妻人形に追いつけない場合
//追いつくために必要な時間を追加
elapsed_time += (positions[current_scarecrow+1] - elapsed_time - crow_pos)/2;
//なぜ2で割るのか？
//烏を後ろの稲妻人形が押して進ませるため
//（2）
current_scarecrow++;
positions[current_scarecrow] -= elapsed_time;
//進んだ時間を差し引く
}
else if(positions[current_scarecrow+1] + elapsed_time >= crow_pos){
//烏がこの稲妻人形の前に進む範囲内にいる
//この稲妻人形を烏の位置に移動させる
current_scarecrow++;
positions[current_scarecrow] = crow_pos;
}
else{
//この稲妻人形は烏が進む範囲内にいない
//烏の進んだ時間分だけ位置を更新
current_scarecrow++;
positions[current_scarecrow] += elapsed_time;
}
}
else{
//烏の後ろに稲妻人形がない
elapsed_time += limit - crow_pos;
//最後の稲妻人形が烏を押してlimitに到達する（2）
//crow_posからlimitまでの距離を進む
break;
}
}
cout << elapsed_time << endl;
}
int main(){
int t;
cin >> t;
while(t--) solve();
return 0;
}