GCJ2020 Round 1C 参加記

はじめに

Round 1Bで通過出来なかったのでRound 1Cに参加しました。 Round 1B参加記

競技中

Submit list

1問目 Overexcited Fan

その地点に特定の時間以内に辿りつけるか判定出来れば良さそうでその方法もすぐ思い浮かんだのでそのまま実装しました。

解法

移動する度にその点のX,Y座標の和が経過時間以下かどうか確認し、小さければその時点で到達可能で到達可能な点が無ければ不可能です。

コード(00:10:37)

ID	Verdict	Score
1	AC	4/4
2	AC	6/6
3	AC	12/12

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

int main()
{
  int T;
  cin >> T;
  for (i64 _ = 1; _ <= T; _++)
  {
    i64 X, Y;
    string S;
    cin >> X >> Y >> S;
    for (i64 i = 0; i < S.size(); i++)
    {
      if (S[i] == 'N')
        Y++;
      else if (S[i] == 'S')
        Y--;
      else if (S[i] == 'W')
        X--;
      else
        X++;
      if (abs(X) + abs(Y) <= i + 1)
      {
        cout << "Case #" << _ << ": " << i + 1 << endl;
        goto fin;
      }
    }
    cout << "Case #" << _ << ": "
         << "IMPOSSIBLE" << endl;
  fin:;
  }
  return 0;
}

2問目 Overrandomized

直感的に先頭に出現する回数が高い方が小さい方が値が小さくなりそうだったので直感を信じて実装しました。

解法

先頭での出現回数から1~9の値を確定し、最後に使われてないのが0に確定します。

コード(02:10:21 5WA)

ID	Verdict	Score
1	AC	9/9
2	AC	10/10
3	AC	17/17

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

int main()
{
  int T;
  cin >> T;
  for (i64 _ = 1; _ <= T; _++)
  {
    i64 U;
    cin >> U;
    vector<vector<char>> res(10);
    set<char> tt;
    map<char, i64> s3;
    for (i64 i = 0; i < 10000; i++)
    {
      string M, R;
      cin >> M >> R;
      for (char j : R)
        tt.insert(j);
      s3[R[0]]++;
    }
    string ans;
    set<char> use;
    vector<pair<i64, char>> list;
    for (pair<char, i64> i : s3)
    {
      list.push_back({i.second, i.first});
      use.insert(i.first);
    }
    sort(list.rbegin(), list.rend());
    for (pair<i64, char> i : list)
      ans += i.second;
    for (char j : tt)
      if (use.count(j) == 0)
      {
        ans = j + ans;
        break;
      }
    cout << "Case #" << _ << ": " << ans << endl;
  }
  return 0;
}

3問目 Oversized Pancake Choppers

この時点で順位がかなり惜しいところまで来ていたのでなんとしてもTest set 1を通したいと思い色々試しましたが結局通せませんでした。

競技後

Round 1A、2Bとは違いギリギリのラインで落ちた事が分かりとても悔しくなりました。ペナルティは全く届きそうにないので3問目のTest set 1さえ取れてれば…と何回も思いました。

結果

最終順位が確定し、58点のペナルティが2:30:21で1764位で今年もRound 1で敗退が決まりました。来年こそはRound 1の壁を超えて行きたいです。