#1171305 (C#) No.2035 Tunnel

• 問題: No.2035 Tunnel
• ユーザー: true
• 提出日時: 2026-07-13 03:33:04
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 9,490 bytes
• コンパイル時間: 6,797 ms
• コンパイル使用メモリ: 172,248 KB
• 実行使用メモリ: 201,000 KB
• 最終ジャッジ日時: 2026-07-13 03:33:15
• 合計ジャッジ時間: 10,327 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 28

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System.Text;using System.Numerics;using System.Runtime.CompilerServices;using System;using System.Collections.Generic;using System.Linq;using System.IO;using System.Security.Cryptography;using System.Buffers;using System.Diagnostics;
#nullable enable


var fs = new FastScanner();
var sb = new StringBuilder();




int N=fs.Int();
var S=fs.String();

var nxt=Nms.Array(N, -1);

var st=new Stack<int>();
for(int i=0; i<N; ++i)
{
  if(S[i]=='.') continue;

  if(st.Count>0) nxt[st.Peek()]=i;
  st.Push(i);
}

var arriveAt=Nms.Array(N, 0);

while(st.Count>0)
{
  var u=st.Pop();
  arriveAt[u]=Math.Max(N-u, nxt[u]<0 ? 0 : arriveAt[nxt[u]]+2);

  if(st.Count==0) sb.Append(arriveAt[u]).AppendLine();
}










































Console.Write(sb.ToString());
Console.Out.Flush();
Environment.Exit(0);

static class Nms
{
  public static T[] Array<T>(int n, Func<T> f)
  {
    var a = new T[n];
    for (int i = 0; i < n; i++) a[i] = f();
    return a;
  }
  public static T[] Array<T>(int n, Func<int, T> f)
  {
    var a = new T[n];
    for (int i = 0; i < n; i++) a[i] = f(i);
    return a;
  }
  public static T[] Array<T>(int n, T val)
  {
    var a = new T[n];
    for (int i = 0; i < n; i++) a[i] = val;
    return a;
  }
  public static T[][] Matrix<T>(int h, int w, Func<T> f)
  {
    var a = new T[h][];
    for (int i = 0; i < h; ++i)
    {
      a[i] = new T[w];
      for (int j = 0; j < w; ++j) a[i][j] = f();
    }
    return a;
  }
  public static T[][] Matrix<T>(int h, int w, Func<int, int, T> f)
  {
    var a = new T[h][];
    for (int i = 0; i < h; ++i)
    {
      a[i] = new T[w];
      for (int j = 0; j < w; ++j) a[i][j] = f(i, j);
    }
    return a;
  }
  public static T[][] Matrix<T>(int h, int w, T val)
  {
    var a = new T[h][];
    for (int i = 0; i < h; ++i)
    {
      a[i] = new T[w];
      for (int j = 0; j < w; ++j) a[i][j] = val;
    }
    return a;
  }
  public static StackArray<T> Stack<T>()
    => new StackArray<T>();}

sealed class Count
{
  private readonly int n;
  private readonly long mod;
  private readonly long[] fact;
  private readonly long[] inv;

  public Count(int n, long mod)
  {
    ++n;
    this.n = n;
    this.mod = mod;
    fact = new long[n];

    fact[0] = fact[1] = 1 % mod;
    for (int i = 2; i < n; ++i) fact[i] = fact[i - 1] * i % mod;

    inv = new long[n];
    inv[n - 1] = Sugaku.ModPow(fact[n - 1], mod - 2, mod);
    for (int i = n - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
  }

  public long P(int a, int b)
    => (a < 0 || b < 0 || b > a) ? 0 : fact[a] * inv[a - b] % mod;

  public long C(int a, int b)
   => (a < 0 || b < 0 || b > a) ? 0 : fact[a] * inv[a - b] % mod * inv[b] % mod;

  public long H(int a, int b)
    => C(a + b - 1, a - 1);

  /// <summary>
  /// choose k from n
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long Binom(int n, int k)
    => C(n, k);

  /// <summary>
  /// choose k from n and sort
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long Arrange(int n, int k)
    => P(n, k);

  /// <summary>
  /// have k share n
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long Share(int n, int k)
    => C(n + k - 1, n);

  /// <summary>
  /// split n into nonempty k
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long Part(int n, int k)
    => C(n - 1, k - 1);

  /// <summary>
  /// split n members into nonempty k teams
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long TeamUp(int n, int k)
  {
    if (n < 0 || k < 0 || n < k) return 0;

    long sum = 0;
    for (int i = 0; i <= k; ++i)
    {
      long t = (k - i) % 2 == 0 ? 1 : -1;
      t *= C(k, i) * Sugaku.ModPow(i, n, mod) % mod;
      sum = (sum + mod + t) % mod;
    }
    return sum;
  }

  /// <summary>
  /// split n members into nonempty k groups
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long GroupUp(int n, int k)
    => TeamUp(n, k) * inv[k] % mod;


  /// <summary>
  /// classify n members using k unlabeled groups
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  /// <returns></returns>
  public long Classify(int n, int k)
  {
    if (n < 0 || k < 0) return 0;

    var p = Nms.Array<long>(k + 1, 0);

    for (int i = 0; i <= k; ++i)
    {
      p[i] = i % 2 == 1 ? (mod - inv[i]) % mod : inv[i];
      if (i > 0) p[i] = (p[i] + p[i - 1]) % mod;
    }

    long sum = 0;
    for (int i = 0; i <= k; ++i)
    {
      sum = (sum + inv[i] * Sugaku.ModPow(i, n, mod) % mod * p[k - i]) % mod;
    }
    return sum;
  }

  /// <summary>
  /// represent n using k unordered elements
  /// </summary>
  /// <param name="n"></param>
  /// <param name="k"></param>
  public long Represent(int n, int k)
  {
    var dp = Nms.Matrix<long>(n + 1, k + 1, 0);

    for (int j = 0; j <= k; ++j)
    {
      dp[0][j] = 1;
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= k; ++j)
    {
      dp[i][j] = (dp[i][j - 1] + (i - j >= 0 ? dp[i - j][j] : 0)) % mod;
    }

    return dp[n][k];
  }
}

class StackArray<T>(int n = 128)
{
  private T[] v = new T[n];
  private int count = 0;
  private int n = n;

  public void Push(T val)
  {
    if (count == n)
    {
      var x = new T[2 * n];
      Array.Copy(v, x, count);
      v = x;
      n <<= 1;
    }
    v[count++] = val;
  }

  public T Peek()
  {
    Validate(0);
    return v[count - 1];
  }

  public T Pop()
  {
    Validate(0);
    T item = v[--count];
    v[count] = default!;
    return item;
  }

  public int Count => count;

  public T this[int k]
  {
    get
    {
      Validate(k);
      return v[k];
    }
  }

  private void Validate(int t)
  {
    if (t < 0 || t >= count) throw new IndexOutOfRangeException();
  }
}

static class Sugaku
{

  public static long ModPow(long b, long r, long MOD)
  {
    long res = 1;
    b %= MOD;
    while (r > 0)
    {
      if ((r & 1) != 0) res = res * b % MOD;
      b = b * b % MOD;
      r >>= 1;
    }
    return res;
  }}

class FastScanner
{
  private readonly Stream stream = Console.OpenStandardInput();
  private readonly byte[] buffer = new byte[1 << 16];
  private int ptr = 0, len = 0;

  private byte Read()
  {
    if (ptr >= len)
    {
      len = stream.Read(buffer, 0, buffer.Length);
      ptr = 0;
      if (len == 0) return 0;
    }
    return buffer[ptr++];
  }

  public int Int()
  {
    int c;
    while ((c = Read()) <= ' ') if (c == 0) return 0;
    int sign = 1;
    if (c == '-')
    {
      sign = -1;
      c = Read();
    }
    int val = c - '0';
    while ((c = Read()) >= '0')
    {
      checked
      {
        val = val * 10 + c - '0';
      }
    }
    return val * sign;
  }

  public (int, int) Int2()
    => (Int(), Int());

  public (int, int, int) Int3()
    => (Int(), Int(), Int());

  public (int, int, int, int) Int4()
    => (Int(), Int(), Int(), Int());

  public long Long()
  {
    int c;
    while ((c = Read()) <= ' ') if (c == 0) return 0;
    int sign = 1;
    if (c == '-')
    {
      sign = -1;
      c = Read();
    }
    long val = c - '0';
    while ((c = Read()) >= '0')
      val = val * 10 + c - '0';
    return val * sign;
  }

  public (long, long) Long2()
    => (Long(), Long());

  public (long, long, long) Long3()
    => (Long(), Long(), Long());

  public (long, long, long, long) Long4()
    => (Long(), Long(), Long(), Long());

  public (int, long) IntLong()
    => (Int(), Long());

  public int[] Digits()
  {
    var s = this.String();
    var res = new int[s.Length];
    for (int i = 0; i < s.Length; ++i) res[i] = s[i] - '0';
    return res;
  }

  public string String()
  {
    int c;
    while ((c = Read()) <= ' ') if (c == 0) return "";
    var sb = new StringBuilder();
    do
    {
      sb.Append((char)c);
      c = Read();
    } while (c > ' ');
    return sb.ToString();
  }
  public (string, string) String2()
    => (String(), String());
  public (string, string, string) String3()
    => (String(), String(), String());

  public double Double()
  {
    int c;
    while ((c = Read()) <= ' ') if (c == 0) return 0;

    int sign = 1;
    if (c == '-')
    {
      sign = -1;
      c = Read();
    }

    double val = 0;

    // integer part
    while (c >= '0' && c <= '9')
    {
      val = val * 10 + (c - '0');
      c = Read();
    }

    // fractional part
    if (c == '.')
    {
      double scale = 1;
      while ((c = Read()) >= '0' && c <= '9')
      {
        scale *= 0.1;
        val += (c - '0') * scale;
      }
    }

    // exponent part
    if (c == 'e' || c == 'E')
    {
      int esign = 1;
      int exp = 0;

      c = Read();
      if (c == '-')
      {
        esign = -1;
        c = Read();
      }
      else if (c == '+')
      {
        c = Read();
      }

      while (c >= '0' && c <= '9')
      {
        exp = exp * 10 + (c - '0');
        c = Read();
      }

      val *= Math.Pow(10, esign * exp);
    }

    return val * sign;
  }

  public (double, double) Double2()
    => (Double(), Double());
  public (double, double, double) Double3()
    => (Double(), Double(), Double());

  public char Char()
  {
    int c;
    while ((c = Read()) <= ' ') if (c == 0) return '\0';
    return (char)c;
  }
}