さっきのアルゴリズムの問題の答え載せるで～

1 : 2022/09/03(土) 18:37:44.14 ID:4Diq+sOs0: Nを自然数として、
Nの正の倍数における各桁の和の最小値を求めるアルゴリズムで一番効率いいものはなんだ？

この問題や
まだ自分で解きたいやつはそっ閉じしてや
2 : 2022/09/03(土) 18:38:13.27 ID:FsQbcQ8Ra: 立ててくれて良かったわ
3 : 2022/09/03(土) 18:39:25.05 ID:4Diq+sOs0: まずはNで割った余りの世界を考えるんや

掛け算も足し算も全部Nで割った余りに換算される世界を想定してや

例えばN=7なら

6+5=4やし、
2×6=5
や
4 : 2022/09/03(土) 18:40:22.28 ID:4Diq+sOs0: ここで、0～N-1という番号のついた頂点を平面上に配置するんや
7 : 2022/09/03(土) 18:41:10.64 ID:4Diq+sOs0: >>4
ほんでこれらの頂点に辺を加えてくんやけど
5 : 2022/09/03(土) 18:40:26.06 ID:4YNDGMUz0: 合同式ってことね
6 : 2022/09/03(土) 18:40:48.16 ID:4Diq+sOs0: >>5
その通りやで～
数学分かるやつならZ/NZのことやな
8 : 2022/09/03(土) 18:43:03.87 ID:4Diq+sOs0: 任意の頂点pに対して、
頂点10×pに「コスト(辺を渡る値段と思えばええで)0」の有向辺をくっ付ける

さらに頂点pから頂点p+1に「コスト1」の有向辺をくっ付けるんや
9 : 2022/09/03(土) 18:43:08.69 ID:TcrNK1PR0: 一番効率いいかどうかはわからんくね
10 : 2022/09/03(土) 18:44:05.37 ID:4Diq+sOs0: そうすると>>1の問題は
頂点1から頂点0に渡る経路で最もコストが安いもの
って問題に変化するんや
11 : 2022/09/03(土) 18:44:40.02 ID:4Diq+sOs0: あとはそこから有向グラフの最短経路問題を解けばええから
深さ優先探索とかをすればおしまいや
12 : 2022/09/03(土) 18:45:23.20 ID:zqJcmv24a: 助かるわ
まだ理解できてないけど読み解いていくで
13 : 2022/09/03(土) 18:45:32.60 ID:kqZ5qg8u0: 全探索に対してオーダはいくらになるんや？
14 : 2022/09/03(土) 18:45:48.37 ID:4Diq+sOs0: 1という数から(1を足す or 10倍する)という操作を繰り返してNの倍数を作る

ってのが頂点1から頂点0に渡るって行為になるわけやけど
15 : 2022/09/03(土) 18:47:01.32 ID:7dFouo3Xa: はぇ～
数式から経路探索問題に置き換えて解くんか
競プロ民って凄いな
16 : 2022/09/03(土) 18:48:26.48 ID:4Diq+sOs0: 「各桁の和」という意味では

pを10×pにしても変化しないからコストは0

pをp+1にしたら1だけ増えるからコストは1

ってことなんや
17 : 2022/09/03(土) 18:50:48.81 ID:zqJcmv24a: 9→10に行くのがコスト1ってのが分からんで
高校数学で止まってるから群？とか環？とか慣れてないんだわ
21 : 2022/09/03(土) 18:58:09.59 ID:4Diq+sOs0: >>17
たしかにそれがコスト1ってのはおかしいんやけど、
最短経路を見る上では関係ないんやで
コストの安さで考えれば1を足し続けて桁上げするより10倍した方が効率ええからね
18 : 2022/09/03(土) 18:52:09.11 ID:TcrNK1PR0: いきなり答えにたどり着くならそれが早そうやけど
ヒューリスティックな絞り込みとか出来んのかな確率的に
19 : 2022/09/03(土) 18:54:10.57 ID:AJ4xe/Me0: 7の場合で具体的に説明してくれ
22 : 2022/09/03(土) 18:58:51.50 ID:4Diq+sOs0: >>19
ちょっとまってね
グラフを描くで
20 : 2022/09/03(土) 18:57:31.71 ID:zqJcmv24a: 1から1001を作るには
x10を3回、+1を1回の操作が必要で
ゴールが7の倍数だから7つの頂点で0を目指す感じやな
分かってきたで！！！！
23 : 2022/09/03(土) 18:59:30.28 ID:4Diq+sOs0: >>20
天才やな
このテキトー解説で分かるのは相当頭ええで
25 : 2022/09/03(土) 19:04:09.76 ID:zqJcmv24a: >>23
残念ながら元スレ1じゃなくて外野なんやけどな
勉強になったわさんきゅーやで！
24 : 2022/09/03(土) 19:02:26.67 ID:6wq1G1wbM: 円筒形の模型作って探索するのか
よくこんなん思いつくなぁ
26 : 2022/09/03(土) 19:05:41.20 ID:1DKQklJZa: はえーこれで答え出るんや
27 : 2022/09/03(土) 19:11:19.24 ID:1DKQklJZa: 落ちるで
28 : 2022/09/03(土) 19:13:48.02 ID:6wq1G1wbM: 通る頂点の数関係あるんか？
深度で分けてひたすら7で割るわけじゃないのか

引用元：https://eagle.5ch.net/test/read.cgi/livejupiter/1662197864