前置き
"パソコン甲子園2023 プログラミング部門予選"の問題がAOJ上で公開されたので、7問目までの解法を書いておきます。解説と呼べるほどのものでもないですが、ぜひ大会中に解けなかった問題の解法について知ってもらえればと思います。
問題リンク
1問目
A%(N+1)が答えになるので、それを出力するとよいです。N人に自分を含めたN+1人でキャンディを分ける必要があることに注意しましょう。
解答コード例
#include <bits/stdc++.h>
using namespace std;
int main(){
int A,N;
cin >> A >> N;
cout << A%(N+1) << endl;
}
2問目
少し難しそうな見た目をしていますが、問題文をよく読むとかなりヒントが書かれています。具体的には、問題文中の図の下の二段落分では判定方法を明かしてくれているので、これに基づいて実装するのみです。
原点Oと点Pのマンハッタン距離を計算して、それがd以下ならYes,そうでないならNoが答えになります。マンハッタン距離に関しても、問題文の一番下に計算式が載っていますから、これを利用するとよいです。
αに点Pを、βに原点Oを代入してみるとわかりますが、ここではabs(x)+abs(y)でマンハッタン距離を求めることができます(absは絶対値を返すC++の関数です)。これとif文を組み合わせて判定すると解けます。
解答コード例
#include <bits/stdc++.h>
using namespace std;
int main(){
int d,x,y;
cin >> d >> x >> y;
if(abs(x)+abs(y)<=d) cout << "Yes" << endl;
else cout << "No" << endl;
}
3問目
bが0になるまで、bを出力して、bを2で割って小数点以下切り捨てした数に更新を繰り返すとよいです。while文を用いるのが適切でしょう。
解答コード例
#include <bits/stdc++.h>
using namespace std;
int main(){
int b;
cin >> b;
while(b){
cout << b << endl;
b /= 2;
}
}
4問目
ここからいきなり難易度が上がります。まず図形が正方形であることの必要十分条件として、
- 四角形である
- 四辺の長さがすべて等しい
- 四つの内角がすべて等しい = すべて90°である
の3つが挙げられます。どれか一つでも欠いているならば、正方形であるとは断定不可能です(例えば、上二つの条件を満たす図形=正方形とした場合、ひし形も正方形であると判定されてしまいます)。
よって、この3つの条件を満たす図形が与えられているかを判定していくのが妥当でしょう。
まず四角形かの判定です。これは入力で与えられた4点に重複がないかを判定すればよいです。
入力の制約から、{1,2},{2,3},{3,4},{4,1}の4組が異なる座標の点である=重複していないことは保証されています。しかし、{1番目の点と3番目の点},{2番目の点と4番目の点}が異なる座標の点であることは保証されていません。よって、この2組の点が異なる点かを判定すれば、入力の4点に重複がないか判定することができます。もし2組のうち1組でも重複しているなら、入力からできあがる図形は四角形ですらないため、答えはNoで確定します。
さて、残り2つの条件の判定方法ですが、これは人によって方針が異なりがちです。例えば自分は、大会中には「4辺についてマンハッタン距離を取って、それぞれが等しいか判定」「(a,bの外積=0) = aとbは垂直 という直交判定法を利用して内角が90°か判定」という風にしました。ですが、後者の外積を利用する解法は初等幾何分野への知識かライブラリが必要になり、かなり面倒です1。
なので、別の人の簡潔な実装方針を紹介します。ちゃんと理解していないので説明が正確かは保証できません、ごめんなさい。
こんな感じにA,B,C,Dとナンバリングしたものとして考えます。AB,AD,ACをそれぞれの点とAとのユークリッド距離として求めておいて、これがAB==ADかつAB*2==ACを満たすならYesとなります。そうでなければNoです。
なんで？というのは比を考えるとよくて、{45°,90°,45°}の直角三角形が{1,√2,1}の比になることを利用しています。
ただし、ユークリッド距離を求める式は$\sqrt{(x_a-x_b)+(y_a-y_b)}$というふうに平方根が登場するので、これを考慮すると浮動小数点型を用いることになります。しかし浮動小数点型を用いると判定時に誤差を考慮した処理をする必要があり、面倒です。なので、ユークリッド距離の計算式の平方根を外して整数型で完結するよう求めていきます。
これに対応して、三角比も{1,2,1}という風に各項を2乗して扱います。
かなり複雑になってしまったのですが、つまりは大体こういうことです。(逆に混乱したらすいません…)
これでACできます。本当にいきなり難易度が上がった気がしますが、数学が得意な人にとってはそうでもないのかも。
解答コード例
途中で出てくるautoから始まるやつはラムダ式という記法を用いた関数定義です。
基本的に関数はmain関数の外で定義するもの、というイメージがあると思いますが、ラムダ式だとmain関数内でも書ける、みたいな感じです。便利なので覚えておいて損はしないと思います。基本的にはこれ読んで
特に(個人的には)再帰関数を書くのが格段に楽だと思っています。あまり調べても出てこない書き方で書くので(上のAPG4bに載っている書き方ではないです)、いつか紹介したいですが……
#include <bits/stdc++.h>
using namespace std;
int main(){
using ll = long long;
using pll = pair<ll,ll>;
pll a,b,c,d;
cin >> a.first >> a.second;
cin >> b.first >> b.second;
cin >> c.first >> c.second;
cin >> d.first >> d.second;
// 入力の点に重複があるかを判定
if(a==c || b==d){
cout << "No" << endl;
return 0;
}
auto get_vec = [](pll p, pll q){
pll res = {q.first-p.first, q.second-p.second};
return res;
};
pll ab = get_vec(a,b);
pll ac = get_vec(a,c);
pll ad = get_vec(a,d);
// ユークリッド距離への変換
// ただし整数型の範囲で扱うため、平方根をつけない
auto vec_convert_dist = [](pll p){
return p.first*p.first + p.second*p.second;
};
ll AB = vec_convert_dist(ab);
ll AC = vec_convert_dist(ac);
ll AD = vec_convert_dist(ad);
bool flag = (AB==AD && AB*2==AC);
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
5問目
ここからは計算量を意識する必要があります。
（いきなり余談ですが、この問題とかなり似たような設定の問題がAtCoder Beginner Contest上で出題されたことがあります。それがABC284-Dです。基本的な解法に関してはこの問題と同様、といえます2。）
入力で与えられたNについて、素因数分解をした後の形がp*p*qとなっているかを判定することで解くことができます。Nは最大でも10^9までしか与えられないので、解法としては$O(\sqrt{N})$で十分高速です。ということで、試し割りと呼ばれることの多いアルゴリズムを用いて素因数分解をする方針が妥当でしょう。
試し割りとは
雑に言えば、 Nの約数の組$(p,q),ただしp <= q$ を考える際にpは必ず$\sqrt{N}$以下になる ことを利用して、ループを1からNまでではなく1から$\sqrt{N}$まで回すことで十分だよ、という考え方です。（p*q==Nという形で約数の情報を持たせていると考えてください）
これを利用すると約数列挙・素数判定・素因数分解などの時間計算量が$O(N)$から$O(\sqrt{N})$に削減できます。
アルゴ式より: 試し割りの詳細な説明
素因数分解の実装に関してはそれなりに情報も多いと思うので、アルゴ式のこちらの記事を読むなどして学んでください。ほかの記事に説明を譲るという形で楽をさせていただきます。ちなみに自分の実装例では素因数分解のやり方を忘れていたので無駄なことをしてしまっています。
Nについて素因数分解した後の形がp*p*qになっているかの判定ですが、std::setを用いてやると楽かもしれません。素因数分解した結果を配列vに保存しているとすると、vの各要素をstd::setに入れてやり、それぞれの要素数が3,2に等しいかを判定することで十分です。
std::setは要素の重複を許さないため、v = {p,p,q}ならstd::set = {p,q}となるはずだからです。あるいは、vをstd::sortしてからv[0]==v[1] || v[1]==v[2]で判定するのもよいでしょう。
解答コード例
無駄なこと というのは、エラトステネスの篩を利用して1から300000までの素数判定を行っていることです。この問題であれば、isprimeに関する処理はすべて不要です。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = int(a); i < int(b); i++)
int main(){
int N;
cin >> N;
int lim = 300000;
// エラトステネスの篩
vector<bool> isprime(lim,true);
isprime[0] = isprime[1] = false;
rep(i,2,lim){
if(!isprime[i]) continue;
for(int j = i*2; j <= lim; j += i){
isprime[j] = false;
}
}
vector<int> v;
rep(i,2,lim){
while(isprime[i] && N % i == 0){
v.emplace_back(i);
N /= i;
}
}
if(N != 1) v.emplace_back(N);
set<int> se;
for(auto x : v) se.insert(x);
if(v.size()==3 && se.size()==2) cout << "Yes" << endl;
else cout << "No" << endl;
}
より高速な解法
実は、Miller-Rabin primality testとPollard's rho algorighmというアルゴリズムを組み合わせることで、$O(\sqrt[4]{N})$で素因数分解を行うことができます。Miller-Rabin素数判定法は確率的アルゴリズムなので一概に試し割り法の上位互換であるとは評価できませんが、少なくとも競プロで扱う範囲の数であれば決定的アルゴリズムであるため、競プロにおける素因数分解なら全部これで良いくらいの強力なアルゴリズムです。
理論は高等的で難しいため、興味がある人は各自で調べる程度でよいと思います。自分もちゃんと知らず使っているので…
欠点としては、試し割り法に対して記述量がかなり多くなることです。普段はコピペすればいい話なので気になりませんが、PCK本番ではコピペ禁止なため、写経には勇気が結構要ります。
ちなみに自分は写経しました。手が痛くなりました。(計算量の見積もりが甘く、これを貼らないと無理では？となってしまったので…)
6問目
やること自体は、(1,1)から(H,W)までの到達判定及び最小距離を求めるのをBFSで行えばいいだけです。ただし、現在が何拍目であるかの情報も持たせて、3拍分それぞれ独立に距離を管理する必要があります。よって、dist[縦][横][拍] = 最小距離 という風に持たせてBFSをすればよいです。要素数は[H][W][3]なので最悪ケースでも$3HW=3*10^4$となり、十分TLEやMLEに抵触しない範囲であることがわかります。
問題なのは、独特な入力形式を含めて複雑な実装を、バグなくコピペせず通せるか、というところにあったように思います。ちょっとした重実装問だと思っています。図を描いて頭を整理しながら解くとまだコードも書きやすいと思います。
解答コード例
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = int(a); i < int(b); i++)
using uint = unsigned int;
using P = pair<uint,uint>;
#define inf (1<<30)
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
int main(){
int H,W;
cin >> H >> W;
auto isout = [&](uint y, uint x){
return (y >= H || x >= W);
};
vector<int> dy = {0,1,0,-1};
vector<int> dx = {1,0,-1,0};
vector row(H,vector<int>(W-1));
rep(i,0,H) rep(j,0,W-1) cin >> row[i][j], row[i][j]--;
vector col(W,vector<int>(H-1));
rep(i,0,W) rep(j,0,H-1) cin >> col[i][j], col[i][j]--;
vector dist(H,vector(W,vector<int>(3,inf)));
dist[0][0][0] = 0;
queue<pair<P,int>> que;
que.push({{0,0},0});
while(que.size()){
auto a = que.front();
que.pop();
P p = a.first;
int t = a.second;
auto [y,x] = p;
rep(i,0,4){
uint Y = y+dy[i], X = x+dx[i];
if(isout(Y,X)) continue;
int nt = (t+1)%3;
// 右
if(i==0 && t==row[y][x]){
if(chmin(dist[Y][X][nt], dist[y][x][t]+1)) que.push({{Y,X},nt});
}
// 下
if(i==1 && t==col[x][y]){
if(chmin(dist[Y][X][nt], dist[y][x][t]+1)) que.push({{Y,X},nt});
}
// 左
if(i==2 && t==row[y][X]){
if(chmin(dist[Y][X][nt], dist[y][x][t]+1)) que.push({{Y,X},nt});
}
// 上
if(i==3 && t==col[x][Y]){
if(chmin(dist[Y][X][nt], dist[y][x][t]+1)) que.push({{Y,X},nt});
}
}
}
int ans = inf;
rep(i,0,3) chmin(ans, dist[H-1][W-1][i]);
cout << (ans!=inf ? ans : -1) << endl;
}
7問目
本番で通せなかったのに、改めて考えるとすぐに解けてびっくりしました。厳密に証明済みで確信が持てている、とかでもないので実は嘘解法かもしれない。
結論をいうと、($i={0,1,...,N-1}とする$) i番目のボールの大きさについて累積maxを取り、その累積maxの値が一度も$A_i$を超過しなければYesです。そうでなければNoです。
まず条件から考えて、最終的に左には自身より大きいボールが存在してはなりません。よって、自身より左にある最も大きいボールが(大きさの制限的に)問題なく交換できるかを考える必要があります。逆に、自身より左にあるボールのうち、最も大きいボール以外は考慮する必要がありません。最も大きいボールが問題なく交換できるなら、それより小さいボールも必ず問題なく交換できるためです。
ということで、左のボールからmax演算を累積するように更新していき、これが$A_i$を超過しないか毎回判定するだけで十分です。
自身より小さいボールが左にある場合、最終的な条件から考えて自身と左の小さいボールを交換する必要は無いため、左への移動は考慮しなくてよいものだと考えられます。
解答コード例
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = int(a); i < int(b); i++)
int main(){
int n;
cin >> n;
vector<int> a(n), b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
int maxi = 0;
rep(i,0,n){
if(maxi<b[i]) maxi = b[i];
if(maxi>a[i]){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}
おわり
8問目以降は自分が解けていないので、ここまでです。そこの解説を知りたい人は強そうな人のPCK参加記を読むと良いかもしれません。
改めて考えると4,5問目は割とシンプルな解法でいいんですね。大会中に写経しまくったのは愚行でした。