科学の箱

科学・IT・登山の話題

AtCoder

AtCoder ABC 139D ModSum

投稿日:

問題

正の整数Nが与えられる。
{1,2,3,….N}に関する順列Pについて、Σ i mod Pi (i=1 to N)の最大値を求める。

方針

少ない値について全探索によって答えを出してみる→具体的には10までを全探索する。
その答えについてトレンドを見る。
トレンドを説明してみる。

シミュレーション

N=10
ans=tmp=0
mod=[]

import itertools
# 

for n in range(1,N+1):
    l=[i for i in range(1,n+1)]
    p=list(itertools.permutations(l))
    ans=tmp=0
    for i in p:
        tmp=0
        cnt=1
        for j in i:
            # print(j,cnt, cnt%j)
            tmp+=cnt%j
            cnt+=1
        if ans==tmp:
            mod.append(i)
        elif ans<tmp:
            mod=[]
            mod.append(i)
            ans=tmp
    print(ans, mod)

 

結果

0 [(1,)]
1 [(2, 1)]
3 [(1, 3, 2), (2, 3, 1)]
6 [(2, 3, 4, 1)]
10 [(1, 3, 4, 5, 2), (2, 1, 4, 5, 3), (2, 3, 4, 5, 1)]
15 [(2, 3, 4, 5, 6, 1)]
21 [(1, 3, 2, 5, 6, 7, 4), (1, 3, 4, 5, 6, 7, 2), (2, 3, 1, 5, 6, 7, 4), (2, 3, 4, 5, 6, 7, 1)]
28 [(2, 1, 4, 5, 6, 7, 8, 3), (2, 3, 4, 5, 6, 7, 8, 1)]
36 [(1, 3, 4, 5, 6, 7, 8, 9, 2), (2, 3, 4, 1, 6, 7, 8, 9, 5), (2, 3, 4, 5, 6, 7, 8, 9, 1)]
45 [(2, 3, 4, 5, 6, 7, 8, 9, 10, 1)]

 

シミュレーション結果

数列P={2,3,4…N,1}の時に最大になっていることがわかる。

考察

i=1,2,…,Nを割った時に余りの最大値は割られる数をそのまま利用できた時であるから、{1,2,…N-1,N}となることがわかる。

このような結果にするにはiに対してi+1で割ってあげればよい。

しかし最後のNについてはN+1はないので1を利用する。よって余りの最大値の数列は{1,2,…,N-1,0}である。この合計値はN*(N-1)/2となる。

メタ情報

inarticle



メタ情報

inarticle



-AtCoder
-

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

AtCoder ABC 174D Alter Altar

問題 左から右へN個の石が並んでいる。石の種類は白もしくは赤のいづれかである。 石について、下記の操作を何回でも実行できる。 2個の石を選んで場所を入れ替える(隣合ってなくてよい)。 1個の石を選んで …

no image

蟻本 P42 硬貨の問題

貪欲法の基本 その時点で最善の手を尽くす 尽くした結果を目的とする値に反映させる。 次善の手になるようにする。 1に戻る 硬貨の問題 A=int(input()) *C,=map(int,input( …

no image

UnionFindのfindについて処理を考える。

UnionFindにおけるfind()もしくはroot()はルート(グループの根)を見つける処理である。 記述方法としては2種類ある。 whileループを回す 再帰処理 それぞれについて動きを確認して …

no image

Xより大きな素数で最小値を求める

atcoder ABC149 C Next Primeより <span class="h2"> while any(x%i<1 for i in range(2, …

2020年9月
« 8月   10月 »
 123456
78910111213
14151617181920
21222324252627
282930  

side bar top



アーカイブ

カテゴリー