Educational Codeforces Round 43 (Div.2)

ABC---でこどふぉ初3完です. うれしいね.

A - Minimum Binary Number

1ケタの場合はそのまま出力.
2ケタ以上の場合, '1'はすべて左に寄せて消せば1個になる. 最終的には "1000" のように
最上位ケタに'1'が1つ, 残りは'0'となる.
よって入力の'0'の数を数えて, '1'を出力した後に数えた分'0'を出力すればよい.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n;
  cin >> n;
  string s;
  cin >> s;

  if(n == 1 && s[0] == '0') {
    cout << "0" << endl;
    return 0;
  }

  long long count1 = 0, count0 = 0;
  for(int i = 0; i < n; i++) {
    if(s[i] == '1') {
      count1++;
    }
    else {
      count0++;
    }
  }
  string ans;
  ans.push_back('1');
  for(int i = 0; i < count0; i++) {
    ans.push_back('0');
  }
  cout << ans << endl;
}

B - Lara Croft and the New Game

(1, 1)から(n, 1)に降りたあと残りを蛇行しながら上に昇る.
移動コマ数kがnより小さければ最終地点は(k + 1, 1).
そうでない場合, 蛇行した分を計算する.
昇った行数はk / (m - 1)行となる. 残りの歩数は最終地点にたどり着くまでに昇った行数が奇数なら右から, 偶数なら左から数える.
コンテスト中はなぜか一番下の行を特別扱いしていたけど, そうする必要はない. editorialは一番下の行を特別扱いしていない.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n, m, k;
  cin >> n >> m >> k;

  if(k <= n - 1) {
    cout << k + 1 << " 1" << endl;
    return 0;
  }
  k -= n - 1;
  if(k <= m - 1) {
    cout << n << " " << k + 1 << endl;
    return 0;
  }
  k -= m - 1;
  long long r = k / (m - 1);
  long long c = k % (m - 1);

  if(c == 0) {
    if(r % 2 == 0) {
      cout << n - r << " " << m << endl;
    }
    else {
      cout << n - r << " " << "2" << endl;
    }
  }
  else {
    if(r % 2 == 0) {
      cout << n - r - 1 << " " << m - c + 1 << endl;
    }
    else {
      cout << n - r - 1 << " " << 2 + c - 1 << endl;
    }
  }
}

C - Nested Segments

各[li, ri]に対してtuple配列を作って(li, ri, i)で保存する.
このtuple配列をsortすると第1要素lの昇順に並ぶ.
この配列の隣り合った2つの要素であるj番目とj+1番目を比較する.
このとき考えられるのは
(lj < l(j+1), lj == l(j+1)) * (rj < r(j+1), rj == r(j+1), rj > r(j+1))の6通り.
lj < l(j+1) かつ rj < r(j+1)の場合はjをインクリメントして次の比較をする.
そうでない場合はどちらかがもう片方を包含?(lie within)しているので答えとして出力. 答えにはtupleの3番目の要素を使う.
包含関係が1つでもあればそれを出力すればいいので全部調べなくてもよい. 隣り合っていない要素(例:j番目とj+k番目)の包含関係は見逃すけどその場合は別の包含関係(j+1番目とj+k番目とか)が成り立つので問題ない.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  long long n;
  cin >> n;
  vector <tuple <long long, long long, long long>> lr;
  for(int i = 0; i < n; i++) {
    long long x, y;
    cin >> x >> y;
    lr.push_back(tuple <long long, long long, long long> (x, y, i + 1));
  }

  //  cout << "-------------------" << endl;
  sort(lr.begin(), lr.end());
  //  for(int i = 0; i < n; i++) {
  //    cout << get<0>(lr[i]) << " " << get<1>(lr[i]) << " " << get<2>(lr[i]) << endl;
  //  }

  for(int i = 0; i < n - 1; i++) {
    if(get<0>(lr[i]) == get<0>(lr[i + 1])) {
      if(get<1>(lr[i]) <= get<1>(lr[i + 1])) {
	cout << get<2>(lr[i]) << " " << get<2>(lr[i + 1]) << endl;
      }
      else {
	cout << get<2>(lr[i + 1]) << " " << get<2>(lr[i]) << endl;
      }
      return 0;
    }
    else {
      if(get<1>(lr[i]) >= get<1>(lr[i + 1])) {
	cout << get<2>(lr[i + 1]) << " " << get<2>(lr[i]) << endl;
	return 0;
      }
    }
  }

  cout << "-1 -1" << endl;
}

Dはまた今度.