はじめに
こんにちは。Momijiといいます。
最近競技プログラミングにハマっており、情報オリンピックの問題を解いています。
その解説を備忘録として残していこう！というものです。
今回の問題は、タイトルにもある通り、第15回情報オリンピック予選の問題です。
では行ってみましょう！
問題
- 古い旗を塗り替えて、上から白→青→赤となるような旗を作る。
- 塗り替えるマスが一番少なくなる時の塗り替えるマスの数を出力。 端的にいうとこんな感じでしょうか。 例えば、入力例1の場合、
元の状態
塗り直した後
この時、元の状態から塗り直した後の状態にするためには、11マス塗り替えなければならないので、11を出力します。
コード
私が提出したコードです。
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
vector<vector<char>> s(N, vector<char>(M)); //入力される旗
vector<vector<char>> l(N, vector<char>(M)); //ロシアの旗になっている旗
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> s.at(i).at(j);
}
}
int ans=1000000000; //答え
int count=0; //間違っているマスの数を一時的に保存するもの
for (int white=1; white<=N-2; white++) {
for (int blue=1; blue+white<=N-1; blue++) {
int red = N-white-blue; //①
count=0;
//ロシアの旗を作る。(ここから) ②
for (int i=0; i<white; i++) {
for (int j=0; j<M; j++) {
l.at(i).at(j) = 'W';
}
}
for (int i=white; i<blue+white; i++) {
for (int j=0; j<M; j++) {
l.at(i).at(j) = 'B';
}
}
for (int i=white+blue; i<N; i++) {
for (int j=0; j<M; j++) {
l.at(i).at(j) = 'R';
}
}
//ロシアの旗を作る。(ここまで) ②
//入力されたものとロシアの旗を比較。 ③
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (s.at(i).at(j) != l.at(i).at(j)) count++;
}
}
ans = min(ans, count);
}
}
cout << ans << endl;
}
解説
この問題の解き方は、
1. 塗り直した後の旗を作る
2. 1と入力された旗で一致していない部分を数える
の2点です。
- この時、塗り直した後の旗の塗り分けの方法は、 上から、白の行(white)、青の行(blue)、赤の行(N - white - blue)となります。 白に塗る行がwhite行あるとすると、 青の行はwhite+1行目からblue行、 赤の行はwhite+blue+1行目からN-white-blue行それぞれあるということになります。 これをやっているのが、コードの①までです。
次に上のwhite、blue、redの値を使用して、実際にロシアの旗のカラーリングとなる旗を作ります。
それにあたるのがコードで②と書いてあるところです。
- 続いて、実際にロシアのカラーリングとなっている旗と入力された旗のマス目を比較して、間違っていたら、count++をします。コードでは③と書いてある部分です。 出力しなければならない数字は塗り直すマスが最小となるような数字を出力するので、最後にansとcountを比較して、countの方が小さければ、ansを書き換えます。
まとめ
初めて競プロについて記事を書くので、至らない点や間違っている点等あると思います。
「ここはこうなんじゃないか？」などあったら、コメントしてくださると嬉しいです。
私は初心者なので、このレベル又はそれ以上がスラスラ解けるレベルになりたいです。
ここまで読んで下さりありがとうございました。