第2回 ドワンゴからの挑戦状 予選

A, B, Dを解いて3完42位。

A: ニコニコ数

解法

頭が弱くて, 蟻本の包除原理を写経してしまったので, 13分溶かした。
そもそも 2525 や 252525 は 25 の倍数なので, 25 だけ考えれば良いのは自明。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;
int main()
{
  int N;
  int64 nikoni[5] = {25, 2525, 252525, 25252525, 2525252525};
 
  cin >> N;
 
  int ret = 0;
 
  for(int i = 1; i < 1 << 5; i++) {
    int num = 0;
    for(int j = i; j != 0; j >>= 1) {
      num += j & 1;
    }
    int64 lcm = 1;
    for(int j = 0; j < 5; j++) {
      if((i >> j) & 1) {
        lcm = lcm / __gcd(lcm, nikoni[j]) * nikoni[j];
        if(lcm > N) break;
      }
    }
    if(num % 2 == 0) ret -= N / lcm;
    else ret += N / lcm;
  }
  cout << ret << endl;
}

B: 積み鉛筆

解法

ぱっと見て、数列{L} の制約が厳しいので, 数列{K} の候補はかなり少なさそう。
もうちょっと考えると、問題文通りに実装すればよさそう(たぶん。
なので、適当に書けば通る。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;
int main()
{
  int N, A[100000];
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    cin >> A[i];
  }
  A[N - 1] = A[N - 2];
  int B[100000] = {};
  B[0] = A[0];
  B[N - 1] = A[N - 1];
  for(int i = 0; i < N - 1; i++) {
    if(B[i] == A[i] && A[i + 1] < A[i]) {
      B[i + 1] = A[i + 1];
    } else {
      B[i + 1] = A[i];
    }
  }
  for(int i = 0; i < N; i++) {
    if(i > 0) cout << " ";
    cout << B[i];
  }
  cout << endl; 
}

D: 庭園

解法

C問題より手がつけやすそうだったので, こっちを解こうとする。何かとあって時間を 1 時間かける。
まず 1 つの長方形内のコストを最大化することを考えると、枠 | Aizu Online Judge が頭に浮かぶ。本質的に、全く同じ。長方形の一辺の幅を決めておけば、もう一方の辺の最適値は尺取りで O(N^3) で解ける。
長方形を 2 つに増やす。長方形A(x1, y1, x2, y2), 長方形B(x3, y3, x4, y4) とすると、2つの長方形の関係は被ってはダメなことから、x2 < x3 あるいは、 y2 < y3 を満たしている必要がある。これが分かればそれぞれについて最大値を求めるだけ。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 INF = 1LL << 58;
 
int64 dp3[301], dp4[301];
int64 dp5[301], dp6[301];
 
int main()
{
  int H, W;
  int64 B[301][301] = {{}};
 
  cin >> H >> W;
  for(int i = 1; i <= H; i++) {
    for(int j = 1; j <= W; j++) {
      cin >> B[i][j];
      B[i][j] += B[i][j - 1] + B[i - 1][j] - B[i - 1][j - 1];
    }
  }
 
#define Sum(y1, x1, y2, x2) (B[y2][x2] - B[y2][x1 - 1] - B[y1 - 1][x2] + B[y1 - 1][x1 - 1])

  for(int i = 1; i <= H; i++) {
    for(int j = i; j <= H; j++) {
      int64 RangeSum = 0, ret = -INF;
      for(int k = 1; k <= W; k++) {
        int64 LeftLine = Sum(i, k, j, k);
        RangeSum = max(LeftLine, RangeSum + LeftLine);
        ret = max(ret, RangeSum);
      }
      dp5[j] = max(dp5[j], ret);
      dp6[i] = max(dp6[i], ret);
    }
  }
  for(int i = 1; i <= W; i++) { 
    for(int j = i; j <= W; j++) {
      int64 RangeSum = 0, ret = -INF;
      for(int k = 1; k <= H; k++) {
        int64 LeftLine = Sum(k, i, k, j);
        RangeSum = max(LeftLine, RangeSum + LeftLine);
        ret = max(ret, RangeSum);
      }
      dp3[j] = max(dp3[j], ret);
      dp4[i] = max(dp4[i], ret);
    }
  }
  int64 ret = -INF;
  for(int i = 1; i < W; i++) {
    for(int j = i + 1; j <= W; j++) res = max(res, dp3[i] + dp4[j]);
  }
  for(int i = 1; i < H; i++) {
    for(int j = i + 1; j <= H; j++) res = max(res, dp5[i] + dp6[j]);
  }
  cout << ret << endl;
}

C: メンテナンス明け

解法

あ、これ A Broken Door | Aizu Online Judge だ！ってなる。今回の問題にはコストがあるので、Dijkstraやればいいのかなーってなる。
その解通りに、ゴールからDijkstraしてゴールまでの最短距離を求める。これで、辺が使えるかどうかが分かる。二分探索して解を、スタートからゴールへDijkstraして判定しながら探す。バグる。終わる。
終わってから見てみると、辺をはるフェーズで逆辺をはっていて、移動先が逆転していたりしていた。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
#define int long long
struct edge {
  int to, cost, tog, Type;
};
int N, M, src, dst;
vector< edge > graph[25252];
int L[25252];
int s[25252];
int t[25252];
vector< int > m1;
const int INF = 1LL << 58;
 
void Dijkstra(int s, vector< int > & min_cost)
{  
  typedef pair< int, int > Pi;
  min_cost.assign(N, INF);
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.push(Pi(0, s));
  min_cost[s] = 0;
  while(!que.empty()) {
    int now  = que.top().second;
    int cost = que.top().first;
    que.pop();
    if(cost > min_cost[now]) continue;
    for(int i = 0; i < graph[now].size(); i++) {
      edge e = graph[now][i];
      if(cost + e.cost < min_cost[e.to]) {
        min_cost[e.to] = cost + e.cost;
        que.push(Pi(min_cost[e.to], e.to));
      }
    }
  }
}
int Dijkstra2(int value)
{
  typedef pair< int, int > Pi;
  vector< int > used(N, INF);
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  que.push({0, src});
  used[src] = 0;
  while(!que.empty()) {
    int now  = que.top().second;
    int cost = que.top().first;
    que.pop();
    if(cost > used[now]) continue;
    if(now == dst) return(true);
    for(int i = 0; i < graph[now].size(); i++) {
      edge e = graph[now][i];
      if(cost + e.cost + e.tog + m1[e.Type] <= value && cost + e.cost < used[e.to]) {
        used[e.to] = cost + e.cost;
        que.push({used[e.to], e.to});
      }
    }
  }
  return(false);
}
 
signed main()
{
  
  cin >> N >> M >> src >> dst;
  for(int i = 0; i < M; i++) {
    cin >> L[i];
    for(int j = 0; j < L[i]; j++) {
      cin >> s[j];
    }
    int times = 0;
    for(int j = 0; j < L[i] - 1; j++) {
      cin >> t[j];
      times += t[j];
    }
    int cs = times;
    for(int j = 1; j < L[i]; j++) {
      times -= t[j - 1];
      graph[s[j - 1]].push_back((edge){s[j], t[j - 1], times, s[L[i] - 1]});
    }
    for(int j = L[i] - 1; j > 0; j--) {
      cs -= t[j - 1];
      graph[s[j]].push_back((edge){s[j - 1], t[j - 1], cs, s[0]});
    }
  }
  Dijkstra(dst, m1);
  int low = 0, high = 1LL << 58;
  while(high - low > 0) {
    int mid = (low + high) >> 1;
    if(Dijkstra2(mid)) high = mid;
    else low = mid + 1;
  }
  cout << low << endl;
}