ARC133-C Row Column Sums

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2 4 3");
            WillReturn.Add("0 2");
            WillReturn.Add("1 2 2 0");
            //11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3 4");
            WillReturn.Add("0 1 2");
            WillReturn.Add("1 2 3");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mH;
    static long mW;
    static long mK;

    static long[] mYokoSumArr;
    static long[] mTateSumArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mH = wkArr[0];
        mW = wkArr[1];
        mK = wkArr[2];

        mYokoSumArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mTateSumArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 横計と縦計がmod k で不一致なら不可
        long YokoSumMod = 0;
        Array.ForEach(mYokoSumArr, pX =>
        {
            YokoSumMod += pX;
            YokoSumMod %= mK;
        });

        long TateSumMod = 0;
        Array.ForEach(mTateSumArr, pX =>
        {
            TateSumMod += pX;
            TateSumMod %= mK;
        });

        if (YokoSumMod != TateSumMod) {
            Console.WriteLine(-1);
            return;
        }

        long YokoSumReal = 0;
        foreach (long EachYokoSum in mYokoSumArr) {
            long ProdVal = (mK - 1) * mW;
            long MinusVal = Solve(ProdVal, EachYokoSum);
            YokoSumReal += ProdVal - MinusVal;
        }

        long TateSumReal = 0;
        foreach (long EachTateSum in mTateSumArr) {
            long ProdVal = (mK - 1) * mH;
            long MinusVal = Solve(ProdVal, EachTateSum);
            TateSumReal += ProdVal - MinusVal;
        }

        Console.WriteLine(Math.Min(YokoSumReal, TateSumReal));
    }

    // 合同方程式 A - ? ≡ B mod K
    // の ? を返す
    static long Solve(long pA, long pB)
    {
        pA %= mK;
        pB %= mK;

        long Answer = pA - pB;
        Answer %= mK;

        if (Answer < 0) Answer += mK;
        return Answer;
    }
}

解説

□□□□０
□□□□２
２２０１

の入力例で考えます。

必要条件として、
横計の総合計と
縦計の総合計が
mod k で見て不一致なら、解なしとなります。

mod k ではなく実際の和での最大値を考えると
(k-2) * マス目の数 - ? ≡ 縦計または横計 mod k
の合同方程式で、横計と縦計の最大値を求めることができます。

横計と縦計の2つの最大値の中で
小さいほうを調整により達成可能なので
これが解になります。