업다운 디펜스
업다운 디펜스란 백준에서 Solved.ac 기준으로 특정 난이도의 문제를 랜덤으로 풀고,
$30$분 안에 그 문제를 해결한다면 한 티어 높은 문제로, 그렇지 못한다면 한 티어 낮은 문제로 이동하는 문제풀이법이다.
문제는 Solved.ac에서 *g4 s#50.. -@$me 와 같이 난이도 및 푼 사람이 50명 이상인 문제 중 고르고 랜덤으로 섞어서 가장 먼저 나오는 것을 푼다.
괄호 안에 +는 틀린 횟수이다.
그 뒤에 따라 붙는건 분:초 이다.
초록색은 30분안에 해결을 했음을 나타내고, 빨간색은 못풀었음을 나타낸다.
성공한 예시 - [+2] 15:22
실패한 예시 - [+7] 42:50
$30$분이 지나도 풀이를 못떠올려서 해설을 찾아봐서 풀었을 때 - [-]
간만에 시작해보도록하자.
[Gold 5] BOJ 1553 - 도미노 찾기 [+] 08:40
BOJ 1553 - 도미노 찾기
단순 백트랙킹 문제였다.
펼치기
void solve () {
vs b ( 8 );
fv ( b );
vvi used ( 7 , vi ( 7 ));
int ans = 0 ;
vvi c ( 8 , vi ( 7 ));
function < void ( int ) > fn = [ & ]( int i ) -> void {
debug ( i );
if ( i == 56 ) {
ans ++ ;
return ;
}
int y = i / 7 , x = i % 7 ;
if ( c [ y ][ x ]) {
fn ( i + 1 );
return ;
}
int m = b [ y ][ x ] - '0' ;
if ( x != 6 && ! c [ y ][ x + 1 ]) {
int j = b [ y ][ x + 1 ] - '0' ;
if ( ! used [ m ][ j ]) {
used [ m ][ j ] = used [ j ][ m ] = 1 ;
c [ y ][ x ] = c [ y ][ x + 1 ] = 1 ;
fn ( i + 1 );
c [ y ][ x ] = c [ y ][ x + 1 ] = 0 ;
used [ m ][ j ] = used [ j ][ m ] = 0 ;
}
}
if ( y != 7 && ! c [ y + 1 ][ x ]) {
int j = b [ y + 1 ][ x ] - '0' ;
if ( ! used [ m ][ j ]) {
used [ m ][ j ] = used [ j ][ m ] = 1 ;
c [ y ][ x ] = c [ y + 1 ][ x ] = 1 ;
fn ( i + 1 );
c [ y ][ x ] = c [ y + 1 ][ x ] = 0 ;
used [ m ][ j ] = used [ j ][ m ] = 0 ;
}
}
};
fn ( 0 );
cout << ans ;
}
[Gold 4] BOJ 23031 - 으어어… 에이쁠 주세요.. [+] 10:50
BOJ 23031
시뮬레이션 문제이다.
문제에서 하라는대로 하면 된다.
펼치기
const int dy [] = { - 1 , 0 , 1 , 0 }, dx [] = { 0 , 1 , 0 , - 1 }, op [] = { 2 , 3 , 0 , 1 };
const int dy8 [] = { - 1 , - 1 , 0 , 1 , 1 , 1 , 0 , - 1 }, dx8 [] = { 0 , 1 , 1 , 1 , 0 , - 1 , - 1 , - 1 };
struct zombie {
int y , x , d ;
};
void solve () {
int n ;
cin >> n ;
string s ;
cin >> s ;
vs b ( n );
fv ( b );
vector < zombie > z ;
vvi on ( n , vi ( n ));
for ( int y = 0 ; y < n ; y ++ )
for ( int x = 0 ; x < n ; x ++ ) {
if ( b [ y ][ x ] == 'Z' ) {
z . pb ({ y , x , 2 });
}
}
int d = 2 , y = 0 , x = 0 ;
auto in = [ & ]( int y , int x ) {
return y >= 0 && y < n && x >= 0 && x < n ;
};
for ( char c : s ) {
if ( c == 'L' ) {
d = md ( 4 , d - 1 );
}
if ( c == 'R' ) {
d = md ( 4 , d + 1 );
}
if ( c == 'F' ) {
int ny = y + dy [ d ], nx = x + dx [ d ];
if ( in ( ny , nx )) {
y = ny , x = nx ;
if ( b [ ny ][ nx ] == 'S' ) {
on [ ny ][ nx ] = 1 ;
for ( int d8 = 0 ; d8 < 8 ; d8 ++ ) {
int nny = y + dy8 [ d8 ];
int nnx = x + dx8 [ d8 ];
if ( in ( nny , nnx ))
on [ nny ][ nnx ] = 1 ;
}
}
for ( auto & [ zy , zx , zd ] : z ) {
if ( ! on [ zy ][ zx ] && zy == y && zx == x ) {
cout << "Aaaaaah!" ;
return ;
}
}
}
}
int oy = y , ox = x ;
for ( auto & [ y , x , d ] : z ) {
int ny = y + dy [ d ], nx = x + dx [ d ];
if ( ! in ( ny , nx )) {
d = md ( 4 , d + 2 );
} else {
y = ny , x = nx ;
}
if ( y == oy && x == ox && ! on [ y ][ x ] && b [ y ][ x ] != 'S' ) {
cout << "Aaaaaah!" ;
return ;
}
}
}
cout << "Phew..." ;
}
[Gold 3] BOJ 3806 - S를 T로 [+7] 32:57
BOJ 3806
$10$분만에 제출한 코드가 정답이였는데
내 테스트케이스 문제 템플릿에 #이 들어간 Case #1: 3 처럼 출력하게 되어있어서 계속틀렸다.
그냥 처음 제출에서 # 하나 지우고 제출하니 통과되었다.
해답은 다음과 같다.
$0_s$ 를 $0$이 $s$에 있는 횟수처럼 쓰겠다.
$0$은 언제나 $1$로 바꾸지만 $1 \to 0$ 은 안된다는 점을 관찰한다.
그럼 안되는 경우는 $0_t > 0_s + ?_s$ 임을 알 수 있다.
모든 ?를 $0$으로 바꿔도 $t$에 있는 $0$개수만큼이 안나오기 때문이다.
그 외의 경우에는 항상 만들 수 있다.
일단 ? 는 제쳐두고 $1$번 연산을 얼마나 써야하는지 생각해보자.
$\text{Max}(0, 1_t-1_s-?_s)$ 만큼은 항상 $1$번 연산을 써줘야 하므로 $s_i=0$ 그리고 $t_i=1$ 인 저만큼에 대해서 $1$번 연산을 해주고 시작한다.
그 다음 $?_s$ 만큼 정답에 더해주고, $s_i \neq t_i$ 인 것의 개수를 $s_i=0$ 이라면 $u_0$, $s_i=1$ 이라면 $u_1$ 이라고 했을 때,
$\text{Min}(u_0,u_1)$ 만큼 정답에 더해준다. 3번 연산을 최대한 쓰는것이 이득이기 때문에 서로 교환할 수 있는것들을 모두 교환해준다.
이제 $u_0$과 $u_1$ 중 더 큰것에서 작은것을 뺀 만큼 정답에 더해주면 된다.
왜냐면 현재까지 $s_i \neq t_i$ 인 것들은 항상 ? 중에서 그걸로 바꿔서 교환해줘서 맞춰줘야하는데,
?의 개수만큼 이미 정답에 더해두었고 남는 ?들을 적절히 바꿔서 교체하면 결국 교체하는 비용만 들기 때문이다.
펼치기
void solve () {
string s , t ;
cin >> s >> t ;
int n = sz ( s );
int one_t = cntt ( t , '1' ), zero_t = n - one_t , one_s = cntt ( s , '1' ), zero_s = n - one_s ;
int q = cntt ( s , '?' );
if ( zero_t > zero_s + q ) {
cout << - 1 << endl ;
return ;
}
int ans = q ;
int op1 = max ( 0 , one_t - q - one_s );
for ( int i = 0 ; i < n ; i ++ ) {
if ( s [ i ] == '0' && t [ i ] == '1' && op1 ) {
ans ++ ;
s [ i ] = '1' ;
op1 -- ;
}
}
vi u0 , u1 ;
for ( int i = 0 ; i < n ; i ++ ) {
if (( s [ i ] == '0' ) && t [ i ] == '1' ) u0 . pb ( i );
if (( s [ i ] == '1' ) && t [ i ] == '0' ) u1 . pb ( i );
}
for ( int i = 0 ; i < min ( sz ( u0 ), sz ( u1 )); i ++ ) {
ans ++ ;
swap ( s [ u0 [ i ]], s [ u1 [ i ]]);
}
ans += sz ( u0 ) - min ( sz ( u0 ), sz ( u1 )) + sz ( u1 ) - min ( sz ( u0 ), sz ( u1 ));
cout << ans << endl ;
}
signed main () {
fastio
int tt ;
cin >> tt ;
for ( int t = 1 ; t <= tt ; t ++ ) {
cout << "Case " << t << ": " ;
solve ();
}
return 0 ;
}
[Gold 4] BOJ 25559 - 패스 [+2] 14:57
BOJ 25559
$1$번 사람은 항상 $N$을 패스해야 한다.
왜냐면 다른 사람이 $N$을 쓴다면 자기 자신으로 돌아오게 되고 그럼 그 사람은 그 사람으로 왔을 때의 패스와 자기 자신의 패스에 의해 $2$번 이상 패스를 받는것이 되기 때문이다.
이외에는 짝수라면 항상 가능하다.
$l, r$ 을 관리하며 $l=1,r=N$ 으로 두고 한 칸씩 좁혀가며 계속 패스를 하는 방식으로 하면 된다.
펼치기
void solve () {
int n ;
cin >> n ;
int cur = 0 ;
vi used ( n + 1 );
used [ n ] = 1 ;
vi ans ;
ans . pb ( n );
for ( int i = n - 1 , l = 0 , r = n - 1 ; i >= 1 ; i -- ) {
if ( cur == l ) {
int move = r - l ;
if ( used [ move ]) {
cout << - 1 ;
return ;
}
used [ move ] = 1 ;
ans . pb ( move );
cur = r ;
l ++ ;
} else {
int move = ( l + n - r );
if ( used [ move ]) {
cout << - 1 ;
return ;
}
used [ move ] = 1 ;
ans . pb ( move );
cur = l ;
r -- ;
}
}
for ( int i : ans ) cout << i << ' ' ;
}
[Gold 3] BOJ 20160 - 야쿠르트 아줌마 야쿠르트 주세요 [+2] 12:30
BOJ 20160
다익스트라를 $10$번 돌려서 각 지점에 가장 늦게 도착하는 거리를 모두 기록해둔다음 자신의 시작 위치에서도 다익스트라를 돌려 갈 수 있는 지점 중 가장 작은 번호를 출력하면 된다.
펼치기
const int inf = 2e15 ;
void solve () {
int n , m ;
cin >> n >> m ;
vector < vector < pi >> edges ( n );
for ( int i = 0 , u , v , w ; i < m ; i ++ ) {
cin >> u >> v >> w , u -- , v -- ;
edges [ u ]. pb ({ v , w });
edges [ v ]. pb ({ u , w });
}
vi t ( 10 );
fv ( t );
for ( int & i : t ) i -- ;
int s ;
cin >> s , s -- ;
auto get_dist = [ & ]( int start ) {
vi ret ( n , inf );
ret [ start ] = 0 ;
priority_queue < pi , vector < pi > , greater <>> q ;
q . push ({ 0 , start });
while ( sz ( q )) {
auto [ cur_d , cur ] = q . top ();
q . pop ();
if ( ret [ cur ] < cur_d ) continue ;
for ( auto & [ to , w ] : edges [ cur ]) {
if ( ret [ to ] > ret [ cur ] + w ) {
ret [ to ] = ret [ cur ] + w ;
q . push ({ ret [ to ], to });
}
}
}
return ret ;
};
vi dist_ya ( n , - 1 );
dist_ya [ t [ 0 ]] = 0 ;
int cur_dist = 0 ;
for ( int i = 0 ; i < 10 ;) {
auto d = get_dist ( t [ i ]);
int nxt = - 1 ;
for ( int j = i + 1 ; j < 10 ; j ++ ) {
if ( d [ t [ j ]] == inf ) continue ;
else {
nxt = j ;
break ;
}
}
if ( nxt == - 1 ) break ;
maxa ( dist_ya [ t [ nxt ]], cur_dist + d [ t [ nxt ]]);
cur_dist += d [ t [ nxt ]];
i = nxt ;
}
auto d = get_dist ( s );
int ans = inf ;
for ( int i = 0 ; i < 10 ; i ++ ) {
if ( dist_ya [ t [ i ]] != - 1 && d [ t [ i ]] != inf && d [ t [ i ]] <= dist_ya [ t [ i ]]) {
mina ( ans , t [ i ]);
}
}
if ( ans == inf ) cout << - 1 ;
else cout << ans + 1 ;
}
[Gold 2] BOJ 5625 - 페스트리 [+] 06:04
BOJ 5625
각 삼각형마다 세 개의 점 중 $x,y$ 들이 가장 작은것과 가장 큰것을 미리 파싱한 후 쿼리로 들어오는 좌표에 걸치는 것의 개수를 세면 된다.
누적합 배열 두개(x,y니까 총 4개)를 준비해서 하나는 시작지점, 하나는 끝지점에 1씩 더해놔주자.
$v$ 라는 값이 있을 때 $0 \sim v$ 에 끝지점이 있는 것과 $v \sim \infty$에 시작지점이 있는것의 개수를 각각 $a,b$ 라 한다면 $n-a-b$ 가 정답이다.
펼치기
// region FENWICK
template < class T >
struct fenwick {
int n ;
vector < T > tree ;
fenwick ( int n ) : n ( n ) { tree . resize ( n + 1 ); }
T sum ( int i ) {
T ret = 0 ;
for (; i ; i -= i & - i ) ret += tree [ i ];
return ret ;
}
void update ( int i , T x ) { for ( i ++ ; i <= n ; i += i & - i ) tree [ i ] += x ; }
T query ( int l , int r ) { return l > r ? 0 : sum ( r + 1 ) - sum ( l ); }
};
// endregion
void solve () {
int n ;
cin >> n ;
fenwick < int > X_s ( 1000005 ), X_e ( 1000005 ), Y_s ( 1000005 ), Y_e ( 1000005 );
for ( int i = 0 ; i < n ; i ++ ) {
vector < pi > p ( 3 );
for ( auto & [ x , y ] : p ) cin >> x >> y ;
int mn_x = 2e9 , mx_x = - 2e9 ;
int mn_y = 2e9 , mx_y = - 2e9 ;
for ( auto & [ x , y ] : p ) {
mina ( mn_x , x );
maxa ( mx_x , x );
mina ( mn_y , y );
maxa ( mx_y , y );
}
X_s . update ( mn_x , 1 );
X_e . update ( mx_x , 1 );
Y_s . update ( mn_y , 1 );
Y_e . update ( mx_y , 1 );
}
int q ;
cin >> q ;
while ( q -- ) {
string dir , dd ;
int v ;
cin >> dir >> dd >> v ;
if ( dir == "x" ) {
int left = X_e . query ( 0 , v );
int right = X_s . query ( v , 1000004 );
cout << n - left - right << endl ;
} else {
int left = Y_e . query ( 0 , v );
int right = Y_s . query ( v , 1000004 );
cout << n - left - right << endl ;
}
}
}
[Gold 1] BOJ 10541 - 싸리와 버드의 피라미드 [+1] 23:40
BOJ 10541
수학적인 누적합문제인데 정확한 구현력이 필요했다.
각 알파벳별로 구간합 배열을 모두 만들어두자.
$a=1$ 은 따로 처리하고$a$ 번 째 줄 이전에 $s_0$ 이 가장 마지막으로 나오는 위치를 얻어내자. $O(1)$로 가능하다.
이제 그만큼 prefix가 잘린채로 $a$ 번째 줄에 진입한 후에 뒤에 suffix중 $c$가 나오는 개수를 더해준다.
suffix가 $a$번째 줄을 넘어가는 경우도 잘 처리해주자.
그러면 이제 $a$ 줄에서 남은 개수가 $k$라고 한다면 $\left\lfloor \dfrac{k}{\vert s \vert} \right\rfloor$ 만큼은 모든 단어를 다 포함해주는 것이 된다.
그만큼 $s_0$ 의 위치를 또 이동시킨다음 또 포함되는 prefix 부분에서 $c$의 개수만 더해주면 된다.
int128 로 처리해주도록 하자.
펼치기
void solve () {
int n ;
cin >> n ;
string s ;
cin >> s ;
int m = sz ( s );
// 단어 하나당 몇개씩 있는지
vector < vector < signed >> psum ( 26 , vector < signed > ( m + 1 ));
for ( int i = 0 ; i < m ; i ++ ) {
for ( int j = 0 ; j < 26 ; j ++ ) {
psum [ j ][ i + 1 ] = psum [ j ][ i ] + (( s [ i ] - 'A' ) == j );
}
}
auto qry = [ & ]( int i , int l , int r ) -> int {
if ( l > r ) return 0 ;
return psum [ i ][ r + 1 ] - psum [ i ][ l ];
};
int k ;
cin >> k ;
auto sum = [ & ]( int x ) { return x * ( x + 1 ) / 2 ; };
while ( k -- ) {
string _c ;
int a , c ;
cin >> a >> _c ;
c = _c [ 0 ] - 'A' ;
if ( a == 1 ) {
if ( s [ 0 ] - 'A' == c ) cout << 1 << endl ;
else cout << 0 << endl ;
continue ;
}
int last_first = sum ( a - 1 ) / m * m + 1 ;
if ( last_first == sum ( a - 1 ) + 1 ) last_first -= m ;
assert ( last_first >= 1 );
int ret = 0 ;
int prefix_len = sum ( a - 1 ) - last_first + 1 ;
int remain_len = m - prefix_len ;
if ( remain_len > a ) {
int cut = remain_len - a ;
cout << qry ( c , prefix_len , m - 1 - cut ) << endl ;
continue ;
}
ret = qry ( c , prefix_len , m - 1 );
last_first += m ;
int remain_in_row = sum ( a ) - last_first + 1 ;
int q = remain_in_row / m ;
ret += qry ( c , 0 , m - 1 ) * q ;
last_first += q * m ;
prefix_len = sum ( a ) - last_first + 1 ;
if ( prefix_len >= 1 ) {
ret += qry ( c , 0 , prefix_len - 1 );
}
cout << ret << endl ;
}
}
[Platinum 5] BOJ 20158 - 사장님 달려가고 있습니다 [+] 09:35
BOJ 20158
정답비율이 굉장히 낮은 까다로운 BFS였는데 운좋게 한 번에 맞았다.
$D[i][j][k]$ 를 $(i, j)$ 에 마지막으로 이동한 방향이 $k$ 일 때 최단거리라고 하자.
그럼 4방향을 모두 보며 $k$가 아닌 방향으로만 쭉 나아가면서 간단히 조건을 검사하면 된다.
펼치기
const int dy [] = { - 1 , 0 , 1 , 0 }, dx [] = { 0 , 1 , 0 , - 1 }, op [] = { 2 , 3 , 0 , 1 };
int dist [ 101 ][ 101 ][ 5 ];
const int inf = 0x3f3f3f3f ;
void solve () {
int n ;
cin >> n ;
vvi b ( n , vi ( n ));
fv2 ( b );
memset ( dist , inf , sizeof dist );
queue < array < int , 3 >> q ;
q . push ({ 0 , 0 , 4 });
dist [ 0 ][ 0 ][ 4 ] = 0 ;
auto in = [ & ]( int y , int x ) {
return y >= 0 && y < n && x >= 0 && x < n ;
};
while ( sz ( q )) {
auto [ y , x , no ] = q . front ();
int cur_d = dist [ y ][ x ][ no ];
q . pop ();
for ( int d = 0 ; d < 4 ; d ++ ) {
if ( d == no ) continue ;
int speed = 1 ;
int dt = 1 ;
for ( int k = 1 , nxt = 1 ;; k ++ ) {
int ny = y + dy [ d ] * k ;
int nx = x + dx [ d ] * k ;
if ( ! in ( ny , nx )) break ;
if ( b [ ny ][ nx ]) {
if ( cur_d + ( dt - ( k != nxt )) >= b [ ny ][ nx ]) {
break ;
}
}
if ( k == nxt ) {
if ( dist [ ny ][ nx ][ d ] > cur_d + dt ) {
dist [ ny ][ nx ][ d ] = cur_d + dt ;
q . push ({ ny , nx , d });
}
speed ++ ;
nxt += speed ;
dt ++ ;
}
}
}
}
if ( n == 1 ) {
cout << 0 ;
return ;
}
int ans = inf ;
for ( int i = 0 ; i < 4 ; i ++ ) {
mina ( ans , dist [ n - 1 ][ n - 1 ][ i ]);
}
if ( ans == inf ) cout << "Fired" ;
else cout << ans ;
}
Comments