解いた問題

12/22/2011

12/14/2011

SRM525 Div1 Medium

525
もし、ある時点で知っている噂が1種類だけなら、それを伝えた方が日数がかからないのは明白。
ただ、1日に伝播されられる噂は1つだけ。
同時に2つの噂を知ったときに、どうすれば最適なのかは簡単には分からなそう。
しかし、2つの噂のどちらを先に伝えるかは2^N通りしかないので、全パターン試せる。

11/15/2011

UVa12202

UVa12202
最大30×30のグリッド上に障害物とワープホールがある。
障害物の無い上下左右に隣接したセルに移動できる。
ワープホールに侵入すると、時間T (-10000 <= T <= 10000)を消費して別の場所に飛ばされる。
スタート地点からゴール地点まで到達可能であれば、(負の値になろうとも)最短時間を出力する。
到達できない場合は、どう到達できないのかを判定してゴニョゴニョ。

ベルマンフォードみたいに、値の更新を充分繰り返して試す。

10/27/2011

UVa12218

UVa12218
全部試す。

SRM470 Div1 Easy

目的の部屋の右側にしかない色、左側にしかない色、両方にある色の3つに分類する。
その後は、実際にドアを開けて試してみる。
自分の側にしかない色を優先して開けるのが最善手。
実際に開けなくても、計算して出せる気もする。。。

UVa12172

UVa12172
smallestはDP
largestは貪欲

10/26/2011

UVa12238

UVa12238
クエリー(A, B)が与えられたとき、答えは
ルートからのAまで距離 + ルートからBまでの距離 - ルートからAとBの最近共通祖先までの距離 * 2
参考URL

10/23/2011

10/12/2011

SRM465 Div1 Easy

250
2つの正方形は、互いの最も近い変動しが平行になるように配置すればいい。
( ◇◇ではなく□□の方だけを考える )
片方の正方形の辺の長さを1伸ばすと、2つの正方形の距離はは0.5だけ縮まる。

8/11/2011

UVaまとめ

300弱くらいは紛失。中身が間違っているファイルもいくつか・・・。
古いコードは若さ故の過ち満載。
気が向いたときに更新。

uHunt

8/04/2011

SRM464 Div1 Medium

550
まさかの2-SAT。
論理式にして強連結成分分解? 小さいし、無向だし、律儀にやる必要はなかった。
あまり描く機会がなかったから、気付いても描けなかった。復習しておこう。

SRM464 Div1 Easy

250
全部試す。
明らかに作れない場合、0が答えになりそうな場合は別処理。

8/02/2011

SRM463 Div1 Easy

250
うさぎ同士のmaxNumberを入れ替えても、答えは変わらない => とりあえず昇順にソート
0番のうさぎに割り当てた番号以外を1番に割り当てる。
1番のうさぎに割り振る番号の選択肢は、maxNumber[1] - 1 通り。
同様に、2番のうさぎに割り当てる番号の選択肢は、0番と1番に割り振った数字以外。
つまり、maxNumber[2] - 2 通り。
i番のうさぎに割り当てる数字の選択肢は、maxNumber[i] - i 通り。

7/21/2011

SRM462 Div1 Easy

250
見るからに二分探索。
コーナーケースに注意する。
何度かリサブミットしてやっと通った。Easyじゃないと思った。

SRM461 Div1 Medium

500
ある町からある町へ直接行くために必要な新設の町の数は割り算すれば分かる。
[町][追加した町の数]でダイクストラ。
頂点数が大きい。ちょっと手を抜いて実装してタイムリミット出してしまった。

7/20/2011

SRM461 Div1 Easy

300
交互に(同じ色同士は触れない様に)使うという条件があるので、赤からと青からの2通りを試す。

7/19/2011

SRM460 Div1 Medium

500
dp_table[いくつまで見た][いくつ選んだ][ファンの合計]

dp_table[a+1][b][c] += dp_table[a][b][c] * 選ばれない確率
dp_table[a+1][b+1][c+d] += dp_table[a][b][c] * 選ばれる確率 * d人選ぶ確率

7/18/2011

SRM460 Div1 Easy

250
各問題にYesがNoを割り当てて、どの答えがどの質問に対する答えなのかを全部調べてたら終わらないと思って、頑張って計算する問題だと思った。もちろん、そんなことはなかった。
挙句、解説を見て解いた。意外と単純な回答だった。悲しい。
質問を "Yes" か "No" か "2回目以降の出題" に割り当てながら数える。

7/17/2011

SRM459 Div1 Medium

500
まず、各マスに入る数字の重みを計算する。
次に、重みを足してtopを作るパターンを数える。
数え上げるdpで、for(各重み)for(和)と間違って、for(和)for(各重み)でやると、重複して数えてしまう。
間違えに気付くまで意外と時間をくった・・・。

7/15/2011

SRM458 Div1 Medium

450
かなり悩んだ。
例えば、硬貨が価値1のものと価値Aのものしかない場合、価値Aで払いきれない分(あまり)は価値1の硬貨で払うしかない。
同様に、価値Aの次に大きい硬貨が価値A*Bだった場合、価値A*Bで払いきれない分(あまり)は価値Aを使ってできる限り払うことになる。

7/14/2011

SRM458 Div1 Easy

250
全部試す。

SRM457 Div1 Medium

500
悩んだ。まだまだ実力が足らないみたい。
図に描いてみると分かるけど、1度に使う色の組は意外と少ない。
どの色にどの数を使うかの組み合わせを計算する。

SRM457 Div1 Easy

250
間違う場所が満載な気がする。

7/12/2011

SRM Div1 まとめ

SRM411   Easy

SRM430   Easy  Medium

SRM434   Easy  Medium


SRM450   Easy   Medium
SRM451   Easy   Medium
SRM452   Easy
SRM453   Easy
SRM453.5   Easy   Medium
SRM454   Easy   Medium
SRM455   Easy
SRM456   Easy   Medium
SRM457   Easy   Medium
SRM458   Easy   Medium
SRM459   Easy   Medium
SRM460   Easy   Medium
SRM461   Easy   Medium
SRM462   Easy   Medium
SRM463   Easy   Medium
SRM464   Easy   Medium
SRM465   Easy
SRM466   Easy   Medium
SRM467   Easy   Medium
SRM468   Easy   Medium
SRM469   Easy   Medium
SRM470   Easy   Medium
SRM471   Easy   Medium
SRM472   Easy
SRM473   Easy   Medium
SRM474   Easy
SRM475   Easy
SRM476   Easy
SRM477   Easy   Medium
SRM478   Easy
SRM479   Easy   Medium
SRM480   Easy   Medium
SRM481   Easy   Medium
SRM482   Easy
SRM483   Easy
SRM484   Easy
SRM485   Easy
SRM486   Easy   Medium
SRM487   Easy
SRM488   Easy
SRM489   Easy
SRM490   Easy
SRM491   Easy
SRM492   Easy


SRM495   Easy
SRM496   Easy   Medium
SRM497   Easy
SRM498   Easy   Medium
SRM499   Easy   Medium

SRM501   Easy
SRM502   Easy   Medium
SRM503   Easy   Medium
SRM504   Easy   Medium
SRM504.5   Easy
SRM505   Easy
SRM506   Easy
SRM507   Easy  Medium

SRM509   Easy
SRM510   Easy
SRM511   Easy  Medium
SRM512   Easy
SRM513   Easy  Medium
SRM514   Easy
SRM515   Easy
SRM516   Easy
SRM517   Easy
SRM518   Easy  Medium
SRM519   Easy
SRM520   Easy
SRM521   Easy   Medium
SRM522   Easy   Medium/Medium
SRM523   Easy   Medium
SRM524   Easy   Medium
SRM525   Easy   Medium
SRM526   Easy
SRM527   Easy/Easy   Medium
SRM528   Easy   Medium
SRM529   Easy
SRM530   Easy   Medium
SRM531   Easy   Medium
SRM532   Easy   Medium
SRM533   Easy   Medium
SRM534   Easy
SRM535   Easy
SRM536   Easy   Medium
SRM537   Easy   Medium
SRM538   Easy   Medium
SRM539   Easy
SRM540   Easy
SRM541   Easy
SRM542   Easy
SRM543   Easy   Medium
SRM544   Easy   Medium
SRM545   Easy   Medium
SRM546   Easy   Medium
SRM547   Easy   Medium
SRM548   Easy



SRM550   Easy  Medium
SRM551   Easy  Medium


SRM556   Easy
SRM557   Easy  Medium


SRM560   Easy
SRM561   Easy  Medium
SRM562   Easy
SRM563   Easy  Medium
SRM564   Easy  Medium
SRM565   Easy  Medium
SRM566   Easy  Medium
SRM567   Easy  Medium
SRM568   Easy
SRM569   Easy  Medium
SRM570   Easy
SRM571   Easy  Medium
SRM572   Easy  Medium

SRM574   Easy  Medium
SRM575   Easy  Medium
SRM578   Easy  Medium
SRM579   Easy  Medium
SRM580   Easy


SRM582   Easy
SRM583   Easynbsp; Medium




SRM590   Easy

SRM453.5 Div1 Medium

450

SRM453.5 Div1 Easy

250

SRM454 Div1 Medium

500
意外と苦労した。
dp_table[桁数][動かした本数][他の桁へ移った本数]

SRM454 Div1 Easy

250

SRM455 Div1 Easy

ある長方形の領域中の解は、周囲の4辺の1つを切り落としたモノの最大値 or 4辺全てを切り落としたモノ+1

6/06/2011

SRM343Div2

LiveArchive3153

LiveArchiveにログインできない・・・。アカウントを作り直して挑戦。

答えの上限を大まかに見積もっておく。上限の値が出たら、終了。
入力によっては、少しも早くならない気がする・・・。
というか、ACが出たことに驚いた。
実行速度ランキング6位。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
const int TIME = 420;

int cost[N];
int g[N][N];

int result;
int lim;

void rec(int pos, int vis, int time, int size, int depth)
{
  if( TIME < time )return ;

  result = max( result, depth );
  if( result == lim )return ;

  for(int i=0; i<size; ++i){
    if( vis & (1 << i) ) continue;

    int spend = g[pos][i] + cost[i];
    rec(i, vis | (1 << i), time + spend, size, depth + 1);

    if( result == lim ) return ;
  }
  return ;
}

void wf(int size)
{
  for(int k=0; k<size; ++k){
    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] = min( g[i][j], g[i][k] + g[k][j] );
      }
    }
  }
  return ;
}

int main(void)
{
  int n;
  while( cin >> n && n ){

    for(int i=0; i<n; ++i){
      cin >> cost[i];
    }

    for(int i=0; i<n; ++i){
      for(int j=0; j<n; ++j){
        cin >> g[i][j];
      }
    }

    wf(n);
    
    static int c[N];
    copy( cost, cost + n, c );
    
    int mx = 0;
    for(int i=0; i<n; ++i){
      int mn = 1 << 24;
      for(int j=0; j<n; ++j){
        if( i != j ) mn = min(mn, g[i][j]);
      }
      mx = max(mx, mn);
      c[i] += mn;
    }

    sort( c, c + n );
    lim = 0;
    for(int i=0, sum = -mx; i < n && sum + c[i] <= TIME; lim = ++i){
      sum += c[i];
    }

    result = 0;
    for(int i=0; i<n; ++i){
      rec(i, (1 << i), cost[i], n, 1);
    }
    cout << result << endl;
  }
  return 0;
}

5/25/2011

UVa10111

TCO2011 Qual3

参加記録。

250
Failed System Test

500
 class CoinMachinesGame {
public:
  int maxGames(int c, vector <int> need, vector <int> give) {
    int cnt = 0;

    while( true ){
      int tmp = c;

      const int size = need.size();
      int idx = 0;
      int mx = -(1 << 30 );
      for(int i=0; i<size; ++i){
        if( need[i] <= c ){
          if( mx < give[i] - need[i] ){
            idx = i;
            mx = give[i] - need[i];
          }
        }
      }

      int game = c / need[idx];
      c -= need[idx] * game;
      c += give[idx] * game;
      cnt += game;

      if( tmp == c )break;
    }

    return cnt;
  }
}; 
1000
class ComplementMachine2D {
public:
  int largestSubmatrix(vector <string> m) {

    int r = max( m.size(), m[0].size() );

    for(int begin=0; begin < m[0].size(); ++begin){
      for(int end = begin+1; end <= m[0].size(); ++end){

        for(int top = 0; top < m.size(); ++top){
          for(int bottom = top + 1; bottom <= m.size(); ++bottom){

            bool a, b;
            a = true;
            b = true;

            for(int i=begin; i<end; ++i){
              a = a && m[top][i] == m[bottom-1][i];
              b = b && m[top][i] != m[bottom-1][i];
            }

            if( !a && !b )break;

            r = max( r, (bottom - top) * (end - begin) );
          }
        }
      }
    }
    return r;
  }
};



250再挑戦
個数が多くて6個で、数値の範囲が1-15と小さいので、充分大きい数まで試せばいい。
class AllButOneDivisor {
public:
  int getMinimum(vector <int> v) {
    for(int n = 1; n < 100000; ++n){
      int cnt = 0;
      for(int i=0; i<v.size(); ++i){
        if( n % v[i] == 0 ) ++cnt;
      }
      if( cnt+1 == v.size() )return n;
    }
    return -1;
  }
};

5/22/2011

ppr

何やってんだ、オレは。
ネタ言語ぷんぷくりん
たぶん拡張子は.ppr
参考サイト
 http://kirei.biglobe.ne.jp/news/detail/20110426162331_pch19894

Source Code

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(void)
{
  map<string, char> token;
  token["ですけどぉぉお〜!"] = '>';
  token["ぷんぷくり〜ん"] = '<';
  token["私かわいそーなコ"] = '+';
  token["わかんなぁぁああい"] = '-';
  token["><"] = '.';
  token["覚えたぞぉ"] = ',';
  token["メモメモ"] = '[';
  token["キュンキュンキュン"] = ']';

  const int M = 30000;
  char mem[ M ];
  char *ptr = mem;
  fill( mem, mem + M, 0 );

  vector<string> v;
  for(string s; cin >> s; v.push_back(s));

  for(int i=0; i<v.size(); ++i){    
    if( token[ v[i] ] == '>' ) ptr++;
    else if( token[ v[i] ] == '<' ) ptr--;
    else if( token[ v[i] ] == '+' ) (*ptr)++;
    else if( token[ v[i] ] == '-' ) (*ptr)--;
    else if( token[ v[i] ] == '.' ) cout << *ptr;
    else if( token[ v[i] ] == ',' ) *ptr = cin.get();
    else if( token[ v[i] ] == '[' ){
      if( !(*ptr) ){
        int o = 0, c = 0;
        while(true){
          if( token[ v[i] ] == '[' )++o;
          if( token[ v[i] ] == ']' )++c;
          ++i;
          if( o == c )break;
        }
      }
    }
    else if( token[ v[i] ] == ']' ){
      if( *ptr ){
        int o = 0, c = 0;
        while(true){
          if( token[ v[i] ] == '[' )++o;
          if( token[ v[i] ] == ']' )++c;
          --i;
          if( o == c )break;
        } 
      }
    }
    else ;
  }
  cout << endl;
  return 0;
}
Input

私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
赤ちゃんかわいそうですぅ 赤ちゃんかわいそうですぅ 赤ちゃんかわいそうですぅ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ メモメモ ですけどぉぉお〜! 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ですけどぉぉお〜!
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私のハードディスクに記録しているのでありますっ
私のハードディスクに記録しているのでありますっ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ですけどぉぉお〜!
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ ぷんぷくり〜ん ぷんぷくり〜ん ぷんぷくり〜ん
わかんなぁぁああい キュンキュンキュン ですけどぉぉお〜! ><
ですけどぉぉお〜! 私かわいそーなコ 私かわいそーなコ ><
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ><
>< 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
>< ですけどぉぉお〜! わかんなぁぁああい ><
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
ヒヨコが死んじゃうじゃないですかぁっ
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
>< ぷんぷくり〜ん 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ 私かわいそーなコ
私かわいそーなコ 私かわいそーなコ >< わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい ><
私かわいそーなコ 私かわいそーなコ 私かわいそーなコ ><
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい >< わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい
わかんなぁぁああい わかんなぁぁああい わかんなぁぁああい ><
ですけどぉぉお〜! 私かわいそーなコ ><



Output

Hello, world!


おまけ
 #include <iostream>

using namespace std;

int main(void)
{
  int cnt = 0;
  for(char c; cin >> c; ){
    if( c == '>' )cout << "ですけどぉぉお〜!" << ' ';
    if( c == '<' )cout << "ぷんぷくり〜ん" << ' ';
    if( c == '+' )cout << "私かわいそーなコ" << ' ';
    if( c == '-' )cout << "わかんなぁぁああい" << ' ';
    if( c == '.' )cout << "><" << ' ';
    if( c == ',' )cout << "覚えたぞぉ" << ' ';
    if( c == '[' )cout << "メモメモ" << ' ';
    if( c == ']' )cout << "キュンキュンキュン" << ' ';
    if( ++cnt % 4 == 0 )cout << endl;
  }
  cout << endl;
  return 0;
}

5/20/2011

sleep sort in clojure

話題のSleepSortを描いてみた。

やることは、
・配列の要素と同じ数のスレッドを作る。
・各スレッドは、1つの整数を受け取り、その時間だけsleepする。
・数字を返す。

wait() ==>> notifyAll() ==>> sleep() で実現したかったけど、やり方がよく分からない。
notifiAllしないと微妙に順番が変わる可能性がある? いや、したとしても、変わるか?
とりあえず、sleepする時間を10倍。
(defn sleep-sort [ a ]
  (if (not (empty? a))
    (do
      (.start (Thread.
               (fn []
                 (Thread/sleep (* (first a) 10))
                 (println (first a)))))
      (sleep-sort (rest a)))))

(sleep-sort '(6 1 2 3 7 4 8 9 5 0))
参考サイト
4chan BBS – Genius sorting algorithm: Sleep sort

2/22/2011

UVa10705

uva10705
i番目が(2^i)もしくは-(2^i)の重みを持つ様なビット列を考える。
各ビットが正なのか負なのかと整数nが入力として与えられる。
整数nがビット列で表現できるかどうか、表現できる場合はそのビット列を出力する。
aoj0233と似ている。似たアプローチでやってみた。