結果

問題 No.1231 Make a Multiple of Ten
コンテスト
ユーザー ID 21712
提出日時 2026-06-04 01:36:11
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 2,346 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,502 ms
コンパイル使用メモリ 278,388 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2026-06-04 01:36:32
合計ジャッジ時間 20,831 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import "math/rand"

func main() {
	rd := bf.NewReader(Stdin)
	
	var n int
	Fscan(rd,&n)
	
	a := make([]int, n)
	for i := range a {
		Fscan(rd, &a[i])
	}
	
	ans := solve1(n, a)
	
	Println(ans)
	
}

func solve1(n int, a []int) int {
	dp := make([]int, 10)
	tmp := make([]int, 10)
	dp[0] = 1
	for _, x := range a {
		copy(tmp, dp)
		for i, c := range dp {
			if c > 0 {
				t := (i+x)%10
				tmp[t] = max(tmp[t], c+1)
			}
		}
		dp,tmp = tmp,dp
	}
	return dp[0]-1
}

func solve2(n int, a []int) int {
	table := make([]int, 10)
	sum := 0
	for _, x := range a {
		table[x%10]++
		sum = (sum+x)%10
	}
	if sum == 0 {
		return n
	}	
	dp := make([][]bool, 10)
	for i := range dp {
		dp[i] = make([]bool, 10)
	}
	dp[0][0] = true
	for i := 1; i < 10; i++ {
		if table[i] == 0 {
			continue
		}
		for c := 8; c >= 0; c-- {
			for k := 1; k <= table[i] && c+k <= 9; k++ {
				for j := 0; j < 10; j++ {
					if dp[c][j] {
						dp[c+k][(j+k*i)%10] = true
					}
				}
			}
		}
	}
	for i := 1; i < 10; i++ {
		if dp[i][sum%10] {
			return n - i
		}
	}
	return 0
}

func init() {
	check()
}

func check() {
	for t := 0; t < 10000; t++ {
		n := rand.Intn(500)+30
		a := make([]int, n)
		for i := range a {
			a[i] = rand.Intn(100)+1
		}
		ans1 := solve1(n, a)
		ans2 := solve2(n, a)
		if ans1 != ans2 {
			println("n=",n)
			println("a=",Sprint(a))
			println("ans1=",ans1)
			println("ans2=",ans2)
			panic("wrong")
		}
	}
}

/*
考察

mod 10 で数え上げDPかなあ・・・わからん
DP[i枚目][sum(A0...Ai) mod 10] = 最大使用枚数
とか？

あるいは
Aの総和のmod 10が0にならない場合
その端数分を引き算で除去できる最小の枚数を求める・・・とか？
例えば
sum(A) = 1 (mod 10)
なら
1枚で1 (mod 10)になるカード
2枚の和で 1 (mod 10) になる組み合わせのカード
...
9枚の和で 1 (mod 10) になる組み合わせのカード
を見つければよい…？
DP[枚数][? (mod 10)] = 存在する(1)か否(0)か
これそのままA全体に対してやっちゃうとTLEしそうなので
Aを事前にmod 10で分類して枚数で管理すれば10^3程度の計算で済む？


入力のデータ個数が2e5を超えるとbufio使わないと入力読み込むだけでTLEするのつらい
IOでのTLEはつらい

*/
0