Codeforces Round #374 (Div. 2)

ABCDを解いた.

A. One-dimensional Japanese Crossword

問題概要

個のマスからなる列があって, それぞれ白か黒で塗られている.

連続する黒マスの個数を出力せよ.

解法

一次元のお絵かきロジックである.

ルール通りに, 左から 'B' が連続している個数を数えてそれをそれぞれ出力すれば良い. .

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  string S;

  cin >> N;
  cin >> S;

  int ret = 0;
  vector< int > ans;
  for(char& s : S) {
    if(s == 'B') {
      ++ret;
    } else if(ret > 0) {
      ans.push_back(ret);
      ret = 0;
    }
  }
  if(ret > 0) {
    ans.push_back(ret);
  }

  cout << ans.size() << endl;
  for(int& val : ans) cout << val << " ";
}

B. Passwords

問題概要

個のパスワードの候補となる文字列と, 正しいパスワードを示す文字列が与えられる.

パスワードを忘れてしまったので, 個のパスワードを総当りする. パスワードの文字列長が小さい順に試し, 同じ文字列長のパスワードは順不同である.

個のパスワードを試すのに 秒かかる. 回連続して間違えると 秒間は操作できない.

正しいパスワードを入力するまでの最小値と最大値を求めよ.

解法

ちょっとReadingが難しい...

最小値となる場合は, (正しいパスワードの長さ未満の文字列の個数) + 1 個を試すとき. 最大値となる場合は, (正しいパスワードの長さ以下の文字列の個数) 個を試すとき.

正解するまでに試すパスワードの個数を とすると, 操作できなくなる回数は 回.

あとはそれをそのまま出力するだけ.

ソース

#include<bits/stdc++.h>

using namespace std;

int score(int N, int K)
{
  return((N - 1) / K * 5 + N);
}

int main()
{
  int N, K;
  string S[101], T;
  int length[101] = {};

  cin >> N >> K;
  for(int i = 0; i < N; ++i) {
    cin >> S[i];
    ++length[S[i].size()];
  }
  cin >> T;

  int sum = accumulate(length, length + T.size(), 0);
  cout << score(sum + 1, K) << " " << score(sum + length[T.size()], K) << endl;
}

C. Journey

問題概要

個の街があってそれぞれ から の番号が振られている. また 本の有向の道路があって, 街 から街 へ時間 かけて通れることを意味する. また道路でループを形成することはない.

時間 に間に合うように街 から街 へ移動する.

このとき最大で何個の街を訪れることができるか求め, そのときの街の番号と共に出力せよ.

解法

トポロジカルソート + 動的計画法 + 経路復元.

ループがないのでこれはDAG. DAG なのでトポロジカルソートすればいい感じの更新順序が得られるので, トポロジカルソートしておく.

街 から に 個の街を通って訪れるときの最短時間 とすれば, これは自明なDPができる. 街 から出ている辺の先と自分 で最小を取っていけば良い. .

経路復元はdpの更新時に前の街を保存しておいて面倒だけど頑張る. どうでもいいけど逆辺にして から への移動するときを考えると微妙に楽?

ソース

適当にやったらMLEした.

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

struct edge
{
  int to, cost;
};

vector< edge > graph[5003];
int dp[5003][5003], rev[5003][5003];

vector< int > order;
bool used[5003];

void dfs(int idx)
{
  if(used[idx]++) return;
  for(auto& e : graph[idx]) dfs(e.to);
  order.push_back(idx);
}

int main()
{
  int N, M, T;

  cin >> N >> M >> T;
  while(M--) {
    int A, B, C;
    cin >> A >> B >> C;
    graph[--B].push_back((edge) {--A, C});
  }

  for(int i = 0; i < N; i++) dfs(i);
  reverse(begin(order), end(order));

  fill_n(*dp, 5003 * 5003, INF);
  dp[N - 1][0] = 0;

  for(int _ = 0; _ < N; _++) {
    int i = order[_];
    for(int j = 0; j < N; j++) {
      for(edge& e : graph[i]) {
        if(dp[e.to][j + 1] > dp[i][j] + e.cost) {
          dp[e.to][j + 1] = dp[i][j] + e.cost;
          rev[e.to][j + 1] = i;
        }
      }
    }
  }

  int curr = N;
  while(dp[0][curr] > T) --curr;

  cout << curr + 1 << endl;

  vector< int > now;
  int pos = 0;
  for(int i = curr; i >= 0; i--) {
    cout << pos + 1 << " ";
    pos = rev[pos][i];
  }
}

D. Maxim and Array

問題概要

長さ の数列 が与えられる.

回まで任意の要素を選んでその要素を 増減させる操作ができる.

このとき を最小化したときの数列 を出力せよ.

解法

の符号を負にすることを考える.

が奇数個のときはもともと負なので偶数個のときを考える. このときなるべく少ない回数で符号を反転させたいので, 絶対値が最小の要素の符号を反転させるように努力するのが最適.

符号を負にできたら, すべての を絶対値として見たときの積の最大化である. の間 なので, が最小の要素に を加えることを繰り返すのが最適である. が最小の要素は優先度付きキューをつかって効率的にもとめることができる.

コーナーケースとして があるものがあるけど, このアルゴリズムなら を あるいは と見立ててあげれば同様に成立する.

計算量は .

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
typedef pair< int64, int > Pi;

int main()
{
  int N, K, X;
  int64 A[200000];
  bool sign = true;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;

  scanf("%d %d %d", &N, &K, &X);
  for(int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
    que.emplace(max(A[i], -A[i]), i);
    sign ^= A[i] < 0;
  }

  while(K--) {
    auto p = que.top();
    que.pop();
    if(A[p.second] < 0) sign ^= 1;
    if(sign) A[p.second] -= X;
    else A[p.second] += X;
    if(A[p.second] < 0) sign ^= 1;
    que.emplace(max(A[p.second], -A[p.second]), p.second);
  }

  for(int i = 0; i < N; i++) {
    printf("%lld ", A[i]);
  }
}