TopCoder Open 2014 Algorithm Round 2B
こんにちはtatsyです。
今回はTCO 2014 Round 2Bの解説です。
Easy (350点)
問題
M個のスイッチを操作するゲームがあり、ゲームは全Nステージからなる。最初スイッチはすべてオフの状態になっている。各ステージでは与えられたスイッチの状態を満たすことでクリアできる。与えられる条件は「オン」、「オフ」、「どっちでもいい」のいずれか。各ステージでプレイヤーが行える操作はオンになっているスイッチを自由に選んでオフにする、あるいはオフになっているスイッチを自由に選んでオンにする、そして、ステージクリアのチェックをするの3通りである。このときゲームをクリアするのに必要な最小の操作回数はいくつか？
解法
現在の状態から次の状態に映るときに、行わなければならない手の数は
- 現在オフになっているもので、オンにしなければならないものがあれば+1
- 現在オンになっているもので、オフにしなければならないものがあれば+1
- クリアチェックをするために+1
で計算できる。
これでコードを書くと親切にも一番最後のテストケースが通らない。さすが350点問題。じゃあ、何がいけないのかというと、今の
ゲームでは複数のスイッチを一気に反転できるというところにポイントがある。
いわいる「どっちでもいい」になっているスイッチは必要になった時に反転するよりも、先読みして、反転できるときに反転しておいた方がいい。
なので、必要になったところから「どっちでもいい」の状態がつづく限りステージをさかのぼって調査し、必要な反転をしているステージがあれば、その時に反転してしまった方が良い。
これさえ正確にコーディングできれば大したことはない問題です。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> pii;
class SwitchingGame {
public:
int timeToWin(vector <string> states) {
int n = (int)states.size();
int m = (int)states[0].size();
string s(m, '-');
int ans = 0;
vector<pii> hist(n, pii(0, 0));
REP(i,n) {
int c1 = 0;
int c2 = 0;
REP(j,m) {
if(states[i][j] != '?' && s[j] != states[i][j]) {
if(s[j] == '+') {
c1++;
for(int k=i-1; k>=0; k--) {
if(states[k][j] != '?') break;
if(hist[k].first == 1) {
c1--;
break;
}
}
} else {
c2++;
for(int k=i-1; k>=0; k--) {
if(states[k][j] != '?') break;
if(hist[k].second == 1) {
c2--;
break;
}
}
}
s[j] = states[i][j];
}
}
if(c1 != 0) {
hist[i].first = 1;
ans++;
}
if(c2 != 0) {
hist[i].second = 1;
ans++;
}
ans++;
}
return ans;
}
};
Medium (500点)
問題
3人の数学者がいて、そのうちの1人がx, y (x <= y) という2つの数を選び、その和を数学者Sに、その積を数学者Pに教える。このとき数学者Sが「Pさんには僕の数を当てることはできませんよ」といった。すると数学者Pは「なるほど、そうであるならあなたの持っている数はSですね」といった。
この話を聞いた2人の女の子は新しいパズルを考え付いた。あるSを与えたときに、上のようなことが起こるx, yの組み合わせが存在するかどうかを考えるゲームである。今、AとBという2つの正の数が与えられたとき、A<= S <= BなるSの中で、上のようなx, yが与えられうるものの合計を答えよ。
解法
この問題は、正直問題文をきちんと理解することが解法のポイントだと思います。まず数学者Pがなぜ数学者Sの持つ数を当てられるかを考えます。
数学者Sが「Pさんには僕の数を当てることができません」といえる、ということは数Sが「素数+1」ではない、ということを意味します。なぜなら、もし「素数+1」であるならば数学者Pの持っている数は素数である可能性があり、この場合には数学者Pが数学者Sの持っている数を当てられてしまうからです。
次に数学者Pが数Pを持っているときに、x, yを当てられる場合はどういう時かを考えます。それはPを2つの数の積としてP=xyと表したときに、x+yが「素数+1」でないような分け方が1通しかないときです。数学者Sが「当てられない」といった時点でSの持っている数は「素数+1」ではないので、そのようなx, yが1通りしかないならば数学者Pは数を当てることができます。
ここまでの条件を使えば、小さい数については問題を解くことができますが、大きい数では時間が足りません。なので、もう少し深く考察してみます。
実はよく考えると数学者Pが数を当てることができるのはx=1, y=S-1, P=S-1の時に限られます。仮に、x>=2としてP = x(S-x)だとします。すると数学者PはPをx=1, y=x(S-x)と分解するパターンを考えなくてはなりませんが、この場合x(S-x)は合成数なのでx(S-x)+1は「素数+1」ではありません。当然ながら、x=x, y=S-xと分解した場合のx+y=Sも「素数+1」ではないので、この場合は「素数+1」のパターンが1つに決まらず、数学者Pが答えを言い当てることができません。
上の事実から逆に考えると、2つの数のペア(i, j)で(i, j >= 2)なるものについてi+jが「素数+1」でないならば、S=ij+1のときに数学者Pは数を言い当てられません。なので、ij+1がBを超えない範囲内ですべてのi,jについて、i+jが「素数+1」でないかどうかをチェックし、のこった数のうち「素数+1」でないものが今知りたい数ということになります。
これらをまとめると次のようなコードになります。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
const int MAX_N = 5000011;
bool primes[MAX_N];
bool valid[MAX_N];
class SumAndProductPuzzle {
public:
void erathos() {
fill(primes, primes+MAX_N, true);
primes[0] = primes[1] = false;
for(int i=0; i<MAX_N; i++) {
if(primes[i]) {
for(int j=i*2; j<MAX_N; j+=i) {
primes[j] = false;
}
}
}
}
long long getSum(int A, int B) {
erathos();
fill(valid, valid+MAX_N, true);
for(lint i=2; i<=B; i++) {
for(lint j=i; j*i<=B; j++) {
if(!primes[i+j-1]) {
if(i*j+1 >= MAX_N) {
PRT2(i, j);
}
valid[i*j+1] = false;
}
}
}
lint ans = 0;
for(int i=max(3,A); i<=B; i++) {
if(!primes[i-1] && valid[i]) ans += i;
}
return ans;
}
};
まとめ
今回のEasyは最後のテストケースがコーナーケースを含んでいたので、割と簡単だったと思います。最後のテストケースがなかったら、結構なチャレンジ祭りになっていたんじゃないでしょうか。
Mediumについては、問題文の条件を整理して貪欲なコードを書くところまでは言ったのですが、TLEにならない解法を見つけられませんでしたね。GCJでTシャツ逃したのでTCOでTシャツ狙っていきたいですが、最後のRound2Cの結果次第ですかね。まぁ、気楽にやってみます。
今回も最後までお読みいただき、ありがとうございました。