プログラミングのお題スレ Part18

[過去ﾛｸﾞ] プログラミングのお題スレ Part18 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

503(1): 253 2020/09/08(火)23:16 ID:TMzoRSJV(2/2) AAS
>>502 の実行結果

~ $ cat 18_454_ex1.txt
5
5 4
2 3
3 2
3 4
4 4
~ $ cat 18_454_ex1.txt | go run 18_454_N_vztr_DP.go
4
省15

504(1): 253 2020/09/09(水)09:03 ID:GqQ7+Mc6(1/2) AAS
>>454 Python3

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
T = max([a[i][0] for i in range(n)])
m = [[0] * 11 for t in range(T+1)]
for i in range(n):
　　 m[a[i][0]][a[i][1]] = 1
def v(t, p):
　　return m[t][p] if 0 < p and p < 11 else 0
for t in reversed(range(T)):
省8

505: 253 2020/09/09(水)09:34 ID:GqQ7+Mc6(2/2) AAS
AA省

506: 2020/09/10(木)01:27 ID:8z9ZctT6(1/2) AAS
>>350
Java
外部ﾘﾝｸ:paiza.io

507(1): 453 2020/09/10(木)16:14 ID:ypm5ktrY(1) AAS
お題

>>453
のルールに基いて、以下の3つの10進数のバイト列を、先頭(1バイト目)からチェックしていく時、
最初にルール違反となるのは、何バイト目か

129 130
120 169
240 159 146 206 184

508: 2020/09/10(木)22:23 ID:8z9ZctT6(2/2) AAS
>>507
Java
外部ﾘﾝｸ:paiza.io

509(5): 2020/09/12(土)21:24 ID:2KEhs3KT(1) AAS
お題：自然数nが現れる九九の表の最小サイズを求めよ

octave
外部ﾘﾝｸ:ideone.com

510: 2020/09/13(日)00:20 ID:OR+CcCGz(1) AAS
>>509
Java
外部ﾘﾝｸ:paiza.io

511(1): 2020/09/13(日)00:35 ID:42xWDo9L(1) AAS
>>509
Kotlin
外部ﾘﾝｸ:paiza.io

良いアルゴリズムが思いつかなかったのでほとんど力技。

512(1): 蟻人間 ◆T6xkBnTXz7B0 2020/09/13(日)22:12 ID:p9JSm0uj(1) AAS
お題: 「ジャンケンすたじあむオンライン」というソーシャルゲームのウェブサイト、もしくはソフトウェアパッケージを制作・運営せよ。

ジャンケンをしたい人が集まって、ひたすらジャンケンをして、勝ち数を競うというソーシャルゲーム。

ジャンケン試合は2人組になり、お互いに出す手を事前に申告し、両者が申告したところでシステムが自動で勝敗を判定する。

513: 2020/09/13(日)22:17 ID:phcl8RYj(1) AAS
>>512
消えろ

514: 2020/09/13(日)22:22 ID:lu6eiMc4(1) AAS
動的計画法ってちゃんと勉強しないとなかなか思いつかないよな

515: 2020/09/14(月)12:06 ID:u8/qg5cq(1) AAS
>>509
Haskell

f x = head [ d | d <- [(ceiling $ sqrt $ fromInteger x)..], mod x d == 0]
main = mapM_ print [(x,f x) | x<-[100..130]]

516(2): 蟻人間 ◆T6xkBnTXz7B0 2020/09/14(月)14:12 ID:/Fwk/gkb(1/3) AAS
お題: 沖縄の名物「シークワーサー」のことが書かれた記事のUTF-8日本語テキストファイル「input.txt」がある。
しかし、記事の執筆に多数の編集者が関わったため、シークワーサーの表記がぶれていることが分かった(次のリンクを参照)。

外部ﾘﾝｸ:ja.m.wikipedia.org

表記のぶれを「シークワーサー」に表記を統一したテキストファイル「output.txt」を出力せよ。

517(1): 2020/09/14(月)17:05 ID:xV8mpaUY(1) AAS
エンジニアが書いてるならシークワーサだな
間違いない

518(1): 蟻人間 ◆T6xkBnTXz7B0 2020/09/14(月)17:29 ID:yesAwSRz(1/2) AAS
>>516 input.txtの中身:

「シークヮーサーは、別名シイークワシャーと呼ばれ、シークヮーサーの香りがするシークヮーシャーのような柑橘系の果物である。シィークアーサーはアーサー王とは関係がないと思われる。」

519: 2020/09/14(月)18:00 ID:wBiJ2Dx0(1) AAS
"/シ(?:イ?ー|ィー?)ク[アワァヮ]ー?(?:サ|シャ)ー?/シークヮーサー/g"

520(1): 蟻人間 ◆T6xkBnTXz7B0 2020/09/14(月)20:32 ID:/Fwk/gkb(2/3) AAS
お題: お使いのプログラム言語で、COBOLに負けない最強の通貨型を設計せよ。

任意の桁数の10進整数を扱えること。
任意の有効桁数の10進小数を扱えること(10進浮動小数点数)。
加減乗除、剰余、任意桁での切り捨て・切り上げ・四捨五入が可能。
10進数表記で入出力できること。
比較的高速に演算できること。

521: 蟻人間 ◆T6xkBnTXz7B0 2020/09/14(月)20:55 ID:/Fwk/gkb(3/3) AAS
1÷3をどう扱うかという問題があるようだ。

522: 2020/09/14(月)21:04 ID:I0h6BMX6(1/2) AAS
割り算するときに桁数していするだけっしょ

523(1): 2020/09/14(月)21:07 ID:I0h6BMX6(2/2) AAS
蟻人間さんにお題：銀行丸めを整数型のみを使用して実装してください

524: 2020/09/14(月)21:08 ID:SHGAz9ig(1/2) AAS
>>517
草

525: 2020/09/14(月)21:24 ID:6FD493+N(1/2) AAS
昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな?

526: 2020/09/14(月)21:26 ID:6FD493+N(2/2) AAS
昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな?

527: 2020/09/14(月)21:49 ID:SHGAz9ig(2/2) AAS
分子や分母に分数が入ってきた場合
精度の面で面倒なことになるぞ

528(2): 蟻人間 ◆T6xkBnTXz7B0 2020/09/14(月)23:12 ID:yesAwSRz(2/2) AAS
>>523

外部ﾘﾝｸ:ideone.com
今日はここまで。

529: 2020/09/14(月)23:41 ID:5nyvo7WN(1) AAS
>>528
一生ここまでにしろ

530: 2020/09/15(火)00:21 ID:2J2Mo0F/(1/2) AAS
>>516

sed -r 's/シ([イィ]ー?|ー)ク[アァワヮ]ー?(サ|シャ)ー/シークワーサー/g'

-r は拡張正規表現を使うオプション。
これで >>518 の文を変換するとこうなる。

「シークワーサーは、別名シークワーサーと呼ばれ、シークワーサーの香りがするシークワーサーのような柑橘系の果物である。シークワーサーはアーサー王とは関係がないと思われる。」

531: 蟻人間 ◆T6xkBnTXz7B0 2020/09/15(火)02:31 ID:39uvi0pE(1) AAS
現実問題では、long double型で十分な精度が出るから、独自の浮動小数点数は必要なさそう。

残りは四捨五入とか銀行丸めなどの端数処理。

532: [age] 2020/09/15(火)09:10 ID:gc4PCUOV(1) AAS
工ｴｴｪｪ(´д｀)ｪｪｴｴ工

533: 2020/09/15(火)14:07 ID:2J2Mo0F/(2/2) AAS
bc コマンド使えば良い。
他の言語から使いたい場合はライブラリをリンクするか、またはこっそり裏で fork(), exec() してパイプで繋いで計算させるw

534(1): 蟻人間 ◆T6xkBnTXz7B0 2020/09/15(火)21:40 ID:9dtbuAF3(1) AAS
>>528
外部ﾘﾝｸ:github.com
今日はここまで。足し算、引き算、掛け算を実装。
銀行丸めはもうちょっと待ってね。

535(2): 2020/09/15(火)21:59 ID:ky+PawN1(1/2) AAS
>>534
誰も待ってないから一生滞ってろ

536: 蟻人間 ◆T6xkBnTXz7B0 2020/09/15(火)22:50 ID:i370J0Ri(1/2) AAS
>>535
スレチ

537: 蟻人間 ◆T6xkBnTXz7B0 2020/09/15(火)22:54 ID:i370J0Ri(2/2) AAS
>>535
とりあえずまあソースコードを読んで頂いてクレヨン。

538: 2020/09/15(火)22:56 ID:ky+PawN1(2/2) AAS
ここはお前の日記帳じゃねぇっての
スレチはお前

539: 2020/09/16(水)10:06 ID:eJDvfDFO(1) AAS
ぶぶ漬けどうぞと言われて、美味しくいただいてさらに食レポまで始めてるような状態かな

540: [age] 2020/09/16(水)21:28 ID:XXyygoNj(1) AAS
嫌味なことするなよ

541: 2020/09/17(木)00:07 ID:jOQPl4C7(1) AAS
京都のおっかさんも口あんぐりやで

542: 2020/09/17(木)01:09 ID:FJaokp+J(1) AAS
>>520 Python decimal でできるだろ。

外部ﾘﾝｸ[html]:docs.python.org

543(3): 2020/09/17(木)07:37 ID:Lu9ZyyRf(1/6) AAS
AA省

544(1): 2020/09/17(木)08:03 ID:dVFtUKnH(1) AAS
AA省

545: 2020/09/17(木)08:08 ID:Lu9ZyyRf(2/6) AAS
げっ確かに行ごとにreplace必要ないじゃん
何やってんだ俺
ありがとう

546: 2020/09/17(木)13:17 ID:GTUBgTcD(1) AAS
>>543
問題の意味がわからない。

547: 2020/09/17(木)13:30 ID:/h1W7gqa(1) AAS
>>543
くだらない質問スレか初心者質問スレ行け

548: 2020/09/17(木)13:34 ID:Lu9ZyyRf(3/6) AAS
ほんとにどの問題よりもクソみたいな問題だと思っています
本当にすいませんでした

549: 2020/09/17(木)13:42 ID:Lu9ZyyRf(4/6) AAS
ただ私は純粋にプログラミングが好きで
全く質問したかったわけじゃないのはわかってほしい
二次配列じゃないと処理できないものだと勘違いしていたのが甘いしシンプルにしすぎて問題が破綻してしまった

550(1): 2020/09/17(木)13:48 ID:Lu9ZyyRf(5/6) AAS
純粋にここにいる人たちが解法として書くコードは好きだし
たまに驚くべき角度から解を出す人もいるしマイナーなアルゴリズムも知れて尊敬してる
今回もスマートなコードが見れるんじゃないかと純粋に期待して問題にしてみたんだ
スレも今流れ遅かったし

551(2): 2020/09/17(木)13:50 ID:Lu9ZyyRf(6/6) AAS
しかしお前らは牙を向いた
純粋に問題作成初心者の心を無碍にして
鋭い刃のような言葉を投げつけてきた
お前らは今日から敵とみなす

あばよ😎✋絶望しな

552: ◆QZaw55cn4c 2020/09/17(木)19:40 ID:+AujTTfU(1) AAS
>>551
奏ちゃん「自意識過剰なんじゃないですか？」

553(6): 2020/09/17(木)22:33 ID:H8Ldt8Jg(1) AAS
お題:文字列の末尾の数字をインクリメントしてください

入力
IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS
出力
IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS

554: 2020/09/17(木)22:56 ID:ockp6LF+(1/2) AAS
>>553 vim

?\d<CR><C-a>

555: 2020/09/17(木)23:01 ID:ockp6LF+(2/2) AAS
>>553 Ruby

$><<gets.sub(/\d+(?=\D+$)/, &:succ)

# => IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoim
M3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOn
xhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfP
sQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuu
UBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS

556(1): 2020/09/18(金)01:44 ID:hhldwLbP(1/2) AAS
>>553
Perl

コマンドラインで以下のように入力後に標準入力から文字列を読ませると標準出力に出力される。

perl -pe 's/(\d+)(\D+)$/($1+1).$2/ge'

あるいはファイルに内容を入れておいてそのファイルを指定する。

557: 2020/09/18(金)03:22 ID:Pz26zoiQ(1) AAS
js
window.prompt().replace(/\d(?=\D+$)/,i=>i*1+1)

558(1): 2020/09/18(金)06:23 ID:QICqPxzN(1) AAS
>>556
行末が数字のときに対応できない
perl -pe 's/(\d+)(\D*)$/($1+1).$2/e'
のほうがよくないかな

559(1): 2020/09/18(金)06:53 ID:5l49iFOd(1) AAS
>>511
その場合の良いアルゴリズムって
「素因数分解を早く解くアルゴリズム」
よね。
それがもし思いついたらフィールズ賞ものではw

560: 2020/09/18(金)21:10 ID:JxxZTRpA(1/2) AAS
>>553
Java
外部ﾘﾝｸ:paiza.io

561: 2020/09/18(金)21:36 ID:JxxZTRpA(2/2) AAS
>>544
Java
外部ﾘﾝｸ:paiza.io

562: 2020/09/18(金)21:54 ID:WsEcPr9A(1) AAS
>>553
haskell

theStr = "B0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS"

f x = let
(a,b) = span (\x-> (x<'0') || (x>'9')) $ reverse x
c = show $ (+1) $ read $ return $ head b
in reverse $ a++c++(tail b)

main = do
print $ f theStr

563: 2020/09/18(金)23:21 ID:hhldwLbP(2/2) AAS
>>558
そうだった。 + じゃなくて * だったな。

564: 253 2020/09/18(金)23:34 ID:/yEGF/vF(1/2) AAS
>>559
素因数分解まで行かない。
素でなくてもいいので因数のうちイチバン大きいもの。
なんかいい解法見つけられないか、考えているけどいまのところ見出せていない

565: 253 2020/09/18(金)23:36 ID:/yEGF/vF(2/2) AAS
いや、違うな…
因数のうちイチバン大きいものでは、ﾀﾞﾒだわ

566: 2020/09/19(土)00:05 ID:HLFklpM8(1/2) AAS
>>553
C

外部ﾘﾝｸ:paiza.io

正規表現を使わずに行末から一文字づつ行頭に向かって検索してやっている。

567(1): 2020/09/19(土)00:59 ID:HX0Lirqs(1/4) AAS
√n以上の最小の約数

568(2): 2020/09/19(土)12:14 ID:iLwsU5Ay(1) AAS
初出題
数学板の問題より

５つのサイコロの1〜6の面がそれぞれ赤白黄青緑にそれぞれ

["byrbwg", "yrgwbb", "gbrwwy", "gyrbww", "gbrybw"]

と塗り分けられている
この状態では1-6を天地の軸として2〜5の側面にはそれぞれ

["yrbyb","rgrrr","bwwby","wbwwb"]
省13

569: 2020/09/19(土)15:12 ID:BWMKzapi(1) AAS
2chｽﾚ:math
わけわからん問題文にするなよ・・・

570: 2020/09/19(土)16:07 ID:wSOXcncc(1/2) AAS
全然違って草

571: 2020/09/19(土)16:29 ID:HLFklpM8(2/2) AAS
>>568
君が何を言わんとしているのかが全くわからない。

572(1): 253 2020/09/19(土)17:15 ID:6KnxgpBj(1) AAS
>>509 Perl5、>>567にﾋﾝﾄを貰った通り√を使ってnaiveに書くと…

use POSIX 'ceil';
for $n (81, 87, 91) {
　$r = ceil sqrt $n;
　for ($r..$n) {
　　$i = $_;
　　last until $n % $_;
　}
　print "$n => $i\n"
}
省6

573: 2020/09/19(土)21:37 ID:HX0Lirqs(2/4) AAS
>>568です
やはりちょっと伝わらないですね
>>568
は取り下げます

574: 2020/09/19(土)21:39 ID:HX0Lirqs(3/4) AAS
>>572
計算量減らすなら√n以下の最大の約数d求めてn/dを出力すれば計算量は減るな

575: 2020/09/19(土)21:40 ID:wSOXcncc(2/2) AAS
減るというかそもそも計算量が同じというか

576(2): 2020/09/19(土)21:46 ID:HX0Lirqs(4/4) AAS
イヤnが素数の場合に√nから上むきに探索すると計算量はnになるけど下向きなら√nになる
√n以上の約数と√n以下の約数は同数だけど整数そのものは下側には√nしかなく、上にはn-√nあるので下向きに探していった方が速い

577: 2020/09/20(日)00:25 ID:ZGoKBb8Y(1) AAS
ポラード・ロー法使えばもっと計算量は減る
素数判定と組み合わせればモンテカルロ法ではなくラスベガス法になるから、正当性も担保される

578(1): 2020/09/20(日)01:39 ID:wHMtOvf4(1/5) AAS
素因数分解利用するなら素因数分解そのものが手早くできてもダメでしょ？
それを何個か使って最も√nに近いもの探すのはかなり難しいんじゃなかったっけ？
つまり素因数分解n=Πpi^eiが与えられたとして、つぎは
0≦xi≦eiを動かすときΣxi log(pi) が1/2 log(n)に最も近くなるものを決定しなければならない
コレなんか名前ついてる問題で指数オーダーのアルゴリズムしか見つかってないんじゃなかったっけ？
素因子の数はlog(n)のオーダーで増えていくから、結局exp(c log(n)) のオーダーになって、cがどれくらいに収められるか、そもそも指数オーダー必要なのかも未解決なんじゃなかったっけ？

579(1): 2020/09/20(日)06:22 ID:OZ4qNDWZ(1) AAS
>>576
素数判定はそもそも計算量少ない

580: 2020/09/20(日)10:19 ID:mk/D54YH(1) AAS
>>579
√n以上の最小の約数をdとして上むき探索に必要な時間はすうがく/d-√n\、下向き探索のそれは\√n-n/d/ (/〜\と\〜/はfloorとceiling)
差は/d-√n\-\√n-n/d/ =\d+n/d-2√n/はam≧gmと\〜/の広義単調性から0以上で上むき探索は素数であるか否かに限らず常に計算量は同じかそれ以上
素数であるか予備検査しても結局上向きに探索したら計算量は同じ以上かかる

581: 2020/09/20(日)10:50 ID:g28HruB5(1) AAS
あ、間違えた
上向き探索の探索量はd-/√n\+1=/d-√n+1\で/~\はceiling
下向き探索の探索量は\√n/-n/d+1=\√n-n/d+1/で\~/はfloor
まぁ常に上向きの方が計算量は増える
まぁもちろんnをまともに素因数分解して>>578みたいな方法で√nオーダーより真に早いのがあるなら上向きも下向きもないけど、もうそこまで行ったら研究者レベルの話でしかない気がする

582(1): 2020/09/20(日)11:23 ID:MLu0Cj9r(1/2) AAS
>>550-551
短いこの間でダークサイドに堕ちてて草

583: 2020/09/20(日)11:58 ID:FaUtZa6z(1) AAS
>>582
お詫び→弁解→言い訳→逆ギレ
冷静に書いてたつもりが書いてくうちに興奮して見事なコンボを決めたようだ

584: 2020/09/20(日)12:47 ID:MLu0Cj9r(2/2) AAS
感情豊かでかわいいｗ

585(5): 2020/09/20(日)12:59 ID:wHMtOvf4(2/5) AAS
気分を変えてまた数学板より

自然数nに対して格子点の集合{(a,b) | a,bは1〜nの整数}の中の相異なる4点の組みで同一円周上に並ぶものの個数を数え上げよ
n:1〜8では
[0,1,14,194,826,2491,6364,14564]
のハズ

586: 2020/09/20(日)13:05 ID:wHMtOvf4(3/5) AAS
>>585
ちなみにn=3の場合の14個は
1×1の正方形:4個
2×2の正方形:1個
√2×√2の正方形:1個
2×1の長方形:4個
4辺が1,1,√2,2√2の等脚台形:4個
の14個

587: 2020/09/20(日)18:36 ID:XyOg3AIQ(1/2) AAS
>>585
外部ﾘﾝｸ:ideone.com
{0,1,14,184,762,2257,5704,13040}と出たんだが
どっちが合ってる？

588: 2020/09/20(日)18:44 ID:XyOg3AIQ(2/2) AAS
一直線上にある４点の組を余分に数えたところ >>585 の解と一致した
外部ﾘﾝｸ:ideone.com

589: 2020/09/20(日)18:56 ID:wHMtOvf4(4/5) AAS
あ、ホントだ失礼しました

590: 2020/09/20(日)19:10 ID:wHMtOvf4(5/5) AAS
[0,1,14,184,762,2257,5704,13040]
が正解ですね

外部ﾘﾝｸ:ideone.com

591(1): 2020/09/20(日)22:46 ID:9sb+TTLg(1) AAS
>>585
問題がわからない。

592(1): 2020/09/21(月)00:11 ID:ZXxiMs6i(1) AAS
>>591
n=3だと

●●◯ ◯●● ◯◯◯ ◯◯◯
●●◯ ◯●● ●●◯ ◯●●
◯◯◯ ◯◯◯ ●●◯ ◯●●

●◯● ◯◯◯ ●●◯ ◯●●
●◯● ●◯● ◯◯◯ ◯◯◯
◯◯◯ ●◯● ●●◯ ◯●●

●●◯ ◯●● ◯◯● ●◯◯
◯◯● ●◯◯ ◯◯● ●◯◯
省5

593: 2020/09/21(月)11:36 ID:VFD1LGbi(1) AAS
>>585のお題は、
平面上に４点を選んだとき、その４点をすべて含む円周が存在する場合としない場合がある
xy平面上に、x,yの各座標が1〜nの整数であるような、互いに異なる点を４つ選んだとき、４点すべてを含む円周が存在するものがいくつあるか？
n=1〜8についてそれぞれ数え上げよ
(註:n=1のときは異なる４点を選べないので、解は０でよい)

ってことでいいかな？

594(2): 2020/09/21(月)13:45 ID:tVxoOCVr(1) AAS
>>592
n=4 のときの184通り
画像ﾘﾝｸ[png]:imgur.com

595: 2020/09/21(月)14:54 ID:/KyZWHiy(1) AAS
>>594
正解だと思う
おそらくn=9までは

[0,1,14,184,762,2257,5704,13040,25996]

今作ってるのはC[n^2,4]を全数検査してるのでO(n^8)で計算量増えるので二桁以上はしんどいorz

596: 2020/09/22(火)00:03 ID:jIz1rAqD(1) AAS
誰かフォルダにパスワード駆ける方法教えてくれ

597: 253 2020/09/22(火)02:15 ID:jDcMk3G3(1) AAS
対象性を考慮する以外の計算量の削減手段はないのかねこの手の問題は
解決すべき課題は計算量の削減ばかりではないだろうけれどさ

598: 2020/09/22(火)09:28 ID:yucbsR+t(1) AAS
まぁ何に重きを置くかですな
数学板でこの手のプログラムが必要になるのは誰も答え持ってなくて、一応答えは出てるけど確認したいときとか
その時は速度より“確実に正しい”事の方が重要になる
この場合も対称性やら、明らかに無駄な可能性を排除すれば速度は上がるけど“確実に正しい”のかは怪しくなってしまう
実務でプログラム使う人もその辺のtpoは意識してるのでは？、
コード汚くても高速な奴も募集中

599: 2020/09/22(火)11:56 ID:LgsCAwYw(1) AAS
>>594に挙げられている184通りのうち、その3/4にあたる138通りが、直径が√10のものである
そのうち、円の中心が図の中央にあるものは、候補となる点が8個あるので、8C4 = 70 通りある。
図の中央から(±1,0)または(0,±1)ずれたものは、候補となる点が6個なので4×(6C4)=60通り
図の中央から(±2,0)または(0,±2)ずれたものが、候補となる点が4個なので4×(4C4)=4通り
図の中央から(±1,±1)ずれたものが、候補となる点が4個なので4×(4C4)=4通り
合わせて 70+60+4+4=138 通りと数え上げることができる

図の中央を基準にすることができるものばかりとは限らないところには注意が必要だが
総当たりよりは効率化が見込めると思われる。

600(1): 253 2020/09/28(月)22:51 ID:mT2w1+AU(1/2) AAS
AA省

601: 253 2020/09/28(月)22:53 ID:mT2w1+AU(2/2) AAS
>>600
× 意識した解法を意識してしまうが、
○ 意識した解法を思い浮かべてしまうが、

602(2): 2020/09/29(火)18:23 ID:TPx3FsW2(1) AAS
お題: バブルソートを実装せよ

上下前次 1-新書関写板覧索設栞歴

あと 400 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.250s*