AtCoder Beginner Contest 025

Submission #1587563

Source codeソースコード

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

const mod = 10 ^^ 9 + 7;
alias mint = FactorRing!mod;

void main()
{
  auto x = new int[](25);
  foreach (i; 0..5) x[i*5..i*5+5] = readln.split.to!(int[])[];

  auto c = new int[](26);
  c[] = -1;
  foreach (i, xi; x) c[xi] = i.to!int;

  auto isValid(int b, size_t e)
  {
    auto x = e % 5, y = e / 5;
    if (x != 0 && x != 4) {
      auto n1 = b.bitTest(y*5+x-1), n2 = b.bitTest(y*5+x+1);
      if (n1 && !n2 || !n1 && n2) return false;
    }
    if (y != 0 && y != 4) {
      auto n1 = b.bitTest((y-1)*5+x), n2 = b.bitTest((y+1)*5+x);
      if (n1 && !n2 || !n1 && n2) return false;
    }
    return true;
  }

  mint[int] memo;

  mint calc(int b, int i)
  {
    if (i > 25) return mint(1);
    if (b in memo) return memo[b];

    auto r = mint(0);

    auto e = c[i];
    if (e != -1) {
      if (isValid(b, e)) r += calc(b.bitSet(e), i+1);
    } else {
      foreach (j; 0..25) {
        if (b.bitTest(j) || x[j]) continue;
        if (isValid(b, j)) r += calc(b.bitSet(j), i+1);
      }
    }

    return memo[b] = r;
  }

  writeln(calc(0, 1));
}

pragma(inline) {
  pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; }
  pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); }
  pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); }
  pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); }

  import core.bitop;
  pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); }
  pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); }
  pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); }
}

struct FactorRing(int m, bool pos = false)
{
  version(BigEndian) {
    union { long vl; struct { int vi2; int vi; } }
  } else {
    union { long vl; int vi; }
  }

  @property int toInt() { return vi; }
  alias toInt this;

  this(int v) { vi = v; }
  this(int v, bool runMod) { vi = runMod ? mod(v) : v; }
  this(long v) { vi = mod(v); }

  ref FactorRing!(m, pos) opAssign(int v) { vi = v; return this; }

  pure auto mod(int v) const
  {
    static if (pos) return v % m;
    else return (v % m + m) % m;
  }

  pure auto mod(long v) const
  {
    static if (pos) return cast(int)(v % m);
    else return cast(int)((v % m + m) % m);
  }

  static if (m < int.max / 2) {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vi + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vi - rhs)); }
  } else {
    pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vl + rhs)); }
    pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vl - rhs)); }
  }
  pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!(m, pos)(mod(vl * rhs)); }

  pure auto opBinary(string op)(FactorRing!(m, pos) rhs) const
    if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.vi); }

  static if (m < int.max / 2) {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vi + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vi - rhs); }
  } else {
    auto opOpAssign(string op: "+")(int rhs) { vi = mod(vl + rhs); }
    auto opOpAssign(string op: "-")(int rhs) { vi = mod(vl - rhs); }
  }
  auto opOpAssign(string op: "*")(int rhs) { vi = mod(vl * rhs); }

  auto opOpAssign(string op)(FactorRing!(m, pos) rhs)
    if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.vi); }
}

Submission

Task問題 D - 25個の整数
User nameユーザ名 tesh
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3595 Byte
File nameファイル名
Exec time実行時間 301 ms
Memory usageメモリ使用量 51436 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
Subtask1 30 / 30 sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt,test-1-01.txt,test-1-02.txt,test-1-03.txt,test-1-04.txt,test-1-05.txt,test-1-06.txt,test-1-07.txt,test-1-08.txt,test-1-09.txt,test-1-10.txt,test-1-11.txt,test-1-12.txt,test-1-13.txt,test-1-14.txt,test-1-15.txt
Subtask2 70 / 70 sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt,test-1-01.txt,test-1-02.txt,test-1-03.txt,test-1-04.txt,test-1-05.txt,test-1-06.txt,test-1-07.txt,test-1-08.txt,test-1-09.txt,test-1-10.txt,test-1-11.txt,test-1-12.txt,test-1-13.txt,test-1-14.txt,test-1-15.txt,test-2-01.txt,test-2-02.txt,test-2-03.txt,test-2-04.txt,test-2-05.txt,test-2-06.txt,test-2-07.txt,test-2-08.txt,test-2-09.txt,test-2-10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB
test-1-01.txt AC 1 ms 256 KB
test-1-02.txt AC 1 ms 256 KB
test-1-03.txt AC 1 ms 256 KB
test-1-04.txt AC 1 ms 256 KB
test-1-05.txt AC 1 ms 256 KB
test-1-06.txt AC 1 ms 256 KB
test-1-07.txt AC 1 ms 256 KB
test-1-08.txt AC 1 ms 256 KB
test-1-09.txt AC 1 ms 256 KB
test-1-10.txt AC 1 ms 256 KB
test-1-11.txt AC 1 ms 256 KB
test-1-12.txt AC 1 ms 256 KB
test-1-13.txt AC 1 ms 256 KB
test-1-14.txt AC 1 ms 380 KB
test-1-15.txt AC 1 ms 256 KB
test-2-01.txt AC 4 ms 3068 KB
test-2-02.txt AC 3 ms 508 KB
test-2-03.txt AC 1 ms 380 KB
test-2-04.txt AC 5 ms 1148 KB
test-2-05.txt AC 15 ms 3580 KB
test-2-06.txt AC 187 ms 19836 KB
test-2-07.txt AC 109 ms 16892 KB
test-2-08.txt AC 164 ms 20732 KB
test-2-09.txt AC 144 ms 19580 KB
test-2-10.txt AC 301 ms 51436 KB