Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2014-06-24TopCoder SRM 625 Div2(練習)

TopCoder SRM 625 Div2(練習)

22:50 | TopCoder SRM 625 Div2(練習) - capythm@TopCoder を含むブックマーク はてなブックマーク - TopCoder SRM 625 Div2(練習) - capythm@TopCoder TopCoder SRM 625 Div2(練習) - capythm@TopCoder のブックマークコメント

AddMultiply (250pt)

解法

適当にx[0],x[1]を決めるとx[2]=y-x[0]*x[1]で出てくる。

x[0], x[1]に0,1以外の適当な値をセットして、x[2] が0,1以外になるようにx[1]を動かせば良い。

以下はx[0]=x[1]=2と初期値設定した場合の実装例。

https://ideone.com/JYJKt4

なお、たとえば、x[0]=-2、x[1]=2のようにしておけば、yの条件からx[2]が0,1になり得なくなるのでさらに簡潔に記述出来る。

IncrementingSequence (500pt)

解法

シミュレーション/貪欲法。

ソートして、小さい方からA[i-1] == i になるまで A[i-1]+=kを実行する。

これを繰り返しやって、最終的にユニークな数の数列になるかどうかで判定可能。

以下は実装例。

https://ideone.com/do2klP

ConundrumReloaded (950pt)

考えたこと
  • 文字列にまったく'?'が存在しない場合は矛盾が生じうるので別に判定を行う。
  • 文字列に一つでも'?'が存在する場合は矛盾が生じ得ない。
  • '?'で文字列をスプリットして、文字列の配列v[]を作ったとすると、解はΣf(v[i])で表現可能。
  • f(v[i])では、先頭文字をH/Lの2通りで試してみてシミュレーションを行う。2通りのうち、Lの数が少ない方を選択する。
    • 先述の'?'が全くないパターンに注意する

以下は、上記の考えに基づいて実装を行った例。

https://ideone.com/kPZrku

追記

DPでも解ける。

参考記事: http://kmjp.hatenablog.jp/entry/2014/06/22/1100

  • dp[i][0]:i番目(0-based)の人が正直者だった場合の嘘つきの最小数
  • dp[i][1]:i番目(0-based)の人が嘘つきだった場合の嘘つきの最小数

という状態を考えればいい。0番目の人を正直者/嘘つきの2パターンでシミュレーションをして、小さい方を選択する。

0番目が正直者と仮定したときにN番目が正直者になってないとおかしいので、dp[N][j] (j=0,1)を見てINF以上だったら矛盾していると判定できる。

漸化式は以下の実装例を参照。

https://ideone.com/3VBtPs

2013-07-28

TopCoder SRM 586 練習

23:27 | TopCoder SRM 586 練習 - capythm@TopCoder を含むブックマーク はてなブックマーク - TopCoder SRM 586 練習 - capythm@TopCoder TopCoder SRM 586 練習 - capythm@TopCoder のブックマークコメント

TeamsSelection (Div2Easy)

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12696&rd=15698

解法

シミュレーション。問題文の指示通りの操作をしていけばいい。

ソースコード

http://ideone.com/cywgW2

PiecewiseLinearFunctionDiv2 (Div2 Medium)

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12698&rd=15698

解法

シミュレーション。大小関係が変化するところでカウントアップする。

ソースコード

http://ideone.com/o5yB7r

StringWeightDiv2 (Div2 Hard)

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12695&rd=15698

解法

Lが26以下の場合、Permutation(26,L)が答えになるのは自明(weightは0)。

Lが27以上の場合、weightを極力小さくするためには26文字すべて出現させた上で、なおかつ複数回出現する文字については連続して配置する必要がある。どの文字を何回出現させるかは任意である。たとえばL=28の時はAを3回出現してもいいしA,Bそれぞれ2回ずつ出現させてもいい。

これを数え上げるには、仕切り板を考えればいい。簡単のため文字がA~Zの順に並んでいるとする。各文字の間に仕切り板が入っている。仕切り板の数は25個である。そこに余った文字L-26を仕切り板の任意の場所に挿入していく。余った文字がなんなのかはここでは区別する必要がない。したがって、余った文字の挿入の仕方は

\frac{(L-1)!}{25!(L-26)!}

となる。今A~Zが昇順に並んでいることを仮定していたので、これを任意の順にするには26!を乗ずればいい。したがって、

\frac{26(L-1)!}{(L-26)!}

が解となる。

ソースコード

http://ideone.com/5XxxP7

PiecewiseLinearFunction (Div1 Easy)

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12691&rd=15698

解法

全探索。ただし、全点およびその近傍(+0.5,-0.5)の3回を探索する必要がある(例:整数点だけの探索だと{0,1,0,1}でうまく動作しない。本当は3が解なのに2が出力される)。

小数を扱うのは面倒なので座標をすべて2倍にしてから処理すると、近傍は+1,-1になるので整数点の探索のみで済む。

ソースコード

http://ideone.com/3ddoqM

History (Div1 Medium)

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12692&rd=15698

解法

君主がかぶっている情報から、国家間の西暦オフセットの最小値と最大値を導出する。

入力に存在しない国家間については上記情報から補完する必要がある。これにはワーシャル・フロイド法などを用いる。たとえばA-C間のオフセット情報がなくて、A-B間とB-C間の情報が存在する場合、A-C間のオフセット値はA-B間のオフセット値とB-C間のオフセット値の和になるはずである。これを全国家をpivotとして全国家間のrefineを進めると全国家間の一番厳しいオフセット値制約が導かれる。

その後、query入力のオフセット値を計算して、それが範囲外かどうかをチェックする。

ソースコード

http://ideone.com/id5TUL

2013-07-12

TopCoder SRM 584 (練習)

16:23 | TopCoder SRM 584 (練習) - capythm@TopCoder を含むブックマーク はてなブックマーク - TopCoder SRM 584 (練習) - capythm@TopCoder TopCoder SRM 584 (練習) - capythm@TopCoder のブックマークコメント

TopFox (Div2 Easy)

題意

文字列が2つ与えられる。先頭n文字(n>=1)を連結した場合のユニークな文字列のパターン数は?

http://community.topcoder.com/stat?c=problem_statement&pm=12643&rd=15696

解法

重複があるので単純な数式では計算できない。全探索。

ソースコード

http://ideone.com/mlvRu0

Egalitarianism (Div2 Medium, Div1 Easy)

題意

グラフがある。自分の値と隣接ノードの値の差の最大値をdとしたとき、グラフ内の任意の2点の値の差の最大値はいくつか。無限大の場合は-1を返せ。

http://community.topcoder.com/stat?c=problem_statement&pm=12613&rd=15696

解法

隣接ノード間距離を1としたとき、全ノード間について最短距離を算出して、その最大値×dが答え。

最短距離導出にはワーシャル・フロイド法を使ってもいいが、単にBFSをノード数だけ回す方が簡単。

ソースコード

http://ideone.com/lBNixZ

Excavations2 (Div2 Hard)

題意

n個の建物(0~n-1)がある。建物の種類は1~50の番号で分類できる。それぞれの建物の種類はkind[i]である。

n個の建物をK個選択した結果、種類がfound[]となった。

その場合の建物の選択の仕方は何パターンあるか。

http://community.topcoder.com/stat?c=problem_statement&pm=12644&rd=15696

解法

DP

found[i]の種類の建物を何個か選択した結果、残りがjとなったとしたときのパターン数をdp[i+1][j]とすると、

dp\[i+1\]\[j\]=\sum_k dp\[i\]\[k\]\times Comb(num,k-j)

で表現できる。ここで、numは種類がfound[i]の建物の個数を表している。1つ前で残数k(k>j)からk-j個消費した場合のCombinationを乗じて総和すれば求まる。

ソースコード

http://ideone.com/4d7HNz

2013-04-14

Google Code Jam 2013 Qualification Round

18:22 | Google Code Jam 2013 Qualification Round - capythm@TopCoder を含むブックマーク はてなブックマーク - Google Code Jam 2013 Qualification Round - capythm@TopCoder Google Code Jam 2013 Qualification Round - capythm@TopCoder のブックマークコメント

C-large1まで解いて 115pt、3123位でした。

Problem A. Tic-Tac-Toe-Tomek

問題概要
  • 4x4マスの盤面でX、Oが交互に置いていって先に縦横斜めのいずれか1列を並べた方が勝ち
  • もともと盤面に置いてあるTも含めて縦横斜め1列並べても勝ち
  • 盤面が与えられるのでどちらが勝っているか判定せよ。
解法

実装するだけ

ソースコード
#include <iostream>
#include <string>
using namespace std;
string s[4];
int is_won( char c )
{
  int flag;
  for( int i=0; i<4; i++ ){
    flag=1;
    for( int j=0; j<4; j++ ){
      if( s[i][j] != c && s[i][j] != 'T' ){
        flag=0; break;
      }
    }
    if( flag ) return 1;
  }
  for( int i=0; i<4; i++ ){
    flag=1;
    for( int j=0; j<4; j++ ){
      if( s[j][i] != c && s[j][i] != 'T' ){
        flag=0; break;
      }
    }
    if( flag ) return 1;
  }
  flag=1;
  for( int i=0; i<4; i++ ){
    if( s[i][i] != c && s[i][i] != 'T' ){
      flag=0; break;
    }
  }
  if( flag ) return 1;
  flag=1;
  for( int i=0; i<4; i++ ){
    if( s[i][3-i] != c && s[i][3-i] != 'T' ){
      flag=0; break;
    }
  }
  if( flag ) return 1;
  return 0;
}
int main( void )
{
  int T;
  string r;
  cin >> T;
  for( int testcase=1; testcase<=T; testcase++ ){
    getline( cin, r );
    for( int i=0; i<4; i++ ){
      getline( cin, s[i] );
    }
    r = "Game has not completed";
    if( is_won( 'X' ) ) r = "X won";
    else if( is_won( 'O' ) ) r = "O won";
    else {
      int cnt=0;
      for( int i=0; i<4; i++ )
        for( int j=0; j<4; j++ )
          if( s[i][j] == '.' ) cnt++;
      if( cnt == 0 ) r = "Draw";
    }
    cout << "Case #" << testcase << ": " << r << endl;
  }
  return 0;
}

Problem B. Lawnmower

問題概要

芝がN×Mマスに長さ100mm生えている。芝刈り機で四角形の辺の端から端まで垂直に一定の長さにカットすることができる。芝の長さパターンが与えられるので、それが芝刈り機で作成できるパターンかどうか判定せよ

考えたこと
  • 縦方向と横方向にカットする順はどちらでも結果が同じになりカット順は依存しない。
  • カットする長さはカット後の芝の長さ1列/1行分の最大値になる。
  • カット後の芝の長さは縦と横の芝刈り機の設定値の小さい方になる
  • カット後の芝の長さが与えられたパターンと一致していたら"YES"、そうでないなら"NO"
ソースコード
#include <iostream>
#include <algorithm>
using namespace std;
int main( void )
{
  int T,N,M,a[128][128],b[2][128];
  cin >> T;
  for( int testcase=1; testcase<=T; testcase++ ){
    cin >> N >> M;
    for( int i=0; i<2; i++ ) for( int j=0; j<128; j++ )
      b[i][j]=0;
    for( int y=0; y<N; y++ ){
      for( int x=0; x<M; x++ ){
        cin >> a[y][x];
        b[0][y] = max( b[0][y], a[y][x] );
        b[1][x] = max( b[1][x], a[y][x] );
      }
    }
    int flag=1;
    for( int y=0; y<N; y++ ){
      for( int x=0; x<M; x++ ){
        if( a[y][x] != min( b[0][y], b[1][x] ) ){
          flag=0;
          goto END;
        }
      }
    }
END:
    cout << "Case #" << testcase << ": " << ((flag) ? "YES" : "NO") << endl;
  }
  return 0;
}

Problem C. Fair and Square

問題概要

a,bの2数が与えられる。aからbまでの範囲で、回文になっており、なおかつ回文になっている数字の平方数であるような数の個数を出力せよ

  • small:1000まで、large1:10^{14}まで、large2:10^{100}まで
考えたこと
  • large1までの解法を考える。
  • 回文の平方数が回文になっているかどうかを判定する方針。
  • 回文を作るには、小数点の位置で鏡を置く感じで。
  • ループ回数は、10の14乗までなら、平方なので半分の10の7乗、回文なのでさらに半分の10の4乗程度までで済む。
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
ll make_palindrome( ll n, int f )
{
  ll a=0,b=n,c=1;
  while( b > 0 ){
    a = a*10 + b % 10;
    b /= 10;
    c *= 10;
  }
  if( !f ) n /= 10;
  return n*c + a;
}
int is_palindrome( ll a )
{
  int d[32],n=0;
  while( a > 0 ){
    d[n++] = a % 10;
    a /= 10;
  }
  for( int i=0; i<n/2; i++ )
    if( d[i] != d[n-1-i] ) return 0;
  return 1;
}
int main( void )
{
  vector<ll> v;
  ll a = 1;
  for( int i=1; i<=4; i++ ){
    for( int j=0; j<=1; j++ ){
      for( ll k=a; k<=a*10-1; k++ ){
        ll b = make_palindrome( k, j );
        b *= b;
        if( is_palindrome( b ) ){
          v.push_back( b );
        }
      }
    }
    a *= 10;
  }
  int T;
  cin >> T;
  for( int testcase = 1; testcase <= T; testcase++ ){
    ll a,b;
    cin >> a >> b;
    int r=0;
    for( int i=0; i<v.size(); i++ ){
      if( a <= v[i] && v[i] <= b )
        r++;
    }
    cout << "Case #" << testcase << ": " << r << endl;
  }
  return 0;
}

2013-01-30

Facebook Hacker Cup 2013 Qualification Round

13:48 | Facebook Hacker Cup 2013 Qualification Round - capythm@TopCoder を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2013 Qualification Round - capythm@TopCoder Facebook Hacker Cup 2013 Qualification Round - capythm@TopCoder のブックマークコメント

3問とも一応合ってました。

Beautiful strings (20pt)

問題

https://www.facebook.com/hackercup/problems.php?pid=475986555798659&round=185564241586420

解法

greedyで解く。

  • 各文字の登場回数をカウント
  • ソートして登場回数が多いものほど高い得点を与える。
ソースコード
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main( void )
{
  int n;
  string s;
  cin >> n;
  getline( cin, s );
  for( int testcase=1; testcase<=n; testcase++ ){
    int a[26];
    for( int i=0; i<26; i++ ) a[i] = 0;
    getline( cin, s );
    for( int i=0; i<s.size(); i++ ){
      if( 'A' <= s[i] && s[i] <= 'Z' )
        s[i] += 'a' - 'A';
      if( 'a' <= s[i] && s[i] <= 'z' )
        a[s[i]-'a']++;
    }
    sort( a, a+26 );
    int ret=0;
    for( int i=0; i<26; i++ ) ret += (i+1) * a[i];
    cout << "Case #" << testcase << ": " << ret << endl;
  }
  return 0;
}

Balanced Smileys (35pt)

問題

https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420

解法

コロンを顔文字とするかしないかの両方を考慮する必要があるので、DFSで探索。

ソースコード
#include <iostream>
#include <string>
using namespace std;
int dfs( string s, int idx, int depth )
{
  if( depth < 0 ) return 0;
  if( idx == s.size() ){
    if( depth == 0 ) return 1;
    else return 0;
  }
  if( 'a' <= s[idx] && s[idx] <= 'z' )
    return dfs( s, idx+1, depth );
  else if( s[idx] == ' ' )
    return dfs( s, idx+1, depth );
  else if( s[idx] == '(' )
    return dfs( s, idx+1, depth+1 );
  else if( s[idx] == ')' )
    return dfs( s, idx+1, depth-1 );
  else if( s[idx] == ':' ){
    if( idx+1 < s.size() && ( s[idx+1] == ')' || s[idx+1] == '(' ) ){
      int ret = dfs( s, idx+2, depth );
      if( ret == 1 ) return 1;
    }
    return dfs( s, idx+1, depth );
  }
  return 0;
}
int main( void )
{
  int T;
  string s;
  cin >> T;
  getline( cin, s );
  for( int i=1; i<=T; i++ ){
    getline( cin, s );
    cout << "Case #" << i << ": ";
    cout << (dfs(s,0,0) ? "YES" : "NO") << endl;
  }
  return 0;
}

Find the Min (45pt)

問題

https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420

解法

数列はk番目の要素以降は周期k+1になるので、k~2k+1番目の要素がわかればいい。

k~2k+1番目の要素を決定する際、0~kが直前のk要素に含まれているか判定し、含まれていない最小のものを選択する必要がある。

これを愚直にするとO(k^2)となり、k=100000なので間に合わない。

私の解法では、毎回先頭から探索せずに無駄な探索を省くことで高速化を行っているが、最悪時はO(k^2)なので本当はNG。

priority_queueを使う方法が賢いらしい(未検討)

ソースコード
#include <iostream>
#include <algorithm>
using namespace std;
int m[100005];
int s[100005];
int d[100005];
int main( void )
{
  int T;
  cin >> T;
  for( int testcase=1; testcase<=T; testcase++ ){
    long long n,k,a,b,c,r;
    cin >> n >> k;
    cin >> a >> b >> c >> r;

    for( int i=0; i<k+1; i++ ){
      m[i] = -1; d[i] = 0;
    }
    if( a <= k ){
      m[0] = a; d[a]++;
    }
    for( int i=1; i<k; i++ ){
      a = ( b * a + c ) % r;
      if( a <= k ){
        m[i] = a; d[a]++;
      }
    }
    int idx=0;
    for( int i=k; i<2*k+1; i++ ){
      if( d[m[i%(k+1)]] >= 0 ){
        d[m[i%(k+1)]]--;
        if( d[m[i%(k+1)]] == 0 && idx > m[i%(k+1)] )
          idx = m[i%(k+1)];
      }
      while( d[idx] ) idx++;
      s[i%(k+1)] = idx;
      d[idx]++;
      idx++;
    }

    cout << "Case #" << testcase << ": "
         << s[(n-1) % (k+1)] << endl;
  }
}