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

naoya_t@hatenablog

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

Yandex.Algorithm 2013 Online Round 2

Programming Contest

モスクワ標準時で13時(日本時間で18時)から
1時間40分

6問中2問(D,F)だけAC
178位

A. Degree Sequence

グラフ問題
後回し

B. Frogs

とりあえず問題文が何を言おうとしているのかシミュレーションコードを書いてみたけど答えが合わないし
どゆこと?
Jury messagesにコメントがあるの見落としてた
パス

C. Green Triangle

2000C3 > 1e9通り全パターン見るの無理…だよね?
期待値をΣΣΣなんとかでなんか綺麗に出せる方法あるのかなと色々思案してみたものの思いつかずパス

D. MathWorlds

Standings見たらみんなこれから解いてるじゃん
なーんだ
これ簡単
と思ってたら

  • デバッグ用の #include <cout.h> を外し忘れていてCE(コンパイルエラー)
  • x / y = z のケースを x = yz で判定していて、y=0判定をしていなくてWA

3度目でAC

E. Small Cycltes

グラフ問題
読んでない

F. Swap Balls

Sample 2 の "5 8 58" て何
RGB - GRB - GBR - BGR - BRG - RBG で六角形のグラフを作って、その中をぐるぐる回る感じで書いてみた。
f:id:n4_t:20130719141713p:plain

  • 同じ手を2つ繰り返すと同じノードに戻れることを利用。(a, b, c) 手で可能なものは (a+2i, b+2j, c+2k) 手でも可能。
  • 全パターン網羅するのに何手あればいいのかぱっとわからないので、大きめのつもりで36の剰余で
  • 36の剰余の場合、36の倍数だと0になっちゃってアウト(WAを繰り返したのはこれが原因)なので、n%36 == 0 なら36にするとか
  • メモ化にmap<int,bool>を使ったらTLE食らったのでvector<bool>で
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back

typedef long long ll;

vector<int> mm(1<<21, -1);

bool solve(int p, int q, int r, int d) {
  int k = p | (q << 6) | (r << 12) | (d << 18);
  if (mm[k] >= 0) return mm[k];

  if (d == 0 && p % 2 == 0 && q % 2 == 0 && r % 2 == 0) return mm[k]=1;
  switch (d % 2) {
    case 0:
      if (p>0 && solve(p-1,q,r,(d+1)%6)) return mm[k]=1;
      if (q>0 && solve(p,q-1,r,(d+3)%6)) return mm[k]=1;
      if (r>0 && solve(p,q,r-1,(d+5)%6)) return mm[k]=1;
      break;
    case 1:
      if (p>0 && solve(p-1,q,r,(d+5)%6)) return mm[k]=1;
      if (q>0 && solve(p,q-1,r,(d+3)%6)) return mm[k]=1;
      if (r>0 && solve(p,q,r-1,(d+1)%6)) return mm[k]=1;
      break;
  }
  return mm[k]=0;
}

map<string,int> id;

main() {
  int p, q, r;
  cin >> p >> q >> r;
  string s;
  cin >> s;

  id["RGB"] = 0;
  id["GRB"] = 1;
  id["GBR"] = 2;
  id["BGR"] = 3;
  id["BRG"] = 4;
  id["RBG"] = 5;

  int M = 36;

  int p_ = p%M; if (p > 0 && p_ == 0) p_ = M;
  int q_ = q%M; if (q > 0 && q_ == 0) q_ = M;
  int r_ = r%M; if (r > 0 && r_ == 0) r_ = M;

  cout << (solve(p_,q_,r_,id[s]) ? "Yes" : "No") << endl;
}