Typical DP Contest

Submission #5411035

Source codeソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt();
            var N = line[0];
            var K = line[1];

            if (K == 2)
            {
                var dp2 = new int[N, 2];
                dp2[0, 1] = 1;
                for (int i = 0; i < N - 1; i++)
                {
                    dp2[i + 1, 0] = dp2[i, 0] + dp2[i, 1];
                    dp2[i + 1, 1] = dp2[i, 0];
                }
                return dp2[N - 1, 1];
            }

            var dp = new int[N];
            dp[0] = 1;
            for (int i = 0; i < K - 2; i++)
            {
                dp[i + 1] = dp[i] * 2 % mod;
            }

            for (int i = K - 2; i < N - 2; i++)
            {
                dp[i + 1] = (2 * dp[i] - dp[i - (K - 2)]) % mod;
            }

            return (dp[N - 2] - dp[N - 2 - (K - 2)]) % mod;
        }

        public const int mod = 1000000007;
        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

    #region Console
    public class ConsoleReader { public virtual string String() => Console.ReadLine(); public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); public ulong ULong() => ulong.Parse(String()); public double Double() => double.Parse(String()); public string[] Split() => String().Split().ToArray(); public int[] SplitInt() => String().Split().Select(int.Parse).ToArray(); public long[] SplitLong() => String().Split().Select(long.Parse).ToArray(); public ulong[] SplitULong() => String().Split().Select(ulong.Parse).ToArray(); public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray(); public IEnumerable<string> Repeat(int count) { for (int i = 0; i < count; i++) yield return String(); } public IEnumerable<int> RepeatInt(int count) { for (int i = 0; i < count; i++) yield return Int(); } public IEnumerable<long> RepeatLong(int count) { for (int i = 0; i < count; i++) yield return Long(); } public IEnumerable<string[]> RepeatSplit(int count) { for (int i = 0; i < count; i++) yield return Split(); } public IEnumerable<int[]> RepeatSplitInt(int count) { for (int i = 0; i < count; i++) yield return SplitInt(); } }
    #endregion
}

Submission

Task問題 F - 準急
User nameユーザ名 naminodarie
Created time投稿日時
Language言語 C# (Mono 4.6.2.0)
Status状態 WA
Score得点 0
Source lengthソースコード長 2833 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 4 00,01,02,03,04,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00 WA
01 AC 34 ms 16992 KB
02 WA
03 WA
04 WA
90 AC 23 ms 11348 KB
91 AC 23 ms 11348 KB