読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

Codeforces Round #345 (Div.2)

ダメ。 1707->1661(-46)。

A. Joysticks

問題概要

2 つのジョイスティックと 1 つの充電器がある. それぞれのジョイスティックは充電器に接続されているとき, 1 分ごとに 1 % 充電され, 接続されていないとき, 1 分ごとに 2 % 放電する. 今, 2 つのジョイスティックは  {a_1} %,  {a_2} % 充電されている. 充電器は, 各分の開始時に差し替えることができる. 両方のジィスティックが 1 %以上となる最大の時間を求めよ.

解法

なんか普通に書いたら pretest で落ちたのでよく分からない.
あまりにも分からないので DP を書いたらまた落ちた.
どうも,  {a_1} = 1 %,  {a_2} = 1 % のときがコーナーケースらしい.このとき 1 ターンも行われずに終了する.
これだけ考慮していれば, 各分で貪欲に充電が小さい方を用いれば最大となる. 1 時間を溶かす.

ソース

#include<bits/stdc++.h>
using namespace std;

int v[300][300];
int rec(int x, int y)
{
  if(x <= 0 || y <= 0) return(0);
  if(~v[x][y]) return(v[x][y]);
  return(v[x][y] = max(rec(x + 1, y - 2), rec(x - 2, y + 1)) + 1);
}

int main()
{
  int X, Y;
  cin >> X >> Y;
  memset(v, -1, sizeof(v));
  if(X == 1 && Y == 1) cout << 0 << endl;
  else cout << rec(X, Y) << endl;
}

B. Beautiful Paintings

問題概要

数列 a がある. 任意の順に並べ替えて,  a_i \lt a_{i+1} が現れる数を最大化せよ.

解法

よくありそうな問題. 基本的には昇順が良いのは自明.
但し昇順にして,  a_i = a_{i+1} となるものは, 使っても意味がないので後で使う.

ソース

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int N, A[1000];
  cin >> N;
  multiset< int > vv;
  for(int i = 0; i < N; i++) {
    int K;
    cin >> K;
    vv.insert(K);
  }
  int ret = 0, now = *vv.begin();
  vv.erase(vv.begin());
  while(!vv.empty()) {
    bool f = false;
    for(auto v : vv) {
      if(now < v) {
        now = v;
        vv.erase(vv.find(v));
        ++ret;
        f = true;
        break;
      }
    }
    if(!f) {
      now = *vv.begin();
      vv.erase(vv.begin());
    }
  }
  cout << ret << endl;
}

C. Watchmen

問題概要

二次元平面上に, N 個の整数座標の点がある. 但し, 点の位置は重複することがある. マンハッタン距離とユークリッド距離が等しくなるような点の組み合わせの個数を求めよ.

解法

x 軸か y 軸どちらかが同じであれば, マンハッタン距離とユークリッド距離は等しくなり, 逆にそれ以外は等しくならない.
なので, 軸別に現れた回数を数える.
重複する点があるので, その個数も数えておいて, あとから引く.

ソース

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int N;
  cin >> N;
  map< int, long long > row, col;
  map< pair< int, int >, long long > sss;
  for(int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    row[x]++;
    col[y]++;
    sss[{x, y}]++;
  }
  long long ret = 0;
  for(auto v : row) {
    ret += 1LL * v.second * (v.second - 1) / 2;
  }
  for(auto v: col) {
    ret += 1LL * v.second * (v.second - 1) / 2;
  }
  for(auto v: sss) {
    ret -= 1LL * v.second * (v.second - 1) / 2;
  }
  cout << ret << endl;
}

D. Image Preview

問題概要

スマホの中に写真が N(1 ≦ N ≦ 5 × 10^5) 枚ある. 1 番目の写真が現在表示されている.
a 秒かけて, 左フリップか右フリップをすることができる. フリップすると隣接した写真が表示される(但し 1 枚目の左隣は N 枚目, N 枚目の右隣は 1 枚目とする).
初めて表示される写真なら必ず, 1 秒かけて見る. 二度目以降は見ずにスキップ出来る.
また, それぞれの写真は, 縦向きか横向きである. 横向きの写真は見る前に b 秒かけて, 写真を回転しなければならない(二度目以降は不要).
T 秒の間に見れる写真の最大数を求めよ.

解法

ちょっと問題を整理. 1) 縦向きの写真は 1 秒, 横向きの写真は (b + 1) 秒かかる.
2) 左右に何度も往復することは無駄. 最大で 1 回.
3) 2) より, フリップする順番は, ←のみ(以降←), →のみ(以降→), ←をやって→(以降←→), →をやって←(以降→←)

←, ←→はなんか尺取りできそう. まずできる限り←. そして, 1 個ずつ → の回数を増やしていくことを考える. → を 1 個増やせば, ← の回数はちょっと減る(これは広義単調減少). よってやっぱり尺取りできる. →, →←も同じっぽいけど, 実装が面倒. 写真の左右を入れ替えることで ←, ←→と同様の問題となる.

円環や尺取りが闇で無限にバグって, 5 WA してた. 結局, pretest 残り 2 分位で通って熱かったけど, これが TLE で落ちてダメ. if(ret >= N) return(N); をどうせいつか終わるだろうと, while 抜けてからやってた. T ≦ 10^9 だからダメだよね. もうちょっと詰めをしっかりやります.

ソース

#include<bits/stdc++.h>
using namespace std;
#define int long long

int N, A, B, T;
string S;

long long Solve()
{
  int Cost[500000] = {};
  for(int i = 0; i < S.size(); i++) {
    if(S[i] == 'w') Cost[i] = B + 1;
    else Cost[i] = 1;
  }

  if(T - Cost[0] < 0) {
    return(0);
  }
  T -= Cost[0];

  int RightIdx = 0, ret = 1;
#define Prev(k) (k - 1 + S.size()) % S.size()
#define Next(k) (k + 1) % S.size()

  int best = ret;
  while(T - A - Cost[Prev(RightIdx)] >= 0) {
    RightIdx = Prev(RightIdx);
    T -= A + Cost[RightIdx];
    ++ret;
    if(ret >= N) return(N);
  }

  best = max(best, ret);

  for(int i = 1; i < N; i++) {
    while(RightIdx != 0 && T - Cost[i] - (N - RightIdx + 1) * A < 0) {
      T += A + Cost[RightIdx];
      RightIdx = Next(RightIdx);
      --ret;
    }
    if(T - Cost[i] - (N - RightIdx + 1) * A < 0) break;
    T -= A;
    T -= Cost[i];
    ++ret;
    best = max(best, ret);
  }
  return(best);
}

signed main()
{
  cin >> N >> A >> B >> T;
  int Buffer = T;
  cin >> S;
  int res = Solve();
  T = Buffer;
  reverse(S.begin() + 1, S.end());
  cout << max(res, Solve()) << endl;
}