最近topcoderさんのSRMに参加し始めました。
せっかくなので、自力をつける意味も含めて戦績などを書いていこうと思います。
WhichDay：DIV2イージー250点問題
元問題：http://community.topcoder.com/stat?c=problem_statement&pm=11553
概要：(意訳)曜日を表す文字列を6つ渡すので、その中に含まれない曜日を返しなさい。
提出したコード：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>
class WhichDay {
public:
std::string getDay(std::vector<std::string> notOnThisDay) {
const char * const list[] = {
"Friday", "Monday", "Saturday", "Sunday", "Thursday", "Tuesday", "Wednesday"
};
std::sort(notOnThisDay.begin(), notOnThisDay.end());
for(unsigned int i = 0; i < notOnThisDay.size(); i++) {
if(notOnThisDay[i] == list[i]) {
continue;
}
return list[i];
}
return list[6];
}
protected:
};
説明するまでもないですがｍ、ソート済みのlistとソートした引数を先頭から比較し、相違した曜日、もしくはlist末尾の曜日を返しているだけです。
こういった実装は珍しく、bool配列を持たせて一致した物のフラグを立てていくものが主流、稀にbool配列の代わりに整数を用いたものがありました。
チャレンジの狙い目も特になし、強いて言うならコード中の曜日に誤字がないか、ぐらい？
ThreeTeleports：DIV2ミディアム600点問題
元問題：http://community.topcoder.com/stat?c=problem_statement&pm=11554
概要：(意訳)無限に続く格子状平面でxかy方向に1動くのに1秒、全部で3つ(入口の数で数えると6つ)のテレポートで移動するのに10秒かかる、スタートから目的地まで最短で何秒かかるか。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>
class ThreeTeleports {
public:
int shortestDistance(int xMe, int yMe, int xHome, int yHome, std::vector<std::string> teleports) {
long long int ret = LLONG_MAX;
std::vector<std::vector<int> > list;
for(unsigned int i = 0; i < 3; i++) {
int start_x, start_y, end_x, end_y;
parse_teleport(&start_x, &start_y, &end_x, &end_y, &teleports[i]);
std::vector<int> temp;
temp.push_back(start_x);
temp.push_back(start_y);
temp.push_back(end_x);
temp.push_back(end_y);
list.push_back(temp);
temp.clear();
temp.push_back(end_x);
temp.push_back(end_y);
temp.push_back(start_x);
temp.push_back(start_y);
list.push_back(temp);
}
ret = std::min(ret, static_cast<long long int>(point_point(xMe, yMe, xHome, yHome)));
for(unsigned int i = 0; i < 6; i++) {
ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10 + teleport_point(&list[i], xHome, yHome));
}
for(unsigned int i = 0; i < 6; i++) {
for(unsigned int l = 0; l < 6; l++) {
if(i == l) {
continue;
}
ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10
+ teleport_teleport(&list[i], &list[l]) + 10
+ teleport_point(&list[l], xHome, yHome));
}
}
for(unsigned int i = 0; i < 6; i++) {
for(unsigned int l = 0; l < 6; l++) {
if(i == l) {
continue;
}
for(unsigned int j = 0; j < 6; j++) {
if(i == j || l == j) {
continue;
}
ret = std::min(ret, static_cast<long long int>(point_teleport(xMe, yMe, &list[i])) + 10
+ teleport_teleport(&list[i], &list[l]) + 10
+ teleport_teleport(&list[l], &list[j]) + 10
+ teleport_point(&list[j], xHome, yHome));
}
}
}
return ret;
}
protected:
void parse_teleport(int *start_x, int *start_y, int *end_x, int *end_y, std::string *teleport) {
sscanf(teleport->c_str(), "%d %d %d %d", start_x, start_y, end_x, end_y);
}
int point_teleport(int x, int y, std::vector<int> *teleport) {
return point_point(x, y, (*teleport)[0], (*teleport)[1]);
}
int teleport_teleport(std::vector<int> *start_teleport, std::vector<int> *end_teleport) {
return point_teleport((*start_teleport)[2], (*start_teleport)[3], end_teleport);
}
int teleport_point(std::vector<int> *teleport, int x, int y) {
return point_point((*teleport)[2], (*teleport)[3], x, y);
}
int point_point(int start_x, int start_y, int end_x, int end_y) {
const int move_x = std::abs(start_x - end_x);
const int move_y = std::abs(start_y - end_y);
return move_x + move_y;
}
};
テレポートは入口換算でも6か所しかないのと、同じテレポートを使うことは無意味なので最大でも3回しかテレポートしない事がわかります。
またテレポートを使用しない移動時間は単純計算一回で導き出せます。
以上の理由により、総当たりでもテレポートなし(1種)、1度テレポート(6種)、2度テレポート(6*6=32種)、3度テレポート(6*6*6=216種)の合計255パターンを網羅するだけで最小値を出すことが可能だとわかります。
このパターン数ならばまずどんな入力でもTLE(Time Limit Exceeded)することはないため、あとは適当に計算してやるだけで解くことができます。
(上のコード中では若干パターン数を減らす処理が入っていますが、TLEする恐れがないのにタイプ数を増やしてまで計算量を減らすのは愚の骨頂です、マネしないように)
他の人も書き方の違いこそあれ、大体同じ方法で解いていました。
チャレンジの狙い目はオーバーフローです。
返り値はINTであり、実際どんなinputでもINT_MAXを超える値が返ることはありませんが、総当たりをしている場合は計算中に超えてしまうことがあります。
単純にマイナスになるパターンはサンプルに存在するため大体対策されていますが、マイナスを超えて1以上の数値までオーバーフローした場合の対策が抜けている人が多くいました。
(おそらくこのひっかけこそが600点という高得点問題である理由でしょう)
自分もこの点に気づき撃墜できる人物を絞り込むところまではいきましたが、うまい具合に対策を潜り抜けるテストケースを作っている間に時間切れで↓。
ちなみに、自分のコードではlong long intを使うことで回避しています。
BinaryCards：DIV2ハード900点問題
元問題：http://community.topcoder.com/stat?c=problem_statement&pm=11552
概要：(意訳)2^0=1,2^1=2,2^2=4,2^3=8…2^63までの数値が書かれているカードがあり、表になっているカードの数値合計の初期値をA、そこから最小手数で、なおかつ場の数値合計が最も大きくなるようにカードを裏返してA+1,A+2,A+3…Bと数値を作っていったとき、最も大きくなった場の数値を返せ。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <functional>
#include <algorithm>
#include <utility>
class BinaryCards {
public:
long long largestNumber(long long A, long long B) {
if(A == B) {
return A;
}
#define START_VALUE 0x0800000000000000LL
long long int value = 0;
for(long long int n = START_VALUE; ; n /= 2) {
if(n > B) {
continue;
}
if(n <= A) {
A -= n;
B -= n;
value += n;
n = START_VALUE * 2;
continue;
}
return value + n*2-1;
}
return 0;
}
protected:
};
(※上記のコードはSRM終了後にコーディングした物です)
初期値をなしに考えると2^x-1の数値から2^xの数値を作る際に(2^x)*2-1という最も大きな数値が現れます。
(例えば場7から8を作るとき、場の3枚全てを裏にし8を表にするため、最初に8を表にすれば15が作れます)
また、場2^x+y-1から2^x+y(xは取り得る限り最大の値)を作るときの最大数は、y-1からyを作るときの最大数+2^xである事もわかります。
なので、A<=2^x-1最後に
実際の戦績
室内順位2位/18人、Div2順位134位/950人、レート964->1036と上々の結果です。
前回に続き今回もミディアムが簡単すぎて逆に怖いぐらいでしたが、オーバーフローで落ちる人続出して納得。
サンプルでオーバーフローしていたにもかかわらずifだけで回避しようとする人が多い当たり、競技プログラミングには意外とlong long intを使用する文化はないのかもしれません。
4連続でレートUPしているため、そろそろ苦手な「数学の公式を使わないとTLEする問題」が出てきそうでビクビク。
次回は出られるかわかりませんが、出れたら同じようにレポートを上げる予定です。
