APIO 2020 参加記 (1)

2020-08-20

はじめに

第14回アジア太平洋情報オリンピックに参加しました。 例年APIOはJOI本選Aランクとその所属校の生徒が参加出来ますが、COVID-19の影響で奇跡的に参加する事が出来ました。 この記事では競技中の事を書きます。 参加記(2)

競技中

Scorebord Submit list

1問目 Painting Walls

最初、小課題1,2,3しか解き方が思い浮かびませんでしたが、途中で1と2,3の方法を組み合わせればもしかしたら小課題4も通るのでは…?と思い試したら通ってとても驚きました。

解法(小課題1,2,3,4)

後ろから現在地を起点に試してどの$x$でも成り立たなければ一個後ろ側に戻り戻った地点が既に探索済みのところであれば-1、成り立てば$x-M-1$前に進み-1まで進んだら全地点が塗れているのでそこまでに塗った回数を返します。

コード[63点]
ID Verdict Score
1 AC 12/12
2 AC 15/15
3 AC 13/13
4 AC 23/23
5 TLE 0/37 
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using i64 = long long;
#define endl "\n"

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B)
{
  i64 ans = 0;
  i64 bef = N - M + 1;
  map<i64, vector<i64>> m;
  for (i64 i = 0; i < M; i++)
    for (i64 j : B[i])
      m[j].push_back(i);
  for (i64 i = N - M; i < bef; i++)
  {
    bool ok = false;
    for (i64 j : m[C[i]])
    {
      bool check = true;
      for (i64 k = 0; k < M; k++)
      {
        i64 now = (j + k) % M;
        i64 t = *lower_bound(B[now].begin(), B[now].end(), C[i + k]);
        if (C[i + k] != t)
        {
          check = false;
          break;
        }
      }
      if (check)
      {
        ok = true;
        break;
      }
    }
    if (ok)
    {
      bef = i;
      i = max(-1LL, bef - M - 1);
      ans++;
    }
  }
  if (bef == 0)
    return ans;
  return -1;
}

2問目 Swapping Cities

小課題1を見てこれは全部成り立たないから簡単だなと思い提出してWAが返ってきて良く考えたらそんな事は無いことに気がついて、小課題2でも安易な思い込みをして間違えに気が付かず突き進み、ちゃんと考察をしような、実感しました。

解法(小課題1,2)

小課題1

基本的に存在しない事は明らかですが、円形になっている時だけ各道路の最大コストを返します。

小課題2

グラフがウニなので頂点0から一度別の頂点に退避して進むのが基本で頂点0から目的地までコスト2つと使われていない内最も小さいコストの最大値が答えです。 しかし、片方が頂点0だった場合お互いに退避しあわないと行けないため、先の答えと使われていない内2番目に小さいコストの最大値が答えになります。

コード(小課題1)[6点]
ID Verdict Score
1 AC 6/6
2 WA 0/7
3 RTE 0/17
4 RTE 0/20
5 WA 0/23
6 RTE 0/27 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using i64 = long long;
#define endl "\n"

struct UnionFind
{
  vector<i64> d;
  UnionFind(i64 size) : d(size, -1) {}
  void merge(i64 x, i64 y)
  {
    x = root(x);
    y = root(y);
    if (d[y] < d[x])
      swap(x, y);
    d[x] += d[y];
    d[y] = x;
  }
  bool check(i64 x, i64 y)
  {
    return root(x) == root(y);
  }
  i64 root(i64 x)
  {
    return d[x] < 0 ? x : d[x] = root(d[x]);
  }
};

i64 N;
i64 eRet = 0;

bool task1E = false;

void init(int _N, int M, vector<int> U, vector<int> V, vector<int> W)
{
  N = _N;
  eRet = *max_element(W.begin(), W.end());
  UnionFind uf(N);
  for (i64 i = 0; i < M; i++)
  {
    if (uf.check(U[i], V[i]))
      task1E = true;
    uf.merge(U[i], V[i]);
  }
}

int getMinimumFuelCapacity(int X, int Y)
{
  if (task1E)
    return eRet;
  return -1;
}
コード(小課題2)[7点]
ID Verdict Score
1 WA 0/6
2 AC 7/7
3 WA 0/17
4 WA 0/20
5 WA 0/23
6 WA 0/27 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using i64 = long long;
#define endl "\n"

i64 N, M;
vector<int> W;
vector<vector<pair<i64, i64>>> edge;

void init(int _N, int M, vector<int> U, vector<int> V, vector<int> _W)
{
  N = _N, W = _W;
  sort(W.begin(), W.end());
  edge.resize(N);
  for (i64 i = 0; i < M; i++)
  {
    edge[U[i]].push_back({V[i], _W[i]});
    edge[V[i]].push_back({U[i], _W[i]});
  }
}

int getMinimumFuelCapacity(int X, int Y)
{
  if (N <= 3)
    return -1;
  if (X == 0 || Y == 0)
  {
    i64 t = (X == 0 ? Y : X);
    i64 ret = edge[t][0].second;
    i64 tmp = edge[t][0].second;
    for (i64 i = 0; i < 3; i++)
      if (tmp == W[i])
        tmp = -1;
      else
      {
        ret = max(ret, (i64)W[i]);
        if (i == 1 && tmp != -1)
          break;
      }
    return ret;
  }
  i64 ret = max(edge[X][0].second, edge[Y][0].second);
  i64 tmp[2] = {edge[X][0].second, edge[Y][0].second};
  for (i64 i = 0; i < 3; i++)
    if (tmp[0] == W[i])
      tmp[0] = -1;
    else if (tmp[1] == W[i])
      tmp[1] = -1;
    else
    {
      ret = max(ret, (i64)W[i]);
      break;
    }
  return ret;
}

3問目 Fun Tour

全く分からないが、小課題1はなんかマラソンすれば通せそうだなと思い試したら通ってしまいました。

(嘘)解法(小課題1)

評価値を次の道の方が今の道より時間がかかる場合その差の和として焼き鈍しを書きます。

コード[10点]
ID Verdict Score
1 AC 10/10
2 WA 0/16
3 WA 0/21
4 WA 0/19
5 WA 0/34 
#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using i64 = long long;
#define endl "\n"

const i64 INF = 1e9;

const int timeLimit = 1998;

int xor128()
{
  static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
  int t = (x ^ (x << 11));
  x = y;
  y = z;
  z = w;
  return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

i64 N;
vector<vector<i64>> dist;

int eval(vector<int> &ans)
{
  int ret = 0;
  for (i64 i = 1; i < N - 1; i++)
    if (dist[ans[i - 1]][ans[i]] < dist[ans[i]][ans[i + 1]])
      ret += dist[ans[i]][ans[i + 1]] - dist[ans[i - 1]][ans[i]];
  return ret;
}

vector<int> createFunTour(int _N, int Q)
{
  chrono::system_clock::time_point start = chrono::system_clock::now();
  N = _N;
  dist = vector<vector<i64>>(N, vector<i64>(N, INF));
  for (i64 i = 0; i < N; i++)
    for (i64 j = i + 1; j < N; j++)
      if (hoursRequired(i, j) == 1)
      {
        dist[i][j] = 1;
        dist[j][i] = 1;
      }
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
        dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
  vector<int> ans(N);
  for (i64 i = 0; i < N; i++)
    ans[i] = i;
  vector<int> now = ans;
  double C = timeLimit * 100, forceLine;
  int currentTime;
  int bestScore = 1e9, nowScore = 1e9, loop = 0;
  while ((currentTime = chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now() - start).count() / 1000) < timeLimit)
  {
    int t[2] = {xor128() % N, xor128() % N};
    swap(now[t[0]], now[t[1]]);
    int score = eval(now);
    forceLine = (timeLimit - currentTime) / C;
    if (score < bestScore)
    {
      ans = now;
      bestScore = score;
    }
    if (score < nowScore || forceLine * 1000 > rand() % 1000)
    {
      nowScore = score;
    }
    else
    {
      swap(now[t[0]], now[t[1]]);
    }
  }
  return ans;
}

競技後

やる前は正の得点すら取れるか心配だったので86点取れたし、全力も出し切れたのと思っているので割と満足しています。 アルゴのコンテストでマラソンをするのは良くないと思いました。

結果

結果を見てBronzeの下限が96点だったので後10点欲しかったなぁとなりました。 まあどちらにしろ、国内6位タイ以内は不可能なので順位表に載るのは不可能でしたが、一応129位相当ですね。

競プロ

第28回TCB 参加記

APIO 2020 参加記 (2)