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

**デフォルトの名無しさん** · 2020/11/30(月) 00:04:05.21

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
プログラミングのお題スレ Part18
https://mevius.5ch.net/test/read.cgi/tech/1594702426/

**デフォルトの名無しさん** · 2021/03/08(月) 12:07:43.97

>>421
じゃあお前が死ねよ

**デフォルトの名無しさん** · 2021/03/08(月) 17:45:02.03

>>419
そうですね
広い意味では二分木探索
(ri)^2<n<(ri+2ei)^2のとき(ri+ei)^2<nか否かでr(i+1)を決める
その時n-(ri)^2の値を保持しておいて次の(n-r(i+1))^2を計算するのにわざわざ二乗する手間を省く
いわゆる和算の“開平算”の二進数版ですね
コレも「平方根、アルゴリズム」とかで検索するとよく出てきます
実際Cで実装してる例とかヒットしますね
話をfloor√nの計算に適用すれば与えられた整数nに対して
(n0,r0,b0) = (n,0,4^( floor log[4]n ))
(n(i+1),r(i+1),b(i+1))
=(n(i), r(i)/2, b(i)/4 ) (n(i)<r(i)+b(i)のとき)
=(n(i)-r(i)-b(i), r(i)/2+b(i), b(i)/4) (そうでないとき)
でb(i)=1になるまで続けると最後のriがfloor(√n)を与えるようです

**デフォルトの名無しさん** · 2021/03/10(水) 21:12:56.40

ここって算法設計的なお題オンリー？

**デフォルトの名無しさん** · 2021/03/10(水) 21:16:54.62

半年ROMるか過去スレ眺めろ

**デフォルトの名無しさん** · 2021/03/10(水) 21:56:50.00

OK
前スレ見たらグラフィックスとかサウンドとかのお題もあるのね
要は何でもありってことか

**デフォルトの名無しさん** · 2021/03/10(水) 22:00:42.15

半年でいいのかｗ

**デフォルトの名無しさん** · 2021/03/11(木) 12:49:28.58

なんでもありと言ってもなんでもレスつくわけじゃない
メディア系のお題は環境の違いでほとんど他の人が確かめる方法もないから正直うざい
事実上”みんなが確かめられるメディア系のお題”となるとjavascript一択になってしまう

**デフォルトの名無しさん** · 2021/03/12(金) 13:32:57.02

お題
何番目？

ascii文字列が与えられる
その文字列が、その文字列を並べ替えてできる文字列全体の中で辞書式順序で何番目にあるかを計算せよ

例) 入力が hello であるなら並べ替えて順に並べると
ehllo ehlol eholl
elhlo elhol ellho elloh elohl elolh
eohll eolhl eollh
hello ...
なので13である

"cabaac" -> 47
"2021312" -> 197
"This is an apple." -> 975082180080

**デフォルトの名無しさん** · 2021/03/12(金) 13:54:28.91

発展
ucs4のユニコード文字列も処理できるようにせよ

"いろはにほへとちりぬるを"
34213807

"ちょっとちょっと、大嶋さん。小島だよ！"
2031206446571101

**デフォルトの名無しさん** · 2021/03/12(金) 16:24:36.54

N進数を出せばいいだけじゃねえのコレ

**デフォルトの名無しさん** · 2021/03/12(金) 16:31:07.89

>>431
やってみろやカス

**デフォルトの名無しさん** · 2021/03/12(金) 18:56:05.12

>>429 Python3
https://ideone.com/jk3SDm
最後のは10分ぐらい回したが終わらなかった

**デフォルトの名無しさん** · 2021/03/12(金) 19:34:51.56

>>429
C++
https://ideone.com/Rnbjnb

**デフォルトの名無しさん** · 2021/03/12(金) 21:01:53.27

数学やってたほうが楽しいんじゃね？

**デフォルトの名無しさん** · 2021/03/12(金) 23:58:14.03

解説入れます
例えば2021312が何番目か考えます
樹形図を利用します
樹形図を使って2021312以前に何個の文字列が入り得るか考えます
┳0━(112223)‥‥‥‥‥‥‥‥‥6!/(2!3!1!)=60
┣1━(012223)‥‥‥‥‥‥‥‥‥6!/(1!1!3!1!)=120
┗2━0┳1━(1223)‥‥‥‥‥‥4!/(1!2!1!)=12
┗2━1┳1━(23)‥‥‥2!/(1!1!)=2
┣2━(13)‥‥‥2!/(1!1!)=2
┗3━1━2‥‥..1
図の例えば(112223)は“112223を自由に並べてできる房”を表しており公式により6!/(1!3!2!)=60個の文字列が入ります
右の欄を合計して197が2021312の番号とわかります
この作業をプログラムで自動化して下さいがお題です

**デフォルトの名無しさん** · 2021/03/13(土) 12:51:54.69

>>430 Perl
こうかなあ
https://ideone.com/qwGgdZ

**デフォルトの名無しさん** · 2021/03/13(土) 13:32:35.11

>>436
ようするにコレ階乗進数だよな？
ただの進数変換じゃねえの？

**デフォルトの名無しさん** · 2021/03/13(土) 13:37:55.91

同じ文字が２回以上出てこなければそうかもね

**デフォルトの名無しさん** · 2021/03/13(土) 15:15:23.30

例文が増えていくなww

**デフォルトの名無しさん** · 2021/03/14(日) 04:01:15.90

>>429
Kotlin
https://paiza.io/projects/aJ5J0aIVgB9tYzGBCtrRlA

折角なので順列を求めるクラスを作った。
でもこれ、長いやつは駄目なんだよな。馬鹿正直に全パターン求めてリストに貯め込んでるだけなので。
>>434のプログラムは長くても大丈夫になっているけど、どうしてそれで良いのかがまだよく分からない。
分かったらこちらでも作ろうと思う。(面倒くさくなったら分からないままにするかも知れないが)。

**デフォルトの名無しさん** · 2021/03/14(日) 05:37:41.91

単に>>436に書かれてる方法を忠実に実装するだけじゃないでしょうか

**デフォルトの名無しさん** · 2021/03/14(日) 09:07:42.95

お題: テキストからURLだけを除去しなさい

abc
https://aaaa.bbb/c_c-c/ddee?ff=gg
def
https://aaaa.bbb/c_c-c/ddee?ff=gg
ghi

↓

abc

def

ghi

**デフォルトの名無しさん** · 2021/03/14(日) 09:35:01.23

何をもってURLとする？
関連RFCに完全準拠してるか厳密に判定する？

**デフォルトの名無しさん** · 2021/03/14(日) 09:53:18.83

>>444
RFC準拠でもいいしhttps://だけにマッチさせる適当なやつでもいい

**デフォルトの名無しさん** · 2021/03/14(日) 10:49:49.29

URLのある行はURLしか含まれないの？

**デフォルトの名無しさん** · 2021/03/14(日) 11:00:29.45

>>443
この辺りで判定するだけだろ
https://qiita.com/mpyw/items/1e422848030fcde0f29a

**デフォルトの名無しさん** · 2021/03/14(日) 11:20:26.21

>>446
他のテキストと連続している場合もある

abc https://xxxx.xxx def

みたいに
半角スペースやタブで区切られてる

>>447
それ使ってもいいよ

**デフォルトの名無しさん** · 2021/03/14(日) 12:30:27.16

Ruby のURI.regexp は、Ruby 2.2 から廃止予定で困る。
URL の規格がハッキリしないのか？

誰か、C でも良いし、モジュールを作ってほしい

**デフォルトの名無しさん** · 2021/03/14(日) 15:07:40.98

>>443
Java
https://paiza.io/projects/ZfAVeQHk3wTGm68x-Co_KQ

**デフォルトの名無しさん** · 2021/03/14(日) 17:08:12.27

>>447
この正規表現は\bとかwikipediaに載ってる標準の正規表現じゃないみたいだけどコレの正規表現ってどの言語の正規表現ですか？

**デフォルトの名無しさん** · 2021/03/14(日) 17:27:02.50

'.'が文字列の結合を表してるみたいだからphpという奴ですかね？

**デフォルトの名無しさん** · 2021/03/14(日) 17:41:04.33

>>451
記事のタイトルくらい読みなよ

**デフォルトの名無しさん** · 2021/03/14(日) 17:48:59.93

>>442
そうなのかも知れないが>>436が何を言っているのかよく分からない。

**デフォルトの名無しさん** · 2021/03/14(日) 17:52:58.17

>>443
perl -pe 's#https?://\S+##g'

なんていう誤魔化しでは駄目か?w

**デフォルトの名無しさん** · 2021/03/14(日) 18:27:29.43

>>453
ほんとだw
書いてたww

**デフォルトの名無しさん** · 2021/03/14(日) 18:29:06.56

まぁでも所詮お遊びなんだからurlの切れ目はスペース、タブ、改行と決め打っても十分な気もする
こだわり出すとキリないからなぁ

**デフォルトの名無しさん** · 2021/03/14(日) 19:20:21.27

あらゆるプロトコルのURLに対応したこれが最強かな。

perl -pe 's#\S+://\S+##g'

**デフォルトの名無しさん** · 2021/03/14(日) 19:43:05.91

自分が実装するときに困らないぐらいには、曖昧さのない問題にしようよ

**デフォルトの名無しさん** · 2021/03/15(月) 04:38:00.83

>>411
Pythonにはmath.isqrt()がある(3.8から)。
ttps://docs.python.org/ja/3/library/math.html

**デフォルトの名無しさん** · 2021/03/15(月) 19:27:20.74

お題:
N 個のボールがあります。

A 君がそこから 0 個以上のボールを取り、
B 君が残りから 0 個以上のボールを取り、
C 君が残りから 0 個以上のボールを取りました。

A 君が取ったボールの数を a、
B 君が取ったボールの数を b、
C 君が取ったボールの数を c とします。

3 人がとったボールの数の組 (a, b, c) としてあり得るものはいくつか求めてください。

制約:
0≦N≦10^5
入力例 1:
3
出力例 1:
20

入力例 2:
25252
出力例 2:
2684350843635

入力例 3:
100000
出力例 3:
166676666850001

**デフォルトの名無しさん** · 2021/03/15(月) 19:31:15.27

入力例 1 は以下の 20 通りです

(0,0,0),(0,0,1),(0,0,2),(0,0,3),
(0,1,0),(0,1,1),(0,1,2),
(0,2,0),(0,2,1),
(0,3,0),
(1,0,0),(1,0,1),(1,0,2),
(1,1,0),(1,1,1),
(1,2,0),
(2,0,0),(2,0,1),
(2,1,0),
(3,0,0),

**デフォルトの名無しさん** · 2021/03/15(月) 20:06:21.92

>>461
Haskell

https://ideone.com/37676m

**デフォルトの名無しさん** · 2021/03/15(月) 20:14:30.26

>>461 Perl
https://ideone.com/yOf21q

**デフォルトの名無しさん** · 2021/03/16(火) 00:04:21.21

>>461
間違えた
Haskell
https://ideone.com/C3W6rD

**デフォルトの名無しさん** · 2021/03/16(火) 00:34:34.79

>>463
>>461とは違う答えになるようだが？

**デフォルトの名無しさん** · 2021/03/16(火) 01:01:46.91

>>466
です
公式うろ覚えで間違えました
自力で考えたい人のネタバレになるといけないので詳細などは差し控えます

**デフォルトの名無しさん** · 2021/03/16(火) 01:19:21.90

それほど多くの回数の演算が必要だったのかどうか一考の余地あり

**デフォルトの名無しさん** · 2021/03/16(火) 02:59:00.59

>>461 Haskell
463のやりたかったのはむしろこれじゃなかろうか
https://ideone.com/1TfuY4

**デフォルトの名無しさん** · 2021/03/16(火) 09:47:39.51

>>469
いえ、すでに訂正した>>465です
その式だと答えはあいますけど通例の公式の定義と文字の使い方がズレます
まぁ計算のお題というだけなら答えさえ合えばいいですけど
しかし“数学的に”という縛りもつけるなら、やはり特に理由がないなら文字、関数の命名も極力通例のそれに合わせるものでしょうね

**デフォルトの名無しさん** · 2021/03/16(火) 10:24:11.59

>>470
どういう意味で計算式を使っているか
コメントをいれた方がいいでしょうね

hが重複組み合わせてあることはわかりますが、どういう意図でx回ループさせる必要があるのか想像たけでは読み取れません
その意味では469も同じですが

**デフォルトの名無しさん** · 2021/03/16(火) 14:18:02.75

(n+1)*(n+2)*(n+3)/6
これのどこがプログラムの問題なんだ？

**デフォルトの名無しさん** · 2021/03/16(火) 14:53:32.23

出題者の趣味では？

**デフォルトの名無しさん** · 2021/03/16(火) 15:06:20.75

>>472
AtCoderの問題にも文句言って解けなさそうｗ

**デフォルトの名無しさん** · 2021/03/16(火) 15:16:46.37

お題：しりとり
しりとりで繋げよ

入力：
あんこ, ここあ, ころも, ごりら, だるま, ぱんだ, まくら, もぐら, らっこ, らっぱ, らむね, りんご

出力：
りんご → ごりら → らっこ → ここあ → あんこ → ころも → もぐら → らっぱ → ぱんだ → だるま → まくら → らむね
りんご → ごりら → らっぱ → ぱんだ → だるま → まくら → らっこ → ここあ → あんこ → ころも → もぐら → らむね

**デフォルトの名無しさん** · 2021/03/16(火) 15:32:05.39

拗音・長音の扱いは？
要は、
ばれいしょ　→　しょうゆ
なのか、
ばれいしょ　→　ヨーグルト
なのか。
あるいは、
マヨラー　→　ラーメン
なのか、
マヨラー　→　ラムちゃん
もＯＫなのか。

**デフォルトの名無しさん** · 2021/03/16(火) 15:49:28.65

>>461 C++
https://wandbox.org/permlink/qGKAod3mtvsrdWXk

まあ数学できなくても少し考えればプログラミングで解けるし

**デフォルトの名無しさん** · 2021/03/16(火) 15:53:10.76

>>476
質問するだけで解けなさそうｗ

**デフォルトの名無しさん** · 2021/03/16(火) 16:57:43.50

>>476
まぁその辺はご自由にという事で

よいしょ→よいしょ

も

いでで→てめ、このやろ

もありでもなしでも
やはりありの方が評価高い？

**デフォルトの名無しさん** · 2021/03/16(火) 17:15:58.69

やっぱりなしでいきましょか？
息抜きなんだしぱぱっと作れる範囲という事で
純粋に最初の一文字と最後の一文字完全一致のみ考慮すれば桶が基本路線という事で

**デフォルトの名無しさん** · 2021/03/17(水) 16:35:48.06

制限お題シリーズ
お題: アルファベットと改行(LF)、ダブルクオートのみで構成されたテキストがある
テキストからダブルクオートで囲まれた文字列を抽出せよ
ただし正規表現を使ってはならない

abc"def"ghi"jk
l"mno"pqr"stu"

↓

[def]
[jk
l]
[pqr]

**デフォルトの名無しさん** · 2021/03/17(水) 18:15:48.86

>>481 JavaScript

const s = `abc"def"ghi"jk
l"mno"pqr"stu"`
let quot = ''
let inQuot = false
for (const c of s) {
if (c === '"') {
inQuot = !inQuot
if (!inQuot) {
console.log('[' + quot + ']')
quot = ''
}
continue
}
if (inQuot) quot += c
}

**デフォルトの名無しさん** · 2021/03/17(水) 19:51:53.10

>>481 Ruby
str = <<EOS
abc"def"ghi"jk
l"mno"pqr"stu"
EOS
ans = []
str.chomp.split( ?" ).each_slice( 2 ){|a| a[1] && ans << "[#{a[1]}]" }
puts ans

**483** · 2021/03/17(水) 19:54:51.45

一行だった
str.chomp.split( ?" ).each_slice( 2 ){|a| puts "[#{a[1]}]" if a[1] }

**デフォルトの名無しさん** · 2021/03/17(水) 20:06:06.04

>>481 Common Lisp
https://ideone.com/jTFq2F

**デフォルトの名無しさん** · 2021/03/17(水) 21:41:02.00

>>481
Java
https://paiza.io/projects/yXtzX2TRjwJR8M7L5FPddQ

**デフォルトの名無しさん** · 2021/03/17(水) 22:03:41.35

>>475
Java
https://paiza.io/projects/1lPd6CUbhXvgT28lXYY9lw

**デフォルトの名無しさん** · 2021/03/18(木) 00:09:08.30

>>.481 Python

a='"def"ghi"jk\nl"mno"pqr"stu"'

print (a.split('"')[1:-2:2])

**デフォルトの名無しさん** · 2021/03/18(木) 02:42:51.16

>>481
Kotlin
https://paiza.io/projects/YuEG6qbQJJwhXMYXaysklg

Reader で一文字づつ読むような iterator があるとやり易いなと思ったので作った。
AbstractIterator 使うとほとんど自分で考えないで iterator 作れるから良いな。

**デフォルトの名無しさん** · 2021/03/18(木) 09:08:22.43

>>488
abcはどこ行ったの

**デフォルトの名無しさん** · 2021/03/18(木) 10:39:41.29

>>481
haskell
https://ideone.com/sNkn4h

**デフォルトの名無しさん** · 2021/03/20(土) 20:18:04.87

お題
1～6の目のあるサイコロを3つ振って出目の合計が9になる組み合わせの数を出力し
1～6の目のあるサイコロを3つ振って出目の合計が10になる組み合わせの数を出力してください

**デフォルトの名無しさん** · 2021/03/21(日) 21:33:06.36

>>429
Java
https://paiza.io/projects/w_m2vJOA0QuDXv3rfdTeXw

**デフォルトの名無しさん** · 2021/03/21(日) 22:50:12.62

>>492
(1,2,6)と(6,2,1)は別カウント？

**デフォルトの名無しさん** · 2021/03/21(日) 23:04:48.74

>>492
別カウントでhaskell
https://ideone.com/tYVMtI

**デフォルトの名無しさん** · 2021/03/22(月) 14:10:20.78

>>492
コレ公式使うより普通にdpで計算した方がいいな
haskell
https://ideone.com/4ElczD

**デフォルトの名無しさん** · 2021/03/23(火) 19:53:07.80

>>492
Java
https://paiza.io/projects/rJEqEw-lqApWQ3w1e1Zdpw

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/23(火) 20:11:55.19

お題:正方形のタイルが格子状に規則正しく並んでいて、そのサイズは5x5である。そのタイル一つひとつに東西南北(E/W/S/Nで表す)いずれかの矢印が描かれている。
タイルの矢印をたどるとき、ループがあるかどうか判定せよ。

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/23(火) 20:19:07.94

SWNSW
EWSNN
WSNNE
EEWWS

EESWW
NWSEE
NWWSS
WENNW

EWESN
SWESW
ENNWS
WSEES

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/23(火) 20:24:22.29

>>498
補足。
地図と同じように北は上とします。

**デフォルトの名無しさん** · 2021/03/24(水) 21:45:33.44

逆方向に進むのもループ？
経路としては一直線上の往復でループ状には見えないけど

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/24(水) 21:49:39.25

>>501
逆方向が続くのもループとします。
すべてのループを#で図示して下さい。

**デフォルトの名無しさん** · 2021/03/24(水) 23:30:54.73

なんだ
あるかないか判定するだけじゃなくてループ見つけないといけないのか

**デフォルトの名無しさん** · 2021/03/24(水) 23:38:09.42

>>499
5x4にしか見えないけど一段は空白で良いの？

**デフォルトの名無しさん** · 2021/03/25(木) 03:32:47.52

>>499
haskell

**デフォルトの名無しさん** · 2021/03/25(木) 03:33:15.95

>>499
リトライorz
haskell
https://ideone.com/qd0GmG

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/25(木) 08:30:44.54

>>504
すみません。5x4でした。

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/26(金) 17:38:06.64

>>498 を解けなかった人のために解説！

「数学のグラフ理論を勉強しようね」

以上。。。

**デフォルトの名無しさん** · 2021/03/26(金) 21:29:20.85

>>508
お前が解析と集合論の基礎からやり直せクソ虫が

**デフォルトの名無しさん** · 2021/03/26(金) 22:45:38.30

グラフ理論の恩恵はあまり受けられない
単に「ループがあるか否か判定せよ」ならグラフの一次のベッチナンボー計算するだけなので行列のランク計算するライブラリ持っている言語なら終わり
しかし「ループをホントに見つけて軌道の点を#にして出力せよ」では結局各点の軌跡を全部計算するしかない

**デフォルトの名無しさん** · 2021/03/26(金) 23:22:53.00

嘘書いた
向き付きグラフのoriented cycle探す問題だからbetti numberだけでは決まらない
しかし遷移行列の固有多項式が0になる事が必要十分条件なのでmaximaやmathematicaなら一撃

**デフォルトの名無しさん** · 2021/03/27(土) 16:14:39.84

>>508
これの場合難しく考えなくてもなぞって行って一度通過した所に戻るならループしている、で良いのでは？
ループの個所を示す必要がある場合は2度戻るかを調べて2度通通過した所だけを抜き出す。

**デフォルトの名無しさん** · 2021/03/27(土) 16:15:05.65

まあいいや。これから作ってみよう。

**デフォルトの名無しさん** · 2021/03/27(土) 17:26:26.72

強連結成分分解だっけ？

深さ優先探索を2回すれば、強連結成分分解できるとか

**デフォルトの名無しさん** · 2021/03/27(土) 18:03:52.24

というか難しい数学持ち出してもあまり楽にならない
結局なぞって行くのが1番簡明

**デフォルトの名無しさん** · 2021/03/27(土) 18:32:12.25

トポロジカルソートして矛盾を見つける

**デフォルトの名無しさん** · 2021/03/27(土) 19:27:34.97

>>498 Ruby
https://ideone.com/GgRlaw

ブラウザで見ると空白のサイズがずれてしまう

**デフォルトの名無しさん** · 2021/03/28(日) 03:11:42.96

お題：1のビットが3個ある二進表記文字列が与えられたとき、次に大きい
1のビットが3個ある二進表記文字列を求める。
例
111 -> 1011
1110 -> 10011
101100 -> 110001

**デフォルトの名無しさん** · 2021/03/28(日) 09:27:24.37

>>518
haskell
https://ideone.com/ossRKu

**デフォルトの名無しさん** · 2021/03/28(日) 10:06:41.16

↓のQ4の解き方わかる人いたら、教えてほしいです、、、

https://procon.disco.co.jp/backnumber/hiroshima2017/index.html#Q4_jump

**デフォルトの名無しさん** · 2021/03/28(日) 11:23:09.31

>>518
C++
https://ideone.com/JZSLMR