Codeforces Round #417 (Div. 2)

ABCの ${3}$ 完.

もうちょっと頭の方をね, よくしていきたいんですが…

A. Sagheer and Crossroads

codeforces.com

問題概要

交差点があって, 東西南北 4 つの信号がある.

それぞれの信号は ${4}$ つのライトからなり, それぞれの右折,直進,左折,横断歩道の意味を表す.

現在の点灯状態が与えられるので, 横断歩道の歩行者と車が衝突する可能性があるか判定せよ. 信号

解法

横断歩道の知識を問う問題.

解法は注意力(えぇ…

これは競技プログラミングではないですね…

図を注意深く見てそのままを書くととおる.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int A[4][4];

  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < 4; j++) {
      cin >> A[i][j];
    }
  }

  if((A[0][3] && (A[0][1] | A[2][1] | A[1][0] | A[3][2] | A[0][0] | A[0][2])) ||
     (A[2][3] && (A[0][1] | A[2][1] | A[1][2] | A[3][0] | A[2][0] | A[2][2])) ||
     (A[1][3] && (A[1][1] | A[3][1] | A[0][2] | A[2][0] | A[1][0] | A[1][2])) ||
     (A[3][3] && (A[1][1] | A[3][1] | A[0][0] | A[2][2] | A[3][0] | A[3][2]))) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

}

B. Sagheer, the Hausmeister

codeforces.com

問題概要

${n}$ 階建てで, それぞれの階には ${m}$ 個の部屋が並んでいて, それぞれの部屋について電気の点灯状態が与えられる.

建物の左端と右端は階段である.

今, ${1}$ 階の左端にいる. 電気がついている全ての部屋に訪れて電気を消したい.

自分の階の電気が全部消えるまで上に行けない.

このとき, 最小距離を求めよ.

解法

なんか制約は小さいけど何をしても面倒そうだったので, DP した.

ある階に上がった時, 左端の階段か右端の階段のどちらかにいて, そこからその階の電気を全て消すコストはまぁ求まるのでやる.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int INF = 1 << 30;

int N, M;
string S[18];
int latte[18], malta[18];
int dp[18][110];

int rec(int floor, int pos)
{
  if(floor + 1 == N) {
    if(pos == 0) return (malta[floor]);
    else return (M + 1 - latte[floor]);
  }
  int &memo = dp[floor][pos];
  if(~memo) return (memo);
  int ret = INF;
  if(pos == 0) {
    ret = min(ret, rec(floor + 1, M + 1) + M + 2);
    ret = min(ret, rec(floor + 1, 0) + malta[floor] * 2 + 1);
  } else {
    ret = min(ret, rec(floor + 1, 0) + M + 2);
    ret = min(ret, rec(floor + 1, M + 1) + (M + 1 - latte[floor]) * 2 + 1);
  }
  return (memo = ret);
}

int main()
{
  cin >> N >> M;
  fill_n(latte, 18, M + 1);
  int height = 0;

  for(int i = 0; i < N; i++) cin >> S[N - i - 1];
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < S[i].size(); j++) {
      if(S[i][j] == '1') {
        latte[i] = min(latte[i], j);
        malta[i] = max(malta[i], j);
        height = i;
      }
    }
  }
  N = height + 1;
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 0) << endl;
}

C. Sagheer and Nubian Market

codeforces.com

問題概要

${n}$ 個のアイテムがあって, ${i}$ 番目の基本コストは ${a_i}$ である.

${k}$ 個のアイテムを買う時, それぞれのアイテム ${i}$ に対してコスト ${a_i + i \times k}$ がかかる.

今お金が ${S}$ あるので, ${S}$ 以下で買えるアイテム数の最大と, そのときの最小コストを求めよ.

解法

二分探索で解けなかったら解けないのではい.

アイテムを買う個数が決まっているとする.

するとそれぞれのアイテムのコストが一意に決まって, このときソートして上から買う個数分とるのが最適.

${S}$ を上回らない最大の個数を求めたいので二分探索する.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 N, S, A[100000];
  cin >> N >> S;
  for(int i = 0; i < N; i++) cin >> A[i];

  auto check = [&](int64 k, bool output)
  {
    vector< int64 > vs;
    for(int64 i = 0; i < N; i++) vs.push_back(A[i] + (i+1)*k);
    sort(begin(vs), end(vs));
    int64 ret = 0;
    for(int i = 0; i < k; i++) ret = min(S + 1, ret + vs[i]);
    if(output) cout << k << " " << ret << endl;
    return(ret <= S);
  };

  int low = 0, high = N;
  while(high - low > 0) {
    int mid = (low + high + 1) >> 1;
    if(check(mid, false)) low = mid;
    else high = mid - 1;
  }

  check(low, true);
}

E. Sagheer and Apple Tree

codeforces.com

問題概要

${n}$ 頂点の根付き木があって, それぞれの頂点にはりんごが ${a_i}$ 個ある.

また根から任意の葉までの距離の距離の偶奇は一致する.

以下の操作を ${2}$ 人で繰り返し, できなくなったらまけである.

葉ノードのりんごをいくつか食べる
葉以外のノードのりんごのいくつかを ${1}$ つの子ノードに移動する

後攻の人がゲーム開始前に ${2}$ つの異なる頂点を選んで, りんごの個数を入れ替える.

後攻が勝てるような入れ替え方の個数を求めよ.

解法

葉から葉以外の距離を求めるのはDFSでできる.

葉以外の頂点で, 葉までの距離が奇数の頂点はすべて無視できる(後手はそのまま下に流せばいいので).

解法としては, 距離が偶数の頂点と奇数の頂点かでりんごを分別する.

勝敗は偶数のやつの nim っぽいので xor をとって 0 になるかどうかによって定まる.

xor が 0 になるように頂点の入れ替えをするのは, まあはいなのではいできる.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
#define rep(i, n) for(int i = 0; i < n; i++)

int N, A[100000];
vector< int > g[100000], latte, malta;

int dfs(int idx)
{
  bool flag = false;
  for(auto &to : g[idx]) if(!dfs(to)) flag = true;
  (flag ? latte : malta).push_back(A[idx]);
  return (flag);
}

int main()
{
  cin >> N;
  rep(i, N) cin >> A[i];
  rep(i, N - 1) {
    int p;
    cin >> p;
    --p;
    if(p >= 0) g[p].push_back(i + 1);
  }
  dfs(0);

  int beet = 0;
  int64 ret = 0;
  map< int, int > ps;
  for(auto &s : malta) beet ^= s, ps[s]++;
  if(beet == 0) {
    int sz1 = (int) malta.size(), sz2 = (int) latte.size();
    ret += 1LL * sz1 * (sz1 - 1) / 2;
    ret += 1LL * sz2 * (sz2 - 1) / 2;
  }

  for(auto &p : latte) {
    beet ^= p;
    ret += ps[beet];
    beet ^= p;
  }
  cout << ret << endl;
}

ei1333の日記

ぺこい

Codeforces Round #417 (Div. 2)

A. Sagheer and Crossroads

問題概要

解法

ソース

B. Sagheer, the Hausmeister

問題概要

解法

ソース

C. Sagheer and Nubian Market

問題概要

解法

ソース

E. Sagheer and Apple Tree

問題概要

解法

ソース