AtCoder ARC091 参加記録

AtCoder 競技プログラミング

考えたことメモ

Flip,Flip, and Flip......

C - Flip,Flip, and Flip......

自分自身を含め周りのますの個数回だけ裏返される。

一番外側のますは偶数回、真ん中のマスは奇数回裏返されるから真ん中のマスの個数答えればOK。

真ん中のマスの数は(行数-2)*(列数-2)。

ただ、列か行が1の時はマスの数-2が答え。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, M; cin >> N >> M;
  if(N == 1 && M == 1) cout << 1 << endl;
  else if(N == 1 || M == 1) cout << max(N, M) - 2 << endl;
  else cout << N * M - 2 * (N + M) + 4 << endl;
}

Remainder Reminder

D - Remainder Reminder

aとbを愚直に全探索じゃあO(N2)で間に合わないので、どっちがだけ1~Nまで探索するんだろうな〜という気持ち。

ずっとaを1〜Nまで変えていった時のbの個数をO(1)で求められないか考えてたけど、bを1~Nまで探索した方が楽だね...。

解説みた。

b=b'で割った時のあまりは0,1,2,...b'-1,0,1,2,...,b'-1,0,1,2...と繰り返される。

この繰り返しの中でK以上となる個数 => b=b'の時のaの個数。

繰り返しがどこまで続くか。

aの最大値はN。

N = pb'+rとすると、繰り返しは0,1,2,...b'-1,0,1,2,...,b'-1,0,1,2...rとなる。0,1,2,...b'-1がp個。

よってb=b'の時、K以上となる個数はp*max(0, b'-K)+r-K+1。（K==0の時a==0が含まれてしまうので-1する）

上記の式を用いてb=1~Nまでの和を求めれば良い。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  ll ans = 0;
  FOR(b,1,N+1) {
    int p = N / b;
    int r = N % b;
    ans += p * max(0, b - K) + max(0, r - K + 1);
    if(K == 0) ans--;
  }
  cout << ans << endl;
}

LISDL

E - LISDL

ケアレスミスでAC逃した。ただコンテスト終了後だけど自分で700解けたので嬉しかった。

1234567の時A=3だとすると3つの領域に分ける。 123|45|67。

領域の中を全て逆にするとA=3となる。 321|54|76。

それぞれの領域の中の数の個数の最大値がBとなる。

あり得る最大値の範囲がBの範囲。

その範囲にBが入っていなければ-1を出力。

範囲は12345|6|7のように1つだけ多くした時がBの数の最大値。 123|45|67のようにできるだけ均等に分けた時がBの最小値である。

stack<ll> tmp;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, A, B; cin >> N >> A >> B;
  if(B < (N + A - 1) / A || B > N - (A - 1)) {
    cout << -1 << endl;
    return 0;
  }
  if(A == N && B == 1) {
    FOR(i, 0, N) cout << i + 1 << " ";
  } else if(A == 1 && B == N) {
    FOR(i, 0, N) cout << N - i << " ";
  } else {
    for(int b = B; b > 0; b--) cout << b << " ";
    int cntMax = (N - B) / (A - 1);
    int cnt = 0;
    int up = (N - B) % (A - 1); /// up個は+1
    FOR(b,B+1,N+1) {
      tmp.push(b);
      cnt++;
      if(cnt == cntMax + (up > 0 ? 1 : 0)) {
        while(!tmp.empty()) {
          cout << tmp.top() << " ";
          tmp.pop();
        }
        cnt = 0;
        up--;
      }
    }
  }
  cout << endl;
  return 0;
}

レート気にせず問題解くの楽しもう（）