APIO 2020 参加記 (2)

2020-08-14

はじめに

第14回アジア太平洋情報オリンピックに参加しました。 この記事では競技中以外のの事を書きます。 参加記(1)

開会式

Youtubeでバーチャル開催されました。 今年の主催国はインドネシアですが、英語もインドネシア語も分からないので何言ってるのか殆ど分かりませんでした。 Zoomで顔出しが出来たので少しだけしました、少し映れました。 国際大会の各国の参加者一覧の所に自分の名前が有るのなんか嬉しいですね。

プラクティス

Practice Sessionは1週間有り、成績には影響を与えないので気楽にやっていきました。 普段と違い、main関数を書かずに提出するので若干違和感が有りました。

Scorebord Submit list

1問目 Accident Average

取り敢えず小課題1,2は簡単そうだったので素直に書いてそれ以降、何も思い浮かびませんでした。

解法(小課題1,2)

小課題1

単調減少となってるので平均を上げるには大きい数が欲しいので累積和を取っておいてLから末端までの平均値です。

小課題2

Qが小さいので$O(Q^2)$が通ります。 なので、累積和で区間和を$O(1)$で出せるようにしておき、左端を[L,R]の範囲全て試します。

コード[16点]
ID Verdict Score
1 AC 7/7
2 AC 9/9
3 TLE 0/11
4 TLE 0/28
5 TLE 0/21
6 TLE 0/24 
#include <bits/stdc++.h>
#include "average.h"
using namespace std;
using i64 = long long;
#define endl "\n"

i64 N;
vector<i64> crash, sum;
bool task1 = true;

void init()
{
  sum.push_back(0);
}

void addMonth(int K)
{
  if (crash.size() != 0 && crash[crash.size() - 1] < K)
    task1 = false;
  crash.push_back(K);
  sum.push_back(sum[N] + K);
  N++;
}

double maximumAverage(int L, int R)
{
  if (task1)
    return (double)(sum[N] - sum[L]) / (N - L);
  double ans = 0;
  for (i64 i = L; i <= R; i++)
    ans = max(ans, (double)(sum[N] - sum[i]) / (N - i));
  return ans;
}

Discordで教えて貰ったら小課題3を通すことが出来ました。

解法(小課題3)

$A_{x+1}\leqq A_{x}$であれば$A_{x}$ も含めたほうが良いと教えてもらったので上限100であれば殆どが0で単調減少が崩れないので0以外の数字の箇所と範囲ギリギリの場所だけ見ればその中のどれかが最大値です。

コード[27点]
ID Verdict Score
1 AC 7/7
2 AC 9/9
3 AC 11/11
4 TLE 0/28
5 TLE 0/21
6 TLE 0/24 
#include <bits/stdc++.h>
#include "average.h"
using namespace std;
using i64 = long long;
#define endl "\n"

i64 N;
vector<i64> crash, sum, ind;
bool task1 = true;

void init()
{
  sum.push_back(0);
}

void addMonth(int K)
{
  if (crash.size() != 0 && crash[crash.size() - 1] < K)
    task1 = false;
  crash.push_back(K);
  sum.push_back(sum[N] + K);
  if (K != 0)
    ind.push_back(N);
  N++;
}

double maximumAverage(int L, int R)
{
  if (task1)
    return (double)(sum[N] - sum[L]) / (N - L);
  double ans = 0;
  for (i64 i : ind)
    if (L <= i && i <= R)
      ans = max(ans, (double)(sum[N] - sum[i]) / (N - i));
  ans = max(ans, (double)(sum[N] - sum[L]) / (N - L));
  ans = max(ans, (double)(sum[N] - sum[R]) / (N - R));
  return ans;
}

2問目 Organizing Party

最初は小課題3までの解法しか分かりませんでしたが、どうせ2分探索なんだろうなと思い考えていたら、確かになとなり実装しました。

解法

最初に0人の人を全員に対してのクエリで特定し、居なければ人数の少ない方に必ず2人以上親しい人が居るので2分探索をして特定します。

小課題1,2,3

クエリが7回で$ \displaystyle N,M<=8,N \neq M$であるため、男女一方は7人以下で全員に対して聞けるためその情報でグラフを作り次数が1では無い人が異常なゲストだと分かります。

コード
ID Verdict Score
1 AC 12/12
2 AC 15/15
3 AC 20/20
4 AC 53/53 
#include <bits/stdc++.h>
#include "party.h"
using namespace std;
using i64 = long long;
#define endl "\n"

int findUnusualGuest(int N, int M, int Q)
{
  vector<int> query;
  for (i64 i = 0; i < N + M; i++)
    query.push_back(i);
  vector<int> res = ask(query);
  if (res.size() != N + M)
  {
    for (i64 i = 0; i < N + M; i++)
      if (find(res.begin(), res.end(), i) == res.end())
        return i;
  }
  i64 ok, ng;
  if (N < M)
  {
    ok = 0;
    ng = N;
  }
  else
  {
    ok = N;
    ng = N + M;
  }
  while (ng != ok)
  {
    i64 mid = (ok + ng) / 2;
    query.clear();
    for (i64 i = ok; i <= mid; i++)
      query.push_back(i);
    vector<int> res = ask(query);
    if (res.size() == mid - ok + 1)
      ok = mid + 1;
    else
      ng = mid;
  }
  return ng;
}

3問目 The Game of Pajel

OutputOnlyの問題なので雑にプログラムを書いて後は手作業で頑張りました。

解法

塗れない場所で区切られたグリットで色が存在してる所を適当に塗った物をじっーと見つめて改善出来そうなところを手動で直していきます。

コード
ID Verdict Score
1 AC 10/10
2 AC 10/10
3 AC 10/10
4 AC 10/10
5 AC 10/10
6 AC 10/10
7 AC 10/10
8 AC 10/10
9 AC 10/10
10 AC 10/10

outputs

生成プログラム 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

i64 dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main()
{
  i64 N, P;
  cin >> N >> P;
  vector<string> U(N), D(N), L(N), R(N);
  for (i64 i = 0; i < N; i++)
    cin >> U[i];
  for (i64 i = 0; i < N; i++)
    cin >> L[i] >> R[i];
  for (i64 i = 0; i < N; i++)
    cin >> D[i];
  vector<string> ans(N, string(N, '-'));
  for (i64 i = 0; i < N; i++)
    if (U[i] == "0")
      for (i64 j = 0; j < N; j++)
        ans[j][i] = 'x';
    else if (2 <= U[i].size())
    {
      ans[stoi(U[i].substr(0, U[i].size() - 1)) - 1][i] = U[i][U[i].size() - 1];
      for (i64 j = 0; ans[j][i] != U[i][U[i].size() - 1]; j++)
        ans[j][i] = 'x';
    }
  for (i64 i = 0; i < N; i++)
    if (L[i] == "0")
      for (i64 j = 0; j < N; j++)
        ans[i][j] = 'x';
    else if (2 <= L[i].size())
    {
      ans[i][stoi(L[i].substr(0, L[i].size() - 1)) - 1] = L[i][L[i].size() - 1];
      for (i64 j = 0; ans[i][j] != L[i][L[i].size() - 1]; j++)
        ans[i][j] = 'x';
    }
  for (i64 i = 0; i < N; i++)
    if (D[i] == "0")
      for (i64 j = 0; j < N; j++)
        ans[j][i] = 'x';
    else if (2 <= D[i].size())
    {
      ans[N - stoi(D[i].substr(0, D[i].size() - 1))][i] = D[i][D[i].size() - 1];
      for (i64 j = N - 1; ans[j][i] != D[i][D[i].size() - 1]; j--)
        ans[j][i] = 'x';
    }
  for (i64 i = 0; i < N; i++)
    if (R[i] == "0")
      for (i64 j = 0; j < N; j++)
        ans[i][j] = 'x';
    else if (2 <= R[i].size())
    {
      ans[i][N - stoi(R[i].substr(0, R[i].size() - 1))] = R[i][R[i].size() - 1];
      for (i64 j = N - 1; ans[i][j] != R[i][R[i].size() - 1]; j--)
        ans[i][j] = 'x';
    }
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[i][j] == 'M' || ans[i][j] == 'B')
      {
        queue<pair<i64, i64>> que;
        que.push({i, j});
        while (que.size())
        {
          pair<i64, i64> p = que.front();
          que.pop();
          for (i64 k = 0; k < 4; k++)
          {
            i64 ddx = p.first + dx[k], ddy = p.second + dy[k];
            if (ddx < 0 || N <= ddx || ddy < 0 || N <= ddy || ans[ddx][ddy] != '-')
              continue;
            ans[ddx][ddy] = tolower(ans[p.first][p.second]);
            que.push({ddx, ddy});
          }
        }
      }
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
    {
      if (ans[i][j] == 'x')
        ans[i][j] = '-';
    }
  for (i64 i = 0; i < N; i++)
    cout << ans[i] << endl;
}
ID Verdict Score
1 OK 8/10[Q = 6]
2 OK 7/10[Q = 12]
3 OK 7/10[Q = 13]
4 OK 5/10[Q = 151]
5 AC 10/10
6 OK 0/10[Q = 227]
7 OK 2/10[Q = 212]
8 OK 3/10[Q = 178]
9 OK 4/10[Q = 440]
10 OK 0/10[Q = 1062]

生成されたoutputs

テスター 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl "\n"

i64 dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main()
{
  string tc;
  cin >> tc;
  ifstream in("inputs/pajel_" + tc + ".in");
  cin.rdbuf(in.rdbuf());
  i64 N, P;
  cin >> N >> P;
  vector<string> U(N), D(N), L(N), R(N);
  for (i64 i = 0; i < N; i++)
    cin >> U[i];
  for (i64 i = 0; i < N; i++)
    cin >> L[i] >> R[i];
  for (i64 i = 0; i < N; i++)
    cin >> D[i];
  ifstream out("outputs/pajel_" + tc + ".out");
  cin.rdbuf(out.rdbuf());
  vector<string> ans(N);
  for (i64 i = 0; i < N; i++)
    cin >> ans[i];
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[j][i] != '-')
      {
        if (to_string(j + 1) + string(1, ans[j][i]) != U[i] && U[i] != "-")
          cerr << "U" << i << " " << to_string(j + 1) << ans[j][i] << " " << U[i] << endl;
        break;
      }
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[N - j - 1][i] != '-')
      {
        if (to_string(j + 1) + string(1, ans[N - j - 1][i]) != D[i] && D[i] != "-")
          cerr << "D" << i << " " << to_string(j + 1) << ans[N - j - 1][i] << " " << D[i] << endl;
        break;
      }
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[i][j] != '-')
      {
        if (to_string(j + 1) + string(1, ans[i][j]) != L[i] && L[i] != "-")
          cerr << "L" << i << " " << to_string(j + 1) << ans[i][j] << " " << L[i] << endl;
        break;
      }
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[i][N - j - 1] != '-')
      {
        if (to_string(j + 1) + string(1, ans[i][N - j - 1]) != R[i] && R[i] != "-")
          cerr << "R" << i << " " << to_string(j + 1) << ans[i][N - j - 1] << " " << R[i] << endl;
        break;
      }
  vector<vector<bool>> ch(N, vector<bool>(N));
  i64 q = 0;
  for (i64 i = 0; i < N; i++)
    for (i64 j = 0; j < N; j++)
      if (ans[i][j] != '-' && !ch[i][j])
      {
        q++;
        ch[i][j] = true;
        char now = tolower(ans[i][j]);
        queue<pair<i64, i64>> que;
        que.push({i, j});
        while (que.size())
        {
          pair<i64, i64> p = que.front();
          que.pop();
          for (i64 k = 0; k < 4; k++)
          {
            i64 ddx = p.first + dx[k], ddy = p.second + dy[k];
            if (ddx < 0 || N <= ddx || ddy < 0 || N <= ddy || ch[ddx][ddy] || tolower(ans[ddx][ddy]) != now)
              continue;
            ch[ddx][ddy] = true;
            que.push({ddx, ddy});
          }
        }
      }
  cerr << "P = " << P << endl;
  cerr << "Q = " << q << endl;
  cerr << "Score = " << (i64)(10 - sqrt(2 * (q - P))) << endl;
  return 0;
}

プラクティス後

3問目で文字列とにらめっこするのがとても疲れました。 自力で216点取れたのでとても嬉しかったです。 本番でも良い記録が出せるように頑張ります。

閉会式

バーチャルなのでメダリスト発表もなんかすんなり終わってしまってなんか思ったよりすぐ終わってしいました。 日本勢が金1銀5ですげーという感じです、中国満点10人で金10はマジで化け物だと思いました。

競プロ

APIO 2020 参加記 (1)

[覚書] PC98版 コープスパーティー 起動方法