だいすけ　＠カレー好き

はじめ、ABCDEからも重複ありで結ぶのかと勘違いして悩んでしまいました。 ABCDEは1個ずつ結ぶのでしたね。 ○○○○○｜｜｜｜の並べ方なので、9C4で126通りですね。

1月6日（木） 0:07:59　　 　　51159

Mr.ダンディ

A,B,C,D,Eの行き先をそれぞれ左からa,b,c,d,e番目の点とするとき 1≦a≦b≦c≦d≦e≦5　であればよい ⇔　1≦a<(b+1)<(c+2)<(d+3)<(e+4)≦9 1〜9から5つの数を選び大きく無い順から順に　a,(b+1),(c+2),(d+3),(e+4) を対応させればよいので ９Ｃ５＝１２６ （通り） としました。

1月6日（木） 0:16:46　　 　　51160

今年から高齢者

5個を5個に重複して配分する9C4

1月6日（木） 0:17:02　　 　　51161

Jママ

今年もどうぞよろしくお願いします。 ABCDEから結ばれる点が 5個とも同じ…5通り 4個同じ…5×4=20通り 3個だけ同じ…5×4C2=30通り 3個+2個…5C2×2=20通り 2個だけ同じ…5×4C3=20通り 2個+2個+1個…5C3×3=30通り 1個ずつバラバラ…1通り 以上を合計して126通りになりました。

1月6日（木） 0:20:41　　 　　51162

ゴンとも

十進Basic で FOR a=1 TO 5 FOR b=a TO 5 FOR c=b TO 5 FOR d=c TO 5 FOR e=d TO 5 LET s=s+1 NEXT e NEXT d NEXT c NEXT b NEXT a PRINT s END f9押して　126・・・・・・(答え)

豊川市　　 1月6日（木） 0:27:27　　 MAIL:fttnm528@ybb.ne.jp 　　51163

紫の薔薇の人

直線アにi点、直線イにj点あるときの場合の数をA(i,j)とすると、 直線イの左端の点を使うか使わないかで場合分けして、 A(i,j)=A(i-1,j)+A(i,j-1)が成り立つ。 A(1,j)＝j、A(j,1)＝1 だから、順に表を埋めていき、A(5,5)＝126を得る。 　　 i/j　１　２　 ３　　４　５ １ 1 2 3 4 5 ２ 1 3 6 　10 15 ３ 1 4 10 20 35 ４ 1 5 15 35 70 ５ 1 6 21 56　126 左マスと上マスの数を足すことを繰り返す。 //

1月6日（木） 0:40:29　　 　　51164

紫の薔薇の人

#51164 ＞直線イの左端の点を使うか使わないかで場合分けして、 直線アの左端の点を、直線イの左端の点と結ぶか結ばないかで場合分けして

1月6日（木） 0:43:49　　 　　51165

ベルク・カッツェ

上下とも任意の点同士を結ぶと勘違いしてなぜ合わないのか悩んでいました。 よく読んだらとても簡単な問題だったという。 下の点1つ、選び方5通り×線の引き方1通り＝5通り 下の点2つ　10×4＝40 下の点3つ　10×6＝60 下の点4つ　5×4＝20 下の点5つ　1×1＝1 合計126通り。

1月6日（木） 0:46:41　　 　　51166

スモークマン

冷静に考えたら気づけましたわ ^^; 5個の数字から、重複許して5個選び、それを小さい順に並べる方法は１通りなので、5H5=9C4=126通り♪

1月6日（木） 0:55:53　　 　　51167

EG

明けましておめでとうございます。 上の点も変動すると思い込んでまったく解けませんでした(；＿；) 諦めて風呂に入っている間にもしやって思ったら暗算問題だったという・・・ こんなオッチョコチョイですが今年もよろしくお願いします。

1月6日（木） 1:24:10　　 　　51168

「数学」小旅行

重複組み合わせでやりました！暗算しました（＾＾）〜 今年もよろしくお願いします。

1月6日（木） 4:56:45　　 　　51169

さいと散

明けましておめでとうございます。

1月6日（木） 6:54:41　　 　　51170

ことりちゅん(・8・)

ＡＢＣＤＥと４つの仕切り棒並び順　　　仕切り棒で左からＰＱＲＳＴに分ける ９Ｃ４＝126

埼玉県さいたま市　　 1月7日（金） 0:26:18　　 　　51171

いちごみるく

上も好き勝手に選べる場合の答えを出した方居たら答え合わせたいので教えてくれると嬉しいです。

1月7日（金） 23:27:33　　 　　51172

いちごみるく

2751ですかね #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) map<pair<int, pair<int, int>>, int>mp; int dp(int zan, int l, int r) { if (mp.count({ zan,{l,r} }))return mp[{ zan, { l,r }}]; if (0 == zan)return 1; int val = 0; rep(i, min(5, l + 1))rep(j, min(5, r + 1)) { if ((l == i)&(r == j))continue; val += dp(zan - 1, i, j); } mp[{ zan, { l,r }}] = val; return val; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << dp(5, 5, 5) << endl; return 0; }

1月7日（金） 23:37:08　　 　　51173

ぼけ老人

ばち丸です。 見て全く気付かず、よく見ると高校でやった５つの丸と仕切り線４本の 並べ方だと気づいた次第。お粗末で「ぼけ老人」としか言いようがない。 先日、年賀状出した相手の弟さんからハガキが来て、去年の春に亡くなりました。だと。がっかりしました。たまらんな。

1月8日（土） 21:26:24　　 　　51174

ばち丸

たびたびすみません。掲示板に答えを送ってみたらあっという間に名前が出てきた。まじめに仕事やってるなって感じ。またよろしくおねがいします

1月8日（土） 22:01:12　　 　　51175

「数学」小旅行

#51173 線分が5本になるというのが条件なので、例えば 上端が[aabbc]で、対応する 下端が[pqqqt]のときなどはだめです。4本になってしまいます。 そこでこのようなもの以外を数えました。 Rubyプログラミングです。 x=['a','b','c','d','e'].repeated_combination(5).to_a y=['p','q','r','s','t'].repeated_combination(5).to_a k=0 for f in x for g in y if f[0]!=f[1]||g[0]!=g[1] then if f[1]!=f[2]||g[1]!=g[2] then if f[2]!=f[3]||g[2]!=g[3] then if f[3]!=f[4]||g[3]!=g[4] then k+=1 end;end;end; end;end;end; p k 答えは同じく、2751となりました。

1月9日（日） 6:15:00　　 　　51176

いちごみるく

#51176 ありがとうございます。カッコつけてメモ化再帰で解きましたが 普通に全ケース回したほうがわかりやすいですね。

1月9日（日） 7:20:41　　 　　51177

「数学」小旅行

#51177 とりあえず思いついたのでこうしましたが、一般に上列にｍ個下列にｎ個となり、 ｋ本の線分を引くとなると、別の判定法かアルゴリズムが必要な気がしています。

1月9日（日） 9:50:21　　 　　51178

「数学」小旅行

とか言っている間にとりあえずできました。 m=5;n=5;k=5 x=(1..m).to_a.repeated_combination(k).to_a y=(1..m).to_a.repeated_combination(k).to_a ans=0 for f in x for g in y d=1 for i in (0..k-2) d=d*((f[i]-f[i+1])**2+(g[i]-g[i+1])**2) end if d!=0 then ans+=1 end end end p ans ｍ，ｎ，ｋにいろんな値をいれてみると？

1月9日（日） 10:13:01　　 　　51179

いちごみるく

同じくm,n,kを入出力で受け取れるように 計算量がO(m^2*n^2*k*O(m^2*n^2*k))なはずなので (n,m,k)=(50,50,50)ですら7秒かかります #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) int n, m, k; map<pair<int, pair<int, int>>, long long>mp; long long dp(int zan, int l, int r) { if (0 == zan)return 1; if (mp.count({ zan,{l,r} }))return mp[{ zan, { l,r }}]; int val = 0; rep(i, min(n, l + 1))rep(j, min(m, r + 1)) { if ((l == i)&(r == j))continue; val += dp(zan - 1, i, j); } mp[{ zan, { l,r }}] = val; return val; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k; cout << dp(k, n, m) << endl; return 0; }

1月9日（日） 22:21:58　　 　　51180

いちごみるく

O(m^2*n^2*k*log(m*n*k)) と書きたかったらしい。

1月9日（日） 23:10:21　　 　　51181

いちごみるく

意味もなく再起させなければ(n,m,k)=(50,50,50)でも200msとかで終わるのか

1月10日（月） 9:17:54　　 　　51182

いちごみるく

そもそも2D累積和使えばO(n*m*k)に落ちる

1月10日（月） 9:20:25　　 　　51183

ベルク・カッツェ

#51172 あまり自信はありませんが、 上下のいずれかを5個使う場合　126×2-1＝251 4個と4個の場合、4個と3個の場合・・・と場合分けして数えたら2751通りになりました。

1月11日（火） 1:08:52　　 　　51184

吉川　マサル

非常に悲しいお知らせです。 　算チャレで初期のころから解説ページをお作りになられ、しかし17年前に大きな交通事故に遭い、意識がもどらぬままご自宅での介護生活を続けていた栗原英治さんが昨日、お亡くなりになりました。 　1999年に高知オフミでお会いし、その後に2004年に突然の更新停止、意を決してご自宅にお電話をし、奥様から事情を伺ったのはもう17年も前のことです。その後、年に１回のお見舞いは続けていましたが、コロナの影響で２年ほど伺えていなかったところでした。 　ご冥福をお祈りしたく思います。

Tokyo　　 1月11日（火） 8:53:21　　 HomePage:算チャレ　　51185

「数学」小旅行

#51185　ご冥福を心からお祈り申し上げます。

1月11日（火） 13:12:49　　 　　51186

「数学」小旅行

#51179　自己レスです。 重複組み合わせにとらわれてつまらないことをしていました。 上列と下列を順に増加させてとれば良いだけでした。 $m=5;$n=5;$k=5;$ans=0 def seg(a,b,c) if c>=$k then $ans+=1 else for i in a..$m-1 for j in b..$n-1 if i!=a||j!=b then seg(i,j,c+1) end end end end end p Time.now for i in 0..$m-1 for j in 0..$n-1 seg(i,j,1) end end p Time.now p $ans これを実行すると、 2022-01-11 04:09:19.703474163 +0000 2022-01-11 04:09:19.708215219 +0000 2751 ですが、50,50,50となると、私の環境でＲＵＢＹでは 先ほどからやってますが、30分経過でまだできていません。 遅いですね（＾＾；）

1月11日（火） 13:32:06　　 　　51187

いちごみるく

というかそもそも包除原理でO(k)ですね 9C5*9C5*4C4-8C4*8C4*4C3+7C3*7C3*4C2-6C2*6C2*4C1+5C1*5C1*4C0=1751 ΣBinomial(n+i-1,i)*Binomial(m+i-1,i)*Binomial(k-i,i-1)*-1^((k-i)%2)

1月12日（水） 9:51:44　　 　　51188

kasama

#51185 栗原さんのことは、時折気にしていましたが、お亡くなりなったのですね。 とても悲しいです。ご冥福をお祈り申し上げます。

和歌山　　 1月12日（水） 20:28:19　　 　　51189

量子論

#51185 私は新参者ですので、栗原さんと算チャレで同じ時を 共有したことはありませんでしたが、 掲示板のマサルさんの話からご事情を知りました。 リンク先にある栗原さんのホームページにも何度も訪れました。 算数愛、家族愛、自然愛にあふれ、生前のお人柄が偲ばれます。 可能なら「数学の小部屋」ずっと残していただきたいです。 栗原さんのご冥福を心よりお祈り申し上げます。

1月13日（木） 1:57:54　　 　　51190

June

今週もありがとうございます

1月13日（木） 21:21:22　　 　　51191

「数学」小旅行

#51188 すばらしい！！ やってみました。 m=5;n=5;k=5 def fac(t) f=1 for i in 1..t f=f*i end f end s=0 for i in 1..k s=s+(-1)**((k-i)%2)*(fac(m+i-1)*fac(n+i-1)*fac(k-1)/(fac(m-1)*fac(n-1)*fac(k-i)*fac(i-1)*fac(i)*fac(i))) end p s 総当たりのような気の遠くなるような作業をさせるより、 こんな計算式をあたえてやることの大切さを痛感できます。 m=5,n=5,k=5 で、0.11秒 m=50,n=50,k=50で、0.15秒　でした！！　ありがとうございました。

1月14日（金） 15:40:02　　 　　51192

みかん

今年も共通テストの問題を見てみました。とはいえ、解けそうな場合の数・確率の 部分のみですが。 １Ａの大問３、プレゼント交換という設定にしてあるが、問うていること自体は 見たことのあるようなもの。よくある問題に書き直すとこんな感じか。 ＜問題＞ 「５つの箱にそれぞれ、Ａ・Ｂ・Ｃ・Ｄ・Ｅと記号を付ける。また、５つの玉にも それぞれ、Ａ・Ｂ・Ｃ・Ｄ・Ｅと記号を付ける。５つの箱に玉を１個ずつ入れるとき、 箱と玉の記号が一致するものが１組もない確率を求めよ」 …なんか面白味がないですね。別の場面を考えてみましょう。 ＜問題＞ 「空欄Ａ・Ｂ・Ｃ・Ｄ・Ｅに入る最も適切な語を、選択肢あ・い・う・え・お　 から選べ。ただし、同じ記号を２度以上用いてはならない。 上記の設問でまったく考えずに無作為に記号を解答した時、５つとも不正解に なる確率を求めよ。解答は　あ・い・う・え・お　を１度ずつ記入し、同じ記号を ２回以上書いたり、無解答としたりすることは考えないものとする。」 …試験では考えたあげく１つも当たらない、ということも時々ある話。だけどそれを 試験問題のネタにされると腹が立つだろうなぁ・・・。 ちなみに、「無作為に５つの記号を１度ずつ書く」も「５つとも同じ記号を書く」も 得点の期待値としては同じだったような気がします。

1月17日（月） 0:29:18　　 　　51193