cafelier@SRM

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