kmjp's blog

競技プログラミング参加記です

UnKoder #04 : Islands in Circle

UnKoder#04は本番参加していないので後日の練習のみです。
https://www.hackerrank.com/contests/unkoder-04/challenges/islands-in-circle

問題

N個の島が円形に並んでいる。
ある島から初めて、隣の島に移動するという処理をK回繰り返した場合、最終的にいる可能性のある島は何個あるか。

解法

今の番号を0~(N-1)とし、初期位置を0とする。
Kが奇数なら、-K, -K+2, -K+4, .., -1, 1, .. K (mod N)で止まる。
Kが偶数なら、-K, -K+2, -K+4, .., -2, 0, 2, .. K (mod N)で止まる。

このことを踏まえ、以下N,Kの偶奇で場合分けできる。

  • Nが奇数の場合
    • Kが奇数なら、-K~Kの計2*floor((K+1)/2)箇所に止まれる。
    • Kが偶数なら、-K~Kの計1+2*floor(K/2)箇所に止まれる。
    • ただし、上記値がNを超えても上限はN。
  • Nが偶数の場合
    • 基本的な考え方は奇数の場合と同じ。
    • ただ、最終的に止まれる場所の偶奇はKの偶奇と一致するので、上限がN/2。
ll N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>K;
	if(N%2==1) {
		cout<<min(N,(K%2==0)+2*((K+1)/2))<<endl;
	}
	else {
		cout<<min(N/2,(K%2==0)+2*((K+1)/2))<<endl;
	}
	
}

まとめ

偶奇で混乱するけど、落ち着けば簡単に書ける。