【AtCoder】 9✖️9のタイルの問題を解いてみた
こんにちはchihiroです。今週から唐突に興味本位でAtCoderをやり始めました。
AtCoderはA問題とB問題は基本的なC++の記法を知っていたら解けるけど、C問題は計算量のことも考えたりとか難しいのが増えそうというイメージを持っていましたが、やはりこのC問題のあたりでだいぶ苦戦しています...
今回挑戦したのは11月4日にあったHHKBさんのプログラミングコンテストのC問題 Number Placeです。
問題の内容を見てみると、ぱっと見それほど難しくなさそうです。
とりあえずタテ９マス、ヨコ９マスのタイルがあって、そこにランダムに１から９の数字が入ってるから、ちゃんと縦と横と３✖️３のブロック内に１から９ひとつずつ入っているか確かめてねという問題。9✖️9の魔法陣の状態のときだけ"Yes"を出力させます。
最初は「１から９を足してったら45か、、、全部45になってるか判定するプログラム書けばいけるやん!」と意気揚々にプログラムを書いていました。
#include <iostream>
using namespace std;
int main() {
int A[9][9];
//9*9タイルの1~9の数字を読み取る
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cin >> A[i][j];
}
}
//縦の合計値
int ver_sum[9];
//横の合計値
int wid_sum[9];
//3*3タイルの中の合計値
int box_sum[9];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
//各合計値に値を追加;
ver_sum[i] += A[i][j];
wid_sum[j] += A[i][j];
if(0<=i&&i<=2&&0<=j&&j<=2){
box_sum[0] += A[i][j];
}else if(0<=i&&i<=2&&3<=j&&j<=5){
box_sum[1] += A[i][j];
}else if(0<=i&&i<=2&&6<=j&&j<=8){
box_sum[2] += A[i][j];
}else if(3<=i&&i<=5&&0<=j&&j<=2){
box_sum[3] += A[i][j];
}else if(3<=i&&i<=5&&3<=j&&j<=5){
box_sum[4] += A[i][j];
}else if(3<=i&&i<=5&&6<=j&&j<=8){
box_sum[5] += A[i][j];
}else if(6<=i&&i<=8&&0<=j&&j<=2){
box_sum[6] += A[i][j];
}else if(6<=i&&i<=8&&3<=j&&j<=5){
box_sum[7] += A[i][j];
}else if(6<=i&&i<=8&&6<=j&&j<=8){
box_sum[8] += A[i][j];
}
}
}
//合計値が1+2+3+4+5+6+7+8+9=45 になっているか
for(int i=0;i<9;i++){
if(ver_sum[i]!=45 || wid_sum[i]!=45 || box_sum[i]!=45){
cout << "No" << endl;
exit(0);
}
}
cout << "Yes" << endl;
}
しかしC問題はそう甘くない、ドヤ顔で提出したらWAを返されてしまいました。
何がだめなんだ...?いやでもまともにアルゴリズムの勉強とかしてないし、どこかで条件網羅できてないのか...と諦めかけていました。
再度提出したらAC
なぜかもう一度プログラムを提出したらACもらえました。そしてなぜかさっき提出した時よりbyte数が半分ぐらいになっているという怪奇現象
決して美しいプログラムとは言えなさそうな簡素なプログラムですが、これでもC問題ぐらいのレベルにはしがみつけると知っていただけたら幸いです。
公式解説のシンプルなプログラム
公式解説のプログラムを見させていただくと、cin >> A[i][j]をfor文で回しているところまでは同じでしたが、3✖️3ブロックの中の判定がfor文で綺麗にまとめられてて参考になりました。
1から9の数を配列のインデスクを利用して入れて、数字の数が１じゃなかった時点でfalseにするという処理が行われています。
以下は公式解説のコードの引用ですがコメントを付け加えています。
//i+=3 とj+=3をすることで各3*3タイルの左上の要素に移動している
for(int i=0;i<9;i+=3){
for(int j=0;j<9;j+=3){
//初期値設定
for(int k=0;k<9;k++)b[k]=0;
//ここから３*3タイルの判定
for(int ii=0;ii<3;ii++){
for(int jj=0;jj<3;jj++){
b[a[i+ii][j+jj]-1]++; //1~9それぞれの数をb配列に入れる
}
}
for(int k=0;k<9;k++)if(b[k]!=1)flag=false;
}
}
AtCoderは深く広く面白い
公式解説以外を見てみると、すでにsudoku()というsagemathのライブラリの関数があったらしく、それを利用すればほぼ1行で処理が完結するというとんでも技があったり、他の回答者の方のコードを見ると百人百色ひろんな解き方があったり、一つの問題でもとても学びになるところが多いです。
始めたばかりだとしばらくレートが上がりにくいらしいので、とりあえず3月終わるまでには茶色、あわよくば来年中に緑に入りたいなと思っています。これからものんびりAtCoderを続けていきたいです。