ABCDを出して通って4完.
36位.1800 -> 1924(+124). なんか知らないうちに紫になって Div1になってた面白い.
A. Nicholas and Permutation
問題概要
1 から までの数字が 1 つずつ書かれた数列
がある.
任意の 2 つの要素を選んで数を交換するとき, 最大値() と最小値(1) の要素位置の距離の最大値を求めよ.
解法
全通り試せる. .
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector< int > a(N); for(int i = 0; i < N; ++i) { cin >> a[i]; } int ret = 0; for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { swap(a[i], a[j]); int p = max_element(begin(a), end(a)) - begin(a); int q = min_element(begin(a), end(a)) - begin(a); ret = max(ret, abs(p - q)); swap(a[i], a[j]); } } cout << ret << endl; }
B. Pyramid of Glasses
問題概要
ピラミッド形にグラスが 段並んでいる.
上からグラス 杯分のシャンパンを注ぐ. あふれる分は左右均等に落ちて, 下のグラスに入る.
満杯のグラスの個数を求めよ.
解法
愚直にシミュレーション.
ただ実数演算が入るので誤差が怖いけど通った. . 2 倍して誤差をなくしたほうが頭が良いらしい(それはそう.
ソース
#include<bits/stdc++.h> using namespace std; int N, T; long double ptr[100][100] = {{}}; int main() { cin >> N >> T; ptr[0][0] = T; for(int i = 0; i < N; i++) { for(int j = 0; j <= i; j++) { ptr[i + 1][j] += max((long double)0.0, (ptr[i][j] - 1.0) / 2.0); ptr[i + 1][j + 1] += max((long double)0.0f, (ptr[i][j] - 1.0) / 2.0); } } int ret = 0; for(int i = 0; i < N; i++) { for(int j = 0; j <= i; j++) { if(ptr[i][j] >= 1.0) ++ret; } } cout << ret << endl; }
C. Vasya and String
問題概要
'a' と 'b' の文字からなる長さ の文字列が与えられる.
この中から 個までの文字を選んで文字を変えることができる.
同じ文字からなる連続した部分文字列の長さの最大値を求めよ.
解法
見た感じ尺取り.
例えば 'a' の部分文字列の長さの最大を求めることを考える('b'も同様).
まず, 任意の部分文字列を取り出すとして, その中の 'b' の個数が 個以下であれば 'a' だけに出来ることが分かる.
よって, 部分文字列の最後尾を決めると, その最適な先頭位置は
個以下を満たすうち最小要素位置となる.
普通にやると だが, 部分文字列の最後尾の位置を 1 番目から順に試すとすると, 最適な先頭位置も広義単調増加なので尺取りできる. これで
.
ソース
#include<bits/stdc++.h> using namespace std; int N, K; string S; int cmp(char c) { int ret = 1; int tail = 0, count = 0; for(int i = 0; i < N; i++) { if(S[i] != c) ++count; while(tail < N && count > K) { if(S[tail] != c) --count; ++tail; } ret = max(ret, i - tail + 1); } return(ret); } int main() { cin >> N >> K; cin >> S; cout << max(cmp('a'), cmp('b')) << endl; }
D. Theseus and labyrinth
問題概要
大きさ のブロックからなる
の長方形フィールドがある.
1ステップにつき, すべてのブロックをそれぞれ 90 度回転させる, または隣接マスへ移動することができる.
ただし, A → B に移動するとき, A から B 方向のドア と B から A 方向のドアが共に存在している必要がある.
から
への最小移動回数を求めよ.
解法
BFSする. 状態数は, ブロックの回転角度が 4 通り(0, 90, 180, 270), マスが 通りなので状態数は 高々
. 間に合いそう.
移動できるかの判定が面倒で実装が重くなりがちだけど頑張るしかなさそう....
ドアの数で分けると周期的になる((今の角度+1)%x でドアの具合が求まる)のでそうすると楽.
ソース
#include<bits/stdc++.h> using namespace std; const string tmp[5] = {"+", "-|", "^>v<", "URDL", "*"}; const bool hogei[4][5][5] = { {{1}, {0, 1}, {1, 0, 0, 0}, {0, 1, 1, 1}, {0}}, {{1}, {1, 0}, {0, 1, 0, 0}, {1, 0, 1, 1}, {0}}, {{1}, {0, 1}, {0, 0, 1, 0}, {1, 1, 0, 1}, {0}}, {{1}, {1, 0}, {0, 0, 0, 1}, {1, 1, 1, 0}, {0}} }; const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}; int W, H; string S[1000]; int sx, sy, tx, ty; bool v[1000][1000][4]; bool out(int x, int y) { return (x < 0 || y < 0 || x >= W || y >= H); } bool canMove(int x, int y, int move, int nowdir) { for(int i = 0; i < 5; i++) { for(int j = 0; j < tmp[i].size(); j++) { if(tmp[i][j] == S[y][x]) { return(hogei[move][i][(j + nowdir) % tmp[i].size()]); } } } } int bfs() { queue < tuple < int, int, int, int > > que; que.emplace(0, sx, sy, 0); v[sx][sy][0] = true; while(!que.empty()) { int cost, x, y, dir; tie(cost, x, y, dir) = que.front(); que.pop(); if(x == tx && y == ty) return (cost); for(int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(out(nx, ny)) continue; if(!canMove(x, y, i, dir)) continue; if(!canMove(nx, ny, (i + 2) % 4, dir)) continue; if(v[nx][ny][dir]++) continue; que.emplace(cost + 1, nx, ny, dir); } if(v[x][y][(dir + 1) % 4]++) continue; que.emplace(cost + 1, x, y, (dir + 1) % 4); } return (-1); } int main() { cin >> H >> W; for(int i = 0; i < H; ++i) { cin >> S[i]; } cin >> sy >> sx; cin >> ty >> tx; --sx, --sy; --tx, --ty; cout << bfs() << endl; }
