プログラミングのお題スレ Part19
■ このスレッドは過去ログ倉庫に格納されています
出題者の題意をくみ取るのがお題じゃないんだから
まともに出題出来ないやつは出題するな
と思う >>800
>>801
すまん
要は建物内部の間取りを作れってだけの問題なんだ
難しく書いたつもりは無い >>803
問題文は間違ってはいないだろ
補足が必要だっただけだ >>785
え？
お題は>>773で出てる３つの場合だけ答えが出ればいいの？
そんなんプログラミングのお題にならんやろ？
プログラミングのお題と言うからには手計算ではできないような部屋数が30とかそうマス数が1000マスとかの入力でも対応できるプログラムって事になるでしょ？
>>773だったら手計算でもできるやん >>806
手計算なら意味無いよw
当然あらゆる入力に対応すべきだが、問題は3つだけ まぁでも出題者の言いたい事はまぁわからないでもない
この手の話は計算量の勉強してると時々出てくる
有名なのが巡回セールスマン問題で、本当の巡回セールスマンでは「セールスマンが最も効率よく巡回できる最小経路を算出するアルゴリズムを出せ」でコレにはNP時間かかるアルゴリズムしか知られていない
しかし「最小でなくても最小値に“そこそこ近い”経路ならP時間で求められるアルゴリズム」はある
多分出題者もこの問題について「最小値じゃないだろうけどまぁまぁ小さい答えを出してくれるアルゴリズム」はもってるんだろう
しかしコレをお題として他の人に出題するなら、その“そこそこ”が数学的に“どのくらい”なら合格とするのかを明示しないとお題にならない >>806
そう解釈したから>>797
>>807
適切な回答は用意してあるんだよね？ まあ簡単ではないとは思うが
問題文わかりづらかったかい？ >>813
そんなに意味不明な問題だったか？w
マジかw
じゃあ明日にでも参考解答出すよ 例えば>>777の設定で「総マス数が2N+Tまでは合格」とかその手の縛りにしないと“最小”という縛りでは問題にならない >>814
正しい出題が先
条件は>>773から変更は無いか
３題だけ解ければいいのか
時間やリソースを無視すれば解けるコードならいいのか
どの程度の規模の問題まで現実的な時間、リソースで解けれなければならないのか 今のままでは>>797で正解だ
（面積を追加すれば） >>817
773の条件なら797で正解
773で抜け落ちたが、当初は廊下は一続きであるという趣旨なんだよ
だが無闇に難易度を上げるつもりも無いから797で良し 廊下一続き縛りでも、そこまで計算時間かからんと思うよ
巨大な室数と面積でも無ければね
もちろん、宇宙ホテルでは無い なんで>>815は問題改変したがるんだろう？
総当たりだろうが最小を出すことは出来るだろ
Nがでかくなると実用的な時間では答えが出ないかもしれないけど お題：コイントス（数学板の問題の改変）
コインを3回連続で投げるとき
表表表,表表裏,表裏表,裏表表,表裏裏,裏表裏,裏裏表,裏裏裏の8通りが等確率で出る
2人で先手と後手を決めて、先手が上記の8通りの中から1つ選び、後手は残った7通りの中から1つ選ぶ
そして1枚のコインを連続して投げ続けて、先に選んだパターンが出た者の勝利とする
例えばAさんが 表表裏 を選び、Bさんが 表裏表 を選んだとして、
コインの結果が、裏裏裏表表裏 となったら 表表裏 が先に出たのでAさんの勝利
コインの結果が、裏裏裏表裏表 となったら 表裏表 が先に出たのでBさんの勝利
同様のルールで、コインn回(3≦n≦6)のパターンを2人で予想し合うとき、
先手の予想を表す文字列を入力として、後手の勝率が最大となる後手の予想を表す文字列を出力せよ
入力で与える文字列として、"表" "裏" の代わりに "0" "1" を使用して良い
※入力と出力の文字列は同じ長さとする
例1: 入力 = 0000 → 出力 = 1000
例2: 入力 = 111000 → 出力 = 111100 >>818
廊下が連結が元の題意ならそう訂正すれば良い
>>752からあくまで「補足」だと言い張りたいなら
あとから追加した条件「・廊下の一端は外周に接する事」も消さないと
>>819
部屋数A〜Zの26部屋
各部屋のサイズ20くらいまで
が現実的な時間、リソースで解ける
と思って良いか？ >>821
いや、総当たりなら出せるけど、それでは「巡回セールスマン問題の最小解を求めるアルゴリズムを求めよ」と言ってるのと同じで事実上総当たりしかない
もちろん総当たりアルゴリズム実装するのは難しい話てはないけど面白くもなんともない
しかし「最小値ではないが最小値にかなり近い値でよい」なら工夫のしようもある
例えばこの問題なら廊下の最小値は[N/2]だけどコレをどこかに真っ直ぐ引いてその両脇からN個の部屋をニョロニョロ伸ばして綺麗に長方形に治るようにする解なら多項式時間程度で求まる
しかしその方法で解が見つからなかったとしても、“あらゆる場合”を検討したわけではないから探索を次のステップに進めることができない
あくまで最小値を求めるならここで総当たりしてるダメな事を確認しないといけなくなる
しかし制限が最小値でなくて例えば2N+T以下くらいに緩ければこの方法で解を求める事が(多分)できる
まぁわかってもらえないようだからいいよ
総当たりプログラムなんて面白くもないのでROMします >>822
ほとんど数学の問題
それともモンテカルロで解く？ >>824
アルゴリズムの工夫で現実的な時間で解けるという可能性は？
NP問題だと証明できた？ >>824
> 総当たりプログラムなんて面白くもないのでROMします
よろしくねw >>826
そんなのできるわけないやん？
つまりこの問題かperfect NPか？と聞いてるのと同じで全く新しいPerfectNPを見つけた事になる
そんなの論文レベル
まぁ多項式時間では解けそうにないなぁってのはあくまで第1感で実際には解けるもしれない、しれないけど自分が無理くさいと思ってる問題でペイも発生しないお遊びにそこまで頭と時間使う気になれない
チャレンジして「やっぱダメじゃん」で終わった時虚しさしか残らん >>822
おもしろそうなので考えてみます
数学板などのカンニングは無しで
答えを書くのしばらく待って！ >>823
廊下の一端は外周に接する、この条件は生き
部屋数は26まで、各面積は20坪までとする
（そこまで想定して無かったがw）
現実的な時間で解けない問題も過去には出てたからなあ
それでも猛者は取り組んでたよ
回転寿司の皿の問題とか >>828
興味が無いならROMしててくださいな
以前みんなが指数関数オーダー以上でしか出来なかった問題を
線形オーダーで解いたことがあったのを思い出した >>830
それ
回転寿司問題
私が線形オーダーに縮めたやつ >>829
その問題数学板では答えしか出てない
計算式とかアルゴリズムは出てないので見に行っても大丈夫
いわゆる受験で出てくる“確率漸化式”の話(Homogeneous Morkov Chainと言います)の話が理解できてれば行列計算のルーチン実装すればできます
HMCの話知らなくても受験数学レベルでギリギリできなくもない >>835
わざわざ「カンニングは無しで」って書いたのに
わざわざヒント書くかねえ
しばらくこのスレ見ないことにする
>>830
とりあえず>>830の範囲で考えてみる
このスレにはしばらく来ないけど
寿司問題、ずいぶん前だよね
ずいぶん前からこのスレにいるなら
最初から出題は正しく曖昧性なく書こうよ >>836
ヒントになんかなってないよ
大丈夫
この単語ググっても答えになんか辿り着かないから
数学板にも答え出てません
まぁコレ以上なんかいうとホントに答えになるのでやめときます
頑張ってください >>837
これかな？18レス付いてた
お題:
回転寿司にやってきた私は、コンベア上のすべての寿司を食べて帰ることにしている
コンベアは1秒に1皿分の速度で流れ、目の前の皿を取るか取らないかを選ぶことができる
私は皿取ると同時に食べ始めるが、食べている間は次の皿を取ることができない
コンベア上の皿は、私が取る以外で勝手に追加されたり無くなったりしない
最初のコンベアの状態が次のような文字列で与えられる
"31_2"
数字(1文字)はその皿を食べ終えるのにかかる秒数を表し、_は皿がないことを表す
1文字目が私の目の前であり、1秒毎に左へ回転する
例えば、最初の皿を食べたとすると食べ終わった時の状態は以下である
"2_1_"
すべての寿司を食べ終わるまで最短何秒か求めよ
"12_3" > 6秒
"313__" > 8秒
"4_35_1264_23_434" > 60秒
"123456789123456789" > ? 部屋の問題はダンジョンや迷路生成のアルゴリズムに似た物じゃない
パラメタが違うだけ
起点(玄関兼廊下)から幹道(廊下)があって支道(部屋)を生成し全体を枠内に収める 対称性があるかどうかも分からない
巨大合成数を生成するのは掛け算するだけでかんたんだけど
それを二つに分けるのはちょっとばかし面倒でしょ >>842
まだ大きい数字のチェックが終わってないが、出しましょうか >>842
これになります
大きい数字で条件違反が出るので、もうふた工夫要りますが
https://ideone.com/Rnq0SJ ５００ｘ５００くらいになる手頃な大きさの例とか無いの？ >>822 Ruby
https://ideone.com/uiPy1x
最大深さnまでの負け以外の集計から勝率の集計に変更 >>776
電話番号の最初が 010 や + ならば国際電話でそれ以外は全て国内電話だと思うが、本当にそれだけの判別で良いのか？ >>776
携帯の電話番号というのを見落としていた。で、何が携帯番号かの資料は何処にあるのか? >>678
> 仮名を清音に変換してから比較する
うん、発想はいいが、いまひとつ。
清音のキーと「長音」「濁音」「拗音」とかのキーをそれぞれ生成して、
それをどうにかして整列キーを生成して文字列順の整列ルーチンに
喰わせる、ということを考えたら完璧。 お題: 複数ある改行を1つの改行にまとめる関数join_newlinesを作成せよ
s = 'abc\ndef\n\nghi\n\n\n'
s = join_newlines(s)
print(s)
# 'abc\ndef\nghi\n' >>856 Ruby
p "abc\ndef\n\nghi\n\n\n?".split.join$/ # => "abc\ndef\nghi\n" >>854
小学生の頃、かくれんぼしてたの覚えてるか？ 今でも覚えてるからな。 >>856
js
s.replace(/\n(\n)+/g,"\n") >>856
haskell
import Data.List
joinNewLines = id
. concat
. map (\x -> if ( head x == '\n' ) then "\n" else x )
. group >>847 Wrong Answer 0000→0001
>>849 Wrong Answer 0010→1100 >>864 訂正・補足
>>847 右のケースでWA 入力0001→出力0000
>>849 右のケースでWA 入力0010→出力1100 >>856 Python
def join_newlines(x): return "\n".join(x.split()) >>867
これで文字列の最初に空行があったり、文字列の最後に空行が続いたというような場合の復元ができるものですか？ >>868
確かにおかしいですね
一応直してみましたがあんまりすっきりとはいきませんでした
>>856 Python
def join_newlines(x): return "\n".join(("@"+x+"@").split())[1:-1] 数学板より
お題 ヘビサイド関数で近似
問題は長いのでリンク先
分からない問題はここに書いてね 467
https://rio2016.5ch.net/test/read.cgi/math/1619884204/439-440
出力して欲しい３つの数値の例
上のリンクの下の440の方
【具体例1】
N = 3
l r s w
1 3 6 1
0 8 4 1
5 7 2 1
a=4, b1=6, b2=2 としたとき、F(a,b1,b2)=0 になり、これが最小値です。
a=3, b1=6, b2=2 としたとき、F(a,b1,b2)=4 になり、最小値ではありません。
a=4, b1=5, b2=3 としたとき、F(a,b1,b2)=4 になり、これも最小値ではありません。
【具体例2】
N = 4
l r s w
0 2 4 3
1 5 6 9
4 10 1 2
8 9 7 10
a=0.8, b1=1, b2=6 としたとき、F(a,b1,b2)=70 になります。 >>872
ここは数学板じゃないので、
「この問題を解くと、どういう用途に役立つのか」
ということを聞いておきたいと思います。 >>873
残念ながらこの質問した人このレスを最後に消えてしまいました
なんの役に立つのやら お題：teshimatta関数関数を作れ
入力は1文字以上を保証される
teshimatta("起きた")
> "起きてしまった"
teshimatta("やった")
> "やってしまった"
teshimatta("あ")
> "ってしまっあ"
teshimatta("古畑任三郎")
> "古畑任三ってしまっ郎" >>877 修整
teshimatta("あ")
> "てしまっあ"
teshimatta("古畑任三郎")
> "古畑任三てしまっ郎" >>877 Ruby
def teshimatta(str) = str.insert(-2, 'てしまっ') >>877
haskell
teshimatta = reverse . concat . zipWith ( flip ( : ) ) ( "っまして" : repeat "" ) . reverse >>877
Kotlin 及び Kotlin script
以下は kotlinc コマンドで REPL で動かした時のコピペ。
>>> はプロンプト。1行目が関数定義。2行目から使用している。
>>> fun teshimatta(s: CharSequence): CharSequence = if (s.isNotEmpty()) StringBuilder(s).insert(s.lastIndex, "てしまっ") else s
>>> teshimatta("起きた")
res1: kotlin.CharSequence = 起きてしまった
>>> teshimatta("やった")
res2: kotlin.CharSequence = やってしまった
>>> teshimatta("あ")
res3: kotlin.CharSequence = てしまっあ
>>> teshimatta("古畑任三郎")
res4: kotlin.CharSequence = 古畑任三てしまっ郎
>>> >>877 Python
def teshimatta(s): return s[:-1] + "てしまっ" + s[-1] お題：一筆書き
0：床、1：穴、2：スタート地点
からなる数字列が与えられる。スタート地点から縦または横に1マスずつ移動し、すべての床を通過することとする。
穴や外周は通過できない。床は一度通過すると穴となり二度目は通過できない。
すべての床を通過できれば「OK」、できなければ「NG」と表示せよ。
【例1】OK
0000
0210
0000
0100
【例2】NG
0000
0200
0010
0000
【例3】OK
000000
210000
000100
000001
000000
【例4】NG
000000
210000
000100
000000
000001 >>883
まさかこれ頂点の次数を数えるだけで終わるのか？ NP完全らしいから事実上考えても無駄で総当たりで検索するしかなさそうやね >>883 Prolog
'お題：一筆書き
0：床、1：穴、2：スタート地点
からなる数字列が与えられる。スタート地点から縦または横に1マスずつ移動し、すべての床を通過することと
する。
穴や外周は通過できない。床は一度通過すると穴となり二度目は通過できない。
すべての床を通過できれば「OK」、できなければ「NG」と表示せよ。'(_行,_列,L) :- nth1(_スタート,_数字列,2), 選択(_行,_列,_スタート,_数字列).
選択(_行,_列,_n,_数字列) :- \+(member(0,_数字列)), write('OK\n'),!.
選択(_行,_列,_n,_数字列) :- 隣接(_行,_列,_n,_n_2), nth1(_n_2,_数字列,0), '_n番目を1に変える'(1,_n_2,_数字列,_数字列_2), 選択(_行,_列,_n_2,_数字列_2).
選択(_,_,_,_) :- write('NG\n').
'_n番目を1に変える'(_n,_n,[_|R],[1|R]) :- !.
'_n番目を1に変える'(M,_n,[_現在位置|R1],[_現在位置|R2]) :- succ(M,N), '_n番目を1に変える'(N,_n,R1,R2).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 - 1, \+(0 is _隣接 mod _列).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 + 1, \+(1 is _隣接 mod _列).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 - _列, _隣接 > 0.
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 + _列, _隣接 =< _行 * _列. >>884 すみません。一箇所間違えました。
Prolog
'お題：一筆書き
0：床、1：穴、2：スタート地点
からなる数字列が与えられる。スタート地点から縦または横に1マスずつ移動し、すべての床を通過することと
する。
穴や外周は通過できない。床は一度通過すると穴となり二度目は通過できない。
すべての床を通過できれば「OK」、できなければ「NG」と表示せよ。'(_行,_列,_数字列) :- nth1(_スタート,_数字列,2), 選択(_行,_列,_スタート,_数字列).
選択(_行,_列,_n,_数字列) :- \+(member(0,_数字列)), write('OK\n'),!.
選択(_行,_列,_n,_数字列) :- 隣接(_行,_列,_n,_n_2), nth1(_n_2,_数字列,0), '_n番目を1に変える'(1,_n_2,_数字列,_数字列_2), 選択(_行,_列,_n_2,_数字列_2).
選択(_,_,_,_) :- write('NG\n').
'_n番目を1に変える'(_n,_n,[_|R],[1|R]) :- !.
'_n番目を1に変える'(M,_n,[_現在位置|R1],[_現在位置|R2]) :- succ(M,N), '_n番目を1に変える'(N,_n,R1,R2).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 - 1, \+(0 is _隣接 mod _列).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 + 1, \+(1 is _隣接 mod _列).
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 - _列, _隣接 > 0.
隣接(_行,_列,_現在位置,_隣接) :- _隣接 is _現在位置 + _列, _隣接 =< _行 * _列. >>891
総当たりでやる前に市松判定ではじく処理くらいは入れてもいいと思う お題：今日は第何曜日か計算して現在の日時を以下のように出力する
2021/06/09/第2水曜日/19:21/
ヒント
今日の日にちを7で割る 例：9 / 7
少数点以下は切り捨て
１を足す
カレンダーを見ながら計算すると分かりやすい >>895 Ruby
puts Time.now.then{|t| t.strftime('%Y/%m/%d/第%%d%%s曜日/%R') % [(t.day + 6) / 7, %w[日 月 火 水 木 金 土][t.wday]]}
# => 2021/06/09/第2水曜日/19:52 >>895のヒント通りだと7の倍数の日付で不具合が発生するが宿題か？ >>897
>>896のほうが簡単なのでヒント変更
今日の日にちに6を足して7で割る 例：(9+6) / 7
少数点以下は切り捨て
カレンダーを見ながら計算すると分かりやすい ■ このスレッドは過去ログ倉庫に格納されています
