結果

問題 No.1359 [Zelkova 3rd Tune] 四人セゾン
コンテスト
ユーザー ID 21712
提出日時 2026-05-26 18:34:14
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 721 ms / 2,000 ms
コード長 3,503 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,055 ms
コンパイル使用メモリ 277,604 KB
実行使用メモリ 16,512 KB
最終ジャッジ日時 2026-05-26 18:35:25
合計ジャッジ時間 66,090 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 75
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"
import . "math/big"

func main() {
	rd := bf.NewReader(Stdin)

	var n,k,m int
	Fscan(rd,&n,&k,&m)
	
	p := make([]int, n)
	for i := range p {
		Fscan(rd,&p[i])
	}
	Ints(p)
	
	e := make([]int, n)
	for i := range e {
		Fscan(rd,&e[i])
	}
	Ints(e)
	
	a := make([]int, n)
	for i := range a {
		Fscan(rd, &a[i])
	}
	Ints(a)
	
	h := make([]int, n)
	for i := range h {
		Fscan(rd, &h[i])
	}
	Ints(h)
	
	M := NewInt(int64(m))
	K := NewInt(int64(k))
	
	ans := 0
	for i := 0; i < n; i++ {
		d := max(p[i],e[i],a[i],h[i])-min(p[i],e[i],a[i],h[i])
		ans += int(new(Int).Exp(NewInt(int64(d)),K,M).Int64())
		ans %= m
	}
	
	Println(ans)
}

/*
考察

全体4N人のP,E,A,Hうちのレーティング最小値X
X = min(min(P), min(E), min(A), min(H))
このレーティングXに対して不公平を最小にするのは
P,E,A,Hそれぞれのレーティング最小値でグループを構成することで達成できる（はず）
最小値同士でグループを作ったのでP,E,A,Hからレーティング最小値の人を除いた残りをP',E',A',H'とする
P',E',A',H'の中でのレーティング最小値X'についても同様にすることでグループを構成できるはず

つまり小さい順に貪欲法で作っていけばよさそう？

これが正しいかの証明を自力ではできないのでACするかは不明
直観的には
不公平さの計算に寄与しないいずれかを他の要素と交換すると不公平さが増える可能性がある（減る可能性はない）
という感じがする

P,E,A,Hがソート済みとして
それぞれの最小を P[1],E[1],A[1],H[1]
その次に小さいのをP[2],E[2],A[2],H[2]
として
仮に
P[1] = min(P[1],E[1],A[1],H[1])
H[1] = max(P[1],E[1],A[1],H[1])
とすると
P[1] <= E[1] <= H[1]
P[1] <= A[1] <= H[1]
P[1] <= P[2]
E[1] <= E[2]
A[1] <= A[2]
H[1] <= H[2]
で
グループ1を G1 = { P[1], E[1], A[1], H[1] }
グループ2を G2 = { P[2], E[2], A[2], H[2] }
で構成したとして

例えばP[1]とP[2]を交換すると
G1は最小値min(G1)が上昇して不公正さが減る可能性はある(P[1] < P[2] のとき)
一方でG2は最小値min(G2)が下降し不て公正さが増える可能性がある（P[1] < P[2] かつ P[1] < min(E[2],A[2],H[2]) のとき）
この不公平さの上昇と下降が同時に起きたときは良くても差し引きゼロで不公正さの総和が減少することはない

例えばE[1]とE[2]を交換すると
G1は最大値max(G1)が上昇して不公正さが増える可能性がある（H[1] < E[2] のとき）
G2は最小値が下降して不公正さが増える可能性がある（E[1] < E[2] かつ E[2] = min(P[2],E[2],A[2],H[2]) のとき）
不公正さの総和が増える可能性があるだけ

例えばH[1]とH[2]を交換すると
G1は最大値max(G1)が上昇して不公正さが増える可能性がある（H[1] < H[2]のとき）
G2は最大値max(G2)が下降して不公正さが減る可能性がある（H[1] < H[2] かつ H[2] = max(P[2],E[2],A[2],H[2]) のとき）
この不公平さの上昇と下降が同時に起きたときは良くても差し引きゼロで不公正さの総和が減少することはない

よって、小さい順にグループ作る貪欲法でＯＫ？

ところで、P,E,A,H の文字はどういう理由で選ばれたのだろう？
春・夏・秋・冬の読みとも英語とも無関係そうな


*/
0