Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2012-04-11

Codechef April Challenge 2012

23:01

Ruby使えるしなんとなく参加.

結果は7問とSIMGRAPH解いて7.385pts / 36th.

75分とか2時間とかのコンテストと違って,焦らずゆっくり考えられるのが良かった.


Double Strings(DOUBLE)

N文字の回文が与えられたとき,文字の削除と並び替えだけで/^(.*)\1$/型の文字列に変形したい.最大で何文字の文字列が得られるか,という問題.

Nが偶数なら回文の後半を反転させればよい.奇数文字だと回文の軸が邪魔になるので,それを除く.

#!/usr/bin/ruby

t = gets.to_i
t.times do
  n = gets.to_i
  n -= 1 if n.odd?
  p n
end

Fit to Play(PLAYFIT)

数列anから2つの要素aiとaj(i < j)を取ってきて,aj-aiの値をできるだけ大きくしたい.差が0より大きくできないならUNFITと出力する.

前から舐めていって,最小値と解を同時に更新していけばO(N).

Rubyだと手元でTLEぽかったので投げてない.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int T;
    scanf("%d", &T);

    while(T--) {
        int N;
        scanf("%d", &N);

        int ans = 0;
        int minval = 0;
        for(int i = 0; i < N; ++i) {
            int v;
            scanf("%d", &v);
            if(i == 0) {
                minval = v;
            }
            else {
                minval = min(minval, v);
                int diff = v-minval;
                ans = max(ans, diff);
            }
        }

        if(ans == 0) {
            puts("UNFIT");
        }
        else {
            printf("%d\n", ans);
        }
    }

    return 0;
}

Greatest Dumpling Fight(DUMPLING)

数直線上に2つの点があり,そのうちの1つは±Aか±Bずつ移動でき,もう1つは±Cか±Dずつ移動できる.絶対値がK以下で,どちらの点も到達可能な場所は何箇所あるか.

最初の点だけで考えると,移動可能な最小単位の下限はGCD(A,B)であることはすぐ分かる.このとき拡張ユークリッドの互除法から,nA+mB=GCD(A,B)となるnとmが必ず存在するため,結局GCD(A,B)刻みの移動が可能であることが分かる.もう一方の点についても同様.

2点ともが移動可能な点は,これら最小ステップのLCMごとに出現する.

#!/usr/bin/ruby

gets.to_i.times do
  a,b,c,d,k = gets.split.map(&:to_i)

  pstep = a.gcd(b)
  sstep = c.gcd(d)
  step = pstep.lcm(sstep)

  p (k/step)*2+1
end

Stacking Pancakes(PANSTACK)

整数の直径を持つN個の丸いパンケーキを積み上げたい.任意のパンケーキは,それより下にあるパンケーキのうち一番大きいものより,2以上大きくなってはいけない.大きさの選び方は何通り存在するかMOD 1000000007で求めよ.

ある高さNで最大の直径がRになるとき,これは高さN-1,最大径RのところにR以下のパンケーキを置くか,最大径R-1のところに径Rのパンケーキを置くかのどちらかである.したがって[高さ][最大の直径]でDPして,dp[N][R] = dp[N-1][R]*R + dp[N-1][R-1]で求められる.

これも例によってRubyだとTLEする.

#include <cstring>
#include <cstdio>

using namespace std;

const unsigned MOD = 1000000007;
unsigned dp[1001][1001];

int main() {
    dp[1][1] = 1;
    for(int i = 2; i <= 1000; ++i) {
        for(int r = 1; r <= i; ++r) {
            unsigned long long tmp = (unsigned long long)dp[i-1][r]*r + dp[i-1][r-1];
            dp[i][r] = (unsigned)(tmp % MOD);
        }
    }

    int T;
    scanf("%d", &T);
    while(T--) {
        int N;
        scanf("%d", &N);
        unsigned ans = 0;
        for(int i = 1; i <= N; ++i) {
            ans += dp[N][i];
            ans %= MOD;
        }
        printf("%d\n", ans);
    }

    return 0;
}

最初は毎回DP表を計算していて,無理ゲーだと思って埋め込みに走ってしまったのでスコアボードがあれ…….

PDS Number(PDSNUM)

ある数xを10進数で表記し,各桁の数字の積が各桁の数字の和で割り切れるとき,xはPDS Numberであるという.N番目(N ≦ 109)のPDS Numberを求めよ.

Project Eulerっぽい.とりあえずRubyでナイーブに書いてみて,かなり密に分布していることと,0がどこかにあると積が0になるため必ずPDS Numberになることを確認する.

条件の範囲では求めるPDS NumberはNと同程度のオーダーで収まるっぽいので,和として有り得る数値は高々90通りくらいしかない.最初は和を列挙して素因数分解かなーと思ったのだが,約数条件と総和条件がうまくまとめられないので却下.

問題の雰囲気からして順列のN番目を求める問題なので,よくある感じに再帰で探索する方法を考える.で,いろいろやってると「n桁で総和がsになる数の個数」は「先頭hを0-9のどれかに決め,残りはn-1桁で総和がs-hになる数の個数」と再帰的に表せることに気づく.しかもこれ,探索空間がすごく狭い.

あとはこの数え上げと同時に,それまでの積も持ち回すようにすれば約数判定ができる.更に総和を先に決めておくので,探索の途中で積が総和で割り切れるようになったらその時点で枝刈りができる.よく分からないが,これくらいやれば求められるのではないか?

というわけでRubyで書く.積の取り得る値は上限1010通りくらいあるのだが,0をかけたらずっと0だし,1は積を変えない.しかも上位の桁ほど空間は狭いし総和条件も絡むとそんなにパターンないのでは?と予想して(桁,総和,積)の3つ組で適当にメモ化する*1

で,投げる.TLE.残りの桁を全部9にしても総和条件を満たさない時などで枝刈りを入れて高速化する.TLE.手元(Core2Duo 1.2GHz)でそこそこ速いので,RubyはTLE3倍らしいしChefのサーバががんばれば通ると思うんだけどなーと考えつつFAQ見ると,

Solutions are tested on equal PIII 733 MHZ processors.

悲しみ.仕方ないのでC++に直訳したら通った…….

なお,桁を固定してパターン数を数え上げるとき,最初は全ての総和について毎回計算していたのだが,これもメモ化できることに気づいたのでmemo3でメモ化している.

#include <cstdio>
#include <vector>
#include <ext/hash_map>
#include <cstring>

using namespace std;
using namespace __gnu_cxx;

/////////////////// メモ化用 //////////////////////
struct Tag {
    int n, rem, prod;

    Tag() {}
    Tag(int n, int r, int p) : n(n), rem(r), prod(p) {}

    bool operator ==(const Tag &other) const {
        return n == other.n && rem == other.rem && prod == other.prod;
    }

    size_t operator ()(const Tag &t) const {
        return t.prod + t.n + t.rem*10;
    }
};

struct Tag2 {
    int nth, d, sum, prod;

    Tag2() {}
    Tag2(int n, int d, int s, int p) : nth(n), d(d), sum(s), prod(p) {}

    bool operator ==(const Tag2 &other) const {
        return nth == other.nth && d == other.d && sum == other.sum && prod == other.prod; 
    }

    size_t operator ()(const Tag2&t) const {
        return t.prod + t.nth*10+t.d*100+t.sum*1000;
    }
};
/////////////////////////////////////////////////////

// n桁で総和がremになる数の個数を返す.
// 先頭が0になるものも含める.
// (rec(4, 4)で0022も数える等)
int memo[10][91];
int rec(int n, int rem) {
    if(rem == 0) return 1;
    if(n == 0) return 0;

    if(memo[n][rem] == -1) {
        int res = 0;
        for(int d = 0; d <= 9; ++d) {
            if(d > rem) break;
            res += rec(n-1, rem-d);
        }
        memo[n][rem] = res;
    }
    return memo[n][rem];
}

// 総和がsumになるn桁の数で,PDS Numberであるものを探索する.
// ただし,これより前の数で積prodが得られているものとする.
vector<hash_map<Tag,int,Tag> > memo2(91);
int rec2(int n, int rem, int prod, int sum) {
    if(n == 0) {
        if(rem == 0 && prod % sum == 0) return 1;
        return 0;
    }
    if(rem == 0) return 1;
    if(n*9 < rem) return 0;

    // 途中でprodがsumで割り切れるようになったら,その後はどう並んでも良い.
    if(prod >= 0 && prod % sum == 0) {
        return rec(n, rem);
    }

    const Tag key(n, rem, prod);
    if(memo2[sum].count(key)) return memo2[sum][key];

    int res = 0;
    for(int d = 0; d <= 9; ++d) {
        if(d > rem) break;
        int nprod = prod<0 ? d==0 ? -1 : d : prod*d;
        res += rec2(n-1, rem-d, nprod, sum);
    }
    return memo2[sum][key] = res;
}

hash_map<Tag2,int,Tag2> memo3;
int solve(int n) {
    int ans = 0;
    int prod = -1; // 「先頭からずっと0」は「積が0」と区別しないといけない
    int sum = 0;
    int pat = 0;

    // 上の桁から固定して,パターン数を数えていく.
    // 10^9番目のPDS Numberは10^9オーダで存在するっぽい
    for(int nth = 10; nth >= 1; --nth) {
        ans *= 10;
        int digit = -1;
        for(int d = 0; d <= 9; ++d) {
            int nprod = prod<0 ? d==0 ? -1 : d : prod*d;
            const Tag2 key(nth, d, sum, nprod);
            int subpat = 0;
            if(memo3.count(key) == 0) {
                for(int allsum = 1; allsum <= 90; ++allsum) {
                    if(allsum >= sum+d) subpat += rec2(nth-1, allsum-sum-d, nprod, allsum);
                }
                memo3[key] = subpat;
            }
            else {
                subpat = memo3[key];
            }

            //printf("%d\n", subpat);
            if(pat + subpat >= n) {
                digit = d;
                break;
            }
            pat += subpat;
        }
        if(digit == -1) {
            puts("NEVER REACH HERE!");
        }
        ans += digit;
        sum += digit;
        //printf("%dth digit: %d\n", nth, digit);
        if(ans != 0) {
            if(prod < 0) prod = 1;
            prod *= digit;
        }
    }
    return ans;
}

int main() {
    memset(memo, -1, sizeof(memo));
    while(true) {
        int N;
        scanf("%d", &N);
        if(!N) break;

        printf("%d\n", solve(N));
    }
    return 0;
}

悲しいのでRuby版も.アルゴリズム自体は同じだが,C++版とはrecとrec2の名前が逆になっているので注意.

#!/usr/bin/ruby

$memo2 = {}
def rec2(n, rem)
  return 1 if rem == 0
  if n == 0
    return 1 if rem == 0
    return 0
  end

  key = [n,rem]
  val = $memo2.fetch(key, nil)
  return val if val

  res = 0
  (0..9).each do |d|
    break if d > rem
    res += rec2(n-1, rem-d)
  end
  $memo2[key] = res
end

$memo2 = Array.new(91){Hash.new}
def rec(n, rem, prod, sum)
  if n == 0
    return 1 if rem == 0 && prod % sum == 0
    return 0
  end
  return 1 if rem == 0
  return 0 if n*9 < rem

  if !prod.nil? && prod % sum == 0
    return rec2(n, rem)
  end

  key = [n, rem, prod]
  val = $memo[sum].fetch(key, nil)
  return val if val

  res = 0
  (0..9).each do |d|
    break if d > rem
    nprod = (prod.nil? && d == 0) ? nil : (prod||1)*d
    res += rec(n-1, rem-d, nprod, sum)
  end
  $memo[sum][key] = res
end

$memo3 = {}
def solve(n)
  ans = 0
  prod = nil
  sum = 0
  pat = 0
  (1..10).to_a.reverse.each do |nth|
    ans *= 10
    digit = nil
    (0..9).each do |d|
      nprod = (prod.nil? && d == 0) ? nil : (prod||1)*d
      key = [nth, d, sum, nprod]
      subpat = $memo3.fetch(key, nil)
      if subpat.nil?
        subpat = 0
        (1..90).each do |allsum|
          subpat += rec(nth-1, allsum-sum-d, nprod, allsum) if allsum >= sum+d
        end
        $memo3[key] = subpat
      end
      p subpat
      if pat + subpat >= n
        digit = d
        break
      end
      pat += subpat
    end

    if digit.nil?
      puts "NEVER REACH HERE!"
    end
    ans += digit
    sum += digit
    #puts "#{nth}th digit: #{digit}"
    if ans != 0
      prod ||= 1
      prod *= digit
    end
  end
  ans
end

loop do
  n = gets.to_i
  break if n == 0
  p solve(n)
end

Lucky Array(LUCKY4)

F(x)をxの10進数表記に含まれる4と7の個数と定義する.N(1 ≦ N ≦ 50)個の整数を並べてできる数列A={ai}を考え,F(ai)とF(ai-1)が等しいか異なるかの関係が与えられているとき,条件を満たすAのうち辞書順K番目のものを求めよ.ただし1 ≦ ai ≦ Mとし,M ≦ 109である.

方針としてはPDS Numberと同じように,数字を桁ごとに固定してパターン数を数え上げていく.

決めなければいけない数字はN*log10M個あるが,これらの実際の値は関係なく4と7の個数だけ覚えれば良い.また,F(x)の値の条件から,aiの決め方はF(ai-1)に依存する.

さらに使える数の上限が決まっているため,各桁を決める際には実際にどの数字まで使えるかを管理する必要がある.たとえばM=12345のとき,M=123……まで決まっていると4桁目は4までしか使えない.これはm-1桁目までの全ての桁が,Mの対応する桁と一致しているかを覚えておけばよい.

これらを総合すると,状態変数は

  • 数列内のindex
  • 注目している桁
  • 現在のF(x)の値
  • 一つ前の要素のF(x)の値
  • 桁に上限があるか

の5つとなり,最大で50*50*9*9*2=405000状態であるから十分に計算可能だと言える.

コードは最初Rubyで書いて投げたのだがあえなくTLEし,C++で書き直していたところパターン数がKを越えて爆発することに気づいた.これを抑制する枝刈りを入れたらRubyで通った.

#!/usr/bin/ruby

class Numeric
  def lucky?
    self == 4 || self == 7
  end
end

$maxn = 0
$limit = []
$c = []
$memo = {}

# n番目の数のm桁目以降を自由に決めるときのパターン数.
# fはn番目の数の中でのLucky Number数.
# prevはn-1番目のLucky Number数.
# limitedがtrueのときは,全体でMを越えないようにするためm桁目の数字に上限を設ける.
def solve(n, m, f, prev, limited)
  #puts "#{n} #{m} #{f} #{prev} #{limited}"

  # Base case
  if n == $maxn
    return 1 
  end

  # n番目の数字が決まったら正当性チェックする.
  if m == -1
    return 0 if n > 0 && (f == prev) != $c[n-1]
    return solve(n+1, $limit.size-1, nil, f, true)
  end

  key = [n,m,f,prev,limited]
  res = $memo.fetch(key, nil)
  return res if res

  # 使える数字の上限と下限.
  # A[n] >= 1でないといけないことに注意.
  lim = limited ? $limit[m] : 9
  bot = (m == 0 && f.nil?) ? 1 : 0
  #puts "#{n} #{m} #{f} #{prev} #{limited}: lim=#{lim}"
  
  res = 0
  (bot..lim).each do |d|
    nf = d.lucky? ? f.to_i+1 : (f.nil? && d == 0) ? nil : f.to_i
    nl = limited && (d == lim)
    res += solve(n, m-1, nf, prev, nl)
    # 高速化のための枝刈り.
    # Mは高々10^9なので,それを越えるパターン数を求めても仕方がない.
    # (単純に再帰が増えるだけではなく,Bignumになってしまうと激遅になる)
    break if res > 2000000000
  end
  #puts "#{n} #{m} #{f} #{prev} #{limited}: #{res}"
  $memo[key] = res
end

gets.to_i.times do
  $maxn, m, k = gets.split.map(&:to_i)
  $c = gets.split.map{|c| c == "1"}
  $limit = m.to_s.each_char.to_a.map(&:to_i).reverse
  $memo.clear

  ans = []
  prevf = 0
  acc = 0
  catch(:end) do
    $maxn.times do |pos|
      num = 0
      limited = true
      f = nil
      # 上の桁から固定していき,それ以降のパターン数を数える.
      (0..$limit.size-1).to_a.reverse_each do |dpos|
        lim = limited ? $limit[dpos] : 9
        bot = (dpos == 0 && f.nil?) ? 1 : 0
        digit = nil
        (bot..lim).each do |d|
          nf = d.lucky? ? f.to_i+1 : (f.nil? && d == 0) ? nil : f.to_i
          nl = limited && (d==lim)
          tmp = solve(pos, dpos-1, nf, prevf, nl)
          #puts "#{d}: #{acc+tmp}"
          if acc + tmp >= k
            digit = d
            f = nf
            break
          end
          acc += tmp
        end
        if digit.nil?
          ans = [-1]
          throw :end
        end

        num *= 10
        num += digit
        limited = limited && (digit == lim)
      end
      ans << num
      prevf = f
    end
  end

  puts ans.join(" ")
end

Parallel Computing(PARALLEL)

N(1 ≦ N ≦ 1000)要素の配列X={Xi, 1 ≦ i ≦ N}がある.この配列の要素どうしで足し算を行い,i番目の要素にはX1からXiまでの和が格納されているようにしたい.また,並列計算が可能で,同じ要素に同時に書き込んだり,読み出しと書き込みを同一ステップで行なったりしない条件下で,1ステップにいくらでも同時に演算を行うことができる.ただしステップ数は20まで,全ステップの演算回数合計は2000回までとする.目的の配列を得るための演算をスケジューリングせよ.

解けたけど解けてない.

4日くらい考えても分からなかったので,いかにも有用そうな問題だしどうせ既存のアルゴリズムがあるだろうと思って適当にぐぐったらWikipediaがひっかかった.どうやらこの問題はPrefix sumと呼ばれる問題らしい.

Wikipediaにこの問題の解らしきアルゴリズムが書いてあるのだが,読んでもいまいち何をやっているのか分からない.分かりやすい説明を求めてさまよっていると,GPU Gems 3の記事が見つかったのでRubyで実装した.

このアルゴリズムは分割統治法に基づいており,Up-SweepとDown-Sweepの2つの段階に分かれる.Up-Sweepでは配列の偶数番目の要素だけで構成された小配列Zを作り,Zi=Xi-1+Xiとする.このステップを再帰的に行っていくと,結局kステップ目で生き残っているのは(一番最初のXにおけるインデクスで)2kを因数に持つ要素となり,そこに格納されているのは2k-1個前の要素までの和となる.

Down-SweepではUp-Sweepで形成された配列を利用し,各ステップで選ばれなかった要素の計算を完了させる.kステップ目で選ばれていたがk+1ステップ目で選ばれなかった要素の(一番最初のXにおける)インデクスをiとすると,先の考察からこの要素にはXi-2k+1からXiまでの総和が格納されている.したがってこの要素には,X1からXi-2kまでの要素の総和を加えれば良い.ここでk+1ステップ目で選ばれていた要素は既に計算が完了していると仮定すると,Xi-2kはk+1ステップ目で選ばれているはずであるから,ここにはX1からXi-2kまでの総和が格納されている.したがって,Xi += Xi-2kとすることで,kステップ目も全ての要素が計算完了できる.

ここで,Nが2の羃であるとするとUp-Sweepで最後に残るのはXNであり,1からXNまでの総和が格納されている.したがって,Up-Sweepを逆順にたどってDown-Sweepを行うことで,全ての要素に対してPrefix sumを計算することができる.Nが2の累乗でない場合は羃まで丸め上げ,Nより大きい要素に対する操作を全て無視すればよい.

このアルゴリズムは,Up-Sweepの1ステップで要素数が半分になり,Down-SweepはUp-Sweepの逆順だから,ステップ数は高々2*ceil(log2N)となる.また,kステップ目の演算回数はUp-SweepでN/2k,Down-SweepでN/2kだから総計で高々2N回となり,制約に収まることが分かる.

これ独力で思いつける気がしない…….

#!/usr/bin/ruby

n = gets.to_i
size = n
(0..3).each do |i|
  size |= (size>>(2**i))
end
size ^= size>>1
size <<= 1 if size != n
ans = []

# Up-Sweep
step = 2
while step <= size
  arr = []
  (1..size/step).each do |i|
    cur = i*step
    arr << "#{cur-step/2}+#{cur}=#{cur}" if cur <= n
  end
  ans << arr if arr.size > 0
  step <<= 1
end

# Down-Sweep
step >>= 1
while step >= 2
  arr = []
  (1..size/step).each do |i|
    cur = i*step-step/2
    arr << "#{cur-step/2}+#{cur}=#{cur}" if cur <= n && cur-step/2 > 0
  end
  ans << arr if arr.size > 0
  step >>= 1
end

puts ans.size
ans.each do |arr|
  puts "#{arr.size} #{arr.join(' ')}"
end

Similar Graphs(SIMGRAPH)

頂点数が同じ2つのグラフが与えられる.2つのグラフの頂点間に1対1対応を作成し,どちらのグラフにも含まれる辺がなるべく多くなるようにせよ.

やる気なくlocal search.近傍解を探すのに1つのswapしかしてないのだが,これだと毎回random_shuffuleするアルゴリズムとたいして変わらなかった…….

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdio>

using namespace std;

int calc_score(const vector<int> &ord, const vector<vector<int> > &graph, const vector<pair<int,int> > &to_see) {
    int score = 0;
    for(vector<pair<int,int> >::const_iterator it = to_see.begin(); it != to_see.end(); ++it) {
        if(graph[ord[it->first]][ord[it->second]]) ++score;
    }
    return score;
}

int main() {
    int T;
    scanf("%d", &T);
    srand(time(NULL));
    while(T--) {
        int N;
        scanf("%d", &N);
        vector<vector<int> > target(N, vector<int>(N));
        vector<vector<int> > graph(N, vector<int>(N));
        vector<pair<int,int> > to_see;
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                int v;
                scanf("%d", &v);
                target[i][j] = v;
                if(v) to_see.push_back(make_pair(i, j));
            }
        }
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < N; ++j) {
                int v;
                scanf("%d", &v);
                graph[i][j] = v;
            }
        }

        vector<int> nodes(N), ans;
        int bestscore = 0;
        for(int i = 0; i < N; ++i) {
            nodes[i] = i;
        }

        vector<int> cur = nodes;
        int curscore = 0;

        random_shuffle(cur.begin(), cur.end());
        ans = cur;
        bestscore = curscore = calc_score(cur, graph, to_see);
        for(int CNT = 0; CNT < 2000; ++CNT) {
            vector<int> next_cand = cur;
            int next_best = curscore;

            for(int CN = 0; CN < 10; ++CN) {
                int a = rand() % N, b = rand() % N;
                vector<int> next = cur;
                swap(next[a], next[b]);

                int nc = calc_score(next, graph, to_see);
                if(nc > next_best) {
                    next_cand = next;
                    next_best = nc;
                }
            }
            if(next_cand == cur) {
                random_shuffle(cur.begin(), cur.end());
                next_best = calc_score(cur, graph, to_see);
            }
            cur = next_cand;
            curscore = next_best;
            if(curscore > bestscore) {
                ans = cur;
                bestscore = curscore;
            }
        }

        bool first = true;
        for(int i = 0; i < N; ++i) {
            if(!first) printf(" ");
            printf("%d", i+1);
            first = false;
        }
        puts("");
        first = true;
        for(int i = 0; i < N; ++i) {
            if(!first) printf(" ");
            printf("%d", ans[i]+1);
            first = false;
        }
        puts("");
        //printf("%d\n", bestscore);
    }

    return 0;
}

*1RubyだとArrayリテラルでHashにつっこむだけでメモ化できるのでこういうのが楽で良い

 |