SRM470 Div1 Medium

500
これから引く線同士、既に引かれている線同士、引かれている線と引く線同士の3つに分けて考える。

SRM472 Div1 Easy

250
5でmod

SRM525 Div1 Medium

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

SRM525 Div1 Easy

300
O(N^6)の全通りでも間に合う。

UVa12209

UVa12209
dp[配置済みの行数]

UVa12202

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

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

UVa11610

UVa11610
初BIT(Binary Index Tree)
もう少し賢い実装ができなかったものかと、反省。

SRM471 Div1 Easy

愚直に試す。

UVa12218

UVa12218
全部試す。

SRM470 Div1 Easy

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

UVa12172

UVa12172
smallestはDP
largestは貪欲

UVa12238

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

UVa12299

UVa112299
蟻本からSegmentTreeを拝借。
更新を繰り返して間に合う。

UVa12101

UVa12101
素数表からグラフ作ってBFS

SRM469 Div1 Easy

250

SRM468 Div1 Easy

250

SRM467 Div1 Easy

250
こういう類の問題は不得手だわー。厳しかった。

SRM466 Div1 Easy

250

SRM465 Div1 Easy

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

UVaまとめ

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

uHunt

SRM464 Div1 Medium

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

SRM464 Div1 Easy

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

SRM463 Div1 Easy

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

SRM462 Div1 Easy

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

SRM461 Div1 Medium

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

SRM461 Div1 Easy

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

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人選ぶ確率

SRM460 Div1 Easy

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

SRM459 Div1 Medium

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

SRM459 Div1 Easy

250
全部試す。

SRM458 Div1 Medium

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

SRM458 Div1 Easy

250
全部試す。

SRM457 Div1 Medium

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

SRM457 Div1 Easy

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

SRM456 Div1 Medium

450
答えが実数だし、2分探索ってことに気付くのは難しくなかった。

SRM456 Div1 Easy

250
山登り

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辺の１つを切り落としたモノの最大値 or 4辺全てを切り落としたモノ+1

SRM453Div2

AOJ1215

尺取

SRM452Div2

SRM451Div2

SRM450Div2

SRM349Div2

SRM348Div2

UVa811

全部試す。やるだけ。

SRM347Div2

SRM346Div2

SRM345Div2

SRM344Div2

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;
}

SRM342Div2

SRM341Div2

SRM339Div2

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;
  }
};

UVa11818

SRM340Div2

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;
}

sleep sort in clojure

話題のSleepSortを描いてみた。

やることは、
・配列の要素と同じ数のスレッドを作る。
・各スレッドは、１つの整数を受け取り、その時間だけ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

SRM338Div2

SRM337Div2

SRM336Div2

UVa11262

SRM335Div2

SRM334Div2

ここ数日、bloggerで投稿・編集ができない状態だった。
そのせいか、記事の順番が変。

SRM331Div2

SRM332Div2

SRM333Div2

SRM330Div2

SRM328Div2

SRM329Div2

SRM327Div2

SRM326Div2

SRM325Div2

SRM324Div2

SRM323Div2

SRM322Div2

ここ何回かで解いた問題は、1000より500の方が難しい気がする。

SRM321Div2

SRM320Div2

SRM319Div2

SRM318Div2

SRM317Div2

SRM316Div2

SRM315Div2

SRM314Div2

SRM313Div2

SRM312Div2

SRM311Div2

SRM310Div2

SRM309Div2

SRM308Div2

SRM307Div2

SRM306Div2

SRM305Div2

SRM304Div2

SRM303Div2

SRM302Div2

SRM301Div2

SRM300Div2

UVa10705

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