250 삽질, 500 레코드 찍고 11등 했던 셋. 한번 돌아보았다. 근데 SRM444 가 꽤나 옛날이더라.. 미혼 시절이니... -_-;;;; 근데 250은 더 빨리 풀었지만 500은 완전 느리게 풀고, 1000 도 섭밋만 했지 틀리고.. 완전 패망이라능.. ㅠㅠ 점점 퇴화하는 것 같아. 1000 은 inclusion-exclusion principle 의 좋은 예. 그거 생각 못해서 일단 틀리고, 그거 코딩한 다음엔 off-by-one error 로 틀림.
250 UnfoldingTriangles
구현만 잘 하면 되는 문제.
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
struct UnfoldingTriangles
{
vector<string> g;
int solve(int y, int x, int limit)
{
int ret = -1;
for(int size = 1; ; ++size)
{
if(y-size+1 < 0 || x-size+1 < 0) break;
if(x+1 < g[0].sz && g[y-size+1][x+1] == '#') break;
if(y+1 < g.sz && g[y+1][x-size+1] == '#') break;
bool seenBlack = false, seenWhite = false;
int unfold = 0;
for(int i = 0; i < size; ++i)
{
char ch = g[y - size + 1 + i][x - i];
if(ch == '#') seenBlack = true;
else if(ch == '.') seenWhite = true;
else ++unfold;
}
if(seenWhite) break;
if(!seenBlack)
ret = ((size + 1) * size) / 2;
limit -= unfold;
if(limit < 0) break;
}
return ret;
}
int solve( vector <string> grid, int unfoldLimit )
{
g = grid;
int ret = -1;
REP(i,g.sz) REP(j,g[0].sz) ret = max(solve(i, j, unfoldLimit), ret);
return ret;
}
};
500 FourBlocks
Trivial exp time 동적 계획법. 4개짜리 블럭을 놓을 곳을 과거에는 2^h 를 모두 계산하면서 찾았는데, 이번에는 놓을 수 있는 후보 위치의 서브셋으로 한정해서 풀었다. 덕분에 런타임은 빠르지만 코딩타임은 시궁창. 아아.. ㅠ
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
int cache[1<<10][26];
struct FourBlocks
{
int h, w, taken[26];
int go(int x, int prevCol)
{
if(x == w) return h - __builtin_popcount(prevCol);
int& ret = cache[prevCol][x];
if(ret != -1) return ret;
ret = go(x+1, taken[x]) + (h - __builtin_popcount(prevCol));
if(x)
{
int canPut = (1 << (h-1)) - 1;
canPut &= ~(prevCol | (prevCol >> 1));
canPut &= ~(taken[x] | (taken[x] >> 1));
// int canPut = ~(prevCol | taken[x]) & ((1 << (h-1))-1);
for(int fours = canPut; fours; fours = ((fours-1) & canPut))
{
if(fours & (fours << 1)) continue;
int cand = __builtin_popcount(fours) * 16;
int occupy = fours | (fours << 1);
assert(!(occupy & prevCol));
assert(!(occupy & taken[x]));
cand += h - __builtin_popcount(prevCol | occupy);
cand += go(x+1, taken[x] | occupy);
ret = max(ret, cand);
}
}
return ret;
}
int maxScore( vector <string> grid )
{
h = grid.sz; w = grid[0].sz;
CLEAR(taken,0);
REP(i,h) REP(j,w) if(grid[i][j] == '1') taken[j] += (1<<i);
CLEAR(cache,-1);
int add = 0;
REP(i,w) add += __builtin_popcount(taken[i]);
return go(0, (1<<h)-1) + add;
}
};
1000 AvoidFour
처음에는, 대회했을 때랑 똑같은 패턴으로, 44, 444, 4444.. 만 고려했다가 답이 안나오는 사태에 봉착. 다행히도, 이번에는 44 를 한개의 블록으로 해서 44^n 을 모두 찾으면 되겠다 라는 생각을 할 수 있었다. 그러나, 44 와 444 의 LCM 들은 두번 빼진다는 걸 생각 못했지롱. 후.....
처음에는 그리고 옛날 ValidPlates 인가 하는 문제에서 봤던 starting symbol 패턴을 써서 풀었는데, 생각해보면 A\^1 + A\^2 + ... A\^n 을 계산해서 푸는 것이 훨씬 말끔하다. 그리고 4 외의 숫자들은 한 개의 스테이트로 합칠 수 있다는 것을 이용하면 이와 같이 깔끔한 코드를 얻을 수 있다.. ㅠ
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef long long ll;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll M = 1000000007;
VVI operator + (const VVI& a, const VVI& b)
{
int n = a.sz;
VVI ret(n, VI(n, 0));
REP(i,n) REP(j,n) ret[i][j] = (a[i][j] + b[i][j]) % M;
return ret;
}
VVI operator * (const VVI& a, const VVI& b)
{
int n = a.sz;
VVI ret(n, VI(n, 0));
REP(i,n) REP(j,n) REP(k,n) (ret[i][j] += ((a[i][k] * b[k][j]) % M)) %= M;
return ret;
}
VVI pow(const VVI& unit, ll N)
{
assert(N);
if(N == 1) return unit;
if(N % 2) return pow(unit, N-1) * unit;
VVI half = pow(unit, N/2);
return half*half;
}
// unit + unit**2 + .. + unit**N
VVI powsum(const VVI& unit, ll N)
{
assert(N);
if(N == 1) return unit;
if(N % 2) return pow(unit, N) + powsum(unit, N-1);
VVI half = powsum(unit, N/2);
return half + (half * pow(unit, N/2));
}
struct AvoidFour
{
int count( long long n)
{
VVI C(5, VI(5, 0));
C[1][0] = 8; C[2][0] = 1;
C[1][1] = 9; C[2][1] = 1;
C[3][2] = 1; C[1][2] = 9;
C[4][3] = 1; C[1][3] = 9;
C[1][4] = 9;
VI lens;
for(ll unitLen = 44; unitLen <= n; unitLen = (unitLen * 10) + 4)
lens.push_back(unitLen);
ll A = 0;
REP(mask,(1<<lens.sz))
{
ll lcm = 1;
REP(i,lens.sz) if(mask&(1<<i))
{
lcm = (lcm / __gcd(lcm, lens[i])) * lens[i];
if(lcm > n) break;
}
if(lcm > n) continue;
VVI un = powsum(pow(C, lcm), n / lcm);
ll D = 0;
REP(j,5) (D += un[j][0]) %= M;
if(__builtin_popcount(mask) % 2 == 0)
A = (A + D) % M;
else
A = (A + M - D) % M;
}
return A;
}
};
