はじめに
ICPC2019国内予選は自分が通っている大学からも何チームか出場していて、その結果を見て少し気になっていたので、実際に3時間計ってやってみました。
問題文は大会公式サイトを参照してください。
結果から先に言うと、AからDまでの4問を解いた時点（合っているかはわからないです）で2時間半かかっていたので、そこで諦めています。
A問題
- 開始時点の残り時間：3時間
- 解くのに要した時間：20分
- 使った言語：C++
問題に対する感想
パッと見て、単純な配列操作と条件分岐だけで作れるな。と思ったので特に何も考えることなくつらつらとプログラムを書いていきました。
生徒と科目の最大数が決まっていたので、先にそれらの行列を格納する配列を作っておくのが楽かなと思いました。
解くのに20分と時間を使ってしまったのは、競プロの問題を解くのが4年ぶりだったということもあり、データセットを順番に入れていくのだと思ってループ処理と終了条件の設定をしていなかったことに作ってから気がついて少し修正をしたからです。
実装したアルゴリズムの簡単な説明
- 無限ループ
- データセットに対する変数などの宣言,初期化
- 最初の1行からデータのサイズを取得
- ここで2つとも0なら終了
- 生徒と科目の行列の要素を配列に格納
- 順番に合計値を計算,最大値のみを残して最後の生徒まで計算する
- 結果の出力
ソースコード
/*
5 2
10 20 30 40 50
15 25 35 45 55
6 3
10 20 30 15 25 35
21 34 11 52 20 18
31 15 42 10 21 19
4 2
0 0 0 0
0 0 0 0
0 0
*/
#include <iostream>
int main(){
while(1){ //終了までループ処理
int Data[50][1000] = {}; //データセット用 配列 初期化
int student = 0,subject = 0; //初期化
std::cin >> student >> subject; //行列のサイズの格納
if(student == 0 && subject == 0){ //終了判定
break;
}
//要素の値を格納
for(int i = 0; i < subject; i++){
for(int j = 0; j < student; j++){
std::cin >> Data[i][j];
}
}
int max_score = 0; //最大値 格納用
//最大値探索
for(int i = 0; i < student; i++){
int score = 0; //合計値 格納用
for(int j = 0; j < subject; j++){
score += Data[j][i]; //点数加算
}
if(max_score < score){ //最大値更新
max_score = score;
}
}
std::cout << max_score << std::endl; //結果表示
}
}B問題
- 開始時点の残り時間：2時間35分
- 解くのに要した時間：15分
- 使った言語：C++
B問題を始める前に5分だけ休憩しました。
問題に対する感想
ぶっちゃけA問題とやってる内容変わらなくない？と思いました。
A問題に文字列の扱いが増えた感じですかね。
char型で配列を宣言してやれば文字列から一文字ずつ取得できること、stringヘッダを利用して文字列を文字列型で扱えば文字数を簡単に調べれるということを使って実装すれば良いことがわかっていたので気も楽でした。
読み込んでしまえば配列操作と条件分岐だけで作れてしまうなと思ったので時間をかけずにサクッと作りました。
実装したアルゴリズムの簡単な説明
- 無限ループ
- データセットに対する変数などの宣言,初期化
- 最初の1行からデータのサイズを取得
- ここで2つとも0なら終了
- スクリーンキーボードをchar型配列に格納
- 文字列型を利用し,目的の文字列を格納
- 押下回数を探索
- 位置情報から文字毎に配置場所を探索（ループ処理）
- 上下左右で差の絶対値を取り結果用の変数に加算する
- 位置情報を更新する
- 結果用の変数に1足す
- 位置情報から文字毎に配置場所を探索（ループ処理）
- 結果の出力
ソースコード
/*
3 9
ABCDEFGHI
JKLMNOPQR
STUVWXYZ_
ICPC
5 11
___________
____A______
________M__
___________
_C_________
ACM
4 21
1_2_3_4_5_6_7_8_9_0_-
QqWwEeRrTtYyUuIiOoPp@
AaSsDdFfGgHhJjKkLl;_:
ZzXxCcVvBbNnMm,_._/__ ICPC2019,AsiaYokohamaRegional,QualificationRound
0 0
*/
#include <iostream>
#include <string>
#include <cmath>
int main(){
while(1){ //終了までループ処理
char Data[50][50] = {}; //スクリーンキーボード用 配列 初期化
int row = 0,column = 0; //初期化
std::cin >> row >> column; //行列のサイズの格納
if(row == 0 && column == 0){ //終了判定
break;
}
//スクリーンキーボード格納
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
std::cin >> Data[i][j];
}
}
//対象の文字列格納
std::string str;
std::cin >> str;
int pos[2] = {}; //強調位置 配列
int times = 0; //押下回数
//押下回数探索
for(int k = 0; k < str.length(); k++){
char next = str[k];
for(int i = 0; i < row; i++){
for(int j = 0; j < column; j++){
if(Data[i][j] == next){
times += std::abs(i - pos[0]); //上下操作
times += std::abs(j - pos[1]); //左右操作
pos[0] = i; //位置変換
pos[1] = j; //位置変換
times++; //OKボタン操作
break;
}
}
}
}
std::cout << times << std::endl; //結果表示
}
}C問題
- 開始時点の残り時間：2時間10分
- 解くのに要した時間：1時間
- 使った言語：C++
途中で一度諦めて、先にD問題を解きました。
問題に対する感想
最初パッと見て作れるかわからないな〜と焦りました。分銅の乗せ方の全探索をして、それらと薬品量をうまく使えば解けるんだろうという推測はできたのですが、全探索の方法も何を使えばいいのかわからない。クラスをしっかり作るには時間があまりないからできたら避けたい。
そんな感じでふわふわと書いては消して、ループ処理をいくつも書いて〜としていたら時間がどんどん減っていくので、一旦後でやろうと思ってD問題を解きにいきました。
D問題を解いた後は、もう多分これ以上解くことができないだろうからゆっくりやろうと思って、おそらくもっとコンパクトな道があるんだろうな〜と思いながらも地道にやることにしました。
まずはグローバルに一部の配列や変数をおいて、少し強引に再帰関数で全探索と配列への格納を行いました。
これで後は単純だ！と思ったのですがそう上手くもいかず、分銅を追加する条件を考えて、そのために配列操作を行ったりしながらなんとか作り終えました。
実装したアルゴリズムの簡単な説明
- 無限ループ
- データセットに対する変数などの宣言,初期化
- 最初の1行からデータのサイズを取得
- ここで2つとも0なら終了
- それぞれのデータを格納
- 分銅の組み合わせ（測れる薬品量）の全探索
- 配列サイズを計算してメモリ確保
- 再帰関数によって全探索して配列に格納
- 配列をソートし重複の削除
- 追加する分銅の探索
- 各薬品量について探索（ループ処理）
- 測れる薬品量との差を計算,差の配列へ格納
- ソートし重複の削除
- 分銅が必要な場合（配列の先頭が0出ない場合）
- 一つ目の場合,差の配列の要素を全て追加する分銅用の配列にコピー
- 二つ目以降の場合,分銅用の配列のうち,差の配列の要素と一致する要素以外を削除
- 求められる結果の条件から結果を出力
- 各薬品量について探索（ループ処理）
再帰関数については配列への挿入とカウンタの増加、最後でない場合に3通りの分銅の置き方を実行するという内容になっています。
ソースコード
/*
4 2
9 2 7 11
2 9
6 2
7 3 6 12 16 9
2 9
5 2
7 3 6 12 17
2 9
7 5
15 21 33 48 51 75 111
36 54 57 93 113
0 0
*/
#include <iostream>
#include <cmath>
int m_Data[100], w_Data[10]; //薬品,分銅用 配列
int medicine, weight; //サイズ
int *w_All; //測れる量の種類
int count; //カウンター
void find_wall(int total, int num){ //w_all 再帰的に格納 totalが合計値 numはどの分銅か
if(num == weight){
w_All[count] = total; //配列に挿入
count++; //カウンタを増加
}else{
find_wall(total + w_Data[num],num+1); //加算
find_wall(total - w_Data[num],num+1); //減算
find_wall(total,num+1); //無
}
}
int main(){
while(1){ //終了までループ処理
medicine = 0,weight = 0; //初期化
count = 0; //初期化
std::cin >> medicine >> weight; //行列のサイズの格納
if(medicine == 0 && weight == 0){ //終了判定
break;
}
//薬品量 格納
for(int i = 0; i < medicine; i++){
std::cin >> m_Data[i];
}
//分銅 格納
for(int i = 0; i < weight; i++){
std::cin >> w_Data[i];
}
//測れる量の探索
int w_num = (int)std::pow(3,weight); //配列サイズ
w_All = new int[w_num]; //メモリ確保
find_wall(0,0); //配列への格納
std::sort(w_All, w_All + w_num); //ソート
//重複削除
for(int i = 0; i < w_num; i++){
if(w_All[i] == w_All[i+1]){
for(int j = i+1; j < w_num-1; j++){
w_All[j] = w_All[j+1];
}
w_num--;
i--;
}
}
//追加する分銅の探索
int array_times = 0;
int *array;
int before_num = 0;
for(int i = 0; i < medicine; i++){
int *pos_array = new int[w_num]; //動的メモリ確保 一時保存配列
for(int j = 0; j < w_num; j++){
pos_array[j] = std::abs(m_Data[i] - w_All[j]); //測れる量との差の入力
}
std::sort(pos_array, pos_array + w_num); //ソート
int array_num = w_num; //配列の長さ 変数
//重複削除
for(int j = 0; j < array_num; j++){
if(pos_array[j] == pos_array[j+1]){
for(int k = j+1; k < array_num-1; k++){
pos_array[k] = pos_array[k+1];
}
array_num--;
j--;
}
}
//分銅を必要とする場合
if(!(pos_array[0] == 0)){
if(array_times == 0){ //分銅を必要とする薬品1つ目
array = new int[array_num];
for(int j = 0; j < array_num; j++){
array[j] = pos_array[j];
before_num = array_num;
}
}else{
for(int j = 0; j < before_num; j++){ //2つ目以降
int flag = 0; //一致確認フラグ
for(int k = 0; k < array_num; k++){
if(array[j] == pos_array[k]){
flag = 1;
}
}
if(flag == 0){ //一致がなければ削除
for(int k = j; k < before_num-1; k++){
array[k] = array[k+1];
}
before_num--;
j--;
}
}
}
array_times++;
}
delete[] pos_array;
}
if(array_times > 0 && before_num == 0){
std::cout << -1 << std::endl;
}else if(array_times == 0){
std::cout << 0 << std::endl;
}else{
std::cout << array[0] << std::endl;
}
//メモリ解放
delete[] array;
delete[] w_All;
}
}D問題
- 開始時点の残り時間：1時間50分
- 解くのに要した時間：40分
- 使った言語：C++
一度C問題を諦めて、先にD問題を解きました。
問題に対する感想
これが正解のアルゴリズムだ！と自信を持って言えるものがしばらく思い浮かばなかったので、初めてシャーペンと紙を手にとってカウンタの数値などを書きながら考察しました。
隣接するカウンタを同時に押せるということは、どちらの端から押しても最短の結果が得られそうなので左から優先に押していくこととしました。
隣接するカウンタの目標値との差は最も近い二つ（大小）に設定することで最も無駄がなくなるため、それを再帰関数で実現し、最小値を返すようにしました。
実装したアルゴリズムの簡単な説明
- 無限ループ
- データセットに対する変数などの宣言,初期化
- 最初の1行からデータのサイズを取得
- ここで2つとも0なら終了
- データの格納
- データから目標値との差を格納
- 再帰関数に放り込んで結果表示
再帰関数については
- 前のカウンタの目標値との差に最も近い二つの目標値との差の探索
- 探索の最後の場合
- 前のカウンタの目標値との差よりも目標値との差が大きい場合には加算
- 返り値として今までの合計を返す
- 探索の途中の場合
- 前のカウンタの目標値との差に最も近い二つの目標値について再帰関数を実行
- 返り値として返り値が小さい方の再帰関数の返り値を返す
ソースコード
/*
4 5
2 3 1 4
2 5 5 2
3 100
1 10 100
1 10 100
5 10000
4971 7482 1238 8523 1823
3287 9013 9812 297 1809
0 0
*/
#include <iostream>
#include <cmath>
int Data[3][1000] = {}; //各カウンタの値 格納用 配列 0初期値 1目標値 2目標値との差
int num = 0,max = 0; //カウンタの個数と最大値 初期化
//再帰的に最小値を求める
int search(int total, int Data_weight, int Data_num){
int i = 0;
while(Data_weight > Data[2][Data_num] + max*i){ //何周させるか
i++;
}
int min_next = 0;
int max_next = 0;
if(Data_num == num-1){ //最後
if(i == 0){
total += Data[2][Data_num] + max*i - Data_weight;
}
return total;
}else{ //途中
if(i > 0){
min_next = search(total,Data[2][Data_num] + max*(i-1),Data_num+1);
}
max_next = search(total + Data[2][Data_num] + max*i - Data_weight,Data[2][Data_num] + max*i,Data_num+1);
}
if(i > 0 && min_next < max_next){
return min_next;
}else{
return max_next;
}
}
int main(){
while(1){
//初期化
num = 0;
max = 0;
std::cin >> num >> max; //行列のサイズの格納
if(num == 0 && max == 0){ //終了判定
break;
}
for(int i = 0; i < num; i++){ //初期値
std::cin >> Data[0][i];
}
for(int i = 0; i < num; i++){
std::cin >> Data[1][i]; //目標値
//目標値との差の計算
if(Data[0][i] <= Data[1][i]){
Data[2][i] = Data[1][i] - Data[0][i];
}else{
Data[2][i] = max - Data[0][i] + Data[1][i];
}
}
std::cout << search(0,0,0) << std::endl;
}
return 0;
}最後に
合っているかはわかりませんが、提示されたテストケースはとりあえず乗り切っています。
気が向いたら来年は参加してみたいですね。
コメント