結果

問題 No.906 Y字グラフ
コンテスト
ユーザー kakel-san
提出日時 2026-01-19 00:37:53
言語 C#
(.NET 10.0.101)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 1,933 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,589 ms
コンパイル使用メモリ 169,340 KB
実行使用メモリ 193,832 KB
最終ジャッジ日時 2026-01-19 00:38:12
合計ジャッジ時間 14,253 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (101 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Security.Cryptography;
using Microsoft.VisualBasic;

class Program
{
    static int NN => int.Parse(ReadLine());
    static long[] NList => ReadLine().Split().Select(long.Parse).ToArray();
    static long[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = long.Parse(ReadLine()) - 4;
        var min = (n + 2) / 3;
        var max = n;
        if (min == max)
        {
            WriteLine(1);
            return;
        }
        var min1 = min + 1;
        var max1 = max - 1;
        if (min % 2 == max % 2)
        {
            var add = min * 3 - n;
            WriteLine((Mountain(min / 2, max / 2, add / 2) + Mountain(min1 / 2, max1 / 2, (add + 3) / 2)) % mod);
        }
        else
        {
            var add = min * 3 - n;
            WriteLine((Mountain(min / 2, max1 / 2, add / 2) + Mountain(min1 / 2, max / 2, (add + 3) / 2)) % mod);
        }
    }
    static int mod = 1_000_000_007;
    static int half = 500_000_004;
    static long Mountain(long l, long r, long add)
    {
        r -= l;
        l = 0;
        var c1 = -1L;
        var c2 = -1L;
        for (var i = Math.Max(0L, (r - 5) / 4); i <= Math.Min(r, (r + 5) / 4); ++i)
        {
            var v1 = i * 3 + add;
            var v2 = r - i;
            if (v1 <= v2) c1 = i;
            if (c2 < 0 && v1 >= v2) c2 = i;
        }
        if (c1 == c2)
        {
            if (c1 == 0) ++c2;
            else --c1;
        }
        var len1 = (c1 - l + 1) % mod;
        var len2 = (r - c2 + 1) % mod;
        return len1 * (len1 - 1) % mod * 3 % mod * half % mod + len1 * (add + 1) % mod + len2 * (len2 + 1) % mod * half % mod;
    }
}
0