atcoder.jp
$ a[a[a[0]]] $ が答え
提出コード
void solve(){
vector<int> a(10);
REP(i,10) cin >> a[i];
cout << a[a[a[0]]] << endl;
}
mapなどで長さごとに残りの個数を管理しておき、条件を満たすことができるかを判定する
提出コード
void solve(){
int N, M;
cin >> N >> M;
vector<int> A(N), B(M);
map<int, int> mp;
REP(i,N){
cin >> A[i];
mp[A[i]]++;
}
REP(i,M) cin >> B[i];
bool ok = true;
REP(i,M){
if(mp[B[i]] > 0){
mp[B[i]]--;
}
else ok = false;
}
cout << (ok ? "Yes" : "No") << endl;
}
各マスから下、右、左下、右下の四方向に対しそれぞれ連続した6マスの中に黒マスが4つ以上あれば条件を満たすことができる
提出コード
void solve(){
int N;
cin >> N;
vector<string> S(N);
REP(i,N) cin >> S[i];
bool ok = false;
REP(i,N) REP(j,N){
int dx[4] = {1, 0, 1, -1};
int dy[4] = {0, 1, 1, 1};
REP(d,4){
int black = 0, white = 0;
REP(k,6){
int nh = i + dx[d] * k;
int nw = j + dy[d] * k;
if(nh < 0 or nh >= N or nw < 0 or nw >= N) break;
if(S[nh][nw] == '#') black++;
else white++;
}
if((black == 6) or (black == 5 and white == 1) or (black == 4 and white == 2)){
ok = true;
}
}
}
cout << (ok ? "Yes" : "No") << endl;
}
multisetで値を管理しながら愚直に求めればいい
提出コード
void solve(){
int Q;
cin >> Q;
multiset<ll> mst;
mst.insert(-1);
mst.insert(2*LINF);
while(Q--){
int q;
cin >> q;
if(q == 1){
ll x;
cin >> x;
mst.insert(x);
}
else if(q == 2){
ll x, k;
cin >> x >> k;
auto itr = mst.upper_bound(x);
--k;
if(*itr == 2*LINF or *itr > x) itr--;
bool ok = true;
while(k--){
if(*itr == -1){
ok = false;
break;
}
itr--;
}
cout << (ok ? *itr : -1) << endl;
}
else if(q == 3){
ll x, k;
cin >> x >> k;
--k;
auto itr = mst.lower_bound(x);
bool ok = true;
if(*itr == 2*LINF){
ok = false;
k = 0;
}
while(k--){
itr++;
if(*itr == 2*LINF){
ok = false;
break;
}
}
cout << (ok ? *itr : -1) << endl;
}
}
}
周期性があるのでダブリングなどで求めることができる
提出コード
void solve(){
ll N, K;
cin >> N >> K;
vector<ll> A(N);
REP(i,N) cin >> A[i];
vector val(40, vector<ll>(N, 0));
vector to(40, vector<ll>(N, 0));
REP(i,N){
val[0][i] = A[i];
to[0][i] = (i + A[i]) % N;
}
REP(i,40-1) REP(j,N){
to[i+1][j] = to[i][to[i][j]];
val[i+1][j] = val[i][j] + val[i][to[i][j]];
}
ll ans = 0;
ll cur = 0, tmp = 0;
REP(i,40){
if(K >> i & 1){
ans += val[i][cur];
cur = to[i][cur];
}
}
cout << ans << endl;
}
辿り着けるマスは障害物のあるマスの上下左右の4つのみなのでBFSなどで求めることができる
辿り着けるマスの候補をx, y座標それぞれについて座圧し、その個数分setなどで障害物のあるマスを管理する
今いるマスから次のマスへは二分探索で求めることができる
提出コード
void solve(){
int H, W, N;
cin >> H >> W >> N;
int sh, sw, gh, gw;
cin >> sh >> sw >> gh >> gw;
Compress<int> cmp;
cmp.add(0);
cmp.add(INF);
vector<int> X(N), Y(N);
REP(i,N){
cin >> X[i] >> Y[i];
cmp.add(X[i]);
cmp.add(X[i]-1);
cmp.add(X[i]+1);
cmp.add(Y[i]);
cmp.add(Y[i]-1);
cmp.add(Y[i]+1);
}
cmp.build();
int sz = cmp.size();
vector<set<int>> st_x(sz+10), st_y(sz+10);
st_x[cmp.get(sh)].insert(0);
st_x[cmp.get(gh)].insert(W+1);
st_y[cmp.get(sw)].insert(0);
st_y[cmp.get(gw)].insert(H+1);
REP(i,sz){
st_x[i].insert(0);
st_x[i].insert(W+1);
st_y[i].insert(0);
st_y[i].insert(H+1);
}
REP(i,N){
st_x[cmp.get(X[i])].insert(Y[i]);
st_y[cmp.get(Y[i])].insert(X[i]);
}
queue<pair<int, int>> q;
map<pair<int, int>, int> mp;
q.emplace(sh, sw);
mp[{sh, sw}] = 0;
while(!q.empty()){
auto [h, w] = q.front(); q.pop();
{
auto itr = st_y[cmp.get(w)].lower_bound(h);
--itr;
int nh = *itr;
if(nh == 0){}
else{
nh++;
if(!mp.count({nh, w})){
q.emplace(nh, w);
mp[{nh, w}] = mp[{h, w}] + 1;
}
}
}
{
auto itr = st_y[cmp.get(w)].lower_bound(h);
if(*itr != h) itr--;
itr++;
int nh = *itr;
if(nh == H + 1){}
else{
nh--;
if(!mp.count({nh, w})){
q.emplace(nh, w);
mp[{nh, w}] = mp[{h, w}] + 1;
}
}
}
{
auto itr = st_x[cmp.get(h)].lower_bound(w);
itr--;
int nw = *itr;
if(nw == 0){}
else{
nw++;
if(!mp.count({h, nw})){
q.emplace(h, nw);
mp[{h, nw}] = mp[{h, w}] + 1;
}
}
}
{
auto itr = st_x[cmp.get(h)].lower_bound(w);
if(*itr != w) itr--;
itr++;
int nw = *itr;
if(nw == W + 1){}
else{
nw--;
if(!mp.count({h, nw})){
q.emplace(h, nw);
mp[{h, nw}] = mp[{h, w}] + 1;
}
}
}
}
cout << (mp[{gh, gw}] ? mp[{gh, gw}] : -1) << endl;
}
