algospot.com :: 질문과 답변: BOARDCOVER2 질문드립니다.

BOARDCOVER2 질문드립니다.

#pragma GCC diagnostic ignored "-Wwrite-strings"
//#pragma GCC diagnostic ignored "-Wc++11-extensions"

#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <cstring>
#include <queue>
#include <cassert>
#include <ctime>
#include <cassert>
#include <climits>
#include "stdarg.h"
#include <bitset> //http://stackoverflow.com/questions/4048749/bitwise-operations-on-vectorbool //http://www.drdobbs.com/the-standard-librarian-bitsets-and-bit-v/184401382
#include <numeric> //http://stackoverflow.com/questions/6743003/how-calculate-sum-of-values-in-stdvectorint
#include <iomanip> // cout << fixed << setprecision(8);

using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector <VI> VVI;
typedef vector <string> VS;

#define MP make_pair
#define ST first
#define ND second
#define PB push_back
#define FOR(i,a,b) for( int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for( int i=(a); i>=(b); --i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define ALL(X) (X).begin(),(X).end()
#define SZ(X) (int)(X).size()
#define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end();++it)

#define CE cout << endl;
#define CL cout << "--------------------------------------" << endl;
#define ASF assert(false);
#define V vector
#define DQ deque
#define PQ priority_queue

template <class T, class U>
ostream & operator << (ostream &out, const pair<T,U> &A) {
  out << A.ST << "_" << A.ND; return out;
}

template<template<typename, typename> class ContainerT, typename ValueT> //http://cboard.cprogramming.com/cplusplus-programming/145441-stl-container-template-argument.html
ostream & operator << (ostream &out, const ContainerT<ValueT, std::allocator<ValueT> > &A) {
  FORE(i, A) out << *i << " "; return out;
}

template<template<typename, typename> class ContainerT, typename ValueT, typename ValueU> 
ostream & operator << (ostream &out, const ContainerT<pair<ValueT, ValueU>, std::allocator<pair<ValueT, ValueU> > > &A) {
  FORE(i, A) out << *i << " "; return out;
}



#define VA_NARGS_IMPL(_1,_2,_3,_4,_5,_6,_7,_8,N,...) N
#define VA_NARGS(...) VA_NARGS_IMPL(__VA_ARGS__, 8, 7, 6, 5, 4, 3, 2, 1)

#define P_(a)                       #a << ": " << a
#define P__(a)                      " | " << P_(a)
#define P1(a)                       cout << P_(a) << endl;
#define P2(a, b)                    cout << P_(a) << P__(b) << endl;
#define P3(a, b, c)                 cout << P_(a) << P__(b) << P__(c) << endl;
#define P4(a, b, c, d)              cout << P_(a) << P__(b) << P__(c) << P__(d) << endl;
#define P5(a, b, c, d, e)           cout << P_(a) << P__(b) << P__(c) << P__(d) << P__(e) << endl;
#define P6(a, b, c, d, e, f)        cout << P_(a) << P__(b) << P__(c) << P__(d) << P__(e) << P__(f) << endl;
#define P7(a, b, c, d, e, f, g)     cout << P_(a) << P__(b) << P__(c) << P__(d) << P__(e) << P__(f) << P__(g) << endl;
#define P8(a, b, c, d, e, f, g, h)  cout << P_(a) << P__(b) << P__(c) << P__(d) << P__(e) << P__(f) << P__(g) << P__(h) << endl;

#define P_IMPL2(count, ...) P ## count (__VA_ARGS__)
#define P_IMPL(count, ...) P_IMPL2(count, __VA_ARGS__) 
#define P(...) P_IMPL(VA_NARGS(__VA_ARGS__), __VA_ARGS__)

template<class T> void mini(T &a, const T &b) {if(b<a)a=b;}
template<class T> void maxi(T &a, const T &b) {if(b>a)a=b;}

int H,W,R,C;
bitset <100> board;
V<VPII> tile;
int tileSize;
V<V<V<bitset<100> > > > moves;

//false : void
//true : solid

int getPos(PII x) {
  return x.ST * W + x.ND;
}
int getPos(int x, int y) {
  return x*W + y;
}
bool inRange(PII x) {
  return x.ST >= 0 and x.ST < H and x.ND >= 0 and x.ND < W;
}
bool inRange(int x, int y) {
  return x >= 0 and x < H and y >= 0 and y < W;
}

int ans;
//connected component? div-con
//getDead & fill & release

void print() {
  CL
  REP(i, H) {
    REP(j, W) 
      if(board[getPos(i,j)]) cout << '#';
      else cout << '.';
    CE
  }
}

void play(int curAns) {
  int voids = H*W - board.count();
  if(curAns + voids/tileSize <= ans) return;

  PII target = MP(-1, -1); 
  REP(i, H*W) if(not board[i]) {target = MP(i/W, i%W); break;}
  if(target.ST == -1) {maxi(ans, curAns); return;}

  int i = target.ST; int j = target.ND;
  //care of symmetric?
  assert(moves[i][j].size() <= tile.size());
  FORE(k, moves[i][j]) {
    if((board & *k).count()) continue;
    board |= *k;
    play(curAns+1);
    board &= ~*k;
  }
  assert(not board[getPos(target)]);
  board[getPos(target)].flip();
  play(curAns);
  board[getPos(target)].flip();
}

void calcMoves() {
  moves = V<V<V<bitset<100> > > > (H, V<V<bitset<100> > >(W, V<bitset<100> >()));
  REP(i, H) REP(j, W) FORE(k, tile) {
    bool chk = true;
    FORE(it, *k) chk &= inRange(i+(*it).ST, j+(*it).ND) and not board[getPos(i+(*it).ST,j+(*it).ND)];
    if(!chk) continue;
    bitset<100> temp;
    temp.reset();
    FORE(it, *k) temp.set(getPos(i+(*it).ST, j+(*it).ND));
    moves[i][j].PB(temp);
  }
}

void shiftTile(VPII &x) {
  sort(ALL(x));
  int dx = -x.front().ST; int dy = -x.front().ND;
  FORE(i, x) {
    (*i).ST += dx;
    (*i).ND += dy;
  }
}

LL solve()
{
  cin >> H >> W >> R >> C;
  board.reset(); 
  REP(i, H) {
    string temp; cin >> temp;
    REP(j, W) if(temp[j] == '#') board.set(getPos(i,j)); //board[getPos(i,j)].flip();
  }
  tileSize = 0;
  tile.clear(); tile.resize(4, VPII());
  REP(i, R) {
    string temp; cin >> temp;
    REP(j, C) if(temp[j] == '#') {
      tile[0].PB(MP(i,j));
      tile[1].PB(MP(j,R-i-1));
      tile[2].PB(MP(R-i-1,C-j-1));
      tile[3].PB(MP(C-j-1,i));
    }
    tileSize++;
  }
  REP(i, 4) shiftTile(tile[i]);
  sort(ALL(tile));
  tile.erase(unique(ALL(tile)), tile.end());
//  FORE(i, tile) P(*i);

  ans = 0;
  calcMoves();
  play(0);
  return ans;
}

int main()
{
  int T; cin >> T; REP(i, T)
  cout << solve() << endl;
  return 0;
}

안녕하세요, BOARDCOVER2 문제의 TLE 를 해결하기가 쉽지 않아 질문드립니다.
책의 풀이와 비교해서, bitset 을 사용하였고, 각각의 좌표에서 움직일 수 있는 가능성이 있는 좌표들을 미리 계산해두었다는 차이점이 있고, 나머지는 비슷한 것 같습니다.

10 10 3 3
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

".#."
"###"
"..#"
이런 인풋을 넣으면 오래 걸리는데요, 어떻게 개선하면 좋을지 잘 모르겠습니다. 계산 횟수의 upper limit 로, 가장 간단하게 4^(100/5) = 2^40 = 10^12 를 생각할 수 있습니다만, 가지치기를 통해서 실제로는 그보다 충분히 짧게 되리라고 생각했습니다. 시간을 어림하는 것도 개선하는 것도 감이 잘 오지 않습니다ㅜㅜ 조언 부탁드립니다.

10년 전

15개의 댓글이 있습니다.

sven

calcMoves 까지는 금방 됩니다.
play 함수 내부에서 계산하는 시간을 줄이는 정도로는 해결이 되지 않을 것 같습니다. (줄인 시간에 정비례해서 전체 시간이 줄어들 것인데, 위 예제의 계산이 오랫동안 끝나지 않아서 1000배 이상의 개선을 하지 않으면 불가능할 듯...)
가지치기를 더 해야 되려나요? 아니면 뭔가 큰 오류를 놓치고 있는 것인지...

10년 전 link
Sharifa

play(0)할 때 cout << tileSize << endl;만 추가하셔도 알 겁니다.
tileSize가 오로지 R로만 저장되는군요.
tileSize가 실제 크기에 비해 대부분의 경우 훨씬 작을 수밖에 없는 행의 크기로 측정되니 당연히 오래 걸리죠.
그것만 바꾸면 몇 초 안에 잘 나옵니다.
제 코드보다 약간 느리긴 한데 그건 함수별 수행 시간의 차이라고 추측되고요

//여기서부터는 일종의 최적화
최초의 빈 칸이 어디 있는지 탐색할 때 굳이 처음부터 돌 필요 없습니다.
이전에 i_before에서 빈 칸을 찾아서 play를 수행했다면,
다음부터는 i_before+1부터 탐색해도 됩니다.
그리고 매번 H*W를 계산하는데 한 테스트 케이스에서 그 값은 일정하니까 굳이 계속 계산할 필요 없습니다.
곱셈은 시간이 많이 소요되는 연산입니다(괜히 karatsuba 알고리즘이 있는게 아닙니다)

그리고..부탁인데(?) 코드는 이렇게 짜지 않았으면 합니다.
정말 읽기 싫게 생겼습니다.
아마 코딩의 편의를 위해 수많은 #define문을 비롯 엄청난 수의 문장들이 들어가 있는데
이 문제와는 관련 없는 코드가 100줄은 됩니다.

10년 전 link
Sharifa

또 하나 최적화 방법을 말해드리자면
1
10 10 1 2
"..#...#...
"...#.#.#..
"#.#.#...#.
".#...#.#.#
"..#.#.#...
".#.#...#..
"#...#.#.#.
".#.#.#...#
"..#...#.#.
"...#...#..
"##
이런 데이터를 한번 넣어보세요.
시간 안에 안 나온다면, 분리된 공간을 각각 탐색한 후 각 공간에서 최댓값을 더하는 방법을 쓰면 훨씬 빨라질 겁니다.
//참고로 위 데이터에서 제일 많이 채울 수 있는 경우의 수만 해도 5억 가지가 넘습니다

10년 전 link
Being
1. 친절한 답변에 감사드립니다. 몇 가지만 짚고 넘어가겠습니다.
2. H*W의 곱셈으로 느려졌다는 건 넌센스입니다.
3. 어디서부터 탐색할지 위치를 저장하는 것이 큰 성능 향상을 가져다 주지는 않을 것입니다. 선형적인 영향을 줄 뿐이죠. 가지치기는 지수적인 영향을 미치므로 여기에 묻힐 수밖에 없습니다.
4. 다른 분의 코드에 조언을 하실 때에는 서로 존중하는 분위기에서 했으면 좋겠습니다. 코드에 개선의 여지가 많기는 하지만, 올림피아드나 ICPC와는 달리 탑코더 등에서는 미리 준비한 코드를 허용하므로 저런 매크로 등을 활용하는 참가자들도 상당수임을 인지하셨으면 합니다.
10년 전 link
Being

가장 큰 원인은 제가 보기에도 Sharifa님이 지적하신 것처럼 tileSize++ 구문의 위치를 단순 실수하신 것 때문일 것 같네요.

10년 전 link
Sharifa

물론 저런 코드를 존중은 합니다만 질문할 때 별로 좋은 코드는 아닌 것 같습니다.
약간 말을 심하게 한 건 사과드립니다.
그리고 Being님께서 탐색 위치하고 H*W가 별 의미 없다고 하셨는데 고쳐 보니까 두 배정도 빨라졌습니다. 사실 가지치기에 비하면 별 것 아닌 건 맞지만 확실히 성능에 영향을 미칩니다.

10년 전 link
Being
1. 그래서 그 두 배 빠르고 느린 게 어떤 의미가 있나요? 질문자님께서는 '1000배' 가량 빨라져야 할 것 같다고 판단하고 계시는데요.
2. 시간에 가장 큰 영향을 미치는 것이 play() 내부의 루프들이니만큼, 마지막 탐색 위치를 기억하는 것은 당연히 변의 길이에 비례한 성능 향상을 기대할 수 있습니다. 이 부분은 제가 선형적인 영향을 준다고 이미 말씀드린 바 있습니다.
3. H*W의 곱셈 결과를 미리 계산해 두는 것은 정말 전혀 영향을 미치지 않습니다. 더욱이, 탐색 위치를 저장한다면 곱셈 결과를 활용하는 가장 바쁜 곳이 사라지기까지 하지요. 이유는 다음과 같습니다.
  1. 곱셈 인스트럭션은 비싸지 않습니다. 메모리 액세스에 비하면 아무 것도 아니지요. 카라츠바의 케이스는, 큰 정수를 곱셈할 때에는 효율적인 방법이 필요함을 나타낼 뿐입니다.
  2. 웬만한 컴파일러는 H*W가 불변이므로 루프 밖으로 꺼냅니다.
10년 전 link
Being

변의 길이를 변의 길이의 곱으로 정정합니다.

10년 전 link
Taeyoon_Lee

사실 나도 도와주고 싶었지만.. 수많은 매크로에 패배함.

10년 전 link
Sharifa

0.제 댓글이 마음에 안 드실 수는 있지만 그렇다고 해도 왜 저한테 시비조로 말씀하시는지 모르겠습니다.
1.1000배가량 빨라질 수 있도록 오류를 정정해드렸습니다. 저는 중요한 것은 놔두고 중요하지 않은 것만 강조하는 게 아닙니다.
1.이 문제는 최적화 문제이기도 한데 두 배의 시간 차이가 의미가 없다고 할 수는 없습니다. 1000배에 비해서는 1%도 되지 않지만, 그렇다고 의미가 없는 건가요?
1.그리고 저는 질문과는 별개로 많은 경우에 대해 1000배 이상의 효과를 낼 수 있는 방법도 말한 걸로 아는데요.
3. H*W를 미리 계산하는 것은 사실 컴퓨터 상황에 따른 수행 시간의 오차보다도 작을 것이고 따라서 크게 차이가 없을 것이라는 건 맞습니다.
3-1.곱셈이 메모리 액세스에 비하면 아무 것도 아니라고 하셨는데, 그 말은 H*W를 참조할 때는 메모리에 액세스하고 H와 W를 참조할 때는 아니라는 것처럼 들립니다.
3-1.HW가 캐시에 들어갈 지는 모르겠지만, 캐시에 의해서는 메모리 액세스 비용이 생각하시는 만큼 비싸지는 않습니다.
3-1.애초에 곱셈이 덧셈만큼 컴퓨터에서 빠르게 수행된다면 카라츠바 알고리즘은 아무런 쓸모도 없었을 겁니다. 카라츠바는 곱셈은 확실히 줄였지만, 총 연산 수는 더 많습니다.

10년 전 link
Being
일단 감정을 좀 가라앉히시고 이야기하시죠.
1. 저는 가장 중요한 부분을 짚어주신 데에 대해 인정합니다. 이견의 여지 없이 훌륭한 지적이었습니다. 이 부분에 있어서 제가 불만을 표현한 적은 없습니다만, 그렇게 느끼셨다니 제 표현 방법에 문제가 있었던 모양입니다. 사과드립니다.
2. 나머지 두 부분에 있어서는, 논란의 여지가 있어 지적하고자 했습니다.
  1. H*W 곱셈의 경우
    
    H*W, H, W를 저장한 변수가 메모리에 있든 없든 캐시에 있든 없든, 곱셈을 직접 하건 저장하건 그것들은 성능에 영향을 거의 미치지 않습니다. 왜냐하면 다른 훨씬 느린 인스트럭션들이 함수 내에 많기 때문입니다. 메모리 액세스는 H, W, H*W에 대한 이야기가 아니라 코드 내에서 메모리를 참조하는 다른 수많은 부분들에 대한 언급입니다.
    
    저 답변을 다는 시점에 혹여나 성능에 영향을 미칠지 모르겠다 생각되어 H*W의 값을 저장하여 테스트해보았으며, 전혀 영향을 미치지 않음을 확인하였습니다.
    
    카라츠바는 지금 논의에 전혀 무관하니 자꾸 이야기 나오지 않았으면 합니다.
    
    곱셈이 느려서 써서는 안 된다! 라고 하실 정도면 배열 크기를 전부 2의 거듭제곱으로 잡고 오프셋 계산을 bitwise 연산 하셔야 합니다.
  2. 마지막 위치를 기억하는 것: 다시금 언급하지만 분명히 성능 향상이 있으나 그 향상량이 문제와 질문자님 의도에 비추어 미미함을 지적하고자 했습니다.
10년 전 link
Sharifa

2.1.1 그렇다면 제가 무엇에 대한 메모리 액세스에 대한 말인지 잘 몰라서 잘못 답을 한 것 같군요.
2.1.2 제가 테스트한 바로는 약간 느렸습니다. 하지만 위에서도 언급했던 것처럼 컴퓨터 상황에 따른 오차보다 작을 것이고 큰 효과가 없음은 이미 말했습니다. 저는 지금 H*W가 효과가 크다고 말하고 있지 않습니다.
2.1.3 ..뭐 별 관련이 없긴 합니다만.
2.1.4 그 정도는 아닙니다. 곱셈이 자꾸 논란이 되는군요.
2.2 맞는 말입니다. 하지만 저는 질문자님의 의도에 맞는 답을 한 후 그 외에 향상할 수 있는 방법을 말해 본 것 뿐입니다. 이거야말로 왜 논란이 자꾸 되는지 모르겠군요.

오해가 많았던 것 같은데 기분 나쁘신 것 있다면 사과드립니다.
정리하자면,
1. tileSize++문 실수가 가장 큰 원인
2. 마지막 탐색 위치 저장은 (질문의 의도와는 큰 상관 없지만)하나의 최적화 옵션
3. H*W는 별다른 효과 없음
정도 되겠군요.

10년 전 link
Being

아닙니다. 저야말로 괜히 Sharifa님 기분 상하게 해드린 것 같아 걱정이었습니다. 다른 것이 더 큰 문제이니 그것만 해결하면 될 것 같아서 정리하려던 것이었는데 마음 쓰게 불편 끼쳐 죄송합니다. 두 배 빠르게 하는 것이 쉬운 일은 아니고, 분명히 의미가 있습니다. :)

10년 전 link
sven

제 코드를 읽어주시고 조언해주신 모든 분들 진심으로 감사드립니다. 덕분에 해결할 수 있었습니다.
저도 매크로는 어디까지나 개인의 편의를 위한 것이고, 이렇게 작성한 코드는 타인이 읽기에 좋은 코드가 아니기에, 프로그래밍 대회라는 특수한 상황에서만 가능한 것이라고 생각합니다. 찾아보니 책 44-45 페이지에서도 같은 이야기가 있군요. 앞으로 타인이 볼 코드는 필요없는 부분을 삭제하는 등의 개선 후에 올려야겠습니다.
이외에도 개선할 부분이 있다면 얼마든지 지적해주세요. 감사합니다.

10년 전 link
sven

@태윤형
사실 형이 쓰시던 매크로에서 프린트를 추가한 정도 밖에 없습니다 ㅋㅋㅋ 혼자 디버깅 할 때만 쓰고, 여기에는 프린트문이 남아있지 않아서 무시하시고 읽으셔도 되요.

10년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

BOARDCOVER2 질문드립니다.

15개의 댓글이 있습니다.