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

ei1333の日記

ぺこい

Codeforces Round #374 (Div. 2)

ABCDを解いた.

A. One-dimensional Japanese Crossword

問題概要

 {n(1 \le n \le 100)} 個のマスからなる列があって, それぞれ白か黒で塗られている.

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

解法

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

ルール通りに, 左から 'B' が連続している個数を数えてそれをそれぞれ出力すれば良い.  {\mathcal{O}(n)}.

ソース

#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

問題概要

 {n(1 \le n \le 100)} 個のパスワードの候補となる文字列と, 正しいパスワードを示す文字列が与えられる.

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

 {1} 個のパスワードを試すのに  {1} 秒かかる.  {k(1 \le k \le 100)} 回連続して間違えると  {5} 秒間は操作できない.

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

解法

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

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

正解するまでに試すパスワードの個数を  {x} とすると, 操作できなくなる回数は  {\displaystyle \lfloor \frac {x - 1} {k} \rfloor} 回.

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

ソース

#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

問題概要

 {n(1 \le n \le 5000)} 個の街があってそれぞれ  {1} から  {n} の番号が振られている. また  {m(1 \le m \le 5000)} 本の有向の道路があって, 街  {u_i} から街  {v_i} へ時間  {t_i(1 \le t_i \le 10^9)} かけて通れることを意味する. また道路でループを形成することはない.

時間  {T(1 \le T \le 10^9)} に間に合うように街  {1} から街  {n} へ移動する.

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

解法

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

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

 {dp[x][y] :=} {1} から  {x} {y} 個の街を通って訪れるときの最短時間 とすれば, これは自明なDPができる. 街  {x} から出ている辺の先と自分  {+ t_i} で最小を取っていけば良い.  {\mathcal{O}(nm)}.

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

ソース

適当にやったら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

問題概要

長さ  {n(1 \le n \le 200\ 000)} の数列  {a_i (|a_i\ \le 10^9)} が与えられる.

 {k(1 \le k \le 200\ 000)} 回まで任意の要素を選んでその要素を  {x(1 \le x \le 10^9)} 増減させる操作ができる.

このとき  {\displaystyle \prod_{ i = 1 }^n a_i} を最小化したときの数列  {a_i} を出力せよ.

解法

 {\displaystyle \prod_{ i = 1 }^n a_i} の符号を負にすることを考える.

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

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

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

計算量は  {O((n + k)\log n)}.

ソース

#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]);
  }
}