メモ兼UAPC
UAPCの話がTLに出てきたので、終了後に問題を少し覗いてみました。なかなか難しそうで、競技プログラミングが得意ではない私には手も足も出なさそうでした。試しにいくつか解いてみたのですが、時間がかかりすぎますね。おそらく勝負にもならないでしょうw。
さて、それに関係することとして、問題中に二次元配列を使う問題が出てきました。それ自体は何の問題もないのですが、配列の大きさが r*c <= 10^6 とかなり大きなサイズで、VisualC++では少なくとも設定をいじらないと静的配列確保ではスタックオーバーフローを起こしかねない(最大だとデフォルトのままでは実行時エラーで落ちます)容量だったので、動的配列を使うことにしました。
二次元の動的配列の場合は
T hoge * * = new T[ n ]; //の後にfor文でmをnew * n・・・・・*1 T hoge *[ n ] = new T[ m ];//・・・・・*2
としなければいけないみたいですね。少し面倒だったのと調べるまで思いもつかなかった(ぇのでメモしておきたいと思います。
_*1はこの後newをfor文で行わないといけません。deleteはその逆の手順です。*2はfor文を使う必要は無いですが、mが定数である必要があります。今回はnとmの積の最大が決められているだけなので前者しか取れませんでした。
眺める程度であり、特にルールは読んでいないので(boostも使って)以下のようなコードを書きました(投稿用に少しだけ書き換えてあります)。
問題文
#include <iostream> #include <boost/shared_array.hpp> #include <limits.h> #include <vector> int main() { std::size_t row = 1, col = 1, q = 1; //const std::size_t MAX = 500; while( 1 ) { std::cin >> row >> col >> q; if( !row && !col && !q ) break; boost::shared_array< boost::shared_array\ < int > > map( new boost::shared_array< int >[ row ] ); for( std::size_t i = 0; i < row; ++i ) map[ i ] = boost::shared_array< int >( new int [ col ] );; //int map[ MAX ][ MAX ] = {}; //mapの読み込み for( std::size_t i = 0; i < row; ++i ) { for( std::size_t j = 0; j < col; ++j ) { int input = 1; std::cin >> input; map[ i ][ j ] = input; } } //小規模グリッド読み込み for ( std::size_t i = 0; i < q; ++i ) { unsigned x = 0, y = 0; std::cin >> x >> y; const unsigned x1 = x; const unsigned y1 = y; std::cin >> x >> y; const unsigned x2 = x; const unsigned y2 = y; int min = INT_MAX; //グリッド内の最小値を求めて表示する for( std::size_t j = x1; j <= x2; ++j ) { for( std::size_t k = y1; k <= y2; ++k ) { min = ( std::min )( min, map[ j ][ k ] ); } } std::cout << min << std::endl; } //for( std::size_t i = 0; i < row; ++i ) // delete [] map[ i ]; //delete [] map; } return 0; }
この問題は15分くらいですね。もう少し早く解けてもよさそうです。
というわけでメモでした。おしまい