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

**風吹けば名無し** · 2022/09/03(土) 18:37:44.14

Nを自然数として、
Nの正の倍数における各桁の和の最小値を求めるアルゴリズムで一番効率いいものはなんだ？

この問題や
まだ自分で解きたいやつはそっ閉じしてや

**風吹けば名無し** · 2022/09/03(土) 18:38:13.27

立ててくれて良かったわ

**風吹けば名無し** · 2022/09/03(土) 18:39:25.05

まずはNで割った余りの世界を考えるんや

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

例えばN=7なら

6+5=4やし、
2×6=5
や

**風吹けば名無し** · 2022/09/03(土) 18:40:22.28

ここで、0～N-1という番号のついた頂点を平面上に配置するんや

**風吹けば名無し** · 2022/09/03(土) 18:40:26.06

合同式ってことね

**風吹けば名無し** · 2022/09/03(土) 18:40:48.16

>>5
その通りやで～
数学分かるやつならZ/NZのことやな

**風吹けば名無し** · 2022/09/03(土) 18:41:10.64

>>4
ほんでこれらの頂点に辺を加えてくんやけど

**風吹けば名無し** · 2022/09/03(土) 18:43:03.87

任意の頂点pに対して、
頂点10×pに「コスト(辺を渡る値段と思えばええで)0」の有向辺をくっ付ける

さらに頂点pから頂点p+1に「コスト1」の有向辺をくっ付けるんや

**風吹けば名無し** · 2022/09/03(土) 18:43:08.69

一番効率いいかどうかはわからんくね

**風吹けば名無し** · 2022/09/03(土) 18:44:05.37

そうすると>>1の問題は
頂点1から頂点0に渡る経路で最もコストが安いもの
って問題に変化するんや

**風吹けば名無し** · 2022/09/03(土) 18:44:40.02

あとはそこから有向グラフの最短経路問題を解けばええから
深さ優先探索とかをすればおしまいや

**風吹けば名無し** · 2022/09/03(土) 18:45:23.20

助かるわ
まだ理解できてないけど読み解いていくで

**風吹けば名無し** · 2022/09/03(土) 18:45:32.60

全探索に対してオーダはいくらになるんや？

**風吹けば名無し** · 2022/09/03(土) 18:45:48.37

1という数から(1を足す or 10倍する)という操作を繰り返してNの倍数を作る

ってのが頂点1から頂点0に渡るって行為になるわけやけど

**風吹けば名無し** · 2022/09/03(土) 18:47:01.32

はぇ～
数式から経路探索問題に置き換えて解くんか
競プロ民って凄いな

**風吹けば名無し** · 2022/09/03(土) 18:48:26.48

「各桁の和」という意味では

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

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

ってことなんや

**風吹けば名無し** · 2022/09/03(土) 18:50:48.81

9→10に行くのがコスト1ってのが分からんで
高校数学で止まってるから群？とか環？とか慣れてないんだわ

**風吹けば名無し** · 2022/09/03(土) 18:52:09.11

いきなり答えにたどり着くならそれが早そうやけど
ヒューリスティックな絞り込みとか出来んのかな確率的に

**風吹けば名無し** · 2022/09/03(土) 18:54:10.57

7の場合で具体的に説明してくれ

**風吹けば名無し** · 2022/09/03(土) 18:57:31.71

1から1001を作るには
x10を3回、+1を1回の操作が必要で
ゴールが7の倍数だから7つの頂点で0を目指す感じやな
分かってきたで！！！！

**風吹けば名無し** · 2022/09/03(土) 18:58:09.59

>>17
たしかにそれがコスト1ってのはおかしいんやけど、
最短経路を見る上では関係ないんやで
コストの安さで考えれば1を足し続けて桁上げするより10倍した方が効率ええからね

**風吹けば名無し** · 2022/09/03(土) 18:58:51.50

>>19
ちょっとまってね
グラフを描くで

**風吹けば名無し** · 2022/09/03(土) 18:59:30.28

>>20
天才やな
このテキトー解説で分かるのは相当頭ええで

**風吹けば名無し** · 2022/09/03(土) 19:02:26.67

円筒形の模型作って探索するのか
よくこんなん思いつくなぁ

**風吹けば名無し** · 2022/09/03(土) 19:04:09.76

>>23
残念ながら元スレ1じゃなくて外野なんやけどな
勉強になったわさんきゅーやで！

**風吹けば名無し** · 2022/09/03(土) 19:05:41.20

はえーこれで答え出るんや

**風吹けば名無し** · 2022/09/03(土) 19:11:19.24

落ちるで

**風吹けば名無し** · 2022/09/03(土) 19:13:48.02

通る頂点の数関係あるんか？
深度で分けてひたすら7で割るわけじゃないのか

**風吹けば名無し** · 2022/09/03(土) 19:16:10.52

ワイ程度の理解で伝わるか分からんが

例えばN=7なら
コスト2の数つまり11、101、110、1001、…から7の倍数を探して見つかれば答えは2や
無かったらコスト3の数つまり111、1110、1101、…から探して見つかれば答えは3や
って感じに探していくんやけどこれだけなら無限回の試行が必要やから
7で割った余りに注目して有限回の試行で済ませば終わりやって感じで
それをグラフに落とし込んだのが1の答えやって感じで理解したわ
間違っとったらすまんな

**風吹けば名無し** · 2022/09/03(土) 19:19:57.20

>>29
考えてみるありがとう

**風吹けば名無し** · 2022/09/03(土) 19:23:51.35

頂点の数の上限ってことかありがとう
>>1と>>29

**風吹けば名無し** · 2022/09/03(土) 19:25:25.55

すまん性の倍数におけるってどういうこと

**風吹けば名無し** · 2022/09/03(土) 19:30:53.13

>>29
7でなにをわるん