結果

問題 No.1603 Manhattan Social Distance
コンテスト
ユーザー ID 21712
提出日時 2026-05-20 01:22:09
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,240 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 17,816 ms
コンパイル使用メモリ 290,320 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-20 01:22:28
合計ジャッジ時間 15,544 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var n,h,w int
	Scan(&n,&h,&w)
	ans := (n/2)*(n-n/2)*((w-1)+(h-1))
	Println(ans)
}

/*
考察

N=5,H=1,W>=N+2で考える
5人バラバラに割り当てたとき
1 < x1 < x2 < x3 < x4 < x5 < W
このとき
x1を1に1だけ近づけると
|x1-x2|,|x1-x3|,|x1-x4|,|x1-x5|がそれぞれ1だけ増えて総和は4増える
x1をWに1だけ近づけると
|x1-x2|,|x1-x3|,|x1-x4|,|x1-x5|がそれぞれ1だけ減って総和は4減る
x2,x3,x4,x5にも同様の考え方をすると
x1,x2は1に近づけるほうが総和が増える
x4,x5はWに近づけるほうが総和が増える
x3はどこにあっても変わらない
つまり、x1=x2=1、x4=x5=Wが最適、x3は1でもWでもそれ以外でもOKだが処理手間を考えると1かWに置いたほうが計算が楽
すなわち、1かWに半分ずつ割り当てればOK
マンハッタン距離なのでx方向とy方向は独立で考えればいいのでy方向でも同様に1かHに半分ずつ割り当てればOK

x=1にfloor(N/2)を割り当て
x=WにN-floor(N/2)を割り当てたとして
x=1側とx=W側のペアの組み合わせ総数はfloor(N/2)*(N-floor(N/2))、距離はW-1、なので距離の総和はその積

*/
0