GCJ2020 Round 1B 参加記

はじめに

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

競技中

Submit list

1問目 Expogo

満点解法が全く思い浮かばす、取り敢えず小さいセットだけでも取っておこうとなり全探索を書きました。

解法(Test set 1,2)

長さNを1から順にを決め打ちして$ \displaystyle 4^N$を全部試します。

コード(01:56:49[13点])

ID	Verdict	Score
1	AC	5/5
2	AC	8/8
3	TLE	0/16

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

string m = "NSEW";

int main()
{
  i64 T;
  cin >> T;
  for (i64 _ = 1; _ <= T; _++)
  {
    i64 X, Y;
    cin >> X >> Y;
    for (i64 i = 1; i <= 10; i++)
    {
      for (i64 j = 0; j < pow(4, i); j++)
      {
        string ans;
        i64 tmp = j;
        for (i64 k = 0; k < i; k++)
        {
          ans += m[tmp % 4];
          tmp /= 4;
        }
        i64 nowX = 0, nowY = 0;
        for (i64 k = 0; k < i; k++)
        {
          i64 move = 1LL << k;
          if (ans[k] == 'E')
            nowX += 1LL << k;
          else if (ans[k] == 'W')
            nowX -= 1LL << k;
          else if (ans[k] == 'N')
            nowY += 1LL << k;
          else if (ans[k] == 'S')
            nowY -= 1LL << k;
        }
        if (nowX == X && nowY == Y)
        {
          cout << "Case #" << _ << ": " << ans << endl;
          goto ok;
        }
      }
    }
    cout << "Case #" << _ << ": "
         << "IMPOSSIBLE" << endl;
  ok:;
  }
  return 0;
}

2問目 Blindfolded Bullseye

全く思い浮かばず取り敢えずset1だけを取りに行きました。

解法

中心は$ \displaystyle -5<= X,Y <= 5$に有るためその範囲を全て試します。

コード(02:09:25[3点])

ID	Verdict	Score
1	AC	3/3
2	TLE	0/12
3	Skip	0/19

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

string m = "NSEW";

int main()
{
  i64 T, A, B;
  cin >> T >> A >> B;
  for (i64 _ = 1; _ <= T; _++)
  {
    for (i64 i = -5; i <= 5; i++)
      for (i64 j = -5; j <= 5; j++)
      {
        cout << i << " " << j << endl;
        string ret;
        cin >> ret;
        if (ret == "CENTER")
          goto ok;
      }
  ok:;
  }
  return 0;
}

競技後

1,2問目両方全く解けそうに無くてめっちゃ萎えました。

結果

最終順位が確定し、16点のペナルティが2:25:25で3580位でRound 1Cに進出しました。