GCJ2020 Round 1A 参加記

はじめに

Qualを通過したのでRound 1Aに参加しました。 Round 1は1500位以内に入らないと通過出来ないので正直諦め半分ですが、頑張って挑んでいきます。 Qual参加記

競技中

Submit list

1問目 Pattern Matching

Test set 1は明らかに素直に一番長い物を頼りに見ていけば良いのが分かりましたがそれ以降が分からず最初から解けなくて少し萎えました。

解法(Test set 1)

長さが最大の物を基準にその他がそれで対応出来るかを見てそれが構成出来ればそのまま出来なければ"*"を出力します。

コード(00:37:34[5点])

ID	Verdict	Score
1	AC	5/5
2	WA	0/5
3	Skip	0/18

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

int main()
{
  i64 T;
  cin >> T;
  for (i64 _ = 1; _ <= T; _++)
  {
    i64 N;
    cin >> N;
    vector<string> P(N);
    vector<i64> size(N);
    for (i64 i = 0; i < N; i++)
    {
      cin >> P[i];
      reverse(P[i].begin(), P[i].end());
      size[i] = P[i].size();
    }
    string ans;
    i64 it = max_element(size.begin(), size.end()) - size.begin();
    ans = P[it].substr(0, size[it] - 1);
    for (i64 i = 0; i < N; i++)
      if (ans.substr(0, size[i] - 1) != P[i].substr(0, size[i] - 1))
      {
        ans = "*";
      }
    reverse(ans.begin(), ans.end());
    cout << "Case #" << _ << ": " << ans << endl;
  }
  return 0;
}

2問目 Pascal Walk

n段目をを全て取ると$ \displaystyle 2^n$になるのでそれを利用出来ないかなと考えていたらふと思い浮かび実験していたら出来そうだったので取り敢えず実装してみました。

解法

何段使うか総当りして最後に不足分端を進んで調整して構築します。

コード(01:52:41 4WA)

ID	Verdict	Score
1	AC	3/3
2	AC	11/11
3	AC	21/21

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

int main()
{
  i64 T;
  cin >> T;
  for (i64 _ = 1; _ <= T; _++)
  {
    i64 N;
    cin >> N;
    cout << "Case #" << _ << ":" << endl;
    for (i64 i = 0; i <= 31; i++)
    {
      i64 t = N - i;
      i64 last = -1;
      i64 cnt = 0;
      for (i64 j = 31; 0 <= j; j--)
      {
        if (t & (1LL << j))
        {
          last = max(last, j);
        }
        if (last != -1 && !(t & (1LL << j)))
        {
          cnt++;
        }
      }
      if (cnt <= i)
      {
        cout << "1 1" << endl;
        i64 now = 1;
        bool left = true;
        for (i64 j = 1; j <= last; j++)
        {
          if (t & (1LL << j))
          {
            for (i64 k = 0; k < j + 1; k++)
              cout << j + 1 << " " << (left ? k + 1 : j + 1 - k) << endl;
            left = !left;
            now += (1LL << j);
          }
          else
          {
            cout << j + 1 << " " << (left ? 1 : j + 1) << endl;
            now++;
          }
        }
        for (; now + 1 <= N; last++)
        {
          cout << last + 2 << " " << (left ? 1 : last + 2) << endl;
          now++;
        }
        break;
      }
    }
  }
  return 0;
}

3問目 Square Dance

更新部分だけど更新していけばなんとかなるかなと思いましたが根本的に誤読していて解けませんでした。

競技後

1問目が解けず、全く駄目だなと実感しました。

結果

最終順位が確定し、40点のペナルティが2:08:41で3208位でRound 1Bに進出しました。