SRM517 Div1

初めてHighest更新して嬉しいのでカキカキ

○○☓ 404.12pt
Rating: 1538→1687

わかれば、コードは簡単な感じの問題セットで、面白かった。

250 CompositeSmash

Nをスマッシュすると、約数2つにランダムに分解される。
(例:12をスマッシュすると、4-3、2-6のいずれかになる)
ある数値Nとtargetに対して、Nをスマッシュしていくことによって確実にtargetをつくり出せるかどうかという問題。

最初はtarget == Nか、targetが素数でNを割り切れればYESという解答を出した。
でもよく考えると、N=8、target=4はYESになる。
なんかtargetが素数の2乗なら行けるのかなぁ、などと思ったけど自身がなかったので、実際に分解していってみる探索コードにした。計算量は読みにくいが、メモ化することで計算量は減らせておそらく大丈夫という判断。
リサブミットは痛かったけど、最初に甘く考えすぎたのが悪い。

以下コード

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#include <cstdio>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
 
using namespace std;
 
class CompositeSmash {
public:
  string thePossible(int N, int target);
  
 
};
 
const int MAX = 100001;
int memo[MAX];
int t;
 
bool solve(int N){
  if(memo[N] != -1) return memo[N];
 
  if(N == t) return memo[N] = true;
  if(N % t != 0) return memo[N] = false;
 
  for(int i = 2; i * i <= N; i++){
    if(N % i == 0){
      int j = N / i;
 
      if((!solve(i)) && (!solve(j))){
  return memo[N] = false;
      }
    }
  }
 
  return memo[N] = true;
}
 
string CompositeSmash::thePossible(int N, int target){
  t = target;
  REP(i,MAX) memo[i] = -1;
  return solve(N) ? "Yes" : "No";
}

600 AdjacentSwaps

N個の数値が並んでいて、各数値間に間にうさぎがいて、各うさぎ(全員)が左右の数値を入れ替える。
最終的に0 1 2 ... になるような入れ替えの順序の総数を求める問題。

最初は、各数値を正しい場所に移動させるためには入れ替える順序に制約が発生するので、その制約を満たすような順序を数え上げる感じで考えていたけど、全く方法が思い浮かばなかった。トポロジカルみょんみょん。
次の発想は、ある場所を入れ替えると、「そこより左にある数値」と「そこより右にある数値」はもう永久に入れ替えられない。
ということは、i番目とi+1番目を入れ替えたあとには、0〜i番目は0〜iの数値、i+1〜Nまでは、i+1〜Nの数値になっていないとおかしい。
この発想を使えば、今入れ替えることが出来る場所が限定される。
あとは入れ替えられる場所を入れ替えてみながら全探索していけば答えがでる。
左端の位置と右端の位置でメモ化しながらやれば、O(N^3)くらい。
コンビネーションをかけるのを忘れていて手間取ったが、なんとか解けた。

以下コード

#include <iostream>
#include <sstream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)
 
typedef long long ll;
 
using namespace std;
 
class AdjacentSwaps {
public:
  int theCount(vector <int> p);
  
 
};
 
int a[50];
int c[51][51];
int n;
int memo[51][51];
const ll mod = 1000000007;
 
int gcd(int a, int b){
  if(a > b) swap(a, b);
  if(a == 0) return b;
  return gcd(a, b % a);
}
 
int comb(int n, int k){
  if(k > n - k) k = n - k;
  vector<int> ue(k);
  vector<int> sita(k);
 
  REP(i,k){
    ue[i] = n - i;
    sita[i] = i + 1;
  }
 
  REP(i,k) REP(j,k){
    int tmp = gcd(ue[i], sita[j]);
    if(tmp != 1){
      ue[i] /= tmp;
      sita[j] /= tmp;
    }
  }
 
  ll ret = 1;
  REP(i,k) ret = (ret * ue[i]) % mod;
 
  return static_cast<int>(ret);
}
 
int solve(int l, int r){
  // [l, r)
  if(memo[l][r] != -1) return memo[l][r];
  if(r == l + 1) return 1;
 
  ll ret = 0;
 
  int maxval = 0;
 
  for(int i = l; i < r - 1; i++){
    maxval = max(maxval, a[i]);
 
    if((a[i + 1] <= i) &&
       ((maxval <= i) || (maxval == a[i] && a[i] >= i + 1))){
      swap(a[i], a[i + 1]);
 
      ll ans1 = static_cast<ll>(solve(l, i + 1));
      ll ans2 = static_cast<ll>(solve(i + 1, r));
 
      int lcnt = i - l;
      int rcnt = (r - l - 1) - 1 - lcnt;
 
      ret = (ret + (((ans1 * ans2) % mod) * c[lcnt + rcnt][lcnt]) % mod) % mod;
 
      swap(a[i], a[i + 1]);
    }
  }
  
  memo[l][r] = static_cast<int>(ret);
  return memo[l][r];
}
 
int AdjacentSwaps::theCount(vector <int> p){
  n = p.size();
  REP(i,n) a[i] = p[i];
  REP(i,51)REP(j,51){
    memo[i][j] = -1;
    if(i >= j) c[i][j] = comb(i,j);
  }
  return solve(0, n);
}

900 ColorfulBoard

全面白のN*Mのタイルがある。縦or横一列を選んでその一列に任意の一色を塗れる。指定されたパターンを塗るのに最速な塗り方をした場合の塗る回数は。という問題。

問題開いた時には残り時間5分くらいで、チャレンジフェーズのために読んだ感じ。
私では方針も思い浮かびません。
撃墜ケース的にも、最大ケースを渡すくらいしかなさそうだった。

チャレンジフェーズ

250で同じミスをしている人を探して、周りのコード見たけど、誰も同じ間違いはしていなかった。
ちょっと残念。
結局とくにチャレンジせずに終了。

感想

今までは初回にとったレーティングがHighestで、成長してる感が全くなかったけど、今回更新できたので大きな一歩だと思う。
気を抜いてると次回で一気に下がりそうなので、次回も頑張りたい。