読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2016 - Round 1A

4/16(土) 10:00〜12:30
Bで躓いて順当にRound 1B進出をキメました*1…orz
いずれにせよ、100点取ってないと(取ってても)上位1000人には入れなかったようなので、1Bでまた頑張ります…


A. The Last Word

与えられた文字列から1文字ずつ、これまでに書いた右端か左端に書き足して行って、辞書順で一番後ろになる単語にしたい問題。
左か右に1文字ずつ、辞書順で出来るだけ後ろになるように貪欲に足して行くだけで良いのでは?→良かった
(こういうのを目をつぶってても出来るようになりたい)

#include <iostream>
#include <string>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)

string solve(string& s) {
  int l = s.size();
  string a;
  rep(i,l){
    if (a+s[i] > s[i]+a)
      a += s[i];
    else
      a = s[i] + a;
   }
  return a;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    string S; cin >> S;
 answer:
    cout << "Case #" << (1+_t) << ": " << solve(S) << endl;
  }
}

B. Rank and File

左から・上から小さい順に並んでる二次元の数列があって、各行・各列の構成をメモってあったんだけど風に飛ばされて1本紛失してしまった&縦横ごっちゃになってしまった。紛失した1本はどんな構成だったか。

それぞれの数が使われる回数を数えればいいのでは?と一瞬思いついたんだけど、
それで行けないケースもあるのでは?とか思っちゃってそっちに行かなかったのが悔やまれる
(strictlyにincreasingってことは、答えになる数字の使用頻度はすべて奇数だから、それで行けるんだよね)

例えばこんな感じか

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

int N;
vector<vector<int> > L; // 2N-1, N

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> N;
    // 2N-1 lines, N fields each
    L.clear();
    rep(i, 2*N-1) {
      vector<int> x(N); rep(j,N) cin >> x[j];
      L.push_back(x);
    }
    sort(all(L));

    map<int,int> st;
    rep(i,2*N-1) {
      rep(j,N){
        st[ L[i][j] ]++;
      }
    }

    set<int> odd;
    tr(it,st) {
      if (it->second % 2) odd.insert(it->first);
    }

    cout << "Case #" << (1+_t) << ":";
    tr(it,odd) cout << " " << *it;
    cout << endl;
  }
}

ソートしたLを見ながら左上から組み上げていくやつを書こうと頑張ってて
ちゃんと実装できずに沈没

実装できてたらどうだったか

実装してみたけど、答えは合うけど、B-large-practice.inでCase #29がいつまで経っても帰ってこない。

#include <iostream>
#include <vector>
using namespace std;
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int N;
vector<vector<int> > L; // 2N-1, N

vector<int> horiz, vert;

int sub(int hx, int vx, int wild) {
  if (hx == N && vx == N) return (wild== 1);
  int ofs = hx + vx - wild;

  // 1. use L[ofs] for hx (if hx < N)
  // 2. use L[ofs] for vx (if vx < N)
  // 3. use -1 for hx (if hx < N && wild == 0)
  // 4. use -1 for vx (if vx < N && wild == 0)
  bool z = false;
  if (hx < N) {
    horiz[hx] = ofs;
    // check
    bool good=true;
    rep(i,vx) {
      if (vert[i] == -1) continue;
      if (L[vert[i]][hx] != L[ofs][i]) { good=false; break; }
    }
    if (good) {
      z = sub(hx+1, vx, wild);
      if (z) return true;
    }

    if (!wild) {
      horiz[hx] = -1;
      // no need to check
      z = sub(hx+1, vx, 1);
      if (z) return true;
    }
  }
  if (vx < N) {
    vert[vx] = ofs;
    // check
    bool good=true;
    rep(i,hx) {
      if (horiz[i] == -1) continue;
      if (L[horiz[i]][vx] != L[ofs][i]) { good=false; break; }
    }
    if (good) {
      z = sub(hx, vx+1, wild);
      if (z) return true;
    }

    if (!wild) {
      vert[vx] = -1;
      // no need to check
      z = sub(hx, vx+1, 1);
      if (z) return true;
    }
  }
  return false;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> N;
    // 2N-1 lines, N fields each
    L.clear();
    rep(i, 2*N-1) {
      vector<int> x(N); rep(j,N) cin >> x[j];
      L.push_back(x);
    }
    sort(all(L));
    L.push_back(vector<int>(N, -1));

    horiz.assign(N, -1);
    vert.assign(N, -1);

    int z = false;
    if (L[0][0] == L[1][0]) {
      horiz[0] = 0;
      vert[0] = 1;
      z = sub(1, 1, 0);
    } else {
      horiz[0] = 0;
      vert[0] = -1;
      z = sub(1, 1, 1);
    }

    vector<int> ans(N, -1);
    rep(i,N) {
      if (horiz[i] == -1) {
        rep(j,N) ans[j] = L[vert[j]][i];
        break;
      } else if (vert[i] == -1) {
        rep(j,N) ans[j] = L[horiz[j]][i];
        break;
      }
    }

    cout << "Case #" << (1+_t) << ":";
    rep(i,N) cout << " " << ans[i];
    cout << endl;
  }
}

C. BFFs

Bで躓いてて開かなかった問題;
子供がN人いて、それぞれにお気に入り(自分ではない)が1人いて、自分の隣り(左右どちらか)にそのお気に入りがいるような輪を最大何人で作れるか、という問題。そんなに難しそうじゃないじゃん…

子供1人1人をスタート地点にして、そこからBFFを辿っていくとどこに行き着くか、

  • スタートに戻る場合→円が1つできる。これを使うと他の子は使えない。←いや、2人で構成されるループは独立した弧と同じだから円の一部を構成できる
  • 最後の2人でループする(というかゴール手前に戻って終わる)→弧が1本できる。同じループに反対側から入る他の弧と合体可能。(合体しようがしまいが)円の一部を構成できる
  • それ以外→サークル状に出来ないから使えない

ゴールが共通な弧は一番長いやつを採用。F[ゴール]で終わる弧と合体できる。

円のイメージしか持ってなかったけど、独立した弧をいくつも(任意の順番で)円状に並べたものでもいいんだよね…
(愚直に実装したものに答えが合うように実装して行ったけど、多分これまっすぐ行けててもSmallで4 wrong triesぐらいしてたと思う)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N; cin >> N; // 3-10, 3-1000
    vector<int> F(N);
    rep(i,N) { //  // 1-N; F_i != i for all i
      int fi; cin >> fi;
      F[i] = fi - 1;
    }

    int best = 0;
    vector<vector<int> > loops, isles, isle2s;
    map<int, vector<int> > thread_tails;
    rep(i,N) {
      vector<int> v;
      int h = i;
      v.pb(h);
      while (true) {
        int next = F[h];
        vector<int>::iterator wh = find(all(v), next);
        if (wh == v.end()) {
          // not found
          v.pb(next);
          h = next;
        } else {
          // found
          int ix = (int)(wh - v.begin());
          if (ix == 0) {
            // valid (loop)
            if (v.size() == 2) {
              isle2s.pb(v);
              best = max(best, 2);
            } else {
              loops.pb(v);
              best = max(best, (int)v.size());
            }
          } else if (ix == v.size()-2) {
            // valid (thread)
            if (found(thread_tails,h)) {
              if (v.size() > thread_tails[h].size()) {
                thread_tails[h] = v;
              }
            } else {
              thread_tails[h] = v;
            }
            best = max(best, (int)v.size());
          } else {
            // invalid
          }
          break;
        }
      }
    }

    rep(i,N) {
      if (!found(thread_tails,i)) continue;
      if (!found(thread_tails,F[i])) {
        isles.pb(thread_tails[i]);
        continue;
      }
      if (F[i] < i) continue;
      int len = thread_tails[i].size() + thread_tails[F[i]].size() - 2;
      vector<int> tmp;
      tmp.insert(tmp.end(), all(thread_tails[i]));
      tmp.insert(tmp.end(), thread_tails[F[i]].begin(), thread_tails[F[i]].begin()+thread_tails[F[i]].size()-2);
      reverse(tmp.begin()+thread_tails[i].size(), tmp.end());
      isles.pb(tmp);
      best = max(best, len);
    }

    if (isles.size() > 0 || isle2s.size() > 0) {
      // composite loop<2>
      int sum = 0;
      vector<int> tmp;
      set<int> visited;
      rep(i, isles.size()) {
        if (found(visited, isles[i][0])) continue;
        visited.insert(all(isles[i]));
        tmp.insert(tmp.end(), all(isles[i]));
        sum += isles[i].size();
      }
      rep(i, isle2s.size()) {
        if (found(visited, isle2s[i][0])) continue;
        visited.insert(all(isle2s[i]));
        tmp.insert(tmp.end(), all(isle2s[i]));
        sum += isle2s[i].size();
      }
      best = max(best, sum);
    }


 answer:
    cout << "Case #" << (1+_t) << ": " << best << endl;
  }
}

愚直版

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N; cin >> N; // 3-10, 3-1000
    vector<int> F(N);
    rep(i,N) { //  // 1-N; F_i != i for all i
      int fi; cin >> fi;
      F[i] = fi-1;
    }

    vector<int> a(N); rep(i,N) a[i]=i;
    int best = 0;
    do {
      for (int L=N; L>0; --L) {
        // [0..N)
        int active = 0;
        rep(i,L) {
          int left = (i-1+L) % L, right = (i+1) % L;
          int here = a[i];
          int ff = F[here];
          if (a[left] == ff || a[right] == ff) ++active;
        }
        if (active == L) {
          vector<int> tmp(a.begin(), a.begin()+active);
          if (active > best) {
              cout << active << " " << tmp << endl;
              best = max(best, active);
          }
          break;
        }
      }
    } while (next_permutation(all(a)));


 answer:
    cout << "Case #" << (1+_t) << ": " << best << endl;
  }
}

*1:ここを読んでる方はご存知だと思いますが、1A,1B,1Cの3回のチャンスのどれかで上位1000人に入ればRound 2に進出できる仕組みです