結果

問題 No.1470 Mex Sum
コンテスト
ユーザー ID 21712
提出日時 2026-05-24 18:28:04
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 985 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 10,462 ms
コンパイル使用メモリ 285,660 KB
実行使用メモリ 7,972 KB
最終ジャッジ日時 2026-05-24 18:28:20
合計ジャッジ時間 15,267 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"

func main() {
	rd:=bf.NewReader(Stdin)
	var n int
	Fscan(rd,&n)
	var c1,c2,c3 int
	for i := 0; i < n; i++ {
		var a int
		Fscan(rd,&a)
		switch a {
			case 1:
				c1++
			case 2:
				c2++
			default:
				c3++
		}
	}
	ans := n*(n-1)/2 + c1*(c1-1)/2 + 2*c1*c2 + c1*c3
	Println(ans)
}

/*
考察

mex(i,j)の値の候補は 1, 2, 3 のいずれか

mex(1, 1) で 2
mex(1, 2) で 3
mex(1, 3) で 2
mex(2, 2) で 1
mex(2, 3) で 1
mex(3, 3) で 1

一方が1のときmexが2か3になるぽい？
Aiを 1　と 2 と 3以上 でまとめて組み合わせ計算すればいいのかな

Ai = 1 が c1 個
Ai = 2 が c2 個
Ai >= 3 が c3 個

mex(1,1) の組は C11 = c1*(c1-1)/2 個
mex(1,2) の組は C12 = c1*c2 個
mex(1,3) の組は C13 = c1*c3 個
それ以外の組は n*(n-1)/2 - (C11 + C12 + C13)
ゆえに答えは
ans = 2*c11 + 3*C12 + 2*C13 + 1*(n*(n-1)/2 - (C11 + C12 + C13))
    = n*(n-1)/2 + C11 + 2*C12 + C13

*/
0