ei1333の日記

ぺこい

Codeforces Round #342 (Div. 2)

Codeforces

A, B, C を解いて3完. 個人的に難易度は B < C < A だと思う.
403位で 1685 -> 1709(+24). 解くのが遅いつらい.

A. Guest From the Past

問題概要

n ヌーブル所持している． それぞれ 1 個あたり, a ルーブルのボトルと b ルーブルのボトルがある.
b ルーブルのボトルは 店に返すことができて，そのとき c ルーブル戻ってくる．
買えるボトルの数の最大値を求めよ．

解法

怖い問題．A は全体で 589 人で, B は 1752 人で, C は 1805 人によって解かれたというデータもある．
それぞれの制約が 10^18 なので, O(1) か O(log N) くらいで解きたい感じになる．

まず最初に a をなるべく買うか, b をなるべく買うかどちらかになりそう.
でその後, 一方をなるべく買うような感じになりそう.
a をなるべく買うときは, floor( (今の金額) / a ) で求まる.
b をなるべく買うときは, 頭が悪くてよく分かんなかったので二分探索で求めた(立式はしたけどなぜかやめた. 買う個数を決めておいて, 最終的に c ルーブル以上残っていればそれは買えると判断できる(キャッシュバック1回分未満なら買った時に負になっているはず.

これを実装すれば, 多分通る(通った.

ソース

3WA して適当なのであんまり参考にならなさそう. 適当にやっていて64bitじゃオーバーフローするので多倍長. 多倍長ライブラリは省略.

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int64 N, A, B, C;
bigint getCost(int64 cost)
{
  bigint hoge = N;
  bigint b = B, c = C, d = C;
  bigint Cost = cost;
  b *= Cost;
  c *= Cost;
  hoge -= b;
  hoge += c;
  return(hoge);
}

int main()
{
  cin >> N >> A >> B >> C;
  int64 low = 0, high = 1LL << 60;

  while(high - low > 0) {
    int64 mid = (low + high + 1) / 2;
    if(getCost(mid) >= C) low = mid;
    else high = mid - 1;
  }
  int64 ret = 0;
  ret = max(ret, low + getCost(low) / A);

  int64 buff = N / A;
  N %= A;
  low = 0, high = 1LL << 60;
  while(high - low > 0) {
    int64 mid = (low + high + 1) / 2;
    if(getCost(mid) >= C) low = mid;
    else high = mid - 1;
  }
  ret = max(ret, buff + low);

  cout << ret << endl;
}

B. War of the Corporations

問題概要

文字列SとTがある. Sの一部の文字を#に置換してSの部分文字列にTが含まないようにしたい. 置換する文字の最小の個数求めよ.

解法

|T|<30 と小さいので何やっても間に合いそう. Grundyに文字列 S を左から見ていって、文字列 T が見つかったら最後尾を#にしていく(同じ文字列を隠すなら右を隠したほうが次に生きる).

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int lcp[100002][32];

int main()
{
  string S, W;
  cin >> S;
  cin >> W;
  for(int i = S.size() - 1; i >= 0; i--) {
    for(int j = W.size() - 1; j >= 0; j--) {
      lcp[i][j] = S[i] == W[j] ? lcp[i + 1][j + 1] + 1 : 0;
    }
  }
  int ret = 0;
  for(int i = 0; i < S.size(); i++) {
    if(lcp[i][0] != W.size()) continue;
    ++ret;
    i += W.size() - 1;
  }
  cout << ret << endl;
}

C. K-special Tables

問題概要

N×Nのマスそれぞれに1からN^2までの数が一つずつ書かれるようにする. また,各行は単調増加である必要がある. K 列目の和を最大化するとき, その和とその時の数字の割り振り方を答えよ.

解法

サンプル眺めてるとわかりそう.

  • 1 列目から K - 1 列目までのマスには左上から順に 1 から数字を入れる(小さい数字はなるべく早く使いたいので)
  • K 列目から N 列目までのマスには右下から左向きに順に N^2 から数字を入れる(大きい数字はなるべく残しておきたいので)

これで特に反例なさそうなので, これを提出.

ソース

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

int mas[500][500], mas2[500][500];
int N, K;
int main()
{
  cin >> N >> K;
  --K;

  int ptr = N * N;
  for(int i = 0; i < N; i++) {
    for(int j = N - 1; j >= K; j--) {
      mas[i][j] = ptr--; 
    }
  }
  for(int i = 0; i < N; i++) {
    for(int j = K - 1; j >= 0; j--) {
      mas[i][j] = ptr--;
    }
  }

  long long sum = 0;
  for(int i = 0; i < N; i++) {
    sum += mas[i][K];
  }
  cout << sum << endl;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      if(j > 0) cout << " ";
      cout << mas[i][j];
    }
    cout << endl;
  }
}

D は桁DPしそうわからないおわり. という感じだった.