結果

問題 No.640 76本のトロンボーン
ユーザー te-shte-sh
提出日時 2018-01-30 11:15:03
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,114 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 107,320 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 23:43:27
合計ジャッジ時間 1,391 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}
T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}

void main()
{
  int n; readV(n);
  auto s = readArrayM!string(n);

  auto r1 = calc(n, s);
  auto r2 = calc(n, s.transposed.map!(si => si.array.to!string).array);

  writeln(max(r1, r2));
}

auto calc(int n, string[] s)
{
  auto h = new int[][](n, n), v = new int[][](n, n);
  foreach (i; 0..n)
    foreach (j; 0..n) {
      h[i][j] = s[i][j] == '#';
      v[i][j] = s[j][i] == '#';
    }

  auto hc = new CumulativeSum!int*[](n), vc = new CumulativeSum!int*[](n);
  foreach (i; 0..n) {
    hc[i] = new CumulativeSum!int(h[i]);
    vc[i] = new CumulativeSum!int(v[i]);
  }

  auto rvh1 = 0;
  if (!(*vc[0])[0..n-1]) {
    ++rvh1;
    foreach (i; 0..n-1) rvh1 += !(*hc[i])[1..n];
    rvh1 += !(*hc[n-1])[0..n-1] || !(*hc[n-1])[1..n];
  }

  auto rvh2 = 0;
  if (!(*vc[0])[1..n]) {
    ++rvh2;
    rvh2 += !(*hc[0])[0..n-1] || !(*hc[0])[1..n];
    foreach (i; 1..n) rvh2 += !(*hc[i])[1..n];
  }

  auto rvh3 = 0;
  if (!(*vc[n-1])[0..n-1]) {
    ++rvh3;
    foreach (i; 0..n-1) rvh3 += !(*hc[i])[0..n-1];
    rvh3 += !(*hc[n-1])[0..n-1] || !(*hc[n-1])[1..n];
  }

  auto rvh4 = 0;
  if (!(*vc[n-1])[1..n]) {
    ++rvh4;
    rvh4 += !(*hc[0])[0..n-1] || !(*hc[0])[1..n];
    foreach (i; 1..n) rvh4 += !(*hc[i])[0..n-1];
  }

  auto rh = 0;
  foreach (i; 0..n)
    rh += !(*hc[i])[0..n-1] || !(*hc[i])[1..n];

  auto ro = 0;
  if (!(*hc[0])[0..n] && !(*hc[n-1])[0..n] && !(*vc[0])[0..n] && !(*vc[n-1])[0..n])
    ro += 4;

  return max(rvh1, rvh2, rvh3, rvh4, rh, ro);
}

struct CumulativeSum(T)
{
  size_t n;
  T[] s;

  this(T[] a)
  {
    n = a.length;
    s = new T[](n+1);
    s[0] = T(0);
    foreach (i; 0..n) s[i+1] = s[i] + a[i];
  }

  T opSlice(size_t l, size_t r) { return s[r]-s[l]; }
  size_t opDollar() { return n; }
}
0