2012-04-17

cafelier のSRM参加記録です。~~コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み~~本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

2012-04-17

競技プログラミングのためのD言語(3/2)

21:26 |

ちょっと分子が分母を上回りましたがいくつかAOJの問題をDで解いてみました（サブミットは当然してないです）。しかしあまり面白くならなかったので途中で飽きた。

AOJ10001 : X Cubic

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10001

import std.conv;
import std.stdio;
import std.string;

void main()
{
   int x = readln().chomp().to!int();
   writeln(x^^3);
}

標準入力から一行読み込むには std.stdio の readln() を使います。std.string の chomp() で末尾の改行文字を除いて、std.conv の to!int() で int に変換できます。3乗を計算するには冪乗演算子^^で。顔文字ではないです。

mainの一行目は int x = to!int(chomp(readln())); という関数呼び出しのちょっと気取った書き方で、D言語では f(x) と書く代わりに x.f() とも書けます。括弧で囲う段数が減って読みやすいので、私はかなりよく使います。ただし、第一引数が配列以外でもこの記法が使えるようになったのは最新版の dmd 2.059 からなので、オンラインジャッジで使うには要注意。

AOJ10002 : Rectangle

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10002

import std.array;
import std.conv;
import std.stdio;

void main()
{
   string[] tok = readln().split();
   int a = tok[0].to!int();
   int b = tok[1].to!int();
   writeln(a*b, " ", (a+b)*2);
}

一行に空白区切りで複数のデータが入力されるときは、std.array の split() で文字列の配列に分割します。その後で to!int() で各要素を変換。writeln には複数の引数を渡して一気に出力させることができます。

AOJ10004 : Sorting Three Numbers

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10004

import std.algorithm;
import std.array;
import std.conv;
import std.stdio;

void main()
{
   int[] arr = readln().split().map!(to!int)().array();
     // 繰り返しますが array(map!(to!int)(split(readln()))) と同じ意味です。
   arr.sort();
     // sort(arr) と同じ意味です。
   writefln("%(%d %)", arr);
}

std.algorithmの関数をいくつか使ってみます。

map!(f)(range) は、range の各要素に関数fを適用した結果の range を返す関数です。["3", "1", "8"] という文字列３つの range が、[3, 1, 8] という整数３つのrangeに変換されました。mapの返値は謎のrange型をしていて配列ではないので、それが嫌なときは、std.array の array() 関数で配列に変換します。

sort 関数は引数の range を破壊的にソートします。

出力は、writefln に配列出力用の不思議な記法が用意されていて、"%(" と "%)" で括って、各要素の出力法 "%d" と区切り文字 " " を指定するとそれっぽい出力がなされるみたいです。

AOJ1004 : Pair of Primes

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1004

さっき実は、10003 は面白くないから 10004 をやろう、と思ったら間違えて 1004 を解いてしまったのでその話をします。

import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

bool is_prime(int n)
{
   if( n == 1 )
      return false;
   for(int p=2; p*p<=n; ++p)
      if( n%p == 0 )
         return false;
   return true;
}

void main()
{
   string line;
   while( !(line=readln()).empty )
   {
      int N = line.chomp().to!int();

      auto ns = iota(1, N+1).map!(is_prime);
      zip(ns, retro(ns)).map!("a[0] && a[1]").count(true).writeln();
   }
}

素数判定は特に工夫せず O(√n) で書いています。入力がEOF終端という仕様なので、readln() の結果が空文字列かどうかを判定するようにしています。.length == 0 と書いてもいいし、std.array の empty() 関数を使ってもいいです。

問題を解いている肝心の部分は最後の方の２行で、頑張って range を使いまくりました。iota(x,y) は [x から y) までの値が順に並んだ range です。is_prime を map して bool が並んだ range に変換します。retro は range を逆順にする関数で、zip は複数の range を1個の Tuple の range にまとめます。これに論理&&をmapして、trueの個数を数えると答えです。

AOJ1005: Advanced Algorithm Class

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1005

せっかくなので1000番台をもう一個。

import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;

int solve(int[][] students)
{
   foreach(y, sy; students)
   foreach(x, me; sy) {
      if( students[y].minPos().front == me
       && transversal(students, x).minPos!"a>b"().front == me )
         return me;
   }
   return 0;
}

void main()
{
   for(;;) {
      int n = readln().chomp().to!int();
      if( n == 0 )
         break;

      int[][] students;
      foreach(_; 0..n)
         students ~= readln().split().map!(to!int).array();

      writeln(solve(students));
   }
}

nが0だと入力が終了、というパターンをreadln()で書くとこういう風になると思います。二次元配列を適当に読み込んで、solve() 関数で解いています。students[y][*] の最小値が自分で、しかも students[*][x] の最大値が自分ならそこを返す、と素直に判定しています。

foreach(i,e; array) { ... } は「i=0, e=array[0] で {...} を実行」「i=1, e=array[1] で {...} を実行」… と繰り返すループです。
minPos() は range の最小値があらわれる部分から先の部分rangeを返す関数です。C++のstd::min_element相当です。rangeのfront()で先頭要素が取り出せるので、それがすなわち最小値です。
transversal は二次元配列（あるいはrangeのrange）を縦に回るための range です。maxPos という関数はないみたいなので、minPos!"a>b" で逆の順序比較関数を渡してminを計算しました。

せっかくなのでつい range を使いまくりながら書いていますが、みんながこんな書き方をしなければいけない、ということはありません。難しすぎてわからん！と思ったら、C や Java の時と変わらず、普通の for 文で普通に回るコードはいつでもDでも動きます。伝統的な書き方をするとこんな感じになります。

int solve(int[][] students)
{
   for(int y=0; y<students.length; ++y)
   for(int x=0; x<students[y].length; ++x) {
      int me = students[y][x];

      int minYoko = int.max;
      for(int i=0; i<students[y].length; ++i)
         minYoko = min(minYoko, students[y][i]);

      int maxTate = int.min;
      for(int i=0; i<students.length; ++i)
         maxTate = max(maxTate, students[i][x]);

      if( minYoko == me && maxTate == me )
         return me;
   }
   return 0;
}

AOJ1001: Binary Tree Intersection And Union

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001

import std.conv;
import std.range;
import std.stdio;

class Tree
{
   static Tree parse(ref string s)
   {
      if( s[0] != '(' )
         return null;

      assert(s[0]=='('); s = s[1..$];
      Tree l = parse(s);
      assert(s[0]==','); s = s[1..$];
      Tree r = parse(s);
      assert(s[0]==')'); s = s[1..$];
      return new Tree(l, r);
   }

   static Tree inter(Tree x, Tree y)
   {
      if( x is null || y is null )
         return null;
      return new Tree(inter(x.left, y.left), inter(x.right, y.right));
   }

   static Tree uni(Tree x, Tree y)
   {
      if( x is null ) return y;
      if( y is null ) return x;
      return new Tree(uni(x.left, y.left), uni(x.right, y.right));
   }

   this(Tree l, Tree r)
   {
      left = l;
      right = r;
   }

   override string toString()
   {
      return "(" ~ (left is null ? "" : left.toString())
           ~ "," ~ (right is null ? "" : right.toString())
           ~ ")";
   }

   Tree left, right;
}

void main()
{
   string line;
   while( !(line=readln()).empty )
   {
      string[] tok = line.split();
      Tree t1 = Tree.parse(tok[1]);
      Tree t2 = Tree.parse(tok[2]);
      writeln( (tok[0]=="u" ? &Tree.uni : &Tree.inter)(t1, t2) );
   }
}

一応クラスを作る必要がある例がでてきました。ツリーを作っています。writeln などにクラスのインスタンスを渡すと toString() が呼ばれます。

AOJ1002: Extraordinary Grid I

21:26 |

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1002

import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.stdio;
import std.string;

void main()
{
   int t = readln().chomp().to!int();
   foreach(_; 0..t) {
      int N = readln().chomp().to!int();
      bool[] books = readln().chomp().map!"a=='Y'"().array();
      writeln(solve(N, books));
   }
}

int solve(int N, bool[] books)
{
   int[][] dp = new int[][](N+1, 3);
      // dp[x][y] = x列目の配達を終わらせてy行目で終わる最短距離

   foreach(y; 0 .. 3)
      dp[0][y] = 一列を最適に配る(0, y, books[0], books[2*N]);

   foreach(x; 1 .. N+1) {
      bool up = books[2*x-1];
      bool dn = books[2*x-1+2*N];
      if(2*x%(2*N) != 0) {
         up |= books[2*x];
         dn |= books[2*x+2*N];
      }
      foreach(y; 0 .. 3) {
         dp[x][y] = min(
            dp[x-1][0] + 1 + 一列を最適に配る(0, y, up, dn),
            dp[x-1][1] + 1 + 一列を最適に配る(1, y, up, dn),
            dp[x-1][2] + 1 + 一列を最適に配る(2, y, up, dn),
         );
      }
   }

   return dp[N][0];
}

int 一列を最適に配る(int スタート, int ゴール, bool 上の棚に本がある, bool 下の棚に本がある)
{
   int 歩行距離(int[] points)
   {
      int total = 0;
      foreach(i; 1..points.length)
         total += abs(points[i] - points[i-1]);
      return total;
   }

   if(上の棚に本がある && 下の棚に本がある)
      return min(歩行距離([スタート*2, 1, 3, ゴール*2]),
                 歩行距離([スタート*2, 3, 1, ゴール*2])) / 2;
   if(上の棚に本がある && !下の棚に本がある)
      return 歩行距離([スタート*2, 1, ゴール*2]) / 2;
   if(!上の棚に本がある && 下の棚に本がある)
      return 歩行距離([スタート*2, 3, ゴール*2]) / 2;
   return 歩行距離([スタート*2, ゴール*2]) / 2;
}

最後に、DPの書き方。書き方と言っても普通に配列を埋めるだけなのですが、多次元配列を new int[][](N+1, 3) のように一気に確保する書き方は便利です。というか、ないと大変です。変数名や関数名を一部日本語にしてみたのはギャグですので真似しないでください。いや、一人でコード読む分には割とたまに便利ですけど。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20120417

presented by cafelier/k.inaba under

cafelier@SRM

2012-04-17

競技プログラミングのためのD言語(3/2)

AOJ10000 : Hello World

AOJ10001 : X Cubic

AOJ10002 : Rectangle

AOJ10004 : Sorting Three Numbers

AOJ1004 : Pair of Primes

AOJ1005: Advanced Algorithm Class

AOJ1001: Binary Tree Intersection And Union

AOJ1002: Extraordinary Grid I