h_nosonの日記

競プロなど

Codeforces Round #350 (Div. 2) B. Game of Robots

問題
Problem - B - Codeforces
ロボットがN体いる.それぞれのロボットに番号が付けられている.
左のロボットから順番に,「ロボットの番号を一番左のロボットの番号から自分の番号まで言う」ことを行うとき,K回目に言われるロボットの番号は幾つか.

制約
1\leq N\leq 100000,1\leq K \leq\min(2\cdot10^9,N\cdot (N+1)/2)

解法
左のロボットから呼ぶ回数が1,2,3,...,N回なのでKから順番に引いていき,Kが0を下回る直前で止める.K(引いた後のK)番目のロボットが呼ばれるロボットになる.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int main() {
    int i, n, k, cnt;
    int id[100000];
    cin >> n >> k;
    rep (i,n) cin >> id[i];
    k--;
    cnt = 0;
    for (i = 0; i < n; i++) {
        cnt += i;
        if (cnt + i + 1 > k)
            break;
    }
    cout << id[k - cnt] << endl;
    return 0;
}