プログラミングのお題スレ 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/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

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

>>520
マルチはよくないなぁ

以下のプログラミングテスト（Q4）の解き方を教えて下さい。http... - Yahoo!知恵袋
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13240901843

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

幅優先探索で各まとまりごとに数える
イメージとしては水を流すかんじ

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

そんな単純じゃなかった
すまん

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

>>498
python3で頑張りました。
https://ideone.com/jRsBaI

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

>>518
python3。
https://ideone.com/J7MbiO

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

>>520
たぶん
外周に番兵を置いて、番兵に接触する空白も番兵とみなす、このとき斜め方向に接触する空白も番兵とする。
あとはそれぞれコマの四方向のコマと空白のつながりから塊を調べる、コマ数をカウントすれば塊の数。
こんな感じ

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

>>498
C
https://ideone.com/y4IBiu

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

>>498
なぞって行って2度通過した個所を出してみたら EW みたいな進んだ方向にただ戻る個所もループという事になったのだが、
それもアリか？アリならできたぞ。そういうのは除外となるともう一段それの発見のための処理を追加する必要がある。

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

>>529
上の方でありだって

**527** · 2021/03/29(月) 00:19:25.86

>>520 Ruby
https://ideone.com/n1jLCH

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 00:44:12.81

お題: 上下左右に広がる、がらんどうのX-Y二次元空間がある。直径10cmで質量7kgで均一な密度のボール状の物体Pの中心は、
時刻ゼロのとき、A地点(x1, y1)にあり、ここから謎の力により空中に固定される非常に丈夫な一枚の板と、時刻ゼロより発生する重力を使って、B地点(x2, y2)まで誘導したい。BはAより下にある(y1>y2)。
板は固定すると重力が働いてもびくとも動かない。物体PはB地点を必ず一度以上通過しなければならない。さてどのように板を設置すればいいか。時刻がゼロになる前に板を注文して固定しなければならない。
板は真っ直ぐ直線的であり、板の厚みは考慮しない。摩擦と空気抵抗は無視し、反発係数は1とする。この板は非常に高価なため(1cmが3万円)、なるべく短い長さで注文する必要がある。
重力加速度は下向きで地球上と同じ強さとする。設置する板の両端の座標(x3, y3)～(x4, y4)[cm]と使用する板の費用price[円]と、時刻ゼロよりB地点到達にかかる時間T[秒]を求めよ。

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 00:48:38.14

>>532
例1)
(x1, y1, x2, y2) == (1, 3, 4, 1).

例2)
(x1, y1, x2, y2) == (0, 10, -8, 0).

例3)
(x1, y1, x2, y2) == (-5, 3, 5, 0).

**デフォルトの名無しさん** · 2021/03/29(月) 07:42:15.30

>>532
二次元空間なのにボール状の物体が存在するのか。重力加速度の下向きってどっち？
蟻人間ていつも凝った設定を作ろうとして杜撰なものばかりなイメージがある

**デフォルトの名無しさん** · 2021/03/29(月) 07:43:41.48

あ、下は書いてあるのね

**デフォルトの名無しさん** · 2021/03/29(月) 07:47:56.84

そりゃ知能が蟻並みだからな

**デフォルトの名無しさん** · 2021/03/29(月) 08:11:58.61

adhdとか何か(学習|発達)障害持ってるんでしょ
ガイジなのは一見して分かるし

**デフォルトの名無しさん** · 2021/03/29(月) 09:01:21.30

少なくとも>>532は最小値が存在せんやろ

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 09:52:29.10

注文できる板の最小の長さは1cmとします。初速はゼロとします。

**デフォルトの名無しさん** · 2021/03/29(月) 09:54:01.19

じゃあ答えは0

**デフォルトの名無しさん** · 2021/03/29(月) 09:54:28.27

じゃなくて1cm

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

(x1,y1)から右下の(x2,y2)へ45度のスロープ作ったら到達時間は何秒かって問題だろ
板の値段は30000√2円

**デフォルトの名無しさん** · 2021/03/29(月) 10:08:28.37

例にあるマイナス座標の意味がわからない

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 10:19:24.26

与えられたパラメータでBを通過するか判定する関数fを定義して下さい。fが正しく定義され、fに成功するパラメータならば正解とします。ブルートフォースや空間探索を使ってもかまいません。

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 10:21:35.37

>>542
はね返りを使えば板はもっと短くなるかと。右下ではなく左下の場合も可能。

**デフォルトの名無しさん** · 2021/03/29(月) 11:08:10.66

>>545
板の設置位置に制限がなく反発係数が1、すなわち運動エネルギーのロスが0なら目標地点がどんなにとおくても、高低差がどんなに小さくても到達できる
hだけ下方に設置してθだけ傾けた時を考える
板に反射した地点を原点、t=0として、初速は√(2gh)、最高到達点までの時間は√(2h/g) cos2θ、水平方向速度は√(2gh)sin2θ、反発地点から最高到達点までの水平距離はhsin4θ、最高到達点の高さはhcos^2(2θ)
方程式
x2-x1=2hsin(2θ)cos(2θ)
y2-y1=-hcos^2(2θ)
はy2-y1<0である時常に解もつ

**デフォルトの名無しさん** · 2021/03/29(月) 11:35:09.16

ちょっとだけ傾いててほぼ水平なら、板の長さは限りなく1cmに近づき、到達時間は無限に近づくわな
あとはB点が線分上にあるか計算するだけでいい

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 11:36:43.02

>>546
だいぶ近いけど、ボールの直径を考慮する必要があるよ。

**デフォルトの名無しさん** · 2021/03/29(月) 12:31:33.01

>>547
どのみち常に解を持つから問題になってない

**蟻人間** ◆T6xkBnTXz7B0 · 2021/03/29(月) 14:04:34.12

お題：次の文章を解読するプログラムを作れ。

「この文書は{SJIS:93C192E894E996A7}です。{SJIS:95948A4F8ED2}が閲覧すると、{SJIS:94B182B982E7}れます。」

**520** · 2021/03/29(月) 21:19:00.34

>>522
すみません、ルール違反なんですね…以後気を付けます。

>>527
>>531
ありがとうございます！
考え方まで記載いただき、本当に助かりました。