質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.53%

  • Python 3.x

    6309questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

python 辞書 値 ○個単位で最小値を求める

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 184

zeitaku_fire

score 18

num = [i for i in map(int,input().split(" "))] #入力データの一行目取り出し [7, 3]

date=[]
uryo=[]
for i in range(num[0]): #7回繰り返し


    dater=[i for i in map(int,input().split(" "))] #入力データをリストとして取り出し
    date.append(dater[0])
    uryo.append(dater[1])
    player_ans = {}
    for h, p in zip(date, uryo): #取り出した入力データをリストに格納
        player_ans[h] = p 

#上記6行に渡って、「入力データ取り出し ⇒ リスト ⇒辞書」としています。
#下記の1行でできると思ったのですが、上手く動かなかったので、やむを得ず上記のコードとしています。
#player_ans = {date:uryo for date,uryo in input().split(" ")} 動かない

print(player_ans) #{1: 0, 2: 20, 3: 10, 4: 80, 5: 10, 6: 0, 7: 10}

#入力データ
7 3 #7は下記入力データの数を表している。 3は連続する回数を表している。 ※詳しくは下記に。
1 0
2 20
3 10
4 80
5 10
6 0
7 10
#希望する出力 5

『やりたいこと』
・入力データの2行目(1,0)からを対象に、右の数字(今回の場合は3個単位 ※最初の入力データの3をみる)を合計。
最も低い合計の行を出力したい。

今回の入力データの場合、まず
1 0
2 20
3 10
これらの右の数を合計(30)

次に
2 20
3 10
4 80
これらの右の数を合計(110)

3 10
4 80
5 10
これらの右の数を合計(100)

と、最後までみていき、
合計が最も低い行を出力したい。
今回の入力データでは、
5 10
6 0
7 10
が、合計20となるため、この合計値の先頭(5)を出力

3個単位で合計を見る必要があるため、例えば先頭の(1,0)が最小(値0)ということで出力するのはNG
最後の(6,0 7,10)が最小(値10)ということで出力するのもNG(2行しかみていないため)

『考えたこと』
・辞書型にして、行をkeyに、値をvalueに、値を3個単位で合計して最小値を求めるのが楽かと思ったんですが、
どのようなコードで計算すればいいかつまづいてしまいました。
※載せているコードは、入力データを辞書化しただけです。

『ご質問』
・辞書型で解く方法、もしくは別なやり方がありましたら、ご教授いただきたいです。
・今回、入力データをリスト化して、辞書型としていますが、
もっと楽に辞書型にできるようでしたら、こちらもご教授いただきたいです。 

ここまで長くなってごめんなさい。
よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+2

個人的には、辞書を使わない方が書きやすい気がします。

解法の方針

  1. 3個ずつ組にしたタプルのリストを作る
  2. 最も合計値が小さいタプルのインデックスを調べる
n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

groups = zip(*[nums[s:] for s in range(span)])
indice = [
    index 
    for index, group in sorted(
        enumerate(groups, start=1),
        key=lambda ig: sum(ig[-1])   # (index, num_group)
    )
]

print(indice[0])

Wandbox


hayataka2049さんのご指摘を受けて修正したバージョン。

n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

groups = zip(*[nums[s:] for s in range(span)])
index, _ = min(
    enumerate(groups, start=1),
    key=lambda ig: sum(ig[-1])   # (index, num_group)
)

print(index)

Wandbox

せっかくなので

辞書を使った方法も書いてみた。

n, span = map(int, input().split())

nums = [
    int(input().split()[-1]) for _ in range(n)
]

sum_dict = {
    i: 0 for i in range(n-span+1)
}
for key in sum_dict:
    for i in range(span):
        sum_dict[key] += nums[key+i]

index = sorted(sum_dict.items(), key=lambda item: item[-1])[0][0]
print(index+1)

Wandbox

コメントを受けて

enumerateなんですが、for文の際に使うもので、リストのインデックスをとるときに使用するものだと認識しておりますが、for文がありません。
ここでのenumerateは何をしているのでしょうか。。?
また、groupsは上記でタプルにされているデータをさしているのはわかるのですが、stard=1は何なのでしょうか?

for文で良く用いられるのは確かですが、その実態はジェネレータを返しているだけなのです。
また、キーワード引数startは、どの数値から順に付与するかを示します。

>>> abc = list('abcdefg')
>>> abc
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>>
>>> enumerate(abc)
<enumerate object at 0x00000270D21ED438>
>>>
>>> list(enumerate(abc))
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'), (5, 'f'), (6, 'g')]
>>>
>>> list(enumerate(abc, start=5))
[(5, 'a'), (6, 'b'), (7, 'c'), (8, 'd'), (9, 'e'), (10, 'f'), (11, 'g')]

key=lambda ig: sum(ig[-1])
lambdaは、引数、:の後に処理を記述すると認識しております。
min(enumerate(groups, start=1)この処理結果がigにはいって、sumして、keyに入って、それをindexと_に戻り値として渡される?という認識でよろしいでしょうか?

enumerate(groups, start=1)が返した各要素がigに入ります。
例えば一回目は(1, (0, 20, 10))が、二回目は(2, (20, 10, 80))がigに与えられるわけです。

keyは関数が『何をもって要素を比べるか』指定するために使います。
今回はsum(ig[-1])、つまり件の三個組の要素の合計を指標にしています。

minした結果をラムダで処理しているのではなく、minを求めるのにラムダを用いています。
minがどんな処理をしているか覗いてみたら、少しイメージが湧くかもしれません。

def my_min(it, key=None):
    print('-' * 42)
    if key is None:
        key = lambda x: x   # 恒等関数

    ret = next(it)
    ret_score = key(ret)

    for e in it:
        e_score = key(e)
        print(f'{ret}[score={ret_score}] vs {e}[score={e_score}]', end='\t')

        if ret_score > e_score:
            print('latter wins')
            ret, ret_score = e, e_score
        else:
            print('former wins')

    print(f'smallest element is {ret}')
    print('-' * 42)
    return ret

実行結果 (minの代わりにmy_minを使用) Wandbox

------------------------------------------
(1, (0, 20, 10))[score=30] vs (2, (20, 10, 80))[score=110]    former wins
(1, (0, 20, 10))[score=30] vs (3, (10, 80, 10))[score=100]    former wins
(1, (0, 20, 10))[score=30] vs (4, (80, 10, 0))[score=90]    former wins
(1, (0, 20, 10))[score=30] vs (5, (10, 0, 10))[score=20]    latter wins
smallest element is (5, (10, 0, 10))
------------------------------------------
5

註: 説明のために書いたコードであり、実際のminの実装を踏襲したものではありません。


前半部分「sorted(sum_dict.items()」は、辞書をソートされている。ここまではわかるのですが、
やはり、lambdaの処理が完璧に理解できません。(ソートした辞書をitemに渡す?)

辞書の各要素をタプルにしたシーケンスを作り、そいつをソートしています。
ソートした結果をラムダで処理しているのではなく、ソートするのにラムダを用いています。

>>> tmp_dict = {i: i**2 for i in range(10)}
>>> tmp_dict
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81}
>>>
>>> tmp_dict.items()
dict_items([(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81)])

回答いただいたのに、それに対しての質問ばかりでごめんなさい。

いえいえ、お気遣いなく。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/29 20:53 編集

    この手のコードを見るたびに思いますが、sortせずに済ませるとO(nlogn)がO(n)になってお得です(どうでも良いけど)

    キャンセル

  • 2018/06/29 20:58

    拡張性をある程度担保しようという考えが根底にはあります。
    が、ただの手癖になってしまっているのが正直なところで、今回も特に意識しないでminを避けsortedを使ってしまいました。
    ご指摘ありがとうございます。

    キャンセル

  • 2018/06/30 03:13

    いつもご教授いただきありがとうございます。
    下記の理解で誤りがありましたらご指摘お願いします。

    ただ、疑問があります。(全部で4個)

    まず、2番目に作成いただいたコードなのですが、

    >>nums = [int(input().split()[-1]) for _ in range(n)]
     ⇒これで入力データの右側をリスト。(1でも右側を取り出せる)
      ※-1を0にすると、左側だけ取り出せる。
      for _ in range
      _(アンダーバー)というのは、変数を使わないということ
      ※for i in rangeとしても同じ動きをする、はず


    >>groups = zip(*[nums[s:] for s in range(span)])
     ⇒リストを3個単位でタプルにしている。
      3個というのは、spanの3である。
    >>index, _ = min(enumerate(groups, start=1),key=lambda ig: sum(ig[-1]) # (index, >>num_group)
    >>)
     index, _は、戻り値がふたつあるから、受け皿を二つ用意。
     必要なのはindexに入る値のみ。_は使用しない?

    『疑問』
    >>index, _ = min(enumerate(groups, start=1),key=lambda ig: sum(ig[-1]) # (index, >>num_group)
    >>)
     minの意味はわかります。※最小値をとる
    ① enumerateなんですが、for文の際に使うもので、リストのインデックスをとるときに使用するものだと認識しておりますが、for文がありません。
    ここでのenumerateは何をしているのでしょうか。。?
    ②また、groupsは上記でタプルにされているデータをさしているのはわかるのですが、stard=1は何なのでしょうか?

    ③key=lambda ig: sum(ig[-1])
    lambdaは、引数、:の後に処理を記述すると認識しております。
    min(enumerate(groups, start=1)この処理結果がigにはいって、sumして、keyに入って、それをindexと_に戻り値として渡される?という認識でよろしいでしょうか?

    ====2番目のコードについてはここまで====


    3番目の辞書でやって頂いたコードなのですが、
    下記のコード以外は、何をやっているのか理解しました。
    >>index = sorted(sum_dict.items(), key=lambda item: item[-1])[0][0]
    ④ 前半部分「sorted(sum_dict.items()」は、辞書をソートされている。ここまではわかるのですが、
    やはり、lambdaの処理が完璧に理解できません。(ソートした辞書をitemに渡す?)


    回答いただいたのに、それに対しての質問ばかりでごめんなさい。

    キャンセル

  • 2018/06/30 13:38

    @zeitaku_fire さん
    ご質問の点について追記しましたので、ご確認ください。

    キャンセル

  • 2018/06/30 14:37

    ありがとうございます。追記頂いた分確認しました。
    ご丁寧にコードも作成頂き、イメージを昨日より持つことができました。

    完全に理解するにはまだ時間がかかりますが、今後ともご教授のほどよろしくお願いします。

    ありがとうございました。

    キャンセル

+2

回答の前にひとつアドバイスしますと、

    player_ans = {}
    for h, p in zip(date, uryo): #取り出した入力データをリストに格納
        player_ans[h] = p 


これをforの中に入れるのはやめましょうか(無駄だから)。


どうせ辞書に入れるなら、もうすこし旨味のある入れ方をした方が良いでしょう。

# めんどいので入力周り省略
num = [7, 3]
date = [1,2,3,4,5,6,7]
uryo = [0,20,10,80,10,0,10]

dn, span = num  # 扱いづらいのでunpack
player_ans = {}
for i in range(dn - span + 1):  # このforループの意味は頭をひねって考えること
    player_ans[date[i]] = uryo[i:i+span]

# 以下3つは確認用のprint
print(player_ans)  # => {1: [0, 20, 10], 2: [20, 10, 80], 3: [10, 80, 10], 4: [80, 10, 0], 5: [10, 0, 10]}
print(player_ans.items())  # => dict_items([(1, [0, 20, 10]), (2, [20, 10, 80]), (3, [10, 80, 10]), (4, [80, 10, 0]), (5, [10, 0, 10])])
print(min(player_ans.items(), key=lambda x:sum(x[1])))  # => (5, [10, 0, 10])

# 最終的にほしいもの
print(min(player_ans.items(), key=lambda x:sum(x[1]))[0])  # => 5

# こっちでもいいかなぁ
print(min(player_ans, key=lambda x:sum(player_ans[x])))  # => 5

あるいは、

for i in range(dn - span + 1):  # このforループの意味は頭をひねって考えること
    player_ans[date[i]] = sum(uryo[i:i+span])


で後ろのminのkeyが単純になります。後からリストを使わないのならこの方が良いかも。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/30 01:12

    いつもありがとうございます。
    下記のように理解しました。誤ってましたらご指摘お願いします。
    ただ、疑問が2点あります。

    >>dn, span = num # 扱いづらいのでunpack
    ⇒numの値をdn=7 span=3へ 解釈。

    >>for i in range(dn - span + 1): # このforループの意味は頭をひねって考えること
    >> player_ans[date[i]] = uryo[i:i+span]
    ⇒まず、繰り返し条件の「dn - span + 1」
     これは、数値にすると5になる
     なぜ5かというと、7個の数値を3個単位で合計する場合、必要なリストの数は合計5となることから、この計算式としている。

    次に「player_ans[date[i]] = uryo[i:i+span]」
    左の部分「player_ans[date[i]]」、date[i]としていることから、keyを指定されていると想定。
    右の部分「uryo[i:i+span]」、uryoはリスト化されていて、[i:i+span]というのは、リストの○番目から○番目を抽出して、keyにリストとして値をもたせている。

    『疑問』
    2点あります。
    ■for i in range(dn - span + 1)
    上記の場合、iは0からはじまります。現に、iをprintしてみたら、0,1,2・・・となっていました。
    しかし、下記コードのdate[i]は1,2,3・・・となっています。
    player_ans[date[i]] = uryo[i:i+span] 
    i+1という表記はどこにもないはずなのに、なぜ、1がはいるのでしょうか?

    ■print(min(player_ans.items(), key=lambda x:sum(x[1]))[0]) # => 5
    前半部分「min(player_ans.items()」ここの意味は、player_ansは辞書化されていて、値には3個ずつにまとめたリストが入っている。minを指定しているから、最小値のkeyとvalueがitemsにより選択されると解釈。
    その先のlambda「key=lambda x:sum(x[1]))[0])」について、
    xに前半部分のminで指定したkeyとvalueが引数と渡されて、:の後の処理を行っているのだと想定したのですが、
    key=とsum(x[1]))[0])これは何をやっているのでしょうか。。?

    キャンセル

  • 2018/06/30 12:10

    疑問1:date = [1,2,3,4,5,6,7]だから。date[0]は1
    疑問2::sum(x[1]))[0])という処理はしていません。3つめの確認用printで出ている結果から、キーだけ取り出してるのが後ろの[0]で、これはminの外にあります
    あとはすべてminの中で完結しています。minのkeyについては理解しづらかったら調べると解説記事があると思います

    キャンセル

  • 2018/06/30 12:18

    maxだけど、こんな記事があった
    http://cointoss.hatenablog.com/entry/2013/10/16/123129

    キャンセル

  • 2018/06/30 12:19

    あとこんなのもわかりやすいかも
    http://doc.code161.com/python/list-key-usage/

    キャンセル

  • 2018/06/30 13:34

    ご教授ありがとうございます。
    keyについて、理解が深まりました。
    記事も目を通しました。
    今後ともよろしくお願いします。

    キャンセル

0

愚直だけど、こんな感じでもできるかもです。
積算値をキュー的に扱い(前の値を引き現在の値を足す)、計算量はO(n)でいけてると思います。

import random
random.seed(110)
cnt = 10
l = [random.randrange(cnt*2) for i in range(cnt)] # rangeも個数に合わせる。(0が連続しないように)
#print(l)
span = 3

# 0番目からspan個を足す。とりあえずこれを最小値とする。
cur_sum = 0
for i in range(span):
    cur_sum += l[i]
#print(cur_sum)
cur_sub = l[0]
min_sum = cur_sum
min_pos = 0

# 1番目から末尾を足すまで
for i in range(1,cnt-span+1):
    # 前の値を引いて、現在の値を足す=現在の積算値
    cur_sum -= cur_sub
    cur_add = l[i+span-1]
    cur_sum += cur_add
    #print('cur pos={} sub={} add={} sum={}'.format(i,cur_sub,cur_add, cur_sum)) #
    cur_sub = l[i]
    if cur_sum <= min_sum:
        min_sum = cur_sum
        min_pos = i
        #print('min pos={} cur_min={}'.format(min_pos,min_sum))

print( 'total_min pos={} sum={}'.format(min_pos, min_sum))


境界値をちゃんと考慮できていないかも。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/06/30 01:31

    ありがとうございます。
    ほかのアプローチを思いつかなかったので、ご教授いただいたコード、参考にさせて頂きます。
    今後ともよろしくお願いします。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.53%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Python 3.x

    6309questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。