結果

問題 No.3041 非対称じゃんけん
ユーザー Nauclhlt🪷
提出日時 2025-01-06 16:46:11
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,831 ms / 2,200 ms
コード長 5,432 bytes
コンパイル時間 17,612 ms
コンパイル使用メモリ 172,924 KB
実行使用メモリ 198,584 KB
最終ジャッジ日時 2025-01-21 10:47:04
合計ジャッジ時間 26,374 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (108 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections;
using System.Text;

StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(writer);

Solver.Solve();

Console.Out.Flush();

public static class Solver
{
    private static readonly AtCoderIO cin = new AtCoderIO();

    public static unsafe void Solve()
    {
        int N = cin.Int();
        int F = cin.Int();
        int[] A = cin.IntArray(N);
        int[] B = cin.IntArray(N);
        int[] C = cin.IntArray(N);

        ulong[] masks = new ulong[65];
        for (int i = 1; i <= 64; i++)
        {
            masks[i] = (masks[i - 1] << 1) | 1UL;
        }
        
        int size = ((F * N) / 64) + 1;
        ulong[] dp = new ulong[size];
        ulong[] nextdp = new ulong[size];
        
        dp[0] |= 1UL << (63 - A[0]);
        dp[0] |= 1UL << (63 - B[0]);
        dp[0] |= 1UL << (63 - C[0]);
        Console.WriteLine(BitOperations.PopCount(dp[0]));

        for (int k = 2; k <= N; k++)
        {
            int a = A[k - 1];
            int b = B[k - 1];
            int c = C[k - 1];

            nextdp[0] = (dp[0] >> a);
            for (int i = 1; i < size; i++)
            {
                nextdp[i] = (dp[i] >> a) | ((dp[i - 1] & masks[a]) << (64 - a));
            }

            nextdp[0] |= dp[0] >> b;
            for (int i = 1; i < size; i++)
            {
                nextdp[i] |= (dp[i] >> b) | (dp[i - 1] & masks[b]) << (64 - b);
            }

            nextdp[0] |= dp[0] >> c;
            for (int i = 1; i < size; i++)
            {
                nextdp[i] |= (dp[i] >> c) | (dp[i - 1] & masks[c]) << (64 - c);
            }

            // popcount of next dp
            int ans = 0;
            for (int i = 0; i < size; i++)
            {
                ans += BitOperations.PopCount(nextdp[i]);
            }
            Console.WriteLine(ans);

            (dp, nextdp) = (nextdp, dp);
        }
    }
}

public sealed class AtCoderIO
{
    Queue<string> _readQueue = new Queue<string>();

    private void LoadQueue()
    {
        if (_readQueue.Count > 0) return;
        string line = Console.ReadLine();
        string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
    }

    private void Guard()
    {
        if (_readQueue.Count == 0)
        {
            throw new Exception("NO DATA TO READ");
        }
    }

    public int Int()
    {
        LoadQueue();
        Guard();
        return int.Parse(_readQueue.Dequeue());
    }

    public long Long()
    {
        LoadQueue();
        Guard();
        return long.Parse(_readQueue.Dequeue());
    }

    public string String()
    {
        LoadQueue();
        Guard();
        return _readQueue.Dequeue();
    }

    public short Short()
    {
        LoadQueue();
        Guard();
        return short.Parse(_readQueue.Dequeue());
    }

    public byte Byte()
    {
        LoadQueue();
        Guard();
        return byte.Parse(_readQueue.Dequeue());
    }

    public char Char()
    {
        LoadQueue();
        Guard();
        return char.Parse(_readQueue.Dequeue());
    }

    public double Double()
    {
        LoadQueue();
        Guard();
        return double.Parse(_readQueue.Dequeue());
    }

    public float Float()
    {
        LoadQueue();
        Guard();
        return float.Parse(_readQueue.Dequeue());
    }

    public T Read<T>()
    {
        Type type = typeof(T);
        if (type == typeof(int)) return (T)(object)Int();
        else if (type == typeof(long)) return (T)(object)Long();
        else if (type == typeof(float)) return (T)(object)Float();
        else if (type == typeof(double)) return (T)(object)Double();
        else if (type == typeof(short)) return (T)(object)Short();
        else if (type == typeof(byte)) return (T)(object)Byte();
        else if (type == typeof(char)) return (T)(object)Char();
        else if (type == typeof(string)) return (T)(object)String();
        else return default(T);
    }

    public int[] IntArray(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int();
        }

        return arr;
    }

    public int[] ZeroIndexedPermutation(int n)
    {
        if (n == 0) return Array.Empty<int>();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Int() - 1;
        }

        return arr;
    }

    public long[] LongArray(int n)
    {
        if (n == 0) return Array.Empty<long>();

        long[] arr = new long[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Long();
        }

        return arr;
    }

    public double[] DoubleArray(int n)
    {
        if (n == 0) return Array.Empty<double>();

        double[] arr = new double[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Double();
        }

        return arr;
    }

    public T[] ReadArray<T>(int n)
    {
        if (n == 0) return Array.Empty<T>();

        T[] arr = new T[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Read<T>();
        }

        return arr;
    }
}
0