プログラミングのお題スレ Part21
レス数が1000を超えています。これ以上書き込みはできません。
https://mobile.twitter.com/mashino8
小中学校教諭はマクドナルドのアルバイトと同じ最低賃金でかつ資格は不要。
プログラミングを他人に教えるなら、まず自作プログラミングを模範として開陳すること。
形式よりもデザインの独自性を追求する。「車輪の再発明」はいらない。
https://twitter.com/5chan_nel (5ch newer account) それじゃあこのスレがどれだけ実力があるのかお題だすね
物体認識で手を認識させたときの指先のトラッキングをやってみてください
物体認識のモデルはすでに学習済みと仮定あとはカメラで写ってる指先の特徴点のポイントを取得するだけです >>6
たしかに…無いとテストとかもできんもんな… お題:自然数nが奇数かどうかチェックする関数oddを定義せよ
c
https://ideone.com/gdiEYq
//int odd(int n) {return n & 1;}
int odd(int);
int even(int n) {return n == 0 ? 1 : odd(n - 1);}
int odd(int n) {return n == 0 ? 0 : even(n - 1);}
ocaml
https://ideone.com/LYsHsF
let rec even = function 0 -> true | n -> odd (n - 1)
and odd = function 0 -> false | n -> even (n - 1) かなり昔に寿司問題というのがあってそれが難しかった記憶だが
問題を忘れた 検索したら見つかった、これ
回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。
コンベアは毎秒1皿分の速度で流れ、目の前の皿を取るか取らないかを選ぶことができる。
皿取ると同時に食べ始め、食べている間は次の皿を取ることができない。
私が取る以外、皿は追加されたり無くなったりしない。
コンベアの状態が次のような文字列で与えられる。
"31_2"
数字はその皿を食べ終えるのにかかる秒数を表し、_は皿がないことを表す。1文字目が目の前にあり毎秒、左へ回転する。
例えば、"31_2"で最初の皿を食べたとき食べ終わった時の状態は、"2_1_"となる。
すべての寿司を食べ終えるまで最短何秒かかるか求めよ。
"12_3" > 6秒
"313__" > 8秒
"4_35_1264_23_434" > 60秒
"123456789123456789" > 98秒
"88967472612377988186" > 149秒
"19898693316679441672" > 170秒
"93769682716711132249893" > ? 1から3999までのローマ数字が与えられるのでそれを算用数字で表示する
例
IV -> 4
XLIX -> 49
CDXLIII -> 443 >>11
昔私が高速で求める方法を見つけたヤツだね
おぼえてます >>11
コレ多項式オーダーとかで行けるんですか?
やはり指数オーダーはかかる? 寿司問題はやり方考えたが確認はしてない
再帰的に解けると想定
寿司2個を食べ終わる時間で寿司1個であるかのようにみなす (寿司セット)
たとえば寿司3個の場合なら、最も最短時間の寿司セットを作って寿司2個の場合に帰着させたら解けるはず
最も最短時間の寿司セットというは合ってるか不明だが、そういうやり方で少ない寿司の場合にもっていけるはず とりあえず寿司3個の場合をランダムか総当りで生成して、2個を連結させる方法が正しいのか確認できそうだがしていない Part9-413にコードがある
いろんな定義と証明が書いてあるメモが見つかったけど意味わからん >>15はべつの言い方でいうと与えられたレーンで食べる順を確定させられるペアを見つけるってことだが
総時間が短いものか、空き時間が短いものか、空き時間が短いうちで最も最長のものか、そういういった組み合わせが考えられるが
正解があるかは不明 単に空の時間が少ないようにペアをあわせていけば解ける気がしてきた
空は0として "313__"の場合はこうなって解ける
2行目への変化だと1秒と3秒の寿司を食べるとして4秒の寿司へ変わる
次は4秒寿司と3秒寿司が続けて食べられて7秒寿司へ
最後は一秒まって7秒寿司をたべて8秒で終わる
31300
34000
07000 これもやってみたら手動で正解できた "123456789123456789" > 98秒
123456789123456789
303456789303456789
703056789703056789
709050789709050789
0090C07890090C0789
009000J89009000J89
0090000X90090000X9
00I0000XI0000000X0
00I0000YI000000000
00I0000Z0000000000
00W000000000000000
10以上の数値は英字で置き換えた
C 12
J 19
X 27
Y 54
Z 73
W 96 食べる、食べない=パス、の2択で再帰じゃないの?
食う カレントが値分後方へ移動、パス連続中フラグdisable
パス カレントが1つ後方へ移動、パス連続中フラグenable、パス連続可能回数セット
パスが連続出来る回数に制限があるので有限
9からパスし続けて良いのは8回まで。9回パスしたら9を食えてるよねって話
パスした次がより少ない値ならばパス連続可能回数は少ない方で上書き
> "93769682716711132249893"
だと1番目の9はパス連続可能回数8でパスした場合、2番目の3にカレントが移りパス連続可能回数は-1されて7
3のパス連続可能回数は2、7と比較し少ない方の2が上書きされる
パスした場合3番目の7へカレントを移しパス連続可能回数1
7のパス連続可能回数6と比較し少ない1
更にパスした場合、4番目の6
6の5と0を比較しパス連続可能回数0となり、ここではパスは選べない
パス連続中フラグとパス連続可能回数の2つのステータスが要る
フラグは能動的にパスしたのか食うものが無くて次に移動したかの区別
という解釈なんだけど間違ってる?もっと良い方法あるの? 上でいってるやつをコードにした
一個結果がちがってるが よく検討していない
Python
https://ideone.com/yXUVxt 可能性としては、このアルゴリズム自体が最小値を出す可能性があるだけでかならずしも最小値ではないだとおもう >>26
修正しておなじやつ全部解けたけど、最小値を出す保証はないとおもう
https://ideone.com/SGX9y8 大局的なこと、試行錯誤はやらずに空レーンでの待ちが少なくなるように2個セットをつくり続けて寿司個数が少ない場合に帰着させるだけ
これで正解が出させるほうが不思議 >>31
それ自分だと9秒になるが、>>26だと8秒になるな
しかし、どうやっても8秒だと無理とおもうが
人間の試行錯誤で >>32
これじゃダメ?
1: *_22(取る)
2: _*22(食べる)
3: __22(休み)
4: __2*(取る)
5: *_2_(食べる)
6: _*2_(休み)
7: __*_(取る)
8: ___*(食べる) 今上がってる
24
26
29
が線形時間で動くコード? 空なしで連続して食べれるなら食べてしまうやり方で失敗する例が2_22か
これがあるならば待ちで0か1で食べれるのに2以上待たないと駄目な例もありそうだ
ややこしい これリニアオーダーで動くアルゴリズムがある事実証できてるの?
>>22はリニアになるの? 連続食いアルゴリズムだと
2_22 よりも3_22や3_23の簡単だが
9以下が言えたら8では出来ないかチェックするために
寿司の総和時間が7、8となるように元の寿司を巨大化させ再チェックすればいいか
計算量はちょっと増えるがこれで見逃しはなくなるはず 寿司をわざとデカくして連続食い優先アルゴリズムで、食べ飛ばしに対応させようとしたけど
たとえばこれだと今の寿司の時間の合計は41で、
合計が59になるように寿司増量するやり方は相当あって、その組み合わせを生成するだけでも困難な数だった
この方針は断念すべきか
"4_35_1264_23_434" > 60秒 >>29と同じアルゴリズムと同じPythonだが
重複するコードとforを別の記述してコンパクト化
最小値候補を見つけるにすぎない、最小値を確定させるのは断念するか
https://ideone.com/1Y1x6Y >>26は解読できないが
これは探索しないと無理な気がしてきたが
リストが与えられたときに確実に連結させされるペアを
探索なしで静的に確定させられるならnのオーダーといえるだろうが無理な気がしてきた 今のところ>>26が最小解をリニアオーダーで与える事の証明上がってこないけど5年前は誰かその証明つけてたん? 寿司問題ってもう5年前か
時間が経つのはあっという間だな https://ideone.com/qPsn3a
5年前のメモです
証明が非常に簡略化して書いてあります
(書いた本人でも解読に時間がかかる)
またコードにコメントで計算量が書いてあります
参考にしてください コレはわかんないな
なんかの基準で候補を絞ってその中で1番短いの見つけてるっぽいけど、その絞り込んだ候補の中に必ず最小元がある事の証明はコードだけではわからないよ 寿司をグループに分けるまでが肝 (メモに書いてある同値関係)
あとは簡単
2通りに場合分けして簡単な計算をするだけ よくわからんけど全通り計算して最短出すだけじゃね? まずレーンからわからん
数学の世界でない用語でしかも定義がないとわからん
ちゃんと文章になってたら前後の文脈から推定できたりもするけど文章じゃないからエスパーのしょうがない ざっとみて正解を確信できん
平易な説明文であってるだろうと思わせることはできないか どやろ
あってるっぽい香りはするけど
多分本人の備忘録に過ぎないもので元から他人に理解してもらうつもりに書いてないな >>12 octave
https://ideone.com/In2JqK
function n = f(s)
k = 'IVXLCDM';
v = [1 5 10 50 100 500 1000];
h = @(x) v(k == x);
n = sum(arrayfun(@(c, d) [h(c) -h(c)](1 + (h(c) < h(d))), s, [s(2:end) s(end)]));
end やっぱり無理やな
おそらく“最小完備閉路”なるものが存在してその中で最小であるものは線形時間で見つかるを示すんだろうけど“最小解は必ず最小完備閉路”である事の証明が1ミリもない
せめてその証明があれば逆にその証明から“完備閉路”の意味をエスパーもできるかもしれないけど 最小完備閉路分解
×「最小完備閉路」への分解
○完備閉路分解のうち(完備閉路の)個数が最小の物 閉路 : (開始位置はどこでもいいけど)丁度n周でお寿司をたべる食べ方
完備閉路 : 効率の良い閉路 最小完備閉路分解 = お寿司のグループ分け ( >>49 ) >>61
あなた筆者
ごめん、メモは全くわからないです
もうちょっと数学っぽく書けませんか? 私の中では解決済みの問題ですので
時間をかけて厳密な記述や分かりやすい記述にしようという気力はありませんし
多くの人に理解してもらおうとも思っていません
メモは私用に書いたもので
グラフ理論の用語や独自定義の言葉などが混ざっています
気に入らないなら見なかったことにしてご自分でゼロから考えてください
しばらく消えます
では これでいいんじゃないの?
下限を計算してるけど答えから逆順に取っていけば必ずうまくいくはず
https://wandbox.org/permlink/oyLHJmsPlbkRgyi7 んー最後にループをまたぐものが残ることがあってだめなのか >>65
できる理由がわかってないが終了位置が特定できるなら良いとおもうが
検討してみる >>65
理解した、この方針でよさげ
これで出来てるのはたまたまで
終了位置は特定できないかと
修正してみる いくつかの例でうまく行ったとしてホントにそのアルゴリズムで“常に”上手くいくとは限らないからな
“常に”上手くいく事を主張するには結局数学的に証明するしかない 例えば寿司が連続9個空の部分があってそのいずれかからスタートする場合を考えるなら全ての周回で元の位置に戻ってくる時には口に何も入ってない状態になる
その場合に全ての周回で毎回「寿司を常に可能な限りとれるだけ取る」事で最小な解を与えるとは限らないやろ
あえてそのような最小解でない解をうまく組み合わせると全体としては最小になる可能性もある >>65
指摘されるまで気づかなかったが
最小値の下限はこういう風に簡単に評価できるんだな
>>47の人も多重度とか乗ってるし考慮してるのかと
>65は最も小さくできる場合の可能性であって実現性は考慮されてなく実際できるか調整ないと 一般での証明を解説するのは諦めたけど
具体例であればアルゴリズムと証明を書いて差し上げます
1周20秒以内で1問出してくださいな >>47 と同じアルゴリズムだけどリメイクした、かならずも正解はださない
https://ideone.com/n9MvXp >>73はmaxvalの位置で終わることを想定してるが
問題点としては、そのような選び方が存在するか OR 終了位置がmaxvalよりも後方へずれる可能性
がある点
修正できてない >>65
最小値下限と終了位置候補がわかっているのは大きいが
実際にできるのか、そのルートを構成するしかないとおもってきてる
実際につくるとなると手間だ 例えば寿司の配置が
┓ ┏━━━━
┏━┓
┏━━━━┓
┏━━┓
┏━━┓
2122121233211
のような場合10番目のところが3なので最低でも3週目の10秒目までは絶対に終了し得ない
ミソはこの10番目で必ず食べ終えることができる寿司、上の例では上から2番目の寿司があって、必ず3週目の10秒の時点でこの寿司を食べ終える解が存在する事を示すことですな >>78
123456789123456789 の解答は98だが
>>65>>73 だと90 となり、訪問回数を表すAの値はこれ
こういったケースだと末尾9を食べて98になるのか?どういう条件でズレが生じるかわからん
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] とりあえずザックリ説明
(i)多重度最大、最後尾に寄与する寿司を取り除いても最大多重度が変化しない時
(下図のような場合2番目、3番目寿司を取り除いても最大多重度は3のままである)
┓ ┏━━━━
┏━┓
┏━━━┓
┏━━┓
┏┓
┏━━┓
2232121233111
この場合、多重度最大、最後尾に寄与する寿司を取り除いた状態における最大多重度、最後尾(例えば上の例で2番目の寿司を取り除くと、最高多重度、最後尾は多重度3、最後尾は3番目の位置となる)に寄与する寿司(上の例だと5番目の寿司)を最後に食べる解が存在する、その解にいま取り除いた寿司を最後にさらに食べる事にすれば良い
(ii)多重度最大、最後尾に寄与する寿司を取り除くと最大多重度が1下がるとき
(下図のような場合2番目、3番目の寿司を取り除くと最大多重度は2になる)
┓ ┏━━━━
┏━┓
┏━━━┓
┏━━┓
┏━━┓
2122121233111
この場合、多重度最大、最後尾に寄与する寿司を取り除いた状態における最大多重度、最後尾(例えば上の例で2番目の寿司を取り除くと、最高多重度、最後尾は多重度2、最後尾は10番目の位置となる)に寄与する寿司(上の例だと3番目の寿司)を最後に食べる解が存在する、その解にいま取り除いた寿司を最後にさらに食べる事にすれば良い >>65
ざっくりではこれでよく、ここかこれ以降の少しずらしたところが解だが
それを特定してるのが>>47か
簡単には終了位置がわからないが >>80はいまいちわかってないけど
終了位置にある寿司を取り除くというのはやってみた、かんがえてみたけど進展なし ┓ ┏━━━━ ‥①
┏━┓ ‥②
┏━━━┓ ‥③
┏━━┓ ‥④
┏┓ ‥⑤
┏━━┓ ‥⑥
2232121233111
②番目を取り除く
┓ ┏━━━━ ‥①
┏━━━┓ ‥③
┏━━┓ ‥④
┏┓ ‥⑤
┏━━┓ ‥⑥
2232121122111
⑤番目を取り除く
┓ ┏━━━━ ‥①
┏━━━┓ ‥③
┏━━┓ ‥④
┏━━┓ ‥⑥
2122121122111
③番目を取り除く ┓ ┏━━━━ ‥①
┏━━┓ ‥④
┏━━┓ ‥⑥
2122110011111
⑥番目を取り除く
┓ ┏━━━━ ‥①
┏━━┓ ‥④
1011110011111
④番目を取り除く
┓ ┏━━━━ ‥①
1000000011111
よって①④⑥③⑤②と食べれば3週目の10秒目で完食できる解が見つかる
これより早く完食する解はない >>84
それは>>73の解けるという証明?
しかし例外があるはずだが
123456789123456789 の答えは98のはずなのに
周回数の最大値の終わりを解答するプログラムでは90を返す その98は絶対正しいの?
全数検査かなんかで確認済み? VBA + Selenium + Chrome で自動ログインをツールを作っています。
Dim Driver As New Selenium.WebDriver
ログインした後にパスワードを保存しますか?
というダイアログが出て邪魔でしょうがないです。
それを削除する為に
credentials_enable_service false
profile.password_manager_enabled false
を使うのは分かったのですが、pythonやjavaのコードばかりブログに乗っていて
VBAの文法でどう書けば良いか分かりません。
詳しい方がいたら教えてください。 すまん
確かに98やな
ちょっと直せるか考えてみる 短縮したこれでも同じだな
これと同様に最後は末尾の3を引いて12ではなく、14が正解か
"123123" 123123を変形した
303303とか306300も答えは14のはず これはわかりやすいが
食べ終わりは2週目ラストではなく、
3週目の6がカウントする部分までだな
306300 まぁ今の問題が片付かないと次の問題出しにくいはあるから、こういう中々片付きそうもない話題が出てしまうと次が出てきにくくなる
もう寿司はやりたい人が各々考える事にして一旦保留でいいんじゃないかな しかし5年経っても話題がつきないお題と言うのはなかなか珍しいな 普通に次のネタ振ってそれが興味深けりゃそっちに移るでしょ
次のネタもない状態で保留にしろとか過疎らせようとしてるのか? しかし実際難しいやん
言ってる人のも怪しいしな
少なくとも数学科卒なら自分のアイデアちゃんと証明できないなんてことはないし、そうでないならできてないか、できたと勘違いしてるかもしれないし
答え出ない問題なんか数学の世界には死ぬほどあるしな たぶん寿司問題のレベルが高くて付いていけない人が多いんだと思う
俺も付いていけてないが別に保留しなくても良いと思う >>102
だって解ける気配なんかしないのに意味あるんかそれってレスばっかり連発してるやん >>103
寿司問題スレか難問専門スレが必要ってことかな 寿司問題、証明はできてないが正しいとおもえる予想はできた
与えられた寿司レーンで、すべての寿司に対して自身の皿を含めた訪問回数の総和配列を計算 >>73や>>65
たとえば、"220"ならば、「110」 + 「011」 → 「121」
この配列の値のどれか一つが異なるならば、その最大値とその末尾の位置を(m,i)とすると
答えは レーン長* (m-1) + i +1 >>73や>>65
配列の値がすべて一致するならば、各寿司の位置からそれを食べたときに最も2週目へ移動したものの先頭からズレを
上記の値に足したものが答え
たとえば、"053" の最長のズレは5を食べたときで3 難問でスレが消費されるならこっちのスレから難問スレに輸入していくって手もあるが
それだとこっちのスレが過疎るかな? >>105
後半部分(配列が全一致)のとき、2週目へ進む寿司が存在しないなら、足すものはゼロ >>105
アホの「正しいと思える予想」ほど無意味な物はないということがよく分かる
>>104
難問かどうかなんてわからんぞ
今まで簡単と判断されていた問題だって
計算オーダーを大きく減らせるかもしれないし 数学の天才が1週間で作ったコード
5年たっても誰も理解出来ない >>112
それも正しいかどうか嘘くさい
そもそも数学勉強してて数学で説明できないような奴の話し信用ならん 多分
>>72
> 一般での証明を解説するのは諦めたけど
> 具体例であればアルゴリズムと証明を書いて差し上げます
>
> 1周20秒以内で1問出してくださいな
コレ作った本人の談なんだろうけどコレは数学便所した人間なら事実上の「私できませんでした」宣言に等しい >>105 >>109 で完全解決したとおもうが
>>105の前半を最大重複度の末尾で終わらせる事(これで意味通じるとして)ということにしてこれが可能なことは分かる、しかもこれより短い終了もない
後半はその2週目にずれるその寿司を取り除くことで上の場合になる
その寿司を最後で食べない場合は、最後に食べる場合以上の時間がかかるはず
ここは証明しろといわれるとすぐできるかわからない >>121
自身へ戻ってくるのは対象外にしてた
それだと11と本質的に一緒だろうと
自己ループを数えるのをいれた
https://ideone.com/IyRWnd まぁもういいのかもしれない
大体この手の“最小値を出す関数を求めよ”系は本当にそれが最小値出してくれる事は“コード”ではなく“証明”が要求される
でもココ数学板じゃないし、それを面白いと思う奴ほとんどいないやろ
そもそもできんくさいし
じゃあ数学板に持っていったらもダメやろ
数学的に面白いのは「ちゃんと答えがある」問題でないとダメ、数学の世界なんか一見解けそうに見えて実は超難題で答え出せない問題なんか山ほどある
数学的才能ってその手の解けない問題をいつまでも解けない解けないってウンウン唸る事じゃなくて数ある解けない問題の中から“解ける奴”を嗅ぎ分けて解く能力やしな お題
座標リストと幅が渡されます
座標リストは線で結ばれるとしてその線に与えられた幅をつけた時の両側の線を作る座標リストを出力せよ
お題
座標リストが与えられます
それを文字列で描画せよ >>129
var 座標リスト = [[1, 1], [2, 2], [3, 3]]
console.log(`(${座標リスト.join`), (`})`) >>130
var 座標リスト = [[1, 1], [2, 2], [3, 3]]
console.log(`(${座標リスト.join`)─(`})`) >>131
これは想定外
これへの対応は終了位置の確定に関する部分ですぐにはできないな
現状、不完全プログラム >>11
なんで 313__ が8秒になるのか? 10秒ではないのか?
コンベアの状態と経過秒数を1秒づつ書くとこうなるよな?
コンベア 経過秒数 状態
313__ 0 3を取る
13___ 1 3を食事中
3___1 2 3を食事中
___13 3 3を食事中
__13_ 4 空なので取れない
_13__ 5 空なので取れない
13___ 6 1を取る
3____ 7 1を食べて3を取る
_____ 8 3を食事中
_____ 9 3を食事中
_____ 10 3を食事中 >>136
意味がわからない。少なくとも最初に手に取るのは1番左の3だろう。空ではない。 >>137
問題よんでたか?
寿司スルー、食べない=空も可能
> 目の前の皿を取るか取らないかを選ぶことができる。 >>11 C https://ideone.com/TRDGP8
https://ideone.com/uupLNI
寿司、正解に関係あるか分からんが、こうしてみるとデフラグのあれみたい
ということで、あらかじめ最後にとる皿だけ決めといて、ほかの皿を順番にとっていくという方法でやってみました。せっかくなのであげさせてください。証明は分かりませんorz >>139
あー。なるほど。3を取らないのもありか。 じゃあ取ったパターンと取らなかったパターンを再帰でやるのが良さそうってことかな。 >>140
2人目登場
なんでそれでいけると思った? >>143, >>145
あー確かに全然だめですね。バカですみません イヤでも実際できそうでできない
実はNPとかいうオチもあり得る イヤ、数学的に証明された理論に基づかないコード並べても答えにならない
コードは証明の代わりにはならない >>152
できんよ
多分できてる言ってるやつもできてないんだろ
つまり現時点で世界のどこにも寿司問題の証明は存在しない
よって現時点では証明不能、すなわちそもそも線形時間で解けるアルゴリズム自体存在しない可能性もある >>153
「多分できてる言ってるやつもできてないんだろ
つまり現時点で世界のどこにも寿司問題の証明は存在しない」
証明してください >>156
そんな義務はない
数学の世界で証明できたできないの問題がでたら常に証明できたと言ってる人間の側にしか責任は生じない
前の方にあったコードについてたメモ書きは証明として数学の世界で認められる類のものじゃない
おまえの言ってるのは数学板で名物になってる高木つていう糖質の言ってるのとおんなじだよ VBA+Seleniumで自動ログイン機能を実装しています。
ログインすると
「パスワードを保存しますか?」というダイアログが表示されてしまって困っています。
ネットで調べて以下の様なコードを記述していますが、出ます。
Dim Driver As New Selenium.WebDriver
Driver.AddArgument "credentials_enable_service=False"
Driver.AddArgument "profile.password_manager_enabled=False"
記述が間違っているのでしょうか? >>158
じゃあ証明できてないおまえはアホだな
他人に伝わる証明書くのは諦めたって言ってたよな? ・理解しようとする強い意志がある
・ある程度以上の頭がある
両方を満たす人ならわからない部分を説明しようとも思うが
全く理解しようという努力もなく頭も悪い人に対して証明するのは不可能 >>161
言い訳はいい
あんなもんただのメモ書き
もちろん数学の世界じゃ通用しないのもお前わかってるやろ?
そしてその場合証明したと言ってる側と証明できてないと言ってる側のどちらの主張が通るわかってるやろ
まぁそれがわかるレベルまでは勉強してないのかもしれんが お前の理論だと
「証明できてない」とただ単に主張するだけで
証明を無効化できるわけだ 少なくとも
いくら煽った所で
お前に何かしてやるつもりはないから 証明出来てないと言う奴は間違ってる箇所を示すなり反例出すなりしろよ >>166
知ってるよ
お前できないんだろ、本当は?
後でメモ書き見返してみたけど結局それみても証明できなかったんだろ?
お前が“証明できた”と思ったのが幻だったんだよ 証明は出来ている
教えないけど
これで満足?
お前に教える義務はないから >>167
きました
これなんですよ、これが数学の世界分かってない奴が必ず使ってくる反論
数学板でやったら袋叩きになるぞwww >>169
それは数学学んだ人間なら誰もがわかる“敗北宣言”ですな >>169
ここに数学界の未解決問題9個解いたって言ってる糖質のレスが並んでるよ
雑談はここに書け!【65】
https://rio2016.5ch.net/test/read.cgi/math/1662116299/
お前の言ってるのはコイツが言ってるのと同じだよ
わからないのはお前のせいwwwww
アホ〜wwwwww >>173
お前が絡んできたんやろが?
あほですか? >>175
大丈夫だよ>>172の糖質の発言見てみろよ
「誰も反証できないからオレの証明は正しい」の連発だよww
もちろんそんなはずもない
まぁこの糖質はその手の発言をオレが知ってるだけでも3年続けてるけどな
普通の知力ある人間はそんな論が立たないのはすぐわかる >>176
だからそんなはずもないならその理由を書けって話
そんなはずもないって連呼するだけならお前も同類だと気付けよw >>177
日本語大丈夫か?
そんなはずもないってのは「反証がないから証明が正しい」って主張が認められるはずないやろって意味だよ >>178
「反証が無いなら正しい」は間違ってるが反証が無いなら正しい可能性はあるだろ
反証もできないのに間違ってるとか言うのがおかしいと言う話である事すら理解できない知能なのか? >>180
「正しい可能性がある」など証明の代わりにならない
数学の世界には“証明された”、“反論が見つかった”、“証明されてない”の3つの状態がある
寿司問題は“証明されていない”
反証がないから“証明されている状態”であるなどと言えない
“証明できた”と主張できるのはある程度以上数学学んだ人間ならきちんと理解できるレベルの証明をあげた時のみ
あんなメモ書きでは証明とも、アウトラインであるとすら認めてもらえない >>181
> 「正しい可能性がある」など証明の代わりにならない
だれもそんなアホな事は言ってない
> 寿司問題は“証明されていない”
だから証明されてない(=否定もされてない)状態で証明出来てないと言うだけならなんの意味もないレスだろ
そんなレスして楽しいのか? >>182
証明できてない状態でしかないのに「証明はできてる、しかし書かない」とか言ってるやつがいるんだからしょうがない
自分1人のチラ裏ワールドで証明できたと思ってる分には好きにすればいい
しかしいかに便所の落書きでも「証明はできてる、信じてくれ」など通用しない >>183
まあ証明自体を書かないアホは無視するとしてメモ書きだからダメとか言ってないでどこがダメなのかを書けって話 >>184
メモ書きというのが証明のアウトラインと呼べるものならともかく、到底そんなレベルではない
たとえばSₙ₊₁の互換の生成元σ₁‥σₙによるreduced expressionを見つけるアルゴリズムの話とかだと
定理 g∈Sₙ₊₁に対してg(i)>g(i+1)である任意のiに対してgσᵢのreduced expression の長さがgのそれより真に1小さくなるものが存在する
とかがキーになる
そしてこれが証明できれば確かに線形時間で証明ができるのは数学ちょっと学んだ人間ならすぐわかる
前の方のレスで「最後の寿司で場合分け」といっていたけどそれでは指数時間になる、ミソは“g(i)>g(i+1)である任意のiに対して”言えてるのがミソで場合分けの必要がなく以下gσᵢのreduced expressionを求める問題に還元されるので線形時間とわかる
逆に言えばこの定理の証明のキーだけ書いてあれば“アウトライン”と呼べるし、オレはこの定理の勉強した時、“なるほどそうか、なら後は自分で挑戦!”と思ってやっていい練習になったのを覚えてる
そういうのが数学の世界でアウトラインと呼んでもらえるやつ
あのメモはそのレベルにない 長々書いてる割には結論は
> あのメモはそのレベルにない
かよw
お前のレベルがよくわかるわ >>186
ないやん?
まず他人に読ませる気なら数学の世界で一般的な用語の定義から入らんと読めない
少なくともひとつの主張の証明でもその用語を使った議論が有ればエスパーできなくはないが、あの文章にはそもそも証明と呼べるレベルの議論が何ひとつない、もちろん意味不明
なんかある性質を持ってる経路を探索するアルゴリズムらしいが、
「最短経路→その性質を持つ」の議論ゼロで以下その性質を持つ経路の探索アルゴリズムの話にはいつてる
アホかと 一般的でない用語の説明ね
まぁ論文レベルの文章読んだ事ないんやろ
読まなきゃ書き方わからんわな しつこいね、具体的な指摘を出来ない事はよくわかったからそろそろ黙ったら? >>189
具体的な不備の指摘ができないなら黙っとけと言うのがバカだと言ってるんだよ能無し君 もっと言うなら用語の説明がない、最小の解→なんとか言う性質持ってるの証明のアウトラインすらないというのは具体的ではないのかね?能無し君? >>190
> 具体的な不備の指摘ができないなら黙っとけと言うのがバカだと言ってるんだよ能無し君
ならいつまでもメモガーとか言ってりゃいいんじゃね?w
>>191
> もっと言うなら用語の説明がない
どの用語かも書かないで具体的とか言われてもね
そもそもここム板なのでアルゴリズムがおかしいならそれを指摘すべきで論文の書き方を指摘したいなら他所で吠えてなさい >>193
もう読み返してみるのもアホらしいから読み返さないけど数学の勉強多少なりともした人間が自分が使った用語のどれか数学の世界でなんの説明もしないでいいかわからない時点でもうダメダメなんだよ >>193
ちなみに別に煽って証明書かせようとしてるわけでもないよ
証明できました系トンデモ君なんか数学板にはアホほどいる
高木、日高、セタ
みんな反応同じ
お前も一緒 結局具体的指摘はできずにダメダメ言うだけの人でしたw >>196
高木そっくり
数学系トンデモ君は全部反応一緒 >>198
これもまぁ一緒
自分の数学力は相手には及ばないのがなんとなくわかった時の反応やな 簡潔明瞭なレス書かないで、ダラダラ雑談してる人は
プログラムや証明も似たようなもんだろう × 簡潔明瞭なレス書かないで
〇 簡潔明瞭なレス書けないので
典型例 ⇒ >>185 うちの研究室にもキチガイおじさんから未解決問題といたぞ!!とかいう長文封書が数年に一回来るわw
それを思い出したw 仮にあってたとしても証明が伝わらない、理解されないなら
インドの魔術師ラマヌジャンみたいなもの ”真に驚くべき証明を見つけたが、それを書くには余白が狭すぎる...” >>205
私は、本当に「驚くべき証明」が今でも未発掘であると妄想しているのです…ハノン ラマヌジャンでもフェルマーでもない
普通の人が1週間で考えたアルゴリズム
アルゴリズムの理解は難しくないし
理解すれば最小性の証明も簡単に思い付く
特別な事は何もない
自力でいろいろな問題を解けば
必然的にアルゴリズムが思い浮かぶ
っていうくらいの感覚 正六角形の各頂点に椅子がある
各椅子に P, Q, R, S, T, U と順不同でラベルを付けるとき
P と Q が向かい合わない組み合わせは何通りあるか
ラベルの重複は無し >>8
Java
static boolean odd(int n) {
return n % 2 == 1;
} >>208
Haskell
https://ideone.com/ciCXSG
fibs = 0 : 1 : zipWith ( + ) fibs ( tail fibs )
main = print $ take 100 $ fibs >>209
Haskell
https://ideone.com/7mv08x
import Data.List
import Data.Maybe
xs = [ x | x <- permutations [ 'P' .. 'U' ],
let i e es = fromJust $ elemIndex e es ,
mod ( ( i 'P' x ) - ( i 'Q' x ) ) 6 == 3 ]
main = print $ length xs >>209
何を区別するとかしないとか書かないと
数学やプログラミング以外の範疇でもめることになる ユークリッド平面上の六角形ですか?
そうでなければ向かい合う組み合わせがひとつもないかもしれない お題:アラレちゃんに出てくるウンコみたいなASCIIアートを数値処理で描画せよ
手段は問わない お題:C言語のfrexp()に相当する処理を、基数が10の場合について実装する。
(入力x>0を、
1≦y<10、nを整数として、
y*10^nに変換する。)
回答者の主観で、「素朴」と思われるやり方と、「技巧的」と思われるやり方の2つを実装し、
どこら辺が素朴/技巧的なのかを付記する事。 普通の倍精度程度の範囲なら
10^n そのまま持つのもあり
工夫しなくても精度が保てる >>222
Perl
ワンライナー。bashから実行。
自分では文字列変換しかしてなくて肝心な所は sprintf の %e にお任せ。
これは素朴なのか技巧的なのか分からない。手抜きであるとは言えるかも知れないが。
$ perl -ne '$s=sprintf("%e", $_); $s=~s/e([\+\-])?0*(\d+)/"*10^".($1eq"-"?"-":"").$2/e; print "$s\n"'
12345
1.234500*10^4
0.000000567
5.670000*10^-7
100000000000000000000
1.000000*10^20 sprintf() で %e で元の文字列を作る形式で良いならばCやJava(及びJavaと同じライブラリを使っているKotlin等)でも似たような書き方が可能。
e±NNN の部分の文字列変換を分かり易く書けるかどうかぐらいの違いしかない。 >>221
Kotlin script
println(String(Character.toChars(0x1f4a9))) お題
ループを使って次の文字列を出力してください
ABCDEDCBA
ABCD DCBA
ABC CBA
AB BA
A A >>230
拙いですが、一応できました。
s = "ABCDE"
l = len(s)
for i in range(l-1, -1, -1):
____if i == l-1:
________print(s[:4]+s[::-1])
____else:
________print(s[:i+1] + " " + s[i::-1]) >>230 Ruby
puts s = "ABCDEDCBA"
puts s while s.sub!(/E|. ./, ' ')
# =>
ABCD DCBA
ABC CBA
AB BA
A A >>233
出力コピペミス
# =>
ABCDEDCBA
ABCD DCBA
ABC CBA
AB BA
A A const char* str[] = {
"ABCDEDCBA\n",
"ABCD DCBA\n",
"ABC CBA\n",
"AB BA\n",
"A A\n"
};
for (auto s : str) printf(s); >>230
ChatGPTにお願いしたら↓のコードができた
for i in range(4):
print("A" * (4 - i) + "B" * (2 * i + 1) + "A" * (4 - i))
結果は間違ってた(笑 出題者の心を読むスレじゃないんだから
出題者は紛れを減らす努力をしろ 繰り返しってなに??!これでもいいいのぉ??!!!
アスペごっこに付き合ってる暇はないので >>239,243,245
なるほどこれが繰り返しか!
…暇そうだねwww お題:リンクの値を解決するsolve_path関数を作れ
第1引数にはブラウザのアドレスバーの今現在のURLが渡される
第2引数にはリンクの値(aタグのhref値)が渡される
返り値は解決したパス(文字列)とする
解決したパスはURLとして機能するように整形すること
つまり「http://xxxx.xxx/yyy/zzz」のようなURLにすること
絶対パス、相対パス、URLの直接指定に対応できるように作ること >>248
アスペごっこに付き合ってる暇はないので。 >>250
日本語も読めないでググってんのか?URL貼れなんて言ってないだろ、ごみ野郎 真面目にやろうとすればRFC参照してクソデカregexp作るだけだから誰もやる気にならないわな アルゴリズムのお題ばっかでつまらんからこういうのも好き お題: トマトの分類。
一個のトマトが画像フレームいっぱいに撮影された画像ファイルが入力として与えられる。画像全体の平均色を求め、それが赤っぽいならYesを、赤っぽくなければNoを出力せよ。 >>260
> 赤っぽいの定義は?
赤RGB(255, 0, 0)に近く、出荷に適したトマトの色とする。 sum=[0,0,0]
for(i=0;i<data.length;i++)
for(j=0;j<data[i].length;j++)
for(k=0;k<3;k++)
sum[k]+=data[i][j][k]
for(k=0;k<3;k++)
sum[k]/=data.length*data[0].length
rgb2hsv(sum).H 適正なトマトの色の範囲は、おそらくRGBやHSVなどの色空間上の範囲として表現するのが適切かも知れない。
それから全ピクセルの平均を求めるのは時間の掛かる処理に思える。 赤っぽいトマトの定義。
HSV色空間において、Hが-45度~+45度の範囲で、かつSが70%以上、かつVが50%以上(テキトーに決めてます)。しらんけど。 おいおい、そうじゃないだろ
アホな出題者を優良な出題者に育てる
それもお前らの仕事だぞ 処理時間とかいうなら動作環境と画像のフォーマットくらい示しとけよアホ 仕様作成のお題じゃなくて
プログラミングのお題なんだから
仕様はちゃんと紛れが無いように書いて
回答も用意しておけ どうせ仕様書いたところでやらないんだろうな
文句言いたいだけ
黙ってれば良いのに でも明らかに誰もやらない問題だろうなってのはあるじゃん >>247
Kotlin script
import java.net.*
println(java.net.URL(java.net.URL(args[0]), args[1])) お題: 在庫管理。
最初は在庫ゼロ。
何個か在庫変動の内容が一行ごとに入力される。
「商品「A」が3個入荷しました」
「商品「A」を2個消費しました」
「商品「B」を5個入荷しました」
。。。
最後に在庫状況を報告する。
「商品「A」が1個、商品「B」が5個あります」
在庫変動は、入荷か消費のどちらか。
商品名は任意の文字列。 お題: 感染者数の集計。
FAXで日本語の表として感染者のリストが某所から大量に送信されてくる。
それをOCRで読み取り、エクセルファイルにした後でPDFに変換した後、集計して印刷してFAXで報道機関に送信するプログラム。 #include <stdio.h>
int main(void)
{
int a, b, c;
int x, y, z;
printf("a = %zu\n",sizeof(unsigned short));
printf("b = %zu\n",sizeof(unsigned int));
printf("c = %zu\n",sizeof(unsigned long));
printf("x = %zu\n",sizeof(short));
printf("y = %zu\n",sizeof(int));
printf("z = %zu\n",sizeof(long));
if (a == x)
printf("等しい\n");
else
printf("等しくない\n");
if (b == y)
printf("等しい\n");
else
printf("等しくない\n");
if (c == z)
printf("等しい\n");
else
printf("等しくない\n");
return 0;
}
上記プログラムで実行結果がすべて「等しくない」で出力されるんですが、なぜなのかわかりません。等価演算子の使い方が間違っているのでしょうか? 282ですけど、原因がわかりました。直接sizeを比較してないからでした。
if (sizeof(unsigned short int) == sizeof(short))
とすれば比較になります。 >>282
a, b, c, x, y, z に何も代入しておらず全て不定値のままで比較をおこなっているため。
つまり「等しくない」0しか出力されなかった理由は偶然。たまたま自動変数がそのような結果になる値になっていただけ。 実行環境で、warning=警告 だらけになりますよね
初学者は、先ずそこを気にしないといけません 昔、ircで外人が質問してきた
c言語のエラーが取れないと
コンパイル結果を見たらwarningだらけだった
俺は「warningを取れ」と言ってやった
そいつは「それは大した問題じゃない」と言ってきた >>261
赤っぽいの定義=赤RGB(255, 0, 0)に近く、出荷に適したトマトの色 っておい! バカは出題禁止にしたいけど
バカは自分がバカな事がわからないんだよな ChatGPT
Q: 出荷に適したトマトの色をRGB値で教えて
A: トマトの色は、その種類や栽培方法、成熟度によって異なります。一般的に、完全に成熟したトマトは、赤い色をしています。ですから、RGB値としては、赤(R)が255、緑(G)が0、青(B)が0になると思われます。ただし、それは概略的な指針であり、実際の色は、異なる品種や栽培条件によって異なるかもしれません。
255,0,0が出荷に適したトマトだそうだぞ 具体的な仕様がない案件をやってみるのもプログラミングの冒険だと思うが。
緑がかったジャガイモ、芽の出たジャガイモを取り除くとか、不発のポップコーンを取り除くとか。 >>293
Kotlin script
println(java.util.UUID.randomUUID()) >>293
bash
uuidgen
正にそのままの名前のコマンドがあるのでそれを実行するだけ。 >>296
C++/Win32
https://ideone.com/WjFMbj
>>297
C++
#include <cstdio>
int main(void)
{
std::remove("蟻人間");
return 0;
} お題:
キーと値のリストがあります。
そのうちキーが0のものを除いてグループ化した結果を出力せよ。
ただし0のものについてもそれぞれの値をリストとすること。
[[0, "a"], [0, "b"], [0, "c"], [1, "d"], [2, "e"], [2, "f"], [3, "g"]]
→ [[0, ["a"]], [0, ["b"]], [0, ["c"]], [1, ["d"]], [2, ["e", "f"]], [3, ["g"]]] お題
数列が入力されます
最も大きな値をHighestに変換してください
最も小さな値をLowestに変換してください
最も大きくもなく最も小さくもない値をMiddleに変換してください
例
7
5.1
4.8
5.5
6.3
5.8
6.1
5.8
4.7
5.6
7.1
Middle
Middle
Middle
Middle
Middle
Middle
Middle
Middle
Lowest
Middle
Highest お題
数列が入力されます
連続する3つの数字(A, B, C)のうち
A <= B <= C
この条件を満たす(A, B, C)を出力してください
例
9.1
8.1
8.8
12.1
10.4
10.3
10.1
8.5
11.5
10.6
(8.1, 8.8, 12.1) >>299
Kotlin
ライブラリ使ってグループ分けしてから0のやつだけ一つづつに作り直しているのでやってることは >>302 のJavaのやつとほぼ同じだと思う。
入出力に凝った所が違うがそこは肝心な所ではない。
https://paiza.io/projects/XKaj8JlMZrlxh3J0bveRlg お題: グラフ理論において、あるグラフGの頂点が頂点番号の集合として、Gの辺が頂点番号の順序対の集合として与えられる。ケーニヒスベルクの橋の問題を解け。 よくわかんないなあ
調べるの面倒臭いなあ
俺はパスする int v[] = {1, 2, 3, 4, 5, 6, 7};
int p[][2] = {{1, 2}, {2, 3}, {1, 4}, {4, 5}, {2, 6}, {4, 6}, {3, 7}, {5, 7}, {6, 7}};
あとはまかせた
↓ 1/11 向け問題
[お題] 1位 + 11位 + 111位 + ...
整数 F, T が与えられる。F以上 T以下の異なる素数を 11個 選び和をとる。
全通りは、NCR(素数の個数, 11) 種類ある。
全通りを, 以下の優先順位で並べ、一意の順位をつけたと考える。
・優先1 和が多い順
・優先2 選んだ11素数を昇順に並べた辞書順
順位の数字が'1'のみであらわせる順位の和を合計し、出力する。
(1位, 11位, 111位, 1111位, ...と存在する順位まで)
制約) 0< F < T <= 4000 かつ T - F <= 1400
参考) この制約下で素数の最大個数は222個。最大順位は64bit整数におさまる
1) 2 39 --> 361
素数は12個あり、12C11で12通りある、1位は195で11位は166 合計して361
2) 123 231 --> 12600
素数20個 20C11 = 167960, [1位,11位, ... , 111111位] と6個分の和を加算
3) 1111 2222 --> ?
4) 2 1402 --> 243741
5) 2600 4000 --> ? なんか趣旨が理解出来なくてすべってる人が多いのな
プログラミングの観点から何か興味を引くようなお題じゃないとこの板じゃ反応ないと思うよ 一筆書き可能の判定法の有向グラフ版ってこと?
すべての頂点について、そこに向かう辺とそこから出る辺が共に偶数であるかどうかと同値かな >>313
与えられる情報が冗長だって言ってるわけだけど
そんなに難しい事を言ったつもりはなかった
>>308でいうとvは不要、pだけで良い
>>314
無向グラフと思う
連結性も必要 蟻の出題はただの思いつきでまともなお題になってないから時間をかける価値は無い ケーニヒスベルクの橋の問題だから無向と思ったが
確かに順序対と書いてある
真意は蟻しかわからない ダメだね
いや、これは偶数じゃないか
グルグル回るだけのものは奇数で成り立つな >>322
有向に決まってんだろjk
往生際が悪いぞ >>327
勘じゃなくてちゃんと考えてから書きなさい 連結
全ての点で入と出の差が1以下
入と出が同数じゃない点が2個以下 お前さんには言われたくなかったねぇ
問題文もよく読んでなかったし思い込みで入力扱いして不要な情報だとかなんだとかしていたわけだからね。 >全ての点で入と出の差が1以下
つまり次数が奇数の場合もありということか。
有向グラフになったらオイラーグラフの「全ての頂点の次数が偶数」よりも条件が緩くなるのかね。
そんなことあるかね
それとも準オイラーグラフも許されているのか?
ケーニヒスベルクの橋はオイラーグラフだからてっきりそれはないかと。 すまない、橋の問題はオイラーグラフではなく閉路と言いたかった。 あぁ、出題文の問題は一筆書きだけではなくて一筆書きで元の場所に戻るんだ 草
アイツほんと問題文読んでないんだね
ドヤ顔で指摘しちゃって恥ずかしいたらありゃしない ケーニヒスベルクの橋って閉路なのか
ただの知識問題でプログラミング全く関係ないけど (単独の点を除いて)連結
全ての点の出入りが同じ
>>331も
単独の点を除かなきゃいけなかった ああ、やっとわかった
>>313は>>311の意味を間違って解釈してたのか ( T_T)\(^-^ )ADHDって生きづらいよね 違うんだよなぁ。
>>313の意図は知らんけど俺が言ってるのは頂点リストをプログラムの入力にするとは明記されてないということ。
単に「グラフの頂点番号の順序対のリストを与える」と言ったときに頂点番号ってなんだ?とならないようにその説明として「頂点に番号を付けたもの」という文言をつけてるだけの可能性もあるだろうということ。
まぁ、分からないか 「AがBとして、CがDとして与えられる」
両方与えられるという文にみえる 「AはBとして、CはBのD」って意味じゃない?ってこと いや、BはAとしてCはBのDか
まぁどうでもいいけどね。 そそ、お前さんは先入観とそのレスに惑われてたってこと。 いやいや、まるで無駄な入力付けるなよって言ってるかのようじゃん…
まだあんまりわかってないかぁ
そもそも入力とは言ってないんだよね 【悲報】アスペクトガイジ、先入観でドヤ顔で指摘するも開き直る ケーニヒスベルクの橋の問題なんだから無向に決まってんだろ
これも1個の解釈 決まってないので指摘するのは間違いよ~
そもそも順序対に気付いていなかったのでそうだと思ってしまったのは仕方ないねぇ 効いてる♪
効いてる♪
効いてる♪
効いてる♪
イライラしちゃって♪顔真っ赤♪
(妖怪ウォッチのリズムで) お題: オブジェクト指向でお絵描きプログラム。
各図形は、描画に必要な座標などを保持する、オブジェクト指向に準じたクラスとして定義する。描画対象のキャンバスは画面、画像、テキスト文字列などを好きに選んでも構わない。
キャンバスでは長方形Rectangle、円Circleの2種類の図形をメモリーの許す限り複数個、追加ができ、また削除できる。色が指定できる場合は塗りつぶしは黄色とし、線の色は青色とする。線の太さは1ピクセル以上とする。
図形を描画する関数は多態性を持ったdraw関数とする。
各図形に図形の位置をずらすmove関数(平行移動)を追加せよ。
複数の図形をグループ化した図形GroupShapeを追加し、GroupShapeにもdraw関数、move関数を追加せよ。
サイズ80x25の空白キャンバスに対して以下の操作を行え。
1. 長方形(8, 10)~(10, 15)を追加。
2. 半径5の円(10, 10)を追加。
3. 1と2をグループ化して+(2, 7)だけmove関数でずらす。
4. キャンバスをdraw関数で描画する。 お題: 電子レンジのワット数に応じた時間計算
例えば500Wでしか暖められない電子レンジがあったとして、600W 2分30秒と書かれた弁当を温める場合に何分何秒にセットするのが良いかを計算して出す。
プログラムの入力はワット数、時間、変換ワット数のように引数で指定でも良いし標準入力から入力しても良いしその辺はご自由に。
出力は何分何秒になるかが分かるように出力されれば良い。 お題:画面左から右に放物線を描け
放物線の大きさは自由とする 解きたくなる問題っていわゆる競技プログラミング的な問題? 辺のリストとして順序のない頂点番号のペアのリストが与えられます
すべての頂点についてそこに接続される辺の数が偶数であるか判定するプログラムを記述せよ お題:2023と出力せよ
ただしソースコードに使う記号とアルファベットと数字の文字数は同じでなければならない >>366 js
console.info(+0b1_11111_00111+''+'')
consoleinfob
.(+__+''+'')
011111100111 >>365
digraph "koenigsberg" {
graph [rankdir=LR]
A [label="い"]
B [label="ろ"]
C [label="は"]
D [label="に"]
A -> B; A -> C; A -> D
C -> B; C -> B
C -> D; C -> D
}
屁が臭い >>366
C
https://paiza.io/projects/i1c5DPBXZ1G-wd1QHitTQA
記号、アルファベット、数字は全て45文字になっている。空白文字はカウントしていない。
まあでも、C言語だからこれでエラーなくコンパイルできたというだけだな。
(paiza.ioのCコンパイラは警告出しまくりではあるが)。
他の言語だと変数に文字列代入するとかコメント使うとかしないと文字数の調整が出来ないかも知れない。 >>361
Kotlin
https://paiza.io/projects/5CeeHK2CT8yX9ExfzW5N8A
実はこのお題を作ったのは俺だ。
計算そのものはとても簡単なのでこういう機能は電子レンジに内蔵して欲しいな。
ワット数一つでダイヤル式の安い電子レンジでもそういう目盛りを書いておいてくれれば出来る。 普通の知能を有した人間なら簡単に暗算出来るから必要ない
重度知能障害のガイジにはその機能すら使えない
つまり
極一部の軽度知能障害ガイジにだけ求められるニッチすぎる機能
そんなバカ向け機能搭載するくらいなら必要な温め時間を商品から読み取る機能を規格化して全(半)自動化すべきだろう 理屈があるのは分かるがまあ普段なら目分量的なイメージで適当に加減するわな
大体でいいんだし暗算っていうか計算すらしてないと思うが 電子レンジにQRコード読み取り部作って弁当のラベルのQRコードで自動的にあっため時間セットしてくれるとかなら便利かな? >>366
PowerShell
-bnot(-2024) >>366
PowerShellでもう1つ。9文字(各種3文字ずつ)に減らした。
0x7EA-(3) お題: エラトステネスのふるいによる素数計算。ただし、発見した素数は
一行ごとにテキストファイルに保存し、途中で中断したり、途中から再開できるようにせよ。 >>378 追記。
可能ならばマルチスレッドを使用し、効率良く計算せよ。 >>374
電子レンジの中のトレイの下の台って重さ測れるの? お題
4桁のダイヤルロックの全パターン(0000~9999)を試すときの
最小手数の手順を一つ構成せよ。一つの桁の数字を1だけずらすことを1手とする。
[出力例]
0000
0001
0002
…
0008
0009
0019
…
… >>374
それできると便利だね。レンジの庫内の上にカメラ付けておいて読ませれば弁当入れてスタートさせるだけで良くなる。 お題: マイドキュメントの中から「secret.txt」というファイルを探して、
見つかったら、そのフルパスと中身を出力するプログラム。 >>389
Linux/MacではHOME環境変数を使っちゃって下さい。
>>390
パチパチパンチやで。 >>392
Linux のコンサバなディストリは今はなにがお勧めですか、もうそろそろ Linux に乗り換えようかと >>393
一般のデスクトップ向けの無料Linuxなら、利用者と情報の多いUbuntuやXubuntuがいい。
工業製品向けとなるとAndroidとかPuppy Linuxかな。私はLinuxは専門外だけど。 WSL2, Ubuntu 20.04 か22.04。
まあ素人は、20.04が無難
VSCode の拡張機能・Remote Development(Remote WSL, Remote SSH, Remote Containers)
これで、WSL2, Docker Desktop も使える
多言語バージョンマネージャーは、日本人が作ったanyenv とか、asdf もある。
それか、Docker 純粋関数型言語触るかテスト駆動開発入門してセンス磨いてくれ お題
月、名前、金額が入力されます
月が2022-12〜2023-01の期間で
金額の合計が最も大きい人の名前と合計の金額を出力してください
2022-10 加藤 10
2022-12 柳沢 10000
2022-10 柳沢 26
2023-01 伊東 10
2022-12 柳沢 151288
2022-11 加藤 10000
2023-02 伊東 257900
2022-12 柳沢 12600
2022-10 伊東 12600
2023-01 伊東 70000
2022-11 加藤 40000
2023-01 伊東 150000
2022-11 加藤 60000
2022-12 柳沢 257900
2023-02 柳沢 40000
2022-11 加藤 26
2023-02 加藤 10000 >>397
Haskell
mport Data.List
makeReport ls = id
$ (\x -> ( minimum x, maximum x ))
$ map (\x -> ( sum $ map (read.(!!2)) x, (head x)!!1))
$ groupBy (\x y -> x!!1 == y!!1 )
$ filter ( \x -> head x >= "2022-12" && head x <= "2023-01" )
$ map words
$ ls
main = do
cont <- getContents
let ls = lines cont
print $ makeReport ls >>397
awk, sort, head
元データをコピペで odai_397.txt に入れておいて Linux で bash から以下を実行した。
awk '$1>="2022-12"&&$1<="2023-01"{t[$2]+=$3}END{for(i in t)print i,t[i]}' odai_397.txt | sort -k 2nr | head -1
結果はこう出た。
柳沢 431788 お題
顧客番号・商品番号・小計のCSV を、
商品番号が連番の場合には、その分だけ行数を増やし、
小計を等分割しろ(1円未満は切り捨て)
入力
1,1,100
2,1-3,200
3,1,500
3,2-3,400
出力
1,1,100
2,1,66
2,2,66
2,3,66
3,1,500
3,2,200
3,3,200
空白行に意味はない。見やすくしただけ >>401
Haskell
https://ideone.com/ESZHys
ただし入力はすべての行が
整数,整数,整数
または
整数,整数-整数,整数
のみの形と仮定、エラー処理やそれ以外の形式でが混じっている(空行など)が混じることは想定せず >>401
PowerShell (入力データはa.txtに保存されているものとし、形式は>>402と同じ)
cat a.txt |% {
$d = $_ -split ","
$r = @(iex ($d[1] -replace "-", ".."))
$r |% {$d[0], $_, [Math]::Floor($d[2] / $r.count) -join ","}
} >>397
Elixir で作った。これは、ややこしかった
{ :ok, input_data } = File.read( "input_data.csv" )
# IO.inspect input_data
# 末尾の改行を削除してから、1行ずつ処理する。空白で区切る。
# 2022-12 〜 2023-01 の期間内のデータだけに絞り込む。
# 名前でグルーピングしてから、金額を取り出す。
# 各人の金額を、数値に変換してから合計する。
# 合計が最も大きい人を求める
tuple = input_data
|> String.trim
|> String.split( "\n" )
|> Enum.map( fn( line ) -> String.split( line, " " ) end )
|> Enum.filter( fn [ head | _ ] -> "2022-12" <= head and head <= "2023-01" end )
# |> IO.inspect
|> Enum.group_by( fn [ _, name, _ ] -> name end, fn [ _, _, money ] -> money end )
# |> IO.inspect
|> Enum.map( fn { key, val } -> { key,
Enum.sum( Enum.map( val, &String.to_integer( &1 ) ) )
}
end )
# |> IO.inspect
|> Enum.max_by( &elem( &1, 1 ) )
# |> IO.inspect
{ name, money } = tuple
IO.puts "#{ name }, #{ money }"
#=> 柳沢, 431788 >>405
の続き。データの変遷
[
["2022-12", "柳沢", "10000"],
["2023-01", "伊東", "10"],
["2022-12", "柳沢", "151288"],
["2022-12", "柳沢", "12600"],
["2023-01", "伊東", "70000"],
["2023-01", "伊東", "150000"],
["2022-12", "柳沢", "257900"]
]
%{
"伊東" => ["10", "70000", "150000"],
"柳沢" => ["10000", "151288", "12600", "257900"]
}
[{"伊東", 220010}, {"柳沢", 431788}]
{"柳沢", 431788} >>397
C#
public static void Main(String[] args) {
var m = ReadLines()
.Select(x => {
var a = x.Split(" ");
return new { Month = a[0], Name = a[1], Money = int.Parse(a[2]) };
})
.Where(x => "2022-12".CompareTo(x.Month) <= 0 && x.Month.CompareTo("2023-01") <= 0)
.GroupBy(x => x.Name)
.Select(g => new { Name = g.Key, Total = g.Select(x => x.Money).Sum() })
.MaxBy(x => x.Total);
Console.WriteLine(m);
}
static IEnumerable<string> ReadLines() {
while (true) {
var line = Console.ReadLine();
if (line == null) {
yield break;
}
yield return line;
}
} お題:与えられた文字列が回文であるかどうかを判定するプログラムを作成してください。 (例: "racecar"は回文) >>408
Haskell
isPalindrome x = x == reverse x
main = do
print $ isPalindrome "DVD"
print $ isPalindrome "TOMATO"
print $ isPalindrome "しんぶんし"
------
True
False
True >>401
C#
public static void Main(String[] args) {
var xs = ReadLines()
.Select(x => {
var a = x.Split(",");
return new { UserId = a[0], ItemIdRange = a[1], Amount = int.Parse(a[2]) };
})
.SelectMany(x => {
var range = x.ItemIdRange.Split("-")
.Select(y => int.Parse(y))
.ToArray();
var from = range[0];
var to = range.Length == 1 ? from : range[1];
var count = to - from + 1;
var amount = x.Amount / count;
return Enumerable.Range(from, count)
.Select(id => new { UserId = x.UserId, ItemId = id, Amount = amount });
});
foreach (var x in xs) {
Console.WriteLine(x);
}
}
static IEnumerable<string> ReadLines() {
while (true) {
var line = Console.ReadLine();
if (line == null) {
yield break;
}
yield return line;
}
} >>408
C#
static bool IsPalindrome(string s) {
var i = -1;
var j = s.Length;
while (++i < --j) if (s[i] != s[j]) return false;
return true;
} お題: 漢字かな混じり文をひらがなにする。
「親子丼を食べたい。」→「おやこどんをたべたい。」
「チャーハン美味しい!」→「ちゃーはんおいしい!」
「電話に出んわ」→「でんわにでんわ」 そんなんライブラリ使えば簡単
ちなコードは書かない ChatGPTに聞いてみた。
プロンプト
漢字とひらがなを含む日本語の文をひらがなに変換するプログラムをPythonで書いて下さい。以下は入出力例です。
「親子丼を食べたい。」→「おやこどんをたべたい。」
「チャーハン美味しい!」→「ちゃーはんおいしい!」
「電話に出んわ」→「でんわにでんわ」
回答
Pythonでは、「janome」という形態素解析ライブラリを利用することで、文字列を形態素解析して単語に分割し、各単語の読みを取得することができます。以下は、janomeを使って入力された日本語の文をひらがなに変換するプログラムの例です。
from janome.tokenizer import Tokenizer
def kanji_to_hiragana(text):
t = Tokenizer()
tokens = t.tokenize(text)
result = ""
for token in tokens:
reading = token.reading
if reading is None:
result += token.surface
else:
result += reading
return result
text = "親子丼を食べたい。"
result = kanji_to_hiragana(text)
print(result) # おやこどんをたべたい。
text = "チャーハン美味しい!"
result = kanji_to_hiragana(text)
print(result) # ちゃーはんおいしい!
text = "電話に出んわ"
result = kanji_to_hiragana(text)
print(result) # でんわにでんわ
このプログラムでは、janomeのTokenizerクラスを使用して、入力されたテキストを形態素解析し、各単語の読みを取得します。単語の読みは、Tokenオブジェクトのreading属性に格納されており、これがひらがなであれば、そのまま結果に追加します。readingがNoneの場合は、漢字や記号などの場合であるため、Tokenオブジェクトのsurface属性をそのまま結果に追加します。最終的に、全ての単語を結合してひらがなに変換された文字列を返します。 お題: 入力されたYYYY-MM-DD形式の日付文字列について、その日付が営業日かどうか判定する。
「2023-02-10」→「営業日です」
「2023-02-11」→「営業日ではありません」
「2023-02-23」→「営業日ではありません」
「2023-03-19」→「営業日ではありません」
土日祝日は営業日ではないものとする。 祝日のうち、「春分の日」及び「秋分の日」は、法律で具体的に月日が明記されずに、それぞれ「春分日」、「秋分日」と定められています。
「春分の日」及び「秋分の日」については、国立天文台が、毎年2月に翌年の「春分の日」、「秋分の日」を官報で公表しています。詳しくは、国立天文台ホームページ「よくある質問」(質問3-1)を御参照ください。
こんなんどうすんの まともな国の政府なら、どっかのデータベースに休日祝日をまとめて公表してるんじゃないの?
じゃなければ、おま国 >>408
Kotlin
折角なので回文判定メソッドを String クラスに追加して判定するようにした。
でも複数文字で1文字扱いになるような場合にダメ(例えば半角カナで濁点や半濁点の文字が入る等)。
https://paiza.io/projects/Sa7SUvtirOLawuwjtMXpWQ >>415
haskell
https://ideone.com/VHHFhk
春分の日、秋分の日は内閣府のhpにも2023,2024しかない
しゃあないのでwikiにあった2299年までのデータベース利用
数式に起こせるかもしれないけどどのみち未来永劫使えるわけでもなし、そんな俺様公式使ってもしゃあないし
曜日の計算はツェラーの公式 お題: かな漢字混じり文を入力とし、それに含まれるHTMLの特殊文字をエスケープ処理し、さらに漢字にHTMLのルビを振ったHTML文字列を出力せよ。カタカナにはルビを振る必要はないものとする。
「親子丼を食べたい。」→「<ruby>親子丼<rt>おやこどん</rt></ruby>を<ruby>食<rt>た</rt></ruby>べたい。」
「チャーハン美味しい!」→「チャーハン<ruby>美味<rt>おい</rt></ruby>しい!」
「電話に出んわ」→「<ruby>電話<rt>でんわ</rt></ruby>に<ruby>出<rt>で</rt></ruby>んわ」 # 10進数128ビット浮動小数点数をIEEE754内部表現の2進数と16進数に変換する関数(python)
https://paiza.io/projects/DjBcWyn3v0D-xpwVQ7FrCg?language=java
上記のプログラムにはバグがあり、特定の値を変換できません。
どう直したら全ての128ビット浮動小数点数を網羅できるのかお考え下さい。 >>422
PowerShell (Microsoft Excelがインストールされている環境限定。例文に特殊文字はないのでエスケープ処理は省略)
Add-Type -AssemblyName Microsoft.VisualBasic
$Excel = New-Object -ComObject Excel.Application
foreach ($s in "親子丼を食べたい。", "チャーハン美味しい!", "電話に出んわ") {
$r = [Microsoft.VisualBasic.Strings]::StrConv($Excel.GetPhonetic($s), 32)
$p1 = $s -replace "[^\p{IsHiragana}\p{IsKatakana}\p{P}]+", "(.+)"
$p2 = [Microsoft.VisualBasic.Strings]::StrConv($p1, 32)
$t1 = [RegEx]::split($s, $p1)
$t2 = [RegEx]::split($r, $p2)
$t3 = [RegEx]::split($p1, "\(\.\+\)")
((0..($t1.count - 1) |% {"<ruby>$($t1[$_])<rt>$($t2[$_])</rt></ruby>$($t3[$_])"}) -join "") -replace "<ruby><rt></rt></ruby>", ""
} お題: 1番目、2番目、3番目など、いわゆる順序数は、英語で1st, 2nd, 3rdなどのように、アラビア数字と英字を混ぜて表記することがある。
入力された整数をこのような英語の順序数として出力せよ。 お題: 日本語の文が非文ではないことを判定する。
「私はご飯を食べました。」→「非文ではありません」
「投げたんばってんそうらんか。」→「非文の可能性があります」
「やなはまなはなあ。」→「非文の可能性があります」 お題: 英文の各単語の先頭の文字を大文字にせよ。
「The quick brown fox jumps over the lazy dog.」→「The Quick Brown Fox Jumps Over The Lazy Dog.」 >>429 js
(word) => word + 's' >>427 js
(today, x) => range(x).map((i) => {
while(!isBusiness(today + x)) today ++
return today
}) >>431 js
text.split(' ').map(([h, ...word}) => h.toUpperCase() + word).join(' ' ) >>432
複数形の規則はそんなに簡単じゃないんだ。
ごめんね。 >>436
https://english-club.jp/blog/english-noun-plural/
まず、英単語が加算名詞か非加算名詞か判定し、非加算名詞なら何も付けない。
さらにすでに複数形ならばそのまま。
sやshで終わる場合、esを付ける。
yで終わる場合、そのyを外してiesを付ける。
とか、いった規則があったはず。 >>437
(word) =>
isNotKasan(word)
? word
: word.endsWith('s') || word.endsWith('sh')
? word + 'es'
: word.endsWith('y')
? word.slice(0, -1) + 'ies'
: word + 's' fで終わる場合はfを外してvesをつける。
xで終わるときはesをつける。
またいくつかの単語には例外がある。
mouse→mice ts
(word: string) =>
蟻(word) ?? (
isNotKasan(word)
? word
: word.endsWith('s') || word.endsWith('sh')
? word + 'es'
: word.endsWith('y')
? word.slice(0, -1) + 'ies'
: word + 's')
type 未定義の処理結果 = string
declare function 蟻(word: string): 未定義の処理結果 | null; 仕様上げろや
仕様はそっちで調べて決めてくださいとか誰もやらん 蟻人間は元々適当なことしか書いてないから相手にしない方がいい >>408
Python
s = input()
print(s == s[::-1]) >>445
date コマンド
bash から実行した時の例。
$ date '+%T です。'
02:56:11 です。 音声を出したい場合はこのテキストを読み上げソフトで読み上げさせたり自分で声に出して読んだりしてください。 >>445
間違えた。日時だったね。こうだ。
$ date '+%Y/%m/%d %T です。'
2023/02/23 02:58:40 です。 【キッシンジャー】 ワクチンを強制し群れを減らす
://rio2016.5ch.net/test/read.cgi/lifesaloon/1662167492/l50
>>401
Elixir で作った
{ :ok, input_data } = File.read( "input_data.csv" )
# IO.inspect input_data
# 末尾の改行を削除してから、1行ずつ処理する。カンマで区切る
input_data
|> String.trim
|> String.split( "\n" )
|> Enum.map( fn( line ) -> String.split( line, "," ) end )
|> Enum.each( fn [ custom_num, seq_num, money ] ->
{ from, to } = case String.split( seq_num, "-" ) do
# - を含まない時は、2つに分割できない
[ first ] -> num = String.to_integer( first )
{ num, num }
# - を含む時は、2つに分割できる
[ first, last ] -> { String.to_integer( first ), String.to_integer( last ) }
end
for n <- from..to, do: IO.puts "#{ custom_num },#{ n },#{ div( String.to_integer( money ), to - from + 1 ) }"
end )
# |> IO.inspect >>445
たまには回答側に回ってみなさい
お題
個人の名前,上司の名前,個人の仕事力
が入力されます
個人の仕事力とその上司たちの仕事力を合計した値を出力してください
入力
ガンド部長,ブリ事業部長,9000
モジャコ,ヤズ係長,39000
ワラサ部長,ブリ事業部長,46000
メジロ部長,ブリ事業部長,34000
ブリ事業部長,,32000
ツバイソ,コズクラ係長,24000
ツバス係長,ハマチ課長,23000
ワカナ,ツバス係長,4000
イナダ課長,ワラサ部長,5000
ヤズ係長,ハマチ課長,23000
ワカナゴ係長,イナダ課長,49000
フクラギ課長,ガンド部長,17000
ハマチ課長,メジロ部長,19000
コズクラ係長,フクラギ課長,31000
出力
41000 : ガンド部長 -> ブリ事業部長
147000 : モジャコ -> ヤズ係長 -> ハマチ課長 -> メジロ部長 -> ブリ事業部長
78000 : ワラサ部長 -> ブリ事業部長
-----省略----- >>456
仕様がわからん
A→B
というpathは各A,B毎に一意もしくはないのどちらかと仮定して良いの?
A,,x
という入力はどうするの
A,B,x
B,,y
B,C,z
はどうなるの? >>456
仕事力の算出方法を示してないガイジ
名前を考えるのに精一杯だったか? >>458
同じ人に複数パターンの上司ってどういうこと? おかしいよな?
しかし
1:ガンド部長,ブリ事業部長,9000
2;ブリ事業部長,,32000
からの出力が
41000 : ガンド部長 -> ブリ事業部長
なら2の行があれば32000を一回足すって事だとしか思えないけど完全に意味不明 やっとわかった
A,B,n
は
社員、直属の上司、仕事力
で例外的に部長は直属の上司なしで
A,,n
と記載されている
求められる仕様は全てのAとその上司Bに対してAの直属の上司、その直属の上司、‥でBに至る社員を全てリストアップしてその仕事力の総和を表示せよ
かね
もういいや まだ間違ってんの?
ならもういいや
仮にまだ間違ってるとして何その言い方?
何様?
そんな空気しか出せないんなら消えろやカス ID:Kkq1C7fSがあれから一回も書き込んでないあたり、何も考えずにお題出したんでしょ お題:N×Nの正方形Aがある。各頂点から点a,b,c,dを正方形の内側のランダムな方向に射出する。点が内側をバウンドし移動してるあいだAの中心点からM×Mの正方形B(最初は点)が徐々に拡大していく。この時、Bの内側に点a,b,c,dが収まるのはMがいくつの時か計算しなさい。 Mの拡大率も書いてないし射出した点の速さも書かれてない
仕様が不十分
ROMってね 指摘するだけで書かない奴な
不足してるなら勝手に補完つくればいいものを
仕事じゃあるまいし 勝手に補完するも何も、そのお題は何を言わんとしているのか全く分からないため補完のしようがない。 俺なんか厳密中が言うからわざわざbnfまで書いたぞ笑
もうあんなつかれるお題出したくないわ 一日経っても反論ないあたり出題者は逃げたってことでいいのかな 整数をランダムに4個選ぶ
4個の整数の和はいくつか?
こんな感じ
お題になってない 蟻は出題がまともに出来てないって自覚がないアホだから
関わっちゃダメ 不足してるなら補ってお題として成立されてばいいものを最近の輩はリジェクトすることしか眼中にない
上のお題で言えば速度はプログラムで任意に定義できるようにすればお題として成立されられる
その方向へ持っていこうという気概を見せられないなら黙っていれば良い。 お題をみんなで作るスレ
じゃないんだから
完成してから出題しろ お題:
>>471からランダム性を抜いて再現性のあるお題に再構築せよ >>49
うん?乱数で値を決定することを任意性というのか?
知らんかったな >乱数で値を決定する
厳密厨ってこの程度の読解力だったのな 蟻と蟻の自演(単発)が消えれば
このスレももう少しマシになると思う >>496
余計な書き込みはいらんから
お前の解釈を書け >>486
あれっ?
デカい口叩いてたクセに何もしないの?お前 「あれっ?」
じゃなくて
「ありっ?」
って書くべきでしたすいません >>486
元のお題が何を言わんとしているのか分からないので何をどう補ったら良いのかも分からない。
見たこともない文字で書かれた未知の言語に対して補って読めるようにしろと言われても出来ないのと同じようなものだ。 頭が良い人なら多くの人に理解できるようにお題を書くことも可能な筈だ。 なぜ仕事でもないのに厳密性を求めるのか
本当にプログラムを書きたいという意欲があるならそれらしく補完して作ればいいものを。 昔はこのスレは変なお題はみんなスルーしてレスもつかなかったよな お題
製品タイプ、製品ID、製品色
が入力されます
製品タイプの配列、製品IDの配列、製品色の配列をJSON形式で出力してください
製品タイプの配列の1番目の値は製品IDの配列の1番目と対応する、というように
それぞれの配列の順番は一致するようにしてください
1つの配列の中で製品タイプは重複してはいけません
出力するJSONの数が最小になるようにしてください
入力例
B,02,B
C,04,Y
F,15,R
E,12,C
C,06,G
D,07,B
D,08,B
D,10,M
C,05,C
F,14,G
A,01,Y
D,09,B
B,03,C
G,16,M
E,11,Y
E,13,B
出力例
{"製品タイプ":["A","B","C","D","E","F","G"],"製品ID":["01","02","04","07","12","15","16"],"製品色":["Y","B","Y","B","C","R","M"]}
{"製品タイプ":["B","C","D","E","F"],"製品ID":["03","06","08","11","14"],"製品色":["C","G","B","Y","G"]}
{"製品タイプ":["C","D","E"],"製品ID":["05","10","13"],"製品色":["C","M","B"]}
{"製品タイプ":["D"],"製品ID":["09"],"製品色":["B"]} 友人がブログを削除したんですが、そのあと、そのURLをクリックすると
アダルトサイトに飛ぶようになりました。本人はずかしいはずです。
これは何が原因なんでしょうか? こんなところで聞く方が無駄だとわかりました。すいません 答えを聞き出す前に暴言はいて逃亡するのは三流
答えを聞き出してから態度を豹変させるのが一流 >>456
Elixir で再帰で書いた。
末尾再帰になっているかどうかは分からないけど。難しかった
https://paiza.io/projects/2HEEsPP7gqa7Yoq2U1darw?language=elixir
以下は、データの変遷
input_list は、[ ["ガンド部長", "ブリ事業部長", "9000"], ["モジャコ", "ヤズ係長", "39000"] ]
input_map は順不同で、%{ "イナダ課長" => {"ワラサ部長", 5000}, "ガンド部長" => {"ブリ事業部長", 9000} }
蓄積変数は、[ {["", "ブリ事業部長", "ガンド部長"], 41000},
{["", "ブリ事業部長", "メジロ部長", "ハマチ課長", "ヤズ係長", "モジャコ"], 147000} ]
出力はリストを逆順にして、
41000 : ガンド部長 -> ブリ事業部長
147000 : モジャコ -> ヤズ係長 -> ハマチ課長 -> メジロ部長 -> ブリ事業部長 >>456
awkで書いてみた
https://ideone.com/Ufy2b4
再帰呼び出ししてみた。
表示順を考えなくて良いならmember[]は要らなくなるので
BEGIN{}も要らないし、もう一段簡単になる。 お題
個人の名前,上司の名前,個人の仕事力
が入力されます
個人の仕事力とその部下たちの仕事力を合計した値を出力してください
ブリ事業部長は全員の仕事力の合計になります
入力
ガンド部長,ブリ事業部長,9000
モジャコ,ヤズ係長,39000
ワラサ部長,ブリ事業部長,46000
メジロ部長,ブリ事業部長,34000
ブリ事業部長,,32000
ツバイソ,コズクラ係長,24000
ツバス係長,ハマチ課長,23000
ワカナ,ツバス係長,4000
イナダ課長,ワラサ部長,5000
ヤズ係長,ハマチ課長,23000
ワカナゴ係長,イナダ課長,49000
フクラギ課長,ガンド部長,17000
ハマチ課長,メジロ部長,19000
コズクラ係長,フクラギ課長,31000
出力
ガンド部長:81000
モジャコ:39000
ワラサ部長:100000
-----省略----- お題:数字が入力されるので日付かどうか判定してください
in < 20230306
out > true
in < 20232250
out > false >>524
ChatGPTに聞いたら瞬殺だった。
@Python
import datetime
def is_valid_date(date_string):
try:
datetime.datetime.strptime(date_string, '%Y%m%d')
return True
except ValueError:
return False >>524
haskell
https://ideone.com/1oSNqd
“数値が読めない”とかは無視
純粋にy/m/dがグレゴリオ歴として成立するかどうかの判定
wikiに載ってたy/m/dから修正ユリウス通日を計算する公式を使ってその月の長さを(次の月の初日のユリウス通日)-(その月の初日のユリウス通日)で算出 お題:引数の絶対値を1-2-5シリーズ(1, 2, 5と、その10の整数べき乗の集合
(..., 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, ...)に切り捨てる関数。
IEEE754で正確に表現出来ない数(0.2とか)になる場合、最も近い値を返す事。
(例 : 0.2の場合は0x1.999999999999ap-3
その場合でも、(切り捨てなので)引数の絶対値を超えてはならない)
f(1) → 1
f(1.1) → 1
f(1.9) → 1
f(2) → 2
f(2.1) → 2
f(4.9) → 2
f(5) → 5
f(5.1) → 5
f(9.9) → 5
f(10) → 10
f(10.1) → 10
発展的なお題:
引数の絶対値が5e-308未満の場合の望ましいと思われる振る舞いについて述べよ
(「思われる」なので正解はありません)。 >>531
俺も最初はそうやって parse() 使ってやるやつを作ったんだけど、それだと 20230229 や 20231131 が true になる。
どうやら parse() でやろうとすると年月日それぞれの値のチェックはするが年月日の値を繋げた状態で日付として
正しいかのチェックがされない。日に関して1~31なら全てOKになってしまってそれが何月なのかのチェックがされない。
それで文字列を分解して整数にしてから LocalDate.of(y, m, d) のやり方でやるようにしたんだよ。それだとチェックされるので。 >>523
親 : 子 = 1 : 多
多分木の走査か。
プログラミング・コンテストの基本だけど、自作するのは難しい >>533
0.2に一番近い値が0.2より小さい場合
この値の入力に対して
0.2に一番近い値を返せばいいのか
0.1に一番近い値を返せばいいのか
どっち? 例えばIEEE754の倍精度だと10^23に一番近い値は2個存在するけど
それぞれの入力値に対して何を返す? >>533
log₂5が無理数なので集合
{ 2ᵐ5ⁿ | 2ᵐ5ⁿ ≦ a }
は最大値を持たない、すなわち“切り捨て=下界の最大値”が一般には存在しない >>543
2^m 5^n じゃなくて [1,2,5] x 10^n >>533
Haskell
https://ideone.com/QDxKsx
負の数とかは無視
f(x) = max { a×10ⁿ | a∈{1,2,5}, n∈ℤ, a×10ⁿ≦x }
を出力 f(x) = max { 近似(a×10ⁿ) | a∈{1,2,5}, n∈ℤ, 近似(a×10ⁿ)≦x }
お題はこれなんだよね >>546
f(10^23) = 10^23
f(9.999999999999999e22) = 5e22
でいいの? とりあえず>>548の解釈でhaskell
https://ideone.com/KMyKL4
入力を普通に受け渡しすると
f(10^23) = 10^23
f(9.999999999999999e22) = 5e22
は実現できるはずないので引数は文字列で渡す
文字列は0〜9, e,.のみ処理
パーサーやん このすいや、違うって、出力側の問題ではなく入力側
出力側は出力が1.0e_、2.0e_、5.9e_の形に限られるため、打ち切り誤差でに4.9999..e23とか9.999...e12とか出力されてもそれぞれ5e23、1e13の打ち切り誤差と判断できるけど、入力側では不可能、つまりそもそも1e23を入力するには文字列がなんかで入力受け取るとか、significantとexponentを整数値で受け取る形式にするとかしないとそもそも入力を受けられないけどそこはどうすんの?つて話 あれ?なんか日本語変換メチャクチャになってる
言いたい事わかる?
1e23なんてそもそも例えばhaskellのDouble型だと受け取れないんだよ もう一回落ち着いて >>536 >>537 を読んでみようか >>553
何がおかしい?
例えば
10^23の結果が10^23にならない
と指摘してたけどこれは違う
コードはちゃんと
f(9.999999999999999e22) = 5e22
を算出してる
しかし>>545のコードでコードの使用者が
a = fl125 $ 10^23
とやってもaには1e23ではなく5e22が返ってきてしまう
しかしそれはfl125がうまく機能していないのではなくhaskellの使用上標準の値受け渡しでは9.999999999999999e22と1e23を区別して渡す方法がないんだよ
かと言って
「9.999999999999999e22が引数で来る事はないな、きっとこれは1e23が精度の限界で誤って渡されてるんだ、引数は1e23とみなして答え返そう」
とかあり得んやろ?
わかる? お題:スレのHTMLが入力されるのでもっともレスが付いているレス番号を表示しなさい
複数同率の場合は複数表示しなさい >>542
そんなやり方があったとは気付かなかった。 >>533
kotlin
出力がちょっと違うけど値としては合っている。
まあしかし BigDecimal 使って文字列で処理しちゃってて桁数大きくてもドーンと来いみたいになっててつまりほぼ手抜き。
https://paiza.io/projects/bgGSIZ8CEEFszHzDBQqD8g こっそり負の値に対応するプログラムに修正しておいた。 だめだ。 -0.9 や 0.9 みたいなのがうまく行かない。後で時間があったら考えよう。 >>557
jQuery なら、
selector = 'div.thread > div.post > div.message > span > a.reply_link'
$( selector ).each( function( index, elem ) {
console.log( index + ': '+ $( elem ).text( ) );
} );
リンクは、こういう >>1
だけじゃなく、範囲もあるのをどうするのか?
998-
-2
1-2 >>533
Kotlin
BigDecimal (及び BigInteger)は使うが文字列を使うのは止めて色々計算して何とかするようにした。
https://paiza.io/projects/6H3b_gf_Kc3RCT6_S_HISw >>557のお題を勝手に改造
お題:5chのスレのURLが入力されるので内容を取得してもっともレスが付いているレス番号から順に出力しなさい
複数同率の場合は複数表示しなさい
回答例
Kotlin
https://paiza.io/projects/CICvfqwT52X4FsmIwxb_Zw
出力はURLと「レス数: レス番号, ...」になる。
要するに、>>557作っている内に最大のやつ一つ出すだけなのも勿体ないなと思って改造して出来上がったが元のお題とちょっと違うのでお題も勝手に改造した。 >>557
については、
>>564
にも書いたけど、リンクの定義が分からない
>>1
みたいに、単独の数字だけとするのか?
998-
-2
1-2
みたいな範囲指定も含むのか? >>509
Ruby で、
require 'csv'
require 'json'
# 製品タイプの出現回数を数える。初期値は0
prod_type_count = Hash.new( 0 )
# 1行ずつ処理する。Array.new( 1 ) で先頭要素に、nil が入る。
# 蓄積変数・ary のインデックスと、出現回数を同じにする。
# 例えば、ary[ 2 ] には、2つ目のB やC などが入る
result_ary = CSV.foreach( "input.csv" ).
each_with_object( Array.new( 1 ) ) do |row, ary|
plus_1 = prod_type_count[ row[ 0 ] ] + 1
prod_type_count[ row[ 0 ] ] = plus_1
if ary[ plus_1 ] # 存在する
ary[ plus_1 ].push row
else # 存在しない
ary[ plus_1 ] = [ row ]
end
end
# p prod_type_count
#=> { "B"=>2, "C"=>3, "F"=>2, "E"=>3, "D"=>4, "A"=>1, "G"=>1 }
次へ続く result_ary.shift # 先頭要素のnil を削除する
res = result_ary.each_with_object( [ ] ) do |outer_ary, accum|
outer_ary.sort_by! { |inner_ary| inner_ary[ 0 ] } # 製品タイプでソートする
transposed_ary = outer_ary.transpose # 2次元配列を転置する
accum.push ( { "製品タイプ" => transposed_ary[ 0 ],
"製品ID" => transposed_ary[ 1 ],
"製品色" => transposed_ary[ 2 ] } )
end
puts JSON.dump( res ) # 文字列化
# p result_ary
=begin
ソート後のデータ
[ [["A", "01", "Y"], ["B", "02", "B"], ["C", "04", "Y"], ["D", "07", "B"], ["E", "12", "C"], ["F", "15", "R"], ["G", "16", "M"]],
[["B", "03", "C"], ["C", "06", "G"], ["D", "08", "B"], ["E", "11", "Y"], ["F", "14", "G"]],
[["C", "05", "C"], ["D", "10", "M"], ["E", "13", "B"]],
[["D", "09", "B"]] ]
=end >>557
Kotlin
>>567を更に改造して>>568の言うような >>xxx-xxx とかも可能にした。
実際に受け付けるのは「>>」の後が「数」または「数-数」で複数ある場合はカンマ区切り。
https://paiza.io/projects/CDH-JDZD12laCkRrON4Q2A マッチ棒パズルソルバ
0123456789+-=×/からなる文字列が与えられる
この文字列にC変換1回、またはA変換とB変換を一回ずつ行って得られる文字列のうち数式として成立するものを列挙せよ
https://youtu.be/2sqvh8KBdQk
例
6 = 3 + 3 - 8 → 6 = 3 + 3 = 6
7 = 6 + 5 → 11 = 6 + 5
2 = 3 + 0 → 3 = 3 + 0, 2 = 2 + 0
6 = 9 - 3 → 5 = 8 - 3
A変換(逆変換がB変換)
6 → 5
8 → 0, 6, 9
9 → 3, 5
= → -
× → /
C変換
0 → 6,9
2 → 3
3 → 2,5
4 → 7,11
5 → 3
6 → 0
7 → 4,11
9 → 0
11 → 4,7 他にも色々と抜けっぽいのが
B変換 : A変換の逆変換
C変換 : B変換=>A変換 (元に戻るのは除く)
だから
A変換だけ(またはB変換だけ)ちゃんと考えて定義すれば良いよ
「数式が成り立つ」もちゃんと定義しないと
"1+1=2" "1+1" "1"
どこまで含む? >>573
"+"→"-"も抜けてたし"-"→"/"とかも抜けてた
あとB変換として「先頭が0〜9のとき先頭に-をつける」もある
これは各文字だけ見ればいい変換ではないらかややこしい
>>574
まぁ()ないから普通に
まともに定義書くとうるさいだけだと思うので
ちなみに当方まだ模範解答作れてません 要するにマッチ棒使って数字と四則演算記号と = 記号を表現した時に1本動かして、最低でも一つは = 記号がある状態で式が成立すれば良いんだよね? >>572
Kotlin
https://paiza.io/projects/mlep0Qk1tQhwMlC1r6awRw
式が成立するかの判定ではパターンマッチング使ってやっているので多分ちゃんと出来ないこともあるんじゃないかと思うが、多分だいたいは大丈夫。
式の計算は括弧を使った入れ子がないので再帰は使ってない。掛け算と割り算を優先してるだけ。 >>523
Elixir で再帰で書いた。多分木の走査か。
末尾再帰になっているかどうかは分からないけど。
>>456 よりも、さらに難しかった
https://paiza.io/projects/oeDtiQEX0oQtWQT7SMKwLA?language=elixir
以下は、データの変遷
input_list は、[ ["ガンド部長", "ブリ事業部長", "9000"], ["モジャコ", "ヤズ係長", "39000"] ]
input_map は順不同で、%{ "イナダ課長" => {"ワラサ部長", 5000}, "ガンド部長" => {"ブリ事業部長", 9000} }
boss_subordinates_map は、%{ "ツバス係長" => ["ワカナ"], "ハマチ課長" => ["ヤズ係長", "ツバス係長"] }
total_power は、[ {"ガンド部長", 81000}, {"モジャコ", 39000} ]
出力
ガンド部長 : 81000
モジャコ : 39000 お題 板違い
数学板に貼られてた問題
こっちでしょ
298 132人目の素数さん[] 2023/03/30(木) 16:50:53.60 ID:FIHeBSy3
66,203,335,759,2227,3663,7249,80,252,420,882,2770,4618,9126
の数字の和を使って22999をピッタリ作りたい
この時、解は存在するか。
数字は重複して何度でも使用して良いが、使う回数は少なければ少ないほど良い。
18-(使用した数字の合計個数)をこの問題の得点とする
という問題誰かといてください! 4618+3663+3663+3663+3663+3663+66 お題 nか2n
長さがn+1, 総和が3nの正の整数の列が入力されます
その連続する部分列で総和がnまたは2nであるものを見つけ、その先頭と最後のindexの組み(indexは1〜n+1とする)を返す関数を作ってください
存在しない時は(-1,-1)を返して下さい
備考 総当たりでも列の長さnに対して計算量はn²オーダーですが、線形オーダーの解があります(四則演算等をO(1)として)
例
[4,1,2,3,3,2]
(3,4)
[3,2,1,3,2,3,4,3,1,4,4]
(6,8)
[3,9,1,1,1,2,5,4,3,5,4,2,1,10,3,4,2,7,1,5,1,2,3,3,1,1,1,1,3,1,2,4,1,1,2,2,11,2,1,4,7,4,6,1,7,1,4,2,1,5,2,5,6,1,5,2,1,1,5,1,1,1,1,5,1,1,3,2,9,6,1,3,4,11,1,1,4,1,2,6,1,2,1,1,3,1,1,1,1,1,2,7,6,2,1,3,9,1,1,2,2]
(36,67) 2^(2^(2^(2^(2^(2^2)))))
を10進数で先頭から100桁を出力する方法は? お題
4つの数字a,b,c,dが複数個入力されます
入力
0, 1, 1, 1
0, 0, 0, 0
1, 0, 0, 1
1, 0, 1, 0
0, 0, 0, 1
0, 0, 1, 1
1, 1, 1, 0
1, 0, 0, 0
1, 1, 1, 1
0, 1, 1, 0
1, 1, 0, 0
1, 0, 1, 1
0, 1, 0, 1
1, 1, 0, 1
0, 0, 1, 0
0, 1, 0, 0
次の条件でソートして出力してください
dの昇順
, bの降順
, cの昇順
, aの降順
出力
1, 1, 0, 0
0, 1, 0, 0
1, 1, 1, 0
0, 1, 1, 0
1, 0, 0, 0
0, 0, 0, 0
1, 0, 1, 0
0, 0, 1, 0
1, 1, 0, 1
0, 1, 0, 1
1, 1, 1, 1
0, 1, 1, 1
1, 0, 0, 1
0, 0, 0, 1
1, 0, 1, 1
0, 0, 1, 1 お題 何通り?
黒玉 b 個、赤玉 r 個、白玉 w 個が入ってる袋の中から玉を一個ずつ取り出し、取り出した玉を順に横一列に b+r+w 個すべて並べる。
どの黒玉同士も隣り合わず、どの赤玉同士も隣り合わない数を求めよ
例
( b, r, w ) = ( 1,2,2)
→ 18
( b, r, w ) = ( 1,2,3 )
→ 40
( b, r, w ) = ( 3,4,5 )
→ 4326
( b, r, w ) = ( 12,34,56 )
→ 138961718287080638152811314224672
( b, r, w ) = ( 1, 2, 2 )の場合の18通り
["BRWRW","BRWWR","BWRWR","RBRWW","RBWRW","RBWWR","RWBRW","RWBWR","RWRBW","RWRWB","RWWBR","RWWRB","WBRWR","WRBRW","WRBWR","WRWBR","WRWRB","WWRBR"] >>595
Kotlin
これは馬鹿正直に並べ替えてるだけなので多くなると結果が中々出ないだけでなくメモリが足りなくなって終わるかも知れない。
https://paiza.io/projects/GIJzZldH4F366cas93uAzg この問題よくある「受験問題計算機で解こう」です
元ネタは今年の東大理系[2]が(b,r,w) = (3,4,5)の場合、もちろん元の問題は「手計算で解け」
https://youtu.be/KAJpzptO5Ws
なのでうまく立式すると(b,r,w) = (3,4,5)程度なら手計算でも解けます、計算機ならこの程度なら全数でも27720通りのうちの4326通りなのでいけます
( b, r, w ) = ( 12,34,56 )あたりだと総当たりするのは難しくなります
ちなみにn = b+r+wについて計算量がO(n²⁺ᵉ)のオーダーの解があります
というか普通に動画のように解いた時の一番素直な解法がO(n²⁺ᵉ)オーダーになります
もっと早いのあるかもしれませんけど 全然違うアプローチで解いた
乗算やCombinationの計算オーダーをどう考えてるか知らないけど、
シンプルな2重ループの中身がCombination、2のn乗、乗算、加減算だけだから、
Combinationを毎回単純に計算してもO(n^4 log(n))
工夫すればO(n^3 log(n))になる 動画の方法の計算量は高々O(n²⁺ᵉ)なのはすぐ言えます
ここでの計算量は普通の固定長のレジスタしか持たない計算機で計算した場合の計算回数
動画の計算は0<b≦rのときは
Σ[ k:1〜b ]C[ b-1, k-1 ]C[ w+1, k ]C[ k+w+1, w+b+1-r ]
( ただしm<0,m>nのときはC[ m,n ] = 0とする )
で漏れなくダブりなく計算できるというやつ
これの計算量ですが
①ループはb≦nなのでO(n)回
②計算で出てくる数値の大きさは大体指数オーダーなので桁数はO(n¹⁺ᵉ)オーダー
③3つあるCの計算は漸化式使って前で求めた値にそれぞれ掛け算1回、割り算1回で求まるので桁数がO(n¹⁺ᵉ)だからO(n¹⁺ᵉ)オーダーで計算可能、それを掛け算2回して累計 に足すだけなので結局ループ1回の計算量はO(n¹⁺ᵉ)オーダー
④総計算量は結局高々O(n²⁺ᵉ)オーダー
Σの各項は階乗がたくさん出る形なのでBinary splittingとか使ったら早くなる可能性もあるけど、流石に暇つぶしにそこまでやる気は出ない Cの但し書き逆 orz
C[ m, n ] = 0 if n < 0 or n > m
でつ eはεか
2.718... かと思って、えらい遅いなあと思ってしまった
桁数はn log n 程度、乗除算の定数の桁数がlog nだから、
だいたい n^2 (log n)^2 くらい そうそう、上つきのεが出ないのでeで代用しました
明示しとくべきでした
そもそも計算過程でO(exp(n))オーダーちょいの数扱わざるを得ないしO(n)より真に小さいオーダーのループも無理っぽいのでO(n²⁺ᵉ)より劇的に早くするのは無理ではなかろかと思う今日この頃 お題 何通り?
黒玉 b 個、赤玉 r 個、白玉 w 個が入ってる袋の中から玉を一個ずつ取り出し、取り出した玉を順に横一列に b+r+w 個すべて並べる。
どの黒玉同士も隣り合わず、どの赤玉同士も隣り合わず、どの白玉同士も隣り合わない数を求めよ オリジナル問題をほんの少し変えただけなんだけど
解き方の解説動画がない問題には回答出来ない人なのかな? haskell
https://ideone.com/ff0ut9
ほとんど大差ないから書かなかっただけだよ >>605
Kotlin
前回のプログラムを修正して入力の最初の値として 0 または 0 以外を受け付けるようにして、
それが 0 だったら前回と同じ動作(Wは連続して良い)、0以外だったら今回のお題の動作(連続不可)
になるようにした。
https://paiza.io/projects/YHo1f9RRZcJ5qWeKjh4A5A >>605
haskell
https://ideone.com/eoDuMc
アルゴリズムは何も変わってないんだけどGHCという一番メジャーなhaskell コンパイラはソースでユニコード文字で処理してるので変数名に漢字とか使えてちょっと面白いんですけど試しr̅みたいな合字やってみたら使えました、まぁそりゃ使えるだろって話なんですけど
ちょっとコードの見た目が全然違って楽しい お題
上半分と下半分にそれぞれ文字列が書かれたカードがN枚ある。
カードiの上半分の文字列をx_i、下半分の文字列をy_iとする。
カードを何枚か選び横一列に並べ、上側と下側でそれぞれ文字列を結合する。
カードを上手く選ぶことで上側と下側の文字列を一致させることが可能か?
ただし、同じカードを2回以上使用しても良い。 >>612
言ってる意味がよく分からない。そのカードは上下で分離できるものなのか? お題出すならまず自分で解答作ってそれに何個か入力してどんな出力になるのか例示しとくべき
そもそももちろん日本語で他人に伝わる仕様書書けないようでは話にならんのだけど 問いは「可能か?」
答えは「可能(例:全て同一の文字列とする)」
以上 ちょっと誰か >>612 を ChatGPT にコピペして入力してどう答えるか試してみ はい、上側と下側の文字列を一致させることが可能です。
以下の手順で可能です。
カードの上半分の文字列x_iをすべて結合すると文字列Xが得られます。
カードの下半分の文字列y_iをすべて結合すると文字列Yが得られます。
文字列Xと文字列Yを逆順に結合した文字列Z = X + Y'を考えます。ここでY'は文字列Yを逆順にしたものです。
Zの中央にあるカードを選びます。つまり、Zを左右に分割するときに真ん中にあるカードです。
このカードを選ぶことで、上側の文字列をカードの上半分の文字列に、下側の文字列をカードの下半分の文字列にすることができます。
残りのカードに対して、上側と下側で同じ文字列を選びます。このとき、カードを上下反転させたものを選ぶことで、
上側と下側で同じ文字列を選ぶことができます。
こうして選んだカードを横一列に並べることで、上側と下側の文字列を一致させることができます。
具体的には、以下の手順で解くことができます。
カードの上半分の文字列x_iをすべて結合すると文字列Xが得られます。
カードの下半分の文字列y_iをすべて結合すると文字列Yが得られます。
文字列Xと文字列YのLCSを求めます。LCSを求めるアルゴリズムには、動的計画法が使われます。
LCSを構成する文字列を上側と下側の文字列に選びます。このとき、同じ文字列を複数回選ぶことができるので、
LCSの中に同じ文字列が複数回現れる場合には、その文字列を選ぶことができます。
残りのカードに対して、上側と下側でLCSに現れない文字列を選びます。同じ文字列を複数回使用することができるので、
LCSに現れない文字列を上側と下側で同じように選ぶことができます。
こうして選んだカードを横一列に並べることで、上側と下側の文字列を一致させることができます。
このアルゴリズムの時間計算量は、文字列Xと文字列Yの長さの合計をNとした場合、O(N^2)です。
LCSを求める動的計画法の時間計算量はO(N^2)であり、残りの処理の時間計算量もO(N^2)です。したがって、全体としての時間計算量はO(N^2)となります。 お題:立方体の頂点x,y,zを格納する配列がある。
ある面の頂点が4つ与えられるのでその頂点をコピーしてx軸上に少し移動させる。
与えられた頂点とコピーした頂点で、3点を結んで面を構築し立方体を表現する頂点のインデックスの配列を生成せよ。
(結果的に立方体の横に新しい立方体ができることがある)
頂点の配列は一次元の実数の配列でx,y,z,x,y,z,というふうに要素が並んでいる。
インデックスの配列も整数の一次元で3点をa,b,cとするとa,b,c,a,b,cというふうに並ぶ。
座標系は右手座標系とする。
頂点は左回りが表面とする。 お題
A、B、C、D、Eの5人が前を向いて横一列に座っている。以下は、異なる5人の発言である。
ア メガネをかけている人は、私の左隣に座っている。
イ 私の右隣にはCが座っている。
ウ 私から右に3番目にはAが座っている。
エ 私の左隣にはB、Bから左に2番目にCが座っている。
オ 私の左隣にはDが座っている。
5人のうち1人だけがメガネをかけているとしたら、それは誰か。 Prologおじさんの大好物だろうけどさすがにもう絶滅したか お題
最長重複文字列を求めてください
入力: mississippi
出力: issi >>631
PowerShell
$s = "mississippi"
$n = $s.length - 1
$t = $u = ""
foreach ($i in 1..$n) {
$t += ((0..$n |% {("-", "#")[$s[$_] -ceq $s[$_ + $i]]}) -join "") + "`n"
$u += ($s[$i..$n + 0..($i - 1)] -join "") + "`n"
}
foreach ($i in $n..1) {
if (!($matches = [regex]::matches($t, "#" * $i)).count) {continue}
$matches |% {$u[$_.index..($_.index + $i - 1)] -join ""}
break
} お題
いろはに王国の国民はみな、氏・ミドルネーム・名を持つ
いろはに政府のマイナンバーシステムでは
氏・ミドルネーム・名
をそれぞれ別項目に保存するはずであったが
氏+ミドルネーム+名の処理が行われて一つの項目に保存されてしまっていた
政府とシステム開発会社のコミュニケーション不足が原因と思われる
再発防止をお願いした
さて、とある国民の名前が「いろはにほ」で保存されていた
この国民の名前を氏・ミドルネーム・名に分割するとき
考えられる分割の仕方をすべて列挙してください
例:
い・ろ・はにほ
い・ろは・にほ
い・ろはに・ほ
いろ・は・にほ
いろ・はに・ほ
いろは・に・ほ 例をコピペ出力するだけでOKなのでそれより長いプログラムは冗長
むしろ出題からして最後の部分以外不要なのを踏まえてそこを楽しむべきかもしれない お題: 直方体の段ボール箱の幅・高さ・奥行きがcm単位で指定される。その段ボール箱の展開図をSVG形式で出力せよ。 >>631 Perl5
$len = length ($s = 'mississippi');
for $a (0..$len-2) {
for $l (1..$len-$a) {
$t = substr($s, $a, $l);
$b = index($s, $t, $a+1);
$h{length $t} = $t if 0 <= $b
}
}
print $h{(sort keys %h)[-1]}, "\n";
注: インデントは全角スペースに置換してあります
実行結果
~ $ perl 21_631_mississippi.pl
issi >>638
重複を検出した文字の長さが二けた以上になる場合にも対応させるには
print $h{(sort keys %h)[-1]}, "\n";
↓
print $h{(sort{$a <=> $b} keys %h)[-1]}, "\n";
だな。 >>640
そんなに簡単に解かれるとは思ってなかった
王国の話に引っ張られて解けない人いるかもと思ってた
3分割に限定したのが良くなかったかも
お題
文字列の分割パターンを全部列挙してください
入力: いろはにほ
出力:
い・ろ・は・に・ほ
い・ろ・は・にほ
い・ろ・はに・ほ
い・ろ・はにほ
い・ろは・に・ほ
い・ろは・にほ
い・ろはに・ほ
い・ろはにほ
いろ・は・に・ほ
いろ・は・にほ
いろ・はに・ほ
いろ・はにほ
いろは・に・ほ
いろは・にほ
いろはに・ほ
いろはにほ >>642 Perl5
use utf8;
binmode STDOUT => "utf8";
use feature qw{:5.16 signatures say};
say for sub($a, @b) {
if (@b) {
my @s = __SUB__->(@b);
(map{"$a・$_"} @s), (map{"$a$_"} @s);
} else { $a }
}->(split'', 'いろはにほ');
※インデントは全角スペースに置換してあります。
perl5の__SUB__は、5.16以降で使用可能な「現在の関数(この場合無名関数)のリファレンス」
実行結果
~ $ perl 21_642_いろはにほ.pl
い・ろ・は・に・ほ
い・ろ・は・にほ
い・ろ・はに・ほ
い・ろ・はにほ
い・ろは・に・ほ
い・ろは・にほ
い・ろはに・ほ
い・ろはにほ
いろ・は・に・ほ
いろ・は・にほ
いろ・はに・ほ
いろ・はにほ
いろは・に・ほ
いろは・にほ
いろはに・ほ
いろはにほ >>642
PowerShell 3以上 (文字列は32文字以下とする)
$s = "いろはにほ"
$n = $s.length - 1
foreach ($i in 0..((1 -shl $n) - 1)) {
(0..$n |% {$s[$_], "・"[!($i -band (1 -shl $_))]}) -join ""
}
[実行結果]
いろはにほ
い・ろはにほ
いろ・はにほ
い・ろ・はにほ
いろは・にほ
い・ろは・にほ
いろ・は・にほ
い・ろ・は・にほ
いろはに・ほ
い・ろはに・ほ
いろ・はに・ほ
い・ろ・はに・ほ
いろは・に・ほ
い・ろは・に・ほ
いろ・は・に・ほ
い・ろ・は・に・ほ お題
次のように定義される関数f(x,y)を実装せよ。
x==0のとき:f(0,y):=y+1
y==0のとき:f(x,0):=f(x-1,1)
それ以外のとき:f(x,y):=f(x-1,f(x,y-1))
また以下の値を計算せよ。
f(1,1)
f(2,3)
f(3,4)
f(4,1)
f(4,2) 世の中にはもっとずっと急激に増加する関数があるんだよね
増加が速過ぎて、宇宙中のリソースを使ってもコンピューター言語では記述不可能 >>648
メモ化してもf(4, 2)でスタックオーバーフローしたわ PowerShell 3以上 (x, yは0以上の整数とする)
function hyper($n, $a, $b)
{
if ($n -eq 0) {return $b + 1}
if ($n -eq 1) {return $a + $b}
if ($n -eq 2) {return $a * $b}
if ($n -eq 3) {return [BigInt]::pow($a, $b)}
$c = 1
1..[Int]$b |% {$c = hyper ($n - 1) $a $c}
$c
}
function f($x, $y)
{
(hyper $x 2 ($y + 3)) - 3
}
((1,1),(2,3),(3,4),(4,1),(4,2)) |% {"f($($_[0]), $($_[1])) = $(f $_[0] $_[1])"}
[実行結果]
f(1, 1) = 3
f(2, 3) = 9
f(3, 4) = 125
f(4, 1) = 65533
f(4, 2) = 2003529930…(19709桁省略)…5719156733 お題: 地球によく似た星earth2では小さなインターネットmininetが整備されている。mininet上の端末はIPv2という2バイトのアドレスでアクセスできる。
IPv2の各バイトの範囲が最小値と最大値のペアとして与えられる。与えられた範囲内のIPv2に対して対応する2個の引数の関数fを呼び出すブルートフォースを順番に実行せよ(シングルスレッド)。関数fは実引数の内容を順番に表示するものとする。
例)
data = {{1, 3}, {3, 4}}
→ f(1, 3), f(1, 4), f(2, 3), f(2, 4), f(3, 3), f(3, 4).
※フィクションです。 お題:割り算を逆数の掛け算で近似する
単に逆数を掛けるだけだと簡単過ぎるので、例えば、
x/60 = x*(1/64 + (1/60 - 1/64)) = x*(1/64 + 1/960) = x*(1/64) + x*(1/960)
の様に、
a)2の整数べき乗と、
b)残り(除数の逆数-a)
に分割する事を考える(∵2の整数べき乗との乗算は誤差が発生しない)。
ゼロより大きい除数が与えられた時、これをa, bに分割せよ。
分割は、除算の計算精度が最も高いものにすること。 要するに2進展開の小数部の最初のゼロでない桁決定するの? お題: 縦3マス、横3マスの○×ゲーム(まるばつげーむ)について、ゲームが完了したときの盤面のパターンを重複なく出力し、何通りのパターンがあるかを計算せよ。 >>658
PowerShell 3以上
function bceil([UInt]$n)
{
if (!$n) {return 0}
$m, $n = [UInt]1, ($n - 1)
while ($n) {$m, $n = ($m -shl 1), ($n -shr 1)}
$m
}
function GCD([UInt]$a, [UInt]$b)
{
while ($b) {$a, $b = $b, ($a % $b)}
$a
}
2..20 + 40, 60 |% {
if (($a = bceil $_) -eq $_) {return "x/$_ = x*(1/$a)"}
$d= GCD $a $_
$b, $c = (($a - $_) / $d), ($a / $d * $_)
"x/$_ = x*(1/$a) + x*($b/$c)"
} [実行結果]
x/2 = x*(1/2)
x/3 = x*(1/4) + x*(1/12)
x/4 = x*(1/4)
x/5 = x*(1/8) + x*(3/40)
x/6 = x*(1/8) + x*(1/24)
x/7 = x*(1/8) + x*(1/56)
x/8 = x*(1/8)
x/9 = x*(1/16) + x*(7/144)
x/10 = x*(1/16) + x*(3/80)
x/11 = x*(1/16) + x*(5/176)
x/12 = x*(1/16) + x*(1/48)
x/13 = x*(1/16) + x*(3/208)
x/14 = x*(1/16) + x*(1/112)
x/15 = x*(1/16) + x*(1/240)
x/16 = x*(1/16)
x/17 = x*(1/32) + x*(15/544)
x/18 = x*(1/32) + x*(7/288)
x/19 = x*(1/32) + x*(13/608)
x/20 = x*(1/32) + x*(3/160)
x/40 = x*(1/64) + x*(3/320)
x/60 = x*(1/64) + x*(1/960) >>662
R
ideone.com/W0gYyh
合っているか分からないが、対称な盤面を除去すればWikipedia英語版に載っている
138通りに一致するから、合っていそう。 >>662
(3^9)/4
= 4920.75
じゃね? >>668
(((3^9)-3)/4)+3
= 4923.
だったか >>667の情報を見て思ったが、日本では先攻が〇、英語版では先攻が×。
その時点でパターンが変わる。 >>660
除数が2の整べき乗よりちょっと大きい場合は、引き算にした方が精度が出たりします。
tps://sagecell.sagemath.org/?z=eJx9j8FqwkAQQO-B_MOClyyahlmN8eLHSGlQ6DZL2A9wEw-KJ-uhlF7FioUIvbT0YD9mCMlnOIlGb8LusPN23uxsGEeSSSVHeswmUkWxpqxDO7QtqR5U_PQ4BDFgLUYR0zWmKabz4vuY_23RfJa7eZG9oXnHZGlbeggemQ4EvBI8CDB5vePZloonL9rRVTmaNZosn27QfJX_KzSzYrcsFwc6UGe4tO4K3g6fo5F2wK-B3-vx5jWq6Yo2XRAkRzTj9Ll7cepcBIKUmwN9FzyCttVixcdvfjiW-03-k2GSNP-jta1nvY4MHUbB1dzT_ApFBcUZngDsTonA&lang=python&interacts=eJyLjgUAARUAuQ== すぐ消えるかも知れない方のリンク(中身は同じ)
tps://sagecell.sagemath.org/?q=tkqhls 補足:>>671の「引き算」は、>>658での「b)残り(除数の逆数-a)」を負数にする事に
相当します。 元のお題に「分ける」とあるのてマイナスなしなんじゃないの? 回分かどうか判定するプログラムを書きなさい。回分とは逆から読んでも同じ文である。
例 step on no pets
使用言語 C >>676 補足
入力した文が回分かどうか判定するプログラムを書きなさい。 >>676,678
これ後から絵文字やらクラスタやらどんどん補足していくパターン >>678
これなんの補足をしたつもりだったんだ…? >>676
Haskell
isPalindrome x = x == ( reverse x )
main = do
print $ isPalindrome "step on no pets" >>662
最終盤面が何通りか理論的に求めてみた。○を先手とし、最終盤面での○と×の個数をそれぞれa, bとすると、(a, b) = (3, 2), (3, 3), (4, 3), (4, 4), (5, 4) の5種類に場合分けされる。
(1) (a, b) = (3, 2) のとき
・○は縦・横・斜めの8本のどれかに並べて置くので8通り
・×は残り6マスのどれかに置くので ₆C₂ = 15通り
・以上より、盤面数は 8 × 15 = 120通り
(2) (a, b) = (3, 3) のとき
・○は縦・横・斜めの8本のどれかに並べて置くので8通り
・×は残り6マスのどれかに置くので ₆C₃ = 20通りだが、○が縦/横に並ぶ場合は、×が縦/横の残り2本のどちらかに並ぶ2通りを除外する
・以上より、盤面数は 8 × 20 − 6 × 2 = 148通り
(3) (a, b) = (4, 3) のとき
・○は3個を縦・横・斜めの8本のどれかに並べ、1個を残り6マスのどれかに置くので、8 × 6 = 48通り
・×は残り5マスのどれかに置くので ₅C₃ = 10通りだが、○が縦/横に並ぶ場合は、×が縦/横の残り1本に並ぶ1通りを除外する
・以上より、盤面数は 48 × 10 − 6 × 6 × 1 = 444通り
(4) (a, b) = (4, 4) のとき
・×は3個を縦・横・斜めの8本のどれかに並べ、1個を残り6マスのどれかに置くので、8 × 6 = 48通り
・○は残り5マスのどれかに置くので ₅C₄ = 5通りだが、○が縦/横に並ぶ場合は、×3個が縦/横の残り1本に並び1個が残り2マスのどちらかに並ぶ2通りを除外する
・以上より、盤面数は 48 × 5 − 6 × 6 × 2 = 168通り
(5) (a, b) = (5, 4) のとき
・×は9マスのどれかに置くので ₉C₄ = 126通りだが、3個を縦・横・斜めの8本のどれかに並べ1個を残り6マスのどれかに置く 8 × 6 = 48通りを除外する
・○は残り5マスに置くので1通り
・以上より、盤面数は (126 − 48) × 1 = 78通り (1)〜(5)を合計すれば、盤面数は 120 + 148 + 444 + 168 + 78 = 958通り
よって>>667のプログラムでの計算値が正しいことが検証された。>>667のプログラムの行列Sを調べると、(1)〜(5)の各場合の盤面数も上記の値と一致した。上のように場合分けして盤面を組み立てていく手順をプログラムで記述するのは複雑で面倒なので、>>667のようにゲームを実際に行ってみるプログラムの方が簡潔に書けて良い。 >> 676 の回答例を載せときます
#include <stdio.h>
#include <string.h>
void kaibun_judge(char *str);
int main(void)
{
char ss[80];
printf("文字列を入力してください ");
gets(ss);
kaibun_judge(ss);
}
void kaibun_judge(char *str)
{
char *p, *q, dmy[strlen(str)];
p = str;
q = dmy;
for (int i = strlen(str)-1;i >= 0;i--) {
dmy[i] = *p++;
}
if (strcmp(str, dmy) == 0) printf("回文です\n");
else printf("回分ではありません\n");
} >>682の(4)の訂正
(誤)○が縦/横に並ぶ場合は、×3個が
(正)×が縦/横に並ぶ場合は、○3個が >>684
よくあるバグ入でかつ分かりやすい速度向上の余地を持つ良い例だ >>684
そのプログラムは char 一つで1文字を表す文字コード以外ではまともに動かない。
80文字以上の入力でバッファーオーバーランする。
dmy[] 配列の最後の次のメモリに \0 以外のゴミが入っていたら strcmp() が想定した通りに動かない。 C使い慣れてないなら他の文字列が楽々使えてメモリ管理についてほとんど考えなくても良い言語使って作った方が良いのではないか? >>662
Kotlin
馬鹿正直に○×と交互に打ちながら途中で縦横斜め何れかで3つ揃ったらそこで終了という感じで全パターンやらせたら
255168 パターンになったのだが、これで合っているのか謎だ。対象になるパターンを抜くとすると4で割って 63792 になる。
それと出力が多すぎて恐らくどのサイトでも実行されると結果がまともに出ない。
paiza.io にソース置いておくが実行するとパターン 1651 の途中で Timeout して中途半端に終わっている。
https://paiza.io/projects/2eV3pNvLM7kdKO0gYfHc-w よく見たら >>676 は使用言語がCだけになってたんだな。
じゃあC使うのは仕方がないが、Cだと色々と気を付けなければならないことが多いので要注意だ。 >>676
C
Locale 考慮して wchar_t 使って書いた。日本語読ませても処理できる。
但しやってることは文字列の順序入れ替えて比較しているだけなので>>684と考え方は同じ。
(書きながら一々メモリ確保して逆順に並べなくても出来ると気付いたがそれは後で公開する)。
入力元が Unicode になっていた場合は濁点半濁点の合成文字みたいなのもあって MacOS でやった時とその他 OS で違ってしまうかも知れないが、その辺は考慮されていない。
https://paiza.io/projects/YXLsX3FqAsVF6DVDxye7bA >>692は改行のみが入力された時の反応がおかしかたのでちょっとだけこっそり修正した。
同様に>>691もおかしかったがそっちは面倒なので放置。 >>684 gets()のかわりにfgets()を使うと改行を含んでしまうので\0で埋めてやらないといけない。 文字列がらみはもはやライブラリ使わないと無理やろ
ユニコードのコーディングルールはもう複雑すぎて素人が自作で作ってもまずうまくいかない
この手のルールは数学的にこうなってるはずだ、こうなってないとおかしいとかいうロジックが何一つ通用しない、単なる取り決めるなのでただひたすら覚えるしかないけど、もはや色んな言語全部取り込むために魑魅魍魎の世界 >>676
U+10000以上の文字、異体字セレクタ、結合文字に対応したプログラムはPowerShellでは
簡単に書ける。ただし、IDS(漢字構成記述文字列)には対応していない。
tps://tio.run/##XZJPS8MwGMbv/RQxVGjRFnvxMPA4hjdhw8sYoxvZVumS2WQqzoKtf5kHD8KGG4i3zcNQbx7ULxM63E3wA8ykm1sxl6bv8@T3Pm/TBjlEHq0h151OK01cZg7BgDLPQweaSnWlpQCxVAa2AITxPp9xScl2nWNbes0s8xxc3cYVUkilMojl0BFLu6iOMEvjZh15NiOeRIGTVdCKQWoRrAmkP0crvqL8a21tJpobe8TBQKV5wzJNQ6Wmi3CV1QrxOeIhu1wDwg6ECTYQo0BgMBEk1IDrAE5GPR4Mv9qvP4/nAQ9ueNj7fnr74MFg9pCFhToUbqiDWeMN07Ti1PGbXBrUxp2X6P1Wl2Rt3B3Eez2vFgsLUzyjUwHailoUqNlEIr8PkEvRX8HalKXFIRhdnI07V9GoG113U0KCS2lyepmUGEzkifoPQhPD8OCZByEP2zz45EGfh3cyYkK@lzEpMMpoXzCWcefX6svPqe5kd8XvIC4iZ5dcNJ3@Ag
これはOutputの下の方に表示されているようにLinuxでの実行結果だが、Windowsと同様に
動作しOSに依存しない。CではOSに依存しないで書くのは難しそう。
(旧式)はUTF-16のワードを逆順に並べただけなので、U+10000以上のU+29E3D、異体字
セレクタ使用のU+82B1 U+E0101、結合文字のU+304B U+309Aが含まれる2番目の例では
正しく判定できていないが、(新式)はできている。異体字は対応しているフォント(例えば
Windowsの標準フォントでは游ゴシック)でないと正しく表示されない。 >>696 ワイド文字対応だけでもすごいのにそこまでやるとは >>696をIDS(漢字構成記述文字列)対応にした。ビャンビャン麵のビャンという漢字の
IDSを正しく表示できるのは、源ノ等幅、源ノ明朝、源ノゴシックのバージョン1.xxxと
Visual Studio Code, Edgeなどの組み合わせに限られる。正しく表示されるとこうなる。
://i.imgur.com/TEDafUA.png
バージョン2.xxxxではビャンという漢字に単独のコードU+30EDEが割り当てられたので、
IDSでは表示できなくなった。
function strrev($s)
{
$m = 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2
$p = $q = ""
$n = 0
[Globalization.StringInfo]::GetTextElementEnumerator($s) |% {
if (0x2FF0..0x2FFB -contains $_[0]) {
if (!$n) {$n = 1}
$n += $m[$_[0] - 0x2FF0]
}
$p += $_
if (!$n -or !--$n) {$p, $q = "", ($p + $q)}
}
$p + $q
}
foreach ($s in "⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心", "⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麺⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心") {
$t = strrev $s
"元文字列: $s"
"逆文字列: $t"
("回文ではありません。", "回文です。")[$s -ceq $t]
""
} [実行結果]
元文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
逆文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
回文です。
元文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麵で麺⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
逆文字列: ⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心麺で麵⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心⿺辶⿳穴⿰月⿰⿲⿱幺長⿱言馬⿱幺長刂心
回文ではありません。 >>700
こっちのPowerShellでやれば全部OK
https://github.com/PowerShell/PowerShell
Name Value
---- -----
PSVersion 7.3.4
PSEdition Core
.NET 7凄すぎ お題:現在の日時の文字列が与えられるのでその文字列の先頭から秒数分を切り出して出力せよ >>702
それって秒の部分だけが残れば良いってこと? たとえば 2023/05/27 02:03:45 なら最後の 45 だけになれば良いの?
もしそうなら sed 使ってこうすればできるな。
sed 's/^.*://'
YYYY/MM/DD hh:mm:ss 形式ではなく秒が最後に出て来ない形式だったとしても最後のコロンの直後の数字が秒で、
その秒の数字文字列の後に数字でない文字が必ず来るのだとすれば (例えば Sat May 27 02:05:47 JST 2023 の
ような形式だとすれば)こうすれば良い。
sed 's/^.*://;s/[^0-9].*$//' お題 ナイトツアー
5×5の狭いチェスボードのどこかにナイトのコマを置きそこからナイトの可能な動きでコマを動かします
ただし同じマスは2回通れません
このとき全マス25マスを全て通る手順の数を数え上げて下さい
しかし実際全部数えるのは流石に無駄なので対称性を利用して
♯{A1→B3}×8
+ ♯{A3→B5}×8 + ♯{A3→C4}×8
+ ♯{B2→C4}×8
+ ♯{C3→D5}×8
はよいとします
例
♯{A1→B3} = 152
--ナイトの動き--
桂馬の動きと同じ、水平方向の移動量+垂直方向の移動量 = 3となる移動(もちろん盤の中) >>705
訂正
> --ナイトの動き--
水平方向の移動量+垂直方向の移動量 = 3となる移動で水平、垂直な移動はなし(もちろん盤の中) >>705
対称性を考慮するのは面倒なので全部数え上げる。Rで書いたら5秒以内に到底終わらなかったので、
ideone.com/y5Dwy7
C++に移植した。盤面表示はideoneでは途中で切れてしまうので非表示にした(関数moveの
コメント部分をコメントでなくせば表示される)。
ideone.com/6Muw9F
対称性を考慮すれば、手順数は1728 / 8 = 216通りになる。 お題: 水の流れる複数のタンクにおいて水の流れをシミュレーションしたいので、以下に定義する入力文字列でタンクと
水の流れなどを記述する。入力文字列は次のような形式の行の並びとする。
「(タンクの名前), (タンクの底面積[m^2]), (タンクの底からの排水口までの高さ[m]), (次のタンクの名前)」
各行は各タンクの情報とその次のタンクを表す。入力文字列の最初の行は最初に水が入るタンクに対応する。最初のタンクには外部から水が0.5[m^3/min]の速度で入る。タンクの形状は円錐か四角錐とし、底面は平面状とする。
各タンクには排水口が付いているかも知れない。排水口があるのならそれはタンクの底より高く、タンクの側面に付いている。
排水口は次のタンクにつながっている。次のタンクはその前のタンクより低い位置にある。各タンクにおいて排水口に水が届いていないときは水は排水されない。
タンクとタンクの間の長さと水の落差にかかる時間は無視して構わない。次のタンクがN/Aならそのタンクに排水口と排水先はない。
シミュレーション開始後、1分ごとに各タンクに何[m^3]の水が入っているかを出力せよ。タンクCが満タンなら終了せよ。
(入力)
A, 3, 0.5, B
B, 2, 0.7, C
C, 1, 0.4, N/A >>705
Kotlin
馬鹿正直に再帰で全パターンやっているだけ。
途中経過は出力しない。既に置かれたマスは1bitで記録されるようにして 5 * 5 = 25 bit で Int (32bit) に収まるのでそれを利用している。
恐らく Boolean の配列を使って書くとそこまで最適化されなさそうなのでこうした。
https://paiza.io/projects/O4Ejxs76h64GSeXYCVs2mg
結果は同じ 1728 になったので多分これで合っていると思う。 >>705
>>707にちょっと付け加えたら対称性を考慮して数え上げることができた。
://ideone.com/NSyJcK (R)
://ideone.com/S1VIUA (C++)
Rでは5秒以内に終わらなかった。 お題: x-y平面上に摩擦のないすべり台がある。重力加速度を9.8[m/s^2]とし、重力はy軸とは逆向きに作用している。
この滑り台は動かないように固定されている。横位置x>=0[m]についてf(x)がすべり台の面の高さ[m]を表す。
体重35kgの子どもがx=0の場所から滑り台を滑り始めた。次の場合の5秒後の子どもの位置ベクトルと速度ベクトルを求めよ。空気抵抗は無視する。
(i) f(x)=10-sqrt(x)。
(ii) f(x)=10-sqrt(sqrt(x))。
※ xの平方根をsqrt(x)とする。 お題
アルファベットが入力されます
> [A, A, B, B, B, C, C, D, D, D, E]
出力上限が入力されます
> 7
出力上限以内のアルファベットを出力してください
> [A, A, B, B, B, C, C]
ただし、出力上限で切った場合に同じアルファベットが分割される場合は出力上限を超えて
同じアルファベットが続く限り出力してください
アルファベット: [A, A, B, B, B]
出力上限: 3
出力: [A, A, B, B, B] >>712
C#でループを使わずに出力
www.ideone.com/Xk3ACt お題:矩形に整形された全角文字のテキストが与えられる。左上から時計回りに
渦巻き状に読んだ文字列を、元の矩形と同文字数で桁数がより多く最も近い矩形に
左上から時計回りに渦巻き状に並べて出力せよ。
[例]
プログラ → プログラミン
題スレミ レス題おのグ
おのグン
[問題]
メロスは激怒した。必ず、かの邪智暴虐の王を除かなけ
ては、人一倍に敏感であった。きょう未明メロスは村れ
し、内気な妹と二人暮しだ。この妹は、村の或る律をば
対の嫁の衣裳やら祝宴の御馳走やらを買いに、は気出な
に六花ロスには竹馬の友があった。セリヌンテるな発ら
悪十、メてみるつもりなのだ。久しく逢わなィば一しぬ
邪。え。ねスは、まちの様子を怪しく思っかウる牧、と
もいゆた訪ロのは当りまえだが、けれどたっス市人野決
ど無れいらメい全体が、やけに寂しいも。たでにをを意
れもそ歩かに暗市不安になって来た。、ひのあや、越し
け房、られちの、ん衆をつかまえ。のなっだるっ近えた
。女はぶこうちくだい若たっ逢で路んんそか。て々山。
た。スら、るま無んだ、もスロメなきだりら今来、越メ
来いロぶをい、はでりかばいせの夜、かし、はた花えロ
て無メを友ててち落も日に既うも。るいて訪此の婿、ス
しも。路のい歩。るあでみし楽がのく行てねのだと十に
暮母る大そ。るいてしを工石、で市のスクラシ。し里は
で、あの都らかれそ、め集い買を々品のそ、ず先ては政
んもでのなか近間も式婚結。たいてっなに事るえ迎な治
遊父はにスロメ。た来てっやに市のスクラシの此たれが
と羊、き吹を笛。るあで人牧の村、はスロメ。ぬらかわ >>714
この部分の意味がわからない。どうしろというのか?
> 元の矩形と同文字数で桁数がより多く最も近い矩形 >>715
[例]で言えば、3行×4桁=12文字が矩形に並ぶのは1, 2, 3, 4, 6, 12桁のときだから、
4桁より多く4桁に最も近いのは6桁となる。 お題: 郵便切手の問題。
切り離されていない、一列に並んだn枚の切手を考える。
一枚の切手の上に全ての切手を折り込む時、
左端の切手を表向きで一番上に折り込む方法は何通りか計算せよ。 >>712 Perl5
use feature qw{signatures say};
sub f($n, $c, @s) {
if (1 < $n) {
$c, f($n - 1, @s);
} elsif (1 == $n) {
$c, f(0, $c, @s);
} else {
$c, f(0, $c, splice @s, 1) if $c eq $s[0];
}
}
say f 7, qw[A A B B B C C D D D E];
say f 3, qw[A A B B B];
※見易くするためインデントは全角スペースに置換してあります。
実行結果
$ perl 21_712.pl
AABBBCC
AABBB >>712 Perl5、もっと簡潔なやり方あるんだった…orz
use feature qw{signatures say};
sub f($n, $s) {
my $r = '^.{' . ($n - 1) . '}(.)\1*';
$s =~ /$r/;
$&;
}
say f 7, 'AABBBCCDDDE';
say f 3, 'AABBB';
実行結果
$ perl 21_712_rex.pl
AABBBCC
AABBB お題 逆順に
文字列が与えられます
使われている文字のリストを作って並べその“反対の”文字を対応させます
例えば登場文字列が
HELLO WORLD
なら出てくる文字をコード順に並べると
" DEHLORW"
であるので
E → O, L →H, ' '→W
となります(空白、句読点等一切区別せず一文字と考えます)
この対応で入力された文字列を変換してください
例
HELLO WORLD →
LOHHEW EDHR
⑨⑫⑦②⑤⑭⑰⑳㉔①⑩⑬㉒⑲④⑮⑪⑧㉓⑥③⑯㉑⑱ →
⑯⑬⑱㉓⑳⑪⑧⑤①㉔⑮⑫③⑥㉑⑩⑭⑰②⑲㉒⑨④⑦ >>720 もっとすんなり書けるんだった… orz
$c, f(0, $c, splice @s, 1) if $c eq $s[0];
↓
$c, f(0, @s) if $c eq $s[0];
関数全体のコードとしてはこうなる:
sub f($n, $c, @s) {
if (1 < $n) {
$c, f($n - 1, @s);
} elsif (1 == $n) {
$c, f(0, $c, @s);
} else {
$c, f(0, @s) if $c eq $s[0];
}
}
すっきりした形になりました >>722 Perl5
use feature qw{signatures say};
use utf8; binmode STDOUT => 'utf8';
use Encode 'encode';
sub f($s) {
@s = split '', $s;
%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
@i = reverse @c = sort keys %h;
%o = map{$h{$c[$_]} => $h{$i[$_]}} 0..$#c;
say map{$o{$_}} @s;
}
f 'HELLO WORLD';
f '⑨⑫⑦②⑤⑭⑰⑳?①⑩⑬?⑲④⑮⑪⑧?⑥③⑯?⑱';
※見易くするためインデントは全角スペースに置換してあります。
実行結果:
$ perl 21_722.pl
LOHHEW EDHR
⑯⑬⑱?⑳⑪⑧⑤①?⑮⑫③⑥?⑩⑭⑰②⑲?⑨④⑦ >>722 Perl5 スマソ、ビューワーから書き込んだら丸数字の一部が文字化けしたのでブラウザから再書き込み
use feature qw{signatures say};
use utf8; binmode STDOUT => 'utf8';
use Encode 'encode';
sub f($s) {
@s = split '', $s;
%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
@i = reverse @c = sort keys %h;
%o = map{$h{$c[$_]} => $h{$i[$_]}} 0..$#c;
say map{$o{$_}} @s;
}
f 'HELLO WORLD';
f 'HKFADMPS㉔@IL㉒RCNJG㉓EBO㉑Q';
実行結果
$ perl 21_722.pl
LOHHEW EDHR
OLQ㉓SJGD@㉔NKBE㉑IMPAR㉒HCF >>722
PowerShell 4以上 (U+10000以上の文字、結合文字、異体字セレクタに対応)
foreach ($s in "HELLO WORLD", "HKFADMPS㉔@IL㉒RCNJG㉓EBO㉑Q", "魚と花󠄁か゚𩸽") {
$c = [Globalization.StringInfo]::GetTextElementEnumerator($s) | sort | unique
$h = @{}
0..($c.length - 1) |% {$h[$c[$_]] = $c[-$_ - 1]}
-join $h[[Globalization.StringInfo]::GetTextElementEnumerator($s)]
}
[実行結果]
LOHHEW EDHR
OLQ㉓SJGD@㉔NKBE㉑IMPAR㉒HCF
と魚花󠄁𩸽か゚ >>726 しくった
utf-8文字を可変長16進数にunpackして辞書的順番でsortするので、例題では意図した通りの結果を得られたが、
半角と全角などutf-8でバイト数の異なる文字が混在する文字列の場合には、順番が違ってくるだろうな… >>726 Perlで文字の数値コードを返すord()関数は半角文字の場合にASCIIコードを返すが、
全角Unicode文字ではコードポイントを返す、ということなので、素直にそれを使い、
文字列としてっではなく数値としてsortし
%h = map{unpack('H*', encode('utf-8', $_)) => $_} @s;
@i = reverse @c = sort keys %h;
↓を
%h = map{ord($_) => $_} @s;
@i = reverse @c = sort{$a <=> $b} keys %h;
と修正するのがよさげ。連投スマソ >>714 octave
https://ideone.com/MXrAYt
m2c = @(m, r, c) mat2cell(m, repelem(r, size(m, 1) / r), repelem(c, size(m, 2) / c));
s2c = @(s) m2c(s, 1, 3);
function v = e2v(e, v)
if nargin < 2
v = e2v(e, []);
elseif ~isempty(e)
v = e2v(rot90(e(2:end, :)), [v e(1, :)]);
end
end
function ind = eddyind(varargin)
if nargin == 2
ind = e2v(reshape(1:times(varargin{1:2}), varargin{1:2}));
elseif nargin == 1
ind = eddyind(size(varargin{1}, 1), size(varargin{1}, 2));
end
end
s = 省略
c = s2c(s);
n = numel(c);
m = find(rem(n, 1:n) == 0 & size(c, 2) < 1:n)(1);
d = cell(n / m, m);
d(eddyind(d)) = c(eddyind(c));
disp(cell2mat(d)); >>722 ruby
https://ideone.com/yqb6sd
f = ->(s) {s.chars.uniq.sort.join.tap{|u| break s.tr(u, u.reverse)}}
p f.('HELLO WORLD')
p f.('HKFADMPS㉔@IL㉒RCNJG㉓EBO㉑Q')
#p f.('HELLO WORLD-') # trのパターンになっちゃう文字があるとダメ >>722
>>727では大・小・全角・半角文字が区別されないのを修正した。PowerShell 2でも正しく動作するようになった。
foreach ($s in "HELLO WORLD", "HKFADMPS㉔@IL㉒RCNJG㉓EBO㉑Q", "魚と花󠄁か゚𩸽", "HeLLO WoRLD") {
$c = [Globalization.StringInfo]::GetTextElementEnumerator($s) | sort -unique {[int[]][char[]]$_}
$h = New-Object Collections.Hashtable
0..($c.length - 1) |% {$h[$c[$_]] = $c[-$_ - 1]}
-join $h[[Globalization.StringInfo]::GetTextElementEnumerator($s)]
}
[実行結果]
LOHHEW EDHR
OLQ㉓SJGD@㉔NKBE㉑IMPAR㉒HCF
と魚花󠄁𩸽か゚
oLeeRW HODL お題
A,B,Cがランダムにいくつか入力されます
隣り合う文字が異なるときそれらは同じグループです
A,B → [A,B]
隣り合う文字が同じ時それらは異なるグループです
A,A → [A],[A]
A,B,A,A,A,B → [A,B,A],[A],[A,B]
もっとも長いグループを出力してください
入力
B,A,B,C,B,B,B,A,C,C,A,B,A,A,C,A,B,C,C,C,B,C,A,B,C,A,A,A,C,B
出力
[C,B,C,A,B,C,A] >>733 Perl5
use feature qw{:5.16 signatures say};
@a = ([]);
sub ($c, @s) {
push @{$a[-1]}, $c;
push @a, [] if $c eq $s[0];
__SUB__->(@s) if @s;
}->(qw{B A B C B B B A C C A B A A C A B C C C B C A B C A A A C B});
$c = (sort{@$a <=> @$b} @a)[-1];
$" = ','; say "[@$c]";
※見易くするためインデントを全角スペースに置換してあります。
実行結果
$ perl 21_733.pl
[C,B,C,A,B,C,A] >>733
PowerShell
$s = "B,A,B,C,B,B,B,A,C,C,A,B,A,A,C,A,B,C,C,C,B,C,A,B,C,A,A,A,C,B"
@($s -replace "(.),(?=\1)", "`$1/" -split "/" | group length | sort -descending {[int]$_.name})[0] |% {$_.group}
[実行結果]
C,B,C,A,B,C,A >>733 ocaml
https://ideone.com/jfFx3Y
open List
let (<<) f g x = f (g x)
let flip f x y = f y x
let f =
let aux x = function
[] :: ys -> [x] :: ys
| (z :: _) as y :: ys -> if x = z
then [x] :: y :: ys
else (x :: y) :: ys
in rev << hd << rev << map snd << sort compare << map (fun x -> (length x, x)) << fold_left (flip aux) [[]]
let g = print_newline << iter print_char << f
let () = g ['B';'A';'B';'C';'B';'B';'B';'A';'C';'C';'A';'B';'A';'A';'C';'A';'B';'C';'C';'C';'B';'C';'A';'B';'C';'A';'A';'A';'C';'B']
>>733 ruby
f = ->(a) {a.each_with_object([[]]) {|x, acc| acc[-1][-1] != x ? acc[-1] << x : acc << [x]}.sort_by(&:size)[-1]}
p f.(%w(B A B C B B B A C C A B A A C A B C C C B C A B C A A A C B)) お題:1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。 実質力技しかないやろな
割ったあまりとかで多少減らせる程度にしかならない 入力nに対してn以下の素数はn オーダーある
最初に素数list upするのにn オーダー、そこから足してnを見つけるのはどうやってもn²オーダーよりは早くできそうにない >>738 c
https://ideone.com/Dbl6mc
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
void sieve_of_eratosthenes(int n, int **isprime, int **primes_beg, int **primes_end) {
int i, m, j, nbytes = (1 + n) * sizeof **isprime, *map = malloc(nbytes), *beg = malloc(nbytes), *end;
for (i = 2; i <= n; i++) map[i] = 1;
for (i = 2, m = sqrt(n); i <= m; i++)
if (map[i]) for (j = i * i; j <= n; j += i) map[j] = 0;
for (i = 2, end = beg; i <= n; i++) if (map[i]) *end++ = i;
*isprime = map, *primes_beg = beg, *primes_end = end;
}
int main() {
int n = 1234567, *isprime, *primes_beg, *primes_end;
sieve_of_eratosthenes(n, &isprime, &primes_beg, &primes_end);
int *a, *b, c, count = 0;
for (a = primes_beg; a < primes_end && *a <= n / 3; a++)
for (b = a; b < primes_end && *b <= (c = n - *a - *b); b++)
if (isprime[c]) count++;
printf("count = %d\n", count);
return 0;
} お題: 与えられた4頂点が長方形または正方形を形成するかどうか判定せよ。長方形または正方形のときtrueを返すものとする。頂点の順序は無視する。
例)
{ (0, 0), (1, 0), (1, 1), (0, 1) } → true.
{ (0, -1), (0, 1), (1, 0), (-1, 0) } → true.
{ (0, -2), (1, 0), (0, 2), (-1, 0) } → false. お題: コマンドロボット。
ロボットはx-y平面の原点(0, 0)に居る。
コマンドIDはロボットによる何かのアクションを表す0以上4以下の整数で、次のように定義する。
コマンド0は何もしない。
コマンド1は位置が(-1, 0)だけ動く。
コマンド2は位置が(+1, 0)だけ動く。
コマンド3は位置が(0, -1)だけ動く。
コマンド4は位置が(0, +1)だけ動く。
入力として、コマンドIDのリストが与えられる。コマンドを順番に実行したときの最終位置を出力せよ。
例)
(2, 3, 0, 3, 1) → (0, -2).
(1, 1, 4, 0, 0, 2) → (-1, 1). >>743
R
www.ideone.com/hNR3VK >>739 >>742
正解。
出題者によるプログラム
www.ideone.com/0R9KaI >>744
R
www.ideone.com/eH07Wk お題: コマンドロボット2。
ロボットはx-y平面の原点(0, 0)に居る。
コマンドIDはロボットによる何かのアクションを表す0以上4以下の整数で、次のように定義する。
コマンド0は何もしない。
コマンド1は位置が(-1, 0)だけ動く。
コマンド2は位置が(+1, 0)だけ動く。
コマンド3は位置が(0, -1)だけ動く。
コマンド4は位置が(0, +1)だけ動く。
入力として、最終位置が与えられる。原点から最終位置まで移動する最短のコマンドIDリストを生成せよ。
最終位置のx成分とy成分がどちらも非ゼロならx成分から先に移動せよ。
例)
(2, -3) → (2, 2, 3, 3, 3).
(-1, 3) → (1, 4, 4, 4). >>748
R
FormatArray <- function(a) paste0("(", paste0(a, collapse = ", "), ")")
P <- list(c(2, -3), c(-1, 3), c(0, 0))
for (p in P) cat(FormatArray(p), " → ", FormatArray(rep((sign(p) + c(3, 7)) / 2, abs(p))), "\n", sep = "")
[実行結果]
(2, -3) → (2, 2, 3, 3, 3)
(-1, 3) → (1, 4, 4, 4)
(0, 0) → () >>722
Kotlin
○付き数字はブラウザやフォントの設定によっては表示が文字ごとに大きかったり小さかったりするかも知れない。
https://paiza.io/projects/I5rPp0OBjWg6RdMlWu3t5g お題: x=0~πの範囲(step: π/8)でsin(x)を数値微分(dx=0.001)すると、その値sin'(x)がほぼcos(x)に一致することを示せ。
xの各値に対する計算結果(x, sin(x), sin'(x), cos(x))を一行に並べて表示せよ。
各数値は小数点以下3桁まで表示するものとする。 >>748 ruby
def moves(x, y)
[].fill(x < 0 ? 1 : 2, ...x.abs) + [].fill(y < 0 ? 3 : 4, ...y.abs)
end
=> :moves
moves(2, -3)
=> [2, 2, 3, 3, 3]
moves(-1, 3)
=> [1, 4, 4, 4]
moves(0, 0)
=> [] お題: 物理シミュレーション。
運動方程式によると、位置の微分が速度になり、速度の微分が加速度となっている。
逆に言えば加速度の積分と初速から現在の速度が求まり、速度の積分と初期位置から現在の位置が求まる。
数直線上を移動可能な点Pがある。Pの初期位置は原点0[cm]とする。Pの初速はゼロ[cm/s]とする。
入力として加速度[cm/s^2]と加速時間[s]のペアのリストが与えられる。時刻t=0[s]から入力に従って点Pが加速する。
dt=0.1として区分求積法により加速度と速度を数値積分し、1秒ごとのPの位置と速度を5秒後まで出力せよ。各数値は小数点以下2桁まで表示せよ。
例) ((1, 1), (-1, 1), (2, 0.5), (-4, 0.25), (3, 1.25), (-8, 1)) >>738 c
・>>742から若干の省メモリ化
判別用配列の要素をintからcharへ
素数の個数を数えてから一覧用領域を確保
・組み合わせループの条件を>>746さんを参考に改善
https://ideone.com/CixK7I
>>738 c
・上記からさらに省メモリ化
判別用配列はint配列だが判別はビットごと
https://ideone.com/JDcFjV >>754
誤: for (i = 2; i <= n; i++) if (at(map, i)) nprimes++;
正: for (i = 2, nprimes = 0; i <= n; i++) if (at(map, i)) nprimes++; >>753
www.ideone.com/jv00La
Rで書いたらdouble型の精度の問題で期待通りに動作しなかったので、decimal型を使えるC#で書いた。
例のリストで解析解と一致する数値解が得られるように、速度は台形則、位置は台形則と中点則の平均
(結局は刻み幅が半分での台形則に一致するが)で計算した。参考のためstdinに解析解を書いておいた。 力ずく問題は苦手なインタプリタ―だが、速度に配慮した書き方をすればこの規模だと数分程度で解ける…
use feature qw{:5.16 signatures say};
$m = 1234567;
%h = map{$_ => ++$k} 2..$m;
for $i (2..int(sqrt $m)) {
if (exists $h{$i}) {
for ($i..(int($m / $i)+1)) { delete $h{$i * $_} }
}
}
@p = sort{$a <=> $b} keys %h;
%o = map{$p[$_] => $_} 0..$#p;
for $i (0..$#p-2) {
$p1 = $p[$i];
last if $m <= 3 * $p1;
for $j ($i+1..$#p-1) {
$p2 = $p[$j]; $s = $p1 + $p2;
$r = $m - $s; last if $r <= $p2;
$n++ if exists $o{$r};
}
}
print "n = $n\n";
実行結果 (CPUは Core-i7 8995u、Mem: 32GB)
$ time perl 21_738_prime+1234567.pl
n = 151055501
real 5m48.035s
user 5m44.468s
sys 0m3.250s
出題者の解と合わん…>< >>761 アンカーしくった><
>>738 Perl5 >>761
インタプリタでもRだともっと速い。以下のプログラムを https: //tio.run で実行すると
9.96秒で完了し、解は>>746の151060650通りと合う。>>761は制限時間 (1分) 以内に
完了しない。Rは自前のループをなるべく書かずにベクトル演算にすれば割と速い。
n <- 1234567L
isprime <- c(FALSE, rep(TRUE, n - 1))
for (i in 2:sqrt(n)) if (isprime[i]) isprime[seq(i + i, n, i)] <- FALSE
p <- which(isprime)
q <- cumsum(isprime)
k <- 0L
for (i in p[1:q[n %/% 3L]]) {
m <- n - i
k <- k + sum(isprime[m - p[q[i]:q[m %/% 2L]]])
}
cat(k, "通り\n", sep = "") >>763
Perlの(多分Pythoも,Rubyはシラネ)配列はリストなのでインデックスで回すとリンク辿りをloopで繰り返し
こういったコードでは遅さに拍車をかけていると思う。あとhashを多用するのもペナルティーがあると思う。
配列の代わりにBit Vectorが使える場面ではそれにより改善できる可能性がある
たとえば序盤のエラトステネスの篩で素数求めるloopについては>>761のコードだと5.2秒くらいなんだけれど
長い文字列をVectorとし、個々の文字をflag要素とみなし、
use feature qw{say};
$m = 1234567;
$o = '1' x $m;
for $i (2..int(sqrt $m)) {
if (substr $o, $i, 1) {
for ($i..(int($m / $i)+1)) {
$j = $i * $_; last if $m <= $j; substr $o, $j, 1, '0';
}
}
}
for (2.. $m) {
$n++ if substr($o, $_, 1);
}
print "$n\n";
と書くと0.3秒くらいに短縮される。ただし5分のうち5秒なので焼け石に…
しかしこの方法は151060650通りを求める後半のループにはうまく効かない。
つかそれ以前に解が合ってない。多分俺が勘違いしてバグ仕込んだと思う。
しかしRのコード短いな…も一回勉強してみようかな やめとけ
短ければいいという時代はとっくに終わってる
いつまでワンライナーとかアホな事やってんねんと思う >>763のプログラムの8〜11行目は以下のように書いた方がすっきりして良い。
for (i in 1:q[n %/% 3L]) {
m <- n - p[i]
k <- k + sum(isprime[m - p[i:q[m %/% 2L]]])
}
>>761のプログラムはa ≤ b ≤ cではなくa < b < cの場合の組み合わせ数を計算している。
14行目の$i+1を$iに、13行目と16行目の<=を<に変更すれば正解が得られる。 PowerShell 7は前のバージョンよりは速くなっていて、以下のプログラムは>>761の
3分の1ほどの時間で実行できた。
$n = 1234567
$isprime = @($false) * 2 + @($true) * ($n - 1)
foreach ($i in 2..[Math]::sqrt($n)) {
if ($isprime[$i]) {for ($j = $i + $i; $j -le $n; $j += $i) {$isprime[$j] = $false}}
}
$j = 0
$p = $q = @(0) * ($n + 1)
foreach ($i in 2..$n) {
if ($isprime[$i]) {$p[$j++] = $i}
$q[$i] = $j - 1
}
$k = 0
foreach ($i in 0..$q[$n / 3]) {
$m = $n - $p[$i]
foreach ($j in $i..$q[$m / 2]) {
if ($isprime[$m - $p[$j]]) {$k++}
}
}
"${k}通り" >>738 rust
https://ideone.com/THk6s8
fn sieve_of_eratosthenes(n: u32) -> (Vec<bool>, Vec<u32>) {
if n < 2 {return (Vec::new(), Vec::new())};
let mut isprime = vec![true; 1 + n as usize];
isprime[0..2].fill(false);
(2..=(n as f64).sqrt() as usize).for_each(|i| if isprime[i] {
(i*i..=n as usize).step_by(i).for_each(|j| isprime[j] = false);
});
let primes = (2..=n).filter(|&i| isprime[i as usize]).collect();
(isprime, primes)
}
fn main() {
let n = 1234567;
let (isprime, primes) = sieve_of_eratosthenes(n);
let count = primes.iter().enumerate().take_while(|(i, &a)| a <= n / 3).map(|(i, &a)|
primes[i..].iter().take_while(|&&b| b <= (n - a) / 2).map(|&b|
isprime[(n - a - b) as usize] as u32
).sum::<u32>()
).sum::<u32>();
println!("count = {}", count);
} >>766
おお、指摘ありがとう。
俺てっきりa < b < cを検索する問題だと思い込んでた。何故合わないか頭ひねっていた。
思い込みにより作りこんだバグというものはなかなか自力で問題だと気づけないんだよな…。
>>767
俺も時間あったら高速化してみるよ。そのうち…、時間があったら…
第二loopの高速化は他にも試作したけどちょっとムズカしい >>738 Perl5 高速化版、>>766のおかげで不具合解決したし、>>761 の1/3に時間短縮できたので俺としてはこのお題これで一区切りつけたい。
$m = 1234567;
$o = '1' x $m; #substr $o, 0, 2, '00';
for $i (2..int(sqrt $m)) {
if (substr $o, $i, 1) {
for ($i..(int($m / $i)+1)) {
$j = $i * $_; last if $m <= $j; substr $o, $j, 1, '0';
}
}
}
for (2.. $m) { push @p, $_ if substr($o, $_, 1) }
for $i (0..$#p) {
$p1 = $p[0];
last if $m < 3 * $p1;
for $p2 (@p) {
$s = $p1 + $p2;
$r = $m - $s;
last if $r < $p2;
$n++ if substr $o, $r, 1;
}
shift @p;
}
print "n = $n\n";
実行結果:(CPU Core-i7 8995u)
$ time perl 21_738_prime+1234567_charVec.pl
n = 151060650
real 1m57.390s
user 1m56.375s
sys 0m0.093s >>738 octave
・n = 1234567 でideone完走できず
https://ideone.com/QzfFfY
>>738 ruby
・n = 1234567 でideone完走できず
https://ideone.com/OPplEt
>>738 java
https://ideone.com/pCHK8L
ちなみに現時点ではそれぞれ
C (gcc 8.3)
Rust (rust 1.56)
Octave (octave 4.4.1)
Ruby (ruby 2.5.5)
Java (HotSpot 12) >>771
nが偶数の場合はaは2しかあり得ないから、ループでaを変化させるのは時間の無駄でしかない。 数値の設定がデカすぎるんだよ
こんなもん個人のパソコンでやって結果だけコピペしても面白くもなんともない
ネットのプログラムサービスとかで完走できるサイズに設定しとけや お題:文字列を入力すると文字列が右に移動を始め画面の端に当たったら当たった側の文字が一つ削れて今度は左に移動しそれを繰り返し最終的に文字がなくなるまでアニメーションするプログラムを作成せよ。 ブラウザでコード描いて実行する環境はいくつかあるけど
ANSIエスケープシーケンスとか解釈してくれるコンソール出力付きの環境ってある? >>738 octave
・for無しでa,b,cを算出(ただしfor版>>771より遅い)
・n = 1234567 でメモリ不足でオチる(bがクソデカサイズ)
・データの型をint32にしてみたりもしたが焼け石に水だし少し遅くもなるのでdoubleに戻した
https://ideone.com/aosEo2
function [isprime, primes] = sieve_of_eratosthenes(n)
if n < 2; isprime = [], primes = [], return; end
isprime = [false true(1, n-1)];
for i = 2:sqrt(n)
if isprime(i); isprime(i*i:i:n) = false; end
end
primes = find(isprime);
end
n = 123456
[isprime, primes] = sieve_of_eratosthenes(n);
a = primes(primes <= n / 3)';
b = primes.*(a <= primes & primes <= (n - a) / 2);
c = (n - a - b)(b ~= 0);
count = sum(isprime(c)) >>775
PowerShellで全角文字、等幅フォント限定
$s = "プログラミングのお題スレです。"
$w = $Host.UI.RawUI.WindowSize.Width - 1
$c = $Host.UI.RawUI.CursorSize
$Host.UI.RawUI.CursorSize = 0;`
foreach ($n in $s.length..0) {
$d = $w - 2 * $n
$m = $s.length - $n
foreach ($x in ((1..$d), ($d..1))[$m % 2]) {
$l = "`r" + " " * $x + $s.SubString([Math]::Floor($m / 2), $n) + " " * ($d - $x)
Write-Host $l -NoNewline
if (!$n) {Write-Host; break}
Sleep -m 20
}
}
$Host.UI.RawUI.CursorSize = $c >>774
フーリエ変換でなぜ計算できるのか知らないが、とりあえずRに移植してみたら
5秒で完了できなかった。www.ideone.com/nhGFqi
tio.runで実行したら5.975秒かかった。fft関数がRのよりnumpyのの方が速いのか?
RのはUses C translation of Fortran code in Singleton (1979)だそうだが。 >>780
数え上げの問題を形式的冪級数の議論に対応づけることができる
形式的冪級数同士の積は長さ n が2の冪なら高速フーリエ変換による畳み込みで O(n log n) で計算できる
Rのfftはおそらく高速になる2の冪の長さのfftをしていないんだと思う この程度の桁数ならfft使う意味などない
ハードのfpuで計算に勝てるはずがない
fft使うメリットなんぞ数万桁とかいかないとでないやろ >>781
Rの標準のfft関数は遅いようなので、fftwパッケージのFFT, IFFT関数に替えたら
実行時間は半分くらいに短縮されたが、ideoneではfftwパッケージがインスール
されていなくて実行できなくて残念。
library(fftw)
conv <- function(f, g) round(Re(IFFT(FFT(f) * FFT(g))))
n <- 1234567L
isprime <- c(FALSE, rep(TRUE, n - 1))
for (i in 2:sqrt(n)) if (isprime[i]) isprime[seq(i + i, n, i)] <- FALSE
N <- nextn(2 * n + 1, 2)
x <- c(0, as.double(isprime), rep(0, N - n - 1))
count <- conv(conv(x, x), x)[n + 1]
i <- 2:(n %/% 2 - 1)
k <- sum(isprime[i] & isprime[n - 2 * i])
cat((count - 3 * k) %/% 6 + k, "通り\n", sep = "") fftなんぞ使って早くなんかならんというに
原理わかってんの?
例えばHaskellの標準のinteger型は何万桁でも計算できる、その際fftで掛け算するので数万桁まで行ってもそこそこ早い
しかし逆に32bitで収まるような計算だと遅くなる
だから“この計算はfftなんか使わなくていいよ、int32の範囲で収まるからそれで計算してね”と専用の型がいっぱいある
Rがそれで早くなるなら素の標準計算がしょぼいとかインタプリタ特有の話
そもそも計算速度気にする場合にRを選択してる時点で筋違い >>785
遅い言語でも工夫次第で制限時間を突破できないかというのがスレの流れなので、
そういう当たり前な突っ込みは野暮というもの。速い言語での正攻法の回答例は
>>746にちゃんと書いた。 だからそこでfft使うなんてのがわかってないって言ってるの
わからんかね? >>787
忖度して読み取ると多倍長整数の乗算の話をしているのだと思うけれど >>738 の問題を解く上ではそもそもあまり関係がない
素数になる次数の係数が 1 でそれ以外が 0 の形式的冪級数を考えてそれを3回乗算して N = 1234567 の次数の係数を求める問題に帰着させているだけ まぁ上の方のレス見ればわかる通りそもそも本人fftの理論何にも勉強した事なさそうでちゃんと勉強した人間(というかちゃんと勉強してなくてもわかる事だけど)>>378の話になんも関係ないってわからんのかな?
しかもそのレベルで噛みついてくるからタチ悪い なんか日本語変になったな
なんで勉強もした事ない話しで他人に噛みついてこれるんだろう? 炎上学習法というのがある
相手に噛みついて解説させて勉強する手法 問題
Σ[n: 1→4000](1/√n)
の整数部を答えよ フィボナッチ数列のn番目の整数zだけ表示するプログラムを書きなさい。
ただし、zが3、5、15のいずれかで割り切れる場合はzの後に改行を挿入して、
"割り切れる"と表示しなさい。
1, 1, 2, 3, ... n
【条件】
1 <= n <= 100000000000 まぁ最後の条件は最後の1桁まで計算させるつもりなんかもしれないけど
5 | Fₙ ⇔ 5 | n
だから意味はないわな >>738
https://paiza.io/projects/0QCNbnKzWMHspiarmHa0Tw
細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた
総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる >>797
解説プリーズ
コード読んでもさっぱりわからん
どうやってO(N)にできたんですか? アレ?
やっぱりこれ三乗してるんじゃないの?
O(N)ちゃうやん
O(N)の意味わかってる? >>797
確かに無駄は大分省けたな。Rでも同じようにしたらばっちり完走できた。
www.ideone.com/7lob9A イヤ、整数計数の多項式環の三乗もfftで早くできるのかな? もしかしたらできるか
fftのアルゴリズムってこっちのコンボリューション積をあっちの各点積に持っていく方法だから多項式環でもできるんかな? >>798
大体わかっているみたいだけど少し丁寧に書いてみる
素数次数の係数が 1 でそれ以外の係数が 0 の形式的冪級数 f を考える
f^3 の k 次の項の係数は 素数 3 個を選んで足した和が k になる場合の数になるので今回は k = 1234567 の係数を求めたい
長さ N の多項式の積は高速フーリエ変換による畳み込みで O(N log N) で計算できるので形式的冪級数を前から必要なだけとって多項式にして適用する
また取りうる値が大きくて誤差が問題になるときは数論変換と中国剰余定理で復元する方法もあるけど今回は不要
3乗している対象は配列の各項なのでそこはボトルネックにはならない うん、やっとわかった
fftの計算への応用つて真っ先に整数そのものの掛け算が思いついてしまうけど、別に整数そのものの掛け算でなくてもいいわけだ
完全に目からウロコ >>795
とりあえずHaskell
10000項くらいまではちゃんと動くよう
Haskellの整数型は一応規格上の制限はないみたいだけど多分GHCには流石に制限あるだらうから何項まで動くか不明 お題
15時間20分を15.2と表記するとして
15.2+2.4=18.0時間って計算させるにはどうやればいいの? 整数部分と小数部分に分ける
小数部分は2桁とみなす
60進数の小数点数として扱う >>807
Rだと自作のクラスでなくても演算子を再定義できてしまうから、そういう奇妙な表記の
数式での計算も可能。
www.ideone.com/xzSCyt >>807 octave
https://ideone.com/S0EqvY
function c = f(a, b)
m = (fix(a) + fix(b)) * 60 + round((a - fix(a) + b - fix(b)) * 100);
c = fix(m / 60) + rem(m, 60) / 100;
end お題 Fourier 変換
長さが2べきの複素数の列が与えられます
(複素数はDouble型2つのタプルで表現するとする)
そのFourier変換である同じ長さの列を計算する関数を実現して下さい
またそれを利用して同じ長さの畳み込み積を計算する関数を実現して下さい
(但し書き)
長さNの数列(aₙ)のFourier変換F(aₙ)とは第k項が
Σ[n=0,N-1] (cos(2πkn/N) + isin(2πkn/N))aₙ
である列を与える変換とする
その逆変換F⁻¹(aₙ)は第k項が
1/NΣ[n=0,N-1] (cos(-2πkn/N) + isin(-2πkn/N))aₙ
で与えられる変換である
数列(aₙ)と(bₙ)の畳み込み積とは
F⁻¹( F(aₙ) × F(bₙ) )
で与えられる積である、ただしこの×は各項毎の積で与えられる列である (例)
・F (a,b,c,d) = (a+b+c+d, a+bi-c-di,a-b+c-d,a-bi-c+di)
・F(1,2,3,0,0,0,0,0) =
6.0 :+ 0.0
2.4142135623730954 :+ 4.414213562373095
(-1.9999999999999996) :+ 2.0
(-0.4142135623730949) :+ (-1.5857864376269046)
2.0 :+ 0.0
(-0.4142135623730949) :+ 1.585786437626905
(-2.0000000000000004) :+ (-2.0)
2.4142135623730945 :+ (-4.414213562373096)
・1,2,3,0,0,0,0,0と4,5,6,0,0,0,0,0の畳み込み積
=
3.999999999999999 :+ 2.6645352591003757e-15
12.999999999999998 :+ (-1.6730659520119792e-15)
28.0 :+ (-5.773159728050814e-15)
27.0 :+ (-5.432361405589022e-15)
18.0 :+ (-8.881784197001252e-16)
1.7763568394002505e-15 :+ 3.656004566188772e-15
1.7763568394002505e-15 :+ 3.9968028886505635e-15
0.0 :+ 3.4494227914122297e-15 お題(難易度★)
a=1のとき、b=1000000
a=2のとき、b=999999
a=3のとき、b=999998
上記の法則を元に、aがnのときのbの値を求めなさい >>813 py
import numpy as np
from scipy.optimize import least_squares
data = np.array([
1000000,
999999,
999998,
999997,
])
def poly_2d(x, a, b, c, d, e, f):
return a * x**5 + b * x**4 + c * x ** 3 + d * x ** 2 + e * x + f
def residuals(params, data):
a, b, c, d, e, f = params
res = []
for x in range(1, len(data) + 1):
res.append(data[x - 1] - poly_2d(x, a, b, c, d, e, f))
return res
initial_guess = [1, 1, 1, 1, 1, 1]
result = least_squares(residuals, initial_guess, args=(data,))
a, b, c, d, e, f = result.x
print(f"fn = lambda x: {a:.6f}*x**5 + {b:.6f}*x**4 + {c:.6f}*x**3 + {d:.6f}*x**2 + {e:.6f}*x + {f:.6f}")
fn = lambda x: round(a*x**5 + b*x**4 + c*x**3 + d*x**2 + e*x + f)
print(fn(1))
print(fn(2))
print(fn(3))
print(fn(4))
fn = lambda x: -9433.011975*x**5 + 81785.062791*x**4 + -204704.849008*x**3 + 32573.601042*x**2 + 400859.570602*x + 698919.625800
1000000
999999
999998
999997 >>813 octave
https://ideone.com/7v5QU9
f = @(n) polyval(polyfit([1 2 3], [1000000 999999 999998], 1), n); >>805
Haskellのオジチャンは 一体どこに回答を書いたんだろう… Haskell爺さんはリンクを書き忘れましたとさ
メデタシメデタシorz
https://ideone.com/TTY3nD お題: 入力を(x, minv, maxv)の3整数とする。xを閉区間[minv, maxv]に制限した値を返すプログラム(ただしminv≦maxv)。
例)
(1, 3, 5)→3.
(100, 5, 120)→100.
(208, 5, 120)→120. >>819 octave
https://ideone.com/gn1GYh
f = @(x, minv, maxv) min(max(minv, x), maxv); お題: 2次元ソート。
与えられた比較関数Compare2Dを用いて2次元のデータを並べ替える。
typedef int DATA;
int Compare2D(DATA left, DATA above, DATA target);
左端でも上端でもない、ターゲットのデータについて
引数leftは一つ左のデータ、
引数aboveは一つ上のデータ、
引数targetはターゲットのデータとする。
比較関数の戻り値は、比較結果が小さいとき-1に、同じとき0に、大きいとき1になる。
比較関数Compare2Dとソートアルゴリズムを適当に定め、アスキーコードの一部(0x20~0x5f)、つまり、アスキー表の一部を乱数で撹乱した二次元データをソートしたときに、
アスキー表の一部を表す長方形状になるようにし、ソート前の撹乱後の二次元データと、ソート後の二次元データを自然にわかりやすく出力するプログラムを作れ。 >>821
修正。比較関数は次の2つとする。
int CompareX(DATA left, DATA target);
int CompareY(DATA above, DATA target); >>822
お題を撤回します。熟慮が足りない。。。 >>819
PowerShell 6以上なら[Math]::Clampを、C++ 2017以上なら#include <algorithm>で
clampを呼び出すだけだな。 お題:数学的な処理を使って東京タワーっぽいアスキーアートを出力せよ
アスキーアートのクオリティは問わない >>811-812
Rでfft関数を使わずに式通りの低速変換。畳み込み積は普通に求めた値を左に併記した。
www.ideone.com/pUV71G >>811-812 Perl5、若いころ物理数学で勉強した記憶を呼び戻しながら、LibraryやComplex型を使用せず、また複素数をタプルで表して愚直に実装してみた。
長さが2のべき乗とのことだがバタフライ演算による計算量の低減は実装していない。なお10^-15乗などの微小な数値の仮数部がお手本解と異なるところがあるが計算誤差によるもので実質0だと思う。
(やっぱ記号を使った数式よりも物理的な意味やイメージと対応付けて捉える方が俺にとってはしっくりくるわ)
use utf8;
use constant PI => 3.141592653589793;
use feature qw{signatures say};
sub 基底($波数, $N) { [map{[cos(2*PI*$波数*$_/$N), sin((2*PI*$波数*$_/$N))]} 0..$N-1] }
sub 複素数の積($a, $b) { [$$a[0]*$$b[0] - $$a[1]*$$b[1], $$a[0]*$$b[1] + $$a[1]*$$b[0]] }
use List::Util 'reduce';
sub 積和相関($x, $e) { reduce{[$$a[0]+$$b[0], $$a[1]+$$b[1]]} map{複素数の積 $$x[$_], $$e[$_]} 0..$#$e }
sub FT(@s) { map{ 積和相関(\@s, 基底($_, scalar @s)) } 0..$#s }
sub iFT(@s) { my $n = @s; map{[$$_[0]/$n, $$_[1]/$n]} map{ 積和相関(\@s, 基底(-$_, $n)) } 0..$n-1 }
sub CV($a, $b) { my @c = FT(@$a); my @d = FT(@$b); iFT( map{複素数の積 $c[$_], $d[$_]} 0..$#c ) }
sub prti { join(', ', map{"$$_[0]". (0 <= $$_[1] and '+') ."$$_[1]i"} @_) }
my @a = ([1, 0], [2, 0], [3, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]);
my @b = ([4, 0], [5, 0], [6, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]);
say 'FT: ', prti FT(@a);
say 'CV: ', prti CV(\@a, \@b);
実行結果
$ perl 21_811_FT_CV.pl
FT: 6+0i, 2.41421356237309+4.41421356237309i, -2+2i, -0.414213562373095-1.5857864376269i, 2-4.89858719658941e-16i, -0.414213562373094+1.58578643762691i, -2-2i, 2.41421356237309-4.4142135623731i
CV: 4+2.66453525910038e-15i, 13+1.77635683940025e-15i, 28+8.88178419700125e-16i, 27-5.77315972805081e-15i, 18-1.77635683940025e-15i, -6.21724893790088e-15-7.99360577730113e-15i, 8.88178419700125e-15+7.105427357601e-15i, 1.24344978758018e-14-2.8421709430404e-14i お題(難易度★★)
0, 1, 2, 3, 6, 11, 20, 37 ...
上記の数列の法則を元に、n番目の整数aを求めるプログラムを作成せよ
【条件】
3 <= n <= 1000
【例】
n=6なら、a=11となる
n=9なら、a=68となる constexpr int foo(int n){
constexpr int t[] = {1, 0, 1, 2, 3, 6, 11, 20, 37, 68};
return t[n % std::size(t)];
}
これでOK
ルールを推測させる系は出題側の意図した答えを出させるためにどう制限かけるかが問われる あーあ、お前が潜水艦に乗って爆縮されたら良かったのにな~ 潜水艦の操縦がゲームコントローラとかワクワク感たまらねぇ
マジレスするとRustで造ってれば安全だったはず >>830 ruby
https://ideone.com/lOvKLI
g = ->(m) {
a = (3...m).inject([0, 1, 2]) {|a, _| a << a[-1] + a[-2] + a[-3]}
->(n) {n < 1 || m < n ? nil : a[n - 1]}
}
f = g.(1000)
p [*0..9, 1000, 1001].map {|i| [i, f.(i)]}
↓
[[0, nil], [1, 0], [2, 1], [3, 2], [4, 3], [5, 6], [6, 11], [7, 20], [8, 37], [9, 68], [1000, 1258890285439289522674621215321790399357402658069918084564035590888323288383996894058630489346490443306057821146808944309219589954636534445475146599057985479816395429617207869586544429749851128733512216004490332659216184693670760709292866744282443549293609850952277], [1001, nil]] >>830
Rでnが大きい場合にも高速に計算(例のnでは意味がないが)
www.ideone.com/FrR91K
C#でHaskell風の遅延評価による無限数列生成
www.ideone.com/ZZhdwh
初期値が一般的な値と異なってもトリボナッチ数列と呼んで良いようなので関数名はそうした。 >>830 Perl5
use feature qw{signatures say}; no warnings 'experimental';
use bigint;
sub g($n, @a) {
push(@a, $a[-3]+$a[-2]+$a[-1]) while @a < $n;
$a[-1];
}
say g($_, (0, 1, 2)) for 6, 9, 1000;
#見易くするためインデントは全角スペースに置換してあります。
実行結果(CPU: Core-i7 8559u)
$ time perl 21_830.pl
11
68
1258890285439289522674621215321790399357402658069918084564035590888323288383996894058630489346490443306057821146808944309219589954636534445475146599057985479816395429617207869586544429749851128733512216004490332659216184693670760709292866744282443549293609850952277
real 0m0.143s
user 0m0.061s
sys 0m0.062s この問題10年前ぐらいで外資系のスキルテストで見たことあるな この手の代数系のn乗計算に持ち込めるタイプは
a^(2n) = (a^n) × (a^n)
a^(2n+1) = (a^n) × (a^n) × a
を利用する実装ができてるかがミソやな >>738
C
https://ideone.com/JGH96u
まぁスーパー亀レスなんだけど普段はHaskellerなのでなんとかHaskellで完走できないかとアレやコレやと考えてみたんだけどダメだったorz
多分競プロに出るようなスーパーHaskellerならなんとかなるのかもしれないけど諦めた、試合終了
しかしせっかく色々考えたので備忘録がわりにCに移植
やっぱりCはえー、Haskellだと1分近くかかる計算が0.5秒とか
使ったのは有限体上のFourier変換
p = 1272446977、buffer size = 524288
で計算、buffer sizeを稼ぐためにBuffer sizeが2べきでなくても使えるように組んだんだけどCならそんなもんこだわらなくても余裕の完走なので結局2^19で利用
逆フーリエ変換も不要だと後で分かったけどせっかく作ったので残してあります >>819
Kotlin
Kotlin には coerceIn() というずばりそれをするための拡張関数があったのでそれを使った。
ついでに入力で負の値も受け付けるようにした。
https://paiza.io/projects/kOpfBfJtefVllIjHTVVX1g お題(初級)
a+b=cの式において、cが5で割り切れるためのaとbの組み合わせは何通りあるか
条件
1 <= c <= 10000000 無限なわけ無いだろと思ったけどa, bが自然数とは指定されてないからなぁ お題:配膳ロボット。
あるレストランでは1台の配膳ロボットが活躍している。
配膳ロボットの仕事は、キッチンまで料理を取りに行き、
シェフに料理をもらい、料理をお客様まで持っていくことだ。
フロア図(上が北):
#######
#____C#
####_##
#K_#__#
##___R#
#######
#:カベ。K:キッチン。R:ロボット。C:お客様。_:空きスペース。
ロボットには次のようなコマンドが定義されている:
コマンド0:1つ待つ(料理を載せるのに必要な待ち時間)。
コマンド1:西に1つ移動。
コマンド2:東に1つ移動。
コマンド3:北に1つ移動。
コマンド4:南に1つ移動。
入力の盤面からロボットの仕事を完了するコマンドリストを生成せよ。
生成例)(1, 1, 1, 3, 1, 0, 2, 4, 2, 2, 3, 3, 3, 2, 0). >>854
R
www.ideone.com/TmKZmx >>855はもう少しすっきり書けた。
www.ideone.com/A4TRQe >>856
フロア図を変えても動くかな?
解法を少し解説お願いします。 >>857
フロア図を変えた場合の実行例
www.ideone.com/vFtBf4
出発位置から目的位置まで複数の経路がある場合は最短経路が選択されるようになっている。
解法は単純で、行列Aの途中経過表示を見れば分かるように、出発位置fromからi + 1個の
コマンドで行ける位置にi + 1と印をつける操作を、i = 1, 2, 3, , ...について順々に、
目的位置toに到達するまで繰り返すだけ。 お題:点と長方形の当たり判定。
「x0≦px<x1かつy0≦py<y1」のときtrueを返し、その他のときfalseを返す
関数PtInRect(px, py, x0, y0, x1, y1)を作成せよ。
例)
PtInRect(1, 2, 2, 2, 4, 3)→false.
PtInRect(3, 2, 2, 2, 4, 3)→true.
PtInRect(3, 3, 2, 2, 4, 3)→false.
PtInRect(4, 4, 3, 2, 5, 5)→true.
PtInRect(5, 4, 3, 2, 5, 5)→false. >>859
Kotlin script
fun PtInRect(px: Int, py: Int, x0: Int, y0: Int, x1: Int, y1: Int) = x0 <= px && px < x1 && y0 <= py && py < y1 お題: テキストキャンバス、再び。
ヨコ20文字×タテ5文字の長方形の半角空白のテキストキャンバスがある。
(1) キャンバスの(x, y)の位置に半角文字chを書き込む関数SetPixelV(x, y, ch)を作成せよ。
(2) SetPixelVを使ってx0≦x≦x1かつy0≦y≦y1を満たす長方形領域(x, y)を半角文字chで塗りつぶす関数FillRect(x0, y0, x1, y1, ch)を作成せよ。
(3) テキストキャンバスを表示する関数PrintCanvas()を作成せよ。
(4) 次の処理を実行せよ。
FillRect(3, 0, 7, 4, '#');
SetPixelV(3, 0, ' ');
SetPixelV(3, 4, ' ');
SetPixelV(7, 4, ' ');
SetPixelV(7, 0, ' ');
FillRect(4, 1, 6, 3, ' ');
FillRect(11, 0, 11, 4, '#');
SetPixelV(12, 2, '#');
SetPixelV(13, 1, '#');
SetPixelV(14, 0, '#');
SetPixelV(13, 3, '#');
SetPixelV(14, 4, '#');
PrintCanvas(); >>861
R 関数の引数には正しい値が与えられるものとし、エラーチェックは省略
www.ideone.com/lb8qym お題: レーザーでカラスを撃退。
右手系の三次元空間に強力なレーザー光を放射できるレーザー砲塔(ほうとう)が原点(0, 0, 0)にある。この砲塔は最初はx軸方向を向いている。
砲塔では以下のコマンドが利用可能だ。
- Turn(Pan, Tilt): 砲塔を水平方向にPanラジアン右向きに自転し、垂直方向にTiltラジアン上向きに自転するコマンド。PanとTiltの値は負でもよい。
- Fire(): 現在の向きにレーザーを放射するコマンド。
カラスの位置(x, y, z)が入力されたら、そのカラスを撃退するコマンドリストを生成せよ。
砲塔の向きはその都度、記憶するものとする。
角度を求めるのにatan2関数を使ってもよい。各数値は小数点以下2桁まで表示せよ。
例) (1, 0, 0)→(Fire()).
(0, 0, 2)→(Turn(π/2, 0), Fire()).
(0, 3, 0)→(Turn(0, π/2), Fire()).
(1, 2, 1)→???
※ カラスは鳥獣保護法で保護対象です。 Turn(Pan, Tilt) は何回使っても良いのかな?
それとも 2回以上使うときは Turn(Pan, Tilt) と Turn(Pan, Tilt) の積を計算した上で
1回にまとめるべき? 大学でちゃんと講義受けてたのかどうか知らんけど
各数値は小数点以下2桁まで表示せよ。
もうこう言う言い回しをするのはやめた方がいい >>867
初期化ミスってた。こっそり直しておいた。 >>864
例は
(1, 0, 0)→(Fire()).
(0, 0, 2)→(Turn(0, π/2), Fire()).
(0, 3, 0)→(Turn(0, -π/2), Fire()).
(1, 2, 1)→???
じゃないの?
だとしてR
www.ideone.com/ddFJ7j >>871
ごめんごめん、正しくは右手系でz軸が上向き。訂正。
(1, 0, 0)→(Fire()).
(0, 0, 2)→(Turn(0, π/2), Fire()).
(0, 3, 0)→(Turn(-π/2, -π/2), Fire()).
砲塔の向きを記憶すると書いてある。また(0, 3, 0)でy軸方向を向くのにPanが必要だから、こうだろう。すみません。 >>872
(0, 0, 2)つまり真上から(0, 3, 0)つまり水平真北へ向きを変えるには、水平方向回転は不要で
下向き90度の垂直方向回転だけでできるんじゃないの?
もしそうでなく>>872のように水平回転も必要という仕様なら、>>871の6行目を
Pan <- c(0, -diff(atan2(P[, 2], P[, 1])))
に変えれば良い。 >>873
うん、水平回転も必要。真上を向いていると垂直方向の意味がわからないからね。 お題:半角スペースで区切られた単語が並ぶ文字列がある
この文字列を単語に分割してソートして配列にして返す関数を実装せよ >>875
PowerShell
function ExtractAndSortWords($s) {[RegEx]::Matches($s, "\w+") |% {$_.value} | sort}
ExtractAndSortWords "The quick brown fox jumped over the lazy dog." |% {$_}
[実行結果]
brown
dog
fox
jumped
lazy
over
quick
The
the >>875 Perl5、出現した単語の重複を許容するか、あるいはuniqにするか明確でないけど、下記は許容する方法
sub f { sort shift =~ /(\w+)/g }
実行結果
https://ideone.com/FjaIX7 お題:放物運動の飛距離。
重量5[kg]の物体が、入力として与えられた仰角[deg]と初速[m/s]で発射され、自由落下する。
空気抵抗は、速度に比例する大きさの力とする。地平は平面と見なす。
時刻t[s]に対してdt=0.1[s]とし、台形求積法を使用するものとする。
空気抵抗係数 k=0.24[kg/m].
重力加速度 g=9.8[m/s^2].
空気抵抗のある場合の飛距離と、空気抵抗のない場合の飛距離を求め、比較せよ。
入力例)
(30, 8)→???
(45, 8)→???
(60, 8)→???
(60, 12)→??? >>879
時間刻み幅が粗すぎて着地時刻を適切に判定できないから、飛距離も求められない。
軌跡のグラフを描いて大体の位置を読み取るしかない。
R
www.mycompiler.io/view/K4qPKREzkRI
[コードを実行] ボタンを押すとグラフが表示される。白丸が空気抵抗なし、黒丸があり。 >>880
天才がおる。
君ならICBMの計算も出来そうだ。
ちょっと試してみようか。 >>875
Kotlin
なんとなく拡張関数で作った。まあでもsplit使っちゃってて肝心な所は自分では何も書いてないな。
https://paiza.io/projects/j1jz6yNCVfWZLIv8d5RFjA >>880の14行目は
a <- c(0, -g) - k * (v + a * dt) ^ 2 / m
でなく
a <- c(0, -g) - k * (v + aprev * dt) ^ 2 / m
の方が良かった。精度が少しだけ上がる。 お題:62進数の計算
62進数の整数の加・減・乗算から成る式の文字列が入力される。計算結果を62進数の文字列で出力せよ。
ただし、10進数の0〜9, 10〜35, 36〜61に相当する数字にはそれぞれ0〜9, A〜Z, a〜zを用い、
計算の途中経過と最終結果は64ビット符号付き整数の範囲内に収まると想定して良い。
[例]
入力: 123 + ABC
出力: 123 + ABC = BDF
[問題]
2023-7-4
printf - (Hello + world)
Windows * 11
The - quick - brown * fox + jumped - over + the - lazy * dog
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ >>884
Perl
計算面倒だから文字列の状態で数値部分を10進数に変換してから eval 使うという手抜きプログラム。
その代わり割り算や割った余りも出せる。( / と % )。ただし結果の出力が整数でしか出ない。
結果が負の値になってもマイナス付けて出せるようにした。
https://paiza.io/projects/zf3aXm60nlM59-TjhoiEyQ >>886
>Perl
>計算面倒だから文字列の状態で数値部分を10進数に変換してから eval 使うという手抜きプログラム
それでOK。出題者が事前に書いたRとPowerShellのプログラムもまさにそのやり方。構文解析を
自前で書かせるつもりはなかった。整数同士の割り算は結果が言語により異なるので問題から外した。
www.ideone.com/L0fgm6
www.ideone.com/J2cLd2 (実行結果は上と同じ)
RubyとPythonもevalを使えるので似たように書けるはず。なんかPとRで始まる言語ばかりだな。 Parser generator使って自前で構文解析&計算させようとして苦戦していた俺涙目 >>890
オレもParser generatorでやろうと思ってるよ
eval なんか使えないからね
でも日曜日までまとまった時間ないからまたまた超遅レスになる予定 お題: 緯度と経度から距離と方位を求める。
地球が球体であると仮定し、地球の半径を6378[km]とする。
緯度と経度を角度[deg]で与える。
北緯と西経は正の値で、南緯と東経は負の値で与えるものとする。
二点ABの緯度と経度を与えるとき、ABの距離d[km]と、AからBへ向かう方位角φ[deg]を求めよ。
方位角は北:0度、東:90度、南:180度、西:270度とする(時計回り)。
例)
A(139.74477, 35.6544), B(39.8261, 21.4225)
→(9491, 293).
参考) https://keisan.casio.jp/exec/system/1257670779 >>892
R
www.ideone.com/S5Jubo >>892
完全にぴったり地球の表裏側2点の場合の方位角は? お題: 緯度経度を三次元座標に変換。
地球を半径6378[km]の球体だと仮定し、地球の中心を三次元空間の原点とする。この空間は右手系である。
原点より緯度0度経度0度の地点に向かう向きをx軸方向とする。
また原点より北極点に向かう向きをz軸方向とする。
入力として与えられた緯度経度のペア[deg^2]を三次元座標[km^3]に変換せよ。
例)
(0, 0)→(6378, 0, 0).
(90, 0)→(0, 0, 6378).
(45, 0)→??? (0, -45)→???
(45, -45)→??? (30, -45)→??? >>884 Perl5、見易くするためインデントは全角スペースに置換してあります。
use feature qw{signatures}; no warnings 'experimental';
use Parse::RecDescent;
sub ope($valp, @args) { my $val = $valp->();
while (@args) { my ($op, $parm) = splice @args, 0, 2; $op->($val, $parm->()); } $val }
%d = map{$_ => $i++} 0..9,'A'..'Z','a'..'z';
%e = map{$d{$_} => $_} keys %d;
use List::Util 'reduce';
sub dec($d62) { reduce {$a*62 + $b} map{$d{$_}} split '', $d62 }
my $parse = new Parse::RecDescent <<'End';
expr: <leftop:term addsub term> {sub { ::ope @{$item[1]} }}
addsub: '+' {sub { $_[0] += $_[1] }} | '-' {sub { $_[0] -= $_[1] }}
term: <leftop:factor muldiv factor> { sub {::ope @{$item[1]} }}
muldiv: '*' {sub { $_[0] *= $_[1] }} | '/' {sub { $_[0] /= $_[1] }}
factor: dig62 | '(' expr ')' { $item[2] }
dig62: /[0-9A-Za-z]+/ {sub { ::dec $item[1] }}
End
sub enc($d) { my $r = $d % 62; $d = int(($d - $r) / 62); $d ? (enc($d) . $e{$r}) : $e{$r}; }
for (<DATA>) {
$n = $parse->expr($_)->();
$n = $n < 0 ? '-' . enc(-$n) : enc($n);
print "$_ = $n\n";
}
__DATA__
123 + ABC
4 - K
2023-7-4
printf - (Hello + world)
Windows * 11
The - quick - brown * fox + jumped - over + the - lazy * dog
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ >>898 の実行結果:
$ perl 21_884_calc_dig26.pl
123 + ABC
= BDF
4 - K
= -G
2023-7-4
= 201s
printf - (Hello + world)
= odFAME
Windows * 11
= XFWRSlos
The - quick - brown * fox + jumped - over + the - lazy * dog
= -Q1YGAW2x
ABCDEFG + HIJKLMNOP + QRSTUV + WXYZ
= HITvzYcgj
※ Parse::RecDescentという再帰降下型Parser generatorのperl moduleを使用したので、
動作させるにはそのインストールされている必要がありますが、ideonなどのオンライン
プログラムサービスには多分インストールされていなくて動作しないんじゃないかなともいます >>897
R
www.ideone.com/RHXhIq
変哲は、普通に書くとsinとcosが合わせて4個か5個必要な所を2個にしたことだけ。 >>898
ならば出題者からもeval任せでない自前の実装プログラムをどうぞ。
C
www.ideone.com/erwpI4
「C言語による最新アルゴリズム事典」に載っている10進小数の四則演算式評価プログラムを
ちょっと改変したらサッと作れた。
C++
www.ideone.com/MFEuc6
Cプログラムのグローバル変数と下請け関数をクラスに入れて隠蔽した。readch関数のかわりに、
空白を読み飛ばすようにオーバーライドした++演算子を使ってすっきり書いた。 四則演算の式評価なら1数十stepでParserを手書きできるということでそれもありじゃね? うーん、まぁそれはそうも言えるかな
しかしその手の話は結局“車輪の再発明”してるだけだからな
parsingみたいに重たい処理は可能なら既存の実績のあるparser generator使えるならそれ使うのか本筋な気はするけどね
初学者がparsingの基礎の練習問題として使うのはありかな GCCやCLangも何とparserはyaccなど使わずに手書きなんだそうだ。
理由は下記サイトなど参照。きめ細かいエラー処理など可能になるかもしれないがコードはとても込み入って大変そうだわ。
c - Are GCC and Clang parsers really handwritten? - Stack Overflow
https://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten まぁ物によるだろうけどほとんどのプログラミング言語は最低でも文脈依存文法以上を解析できるパーサーでないと解析できない
ましてや今日のコンパイラは何行目の何文字目がおかしいのか、それがどんな間違いなのかも示して修正案まで出してくれる、そこまでの作業を一般的なパーサー生成機に落とし込むこと1から考えるよりはパーサーそのもの自分で作る方が早いかもしれんわな
ただ今回のは四則演算とカッコだけなんだから文脈自由文法の解析機で解析できるから素人が作った解析機を使わない意味は実用上はまずない、まさに車輪の再発明の典型になってしまう
しかしまぁここはある意味“再発明を楽しむスレ”でもあるからなw 専門家の作った解析機を使わない意味はないだorz
まぁただパーサー生成機の作ったパーサーはもちろん「どんな文法でも対応できる」ために効率を犠牲にする場合もあるので速度とかをギチギチにチューンするつもりなら意味はあるか
実際今回のも()と+,-,×だけやからな お題: 飛翔体のシミュレーション。
クレムリン(北緯55度東経37度)から東京(北緯35度東経139度)に向けて初速12[km/s]、重量30[kg]の飛翔体が発射される。
地球は半径6378[km]の球体と仮定し、重力加速度を9.8[m/s^2]とする。
飛翔体は噴射せず自由落下すると仮定する。空気抵抗は考慮しない。
発射時刻をt=0[s]とするとき、t=120とt=240のときの飛翔体の座標[deg^2]を求めよ。
(この情報はフィクションであり、架空のものです。実際の軍事情報とは関係ありません) 最後の注意書きが寒い
だったら最初から固有名詞出さなきゃ良いのに >>908
防衛装備移転三原則に反する恐れがあるので、このお題は撤回致します。回答しないで下さい。 自分の書き込みにそんなに勝ちがあると思ってるのかこいつ
スベってるよ >>897 Perl5、見やすくするためインデントは全角スペースに置換してあります。
たまには回答して進ぜるけど、もしかして回答欲しくて簡単なお題だしたん?
use Math::Trig qw{pi deg2rad spherical_to_cartesian};
use constant ra => 6378;
for (<DATA>) {
($lo, $la) = map{deg2rad($_)} /(-?\d+)/g;
# 球面→cartesian座標変換library使用
$phy = pi / 2.0 - $lo;
($x, $y, $z) = spherical_to_cartesian(ra, $la, $phy);
printf "L) (%.3f, %.3f)[rad] -> (%.1f, %.1f, %.1f)\n", $lo, $la, $x, $y, $z;
# 手書き
$ralo = ra * cos($lo);
printf "H) (%.3f, %.3f)[rad] -> (%.1f, %.1f, %.1f)\n", $lo, $la,
$ralo * cos($la), $ralo * sin($la), ra * sin($lo);
}
__DATA__
(0, 0)
(90, 0)
(45, 0)
(45, -45)
実行結果
$ perl 21_897_緯度経度→xyz.pl
L) (0.000, 0.000)[rad] -> (6378.0, 0.0, 0.0)
H) (0.000, 0.000)[rad] -> (6378.0, 0.0, 0.0)
L) (1.571, 0.000)[rad] -> (0.0, 0.0, 6378.0)
H) (1.571, 0.000)[rad] -> (0.0, 0.0, 6378.0)
L) (0.785, 0.000)[rad] -> (4509.9, 0.0, 4509.9)
H) (0.785, 0.000)[rad] -> (4509.9, 0.0, 4509.9)
L) (0.785, -0.785)[rad] -> (3189.0, -3189.0, 4509.9)
H) (0.785, -0.785)[rad] -> (3189.0, -3189.0, 4509.9) お題:神経質なipow10()
整数を引数とし、その10のべき乗を浮動小数点数で返す関数を書け。
結果が浮動小数点数で厳密に表現出来ない場合(10の-1乗=0.1とか)、
浮動小数点数として、(結果を)厳密に最近値に丸めた値を返すこと。 正の整数の範囲だけなら、CPythonのmath.pow()もそう悪くないんだ…
(10**23と10**210が外れ)。
tps://sagecell.sagemath.org/?z=eJxdjUEKwyAURPeB3GG601REt4WeRVxo86H6xQhNb18lLaWd5Zt5TKycsD03UCpcG-KdfXOUI89THF3ybf2UhR-dcgWBMqrPtyC-gk5-d9a4sBecYeVlntBDcXjCGm0USOJ0PU46wbJ08t6NlEq5CVI_hl7DLqT6sw4qXzvIOGU=&lang=python&interacts=eJyLjgUAARUAuQ== この手の計算ライブラリではあるある
真値が無理数の場合次善策として“最近の値”を出す事、当然それ出してくれると思いがちだけどそんな値出してくれるライブラリなどほとんどない
原理的に出せないわけではない、適当にレジスタの精度を設定して上から、下からの近似値を出す、求める桁数まで一致してればそれが“最近”、一致してなければ精度上げて再計算‥を繰り返せば必ず最後は一致する‥でもそのために貴重な時間リソースが無駄になる、なので普通は“精度は±××、上からの近似の中では最良”くらいが関の山、それすら守ってなくても普通、ましてや“小数第何位までは確実に合ってる”などとは全く期待できない
そのあたりの“実用上それで十分、それ以上の事やって誰得?”と割り切れるまでが一週目 "1e23" とかの文字列を構成して、Cのstrtod()やsscand()的な関数を使って変換する分には誤差が出ないっぽいのですけど
(これの誤差が出るライブラリは駆逐されたらしい)、
これはこれで「負け」た気分になるのが…w 分母が2べきでない限り内部的に分母が2べきの有理数で保持するタイプの浮動小数は“定数”を10進のリテラルで与えるとそこで誤差が出たり、あるいはその逆もある、いわゆる基数変換誤差
多くの場合、基数変換誤差は計算の最初と最後でしかでないのでそもそもあまり話題にはならない、大昔のインタプリタ言語とかだったら計算結果を毎回10進表示に変換して文字列として保持してるようなやつもあっただろうけど、もう流石にそのタイプは駆逐されてるんじゃなかろか
大体そもそも他の組み込み関数の誤差評価がもっと大甘なのにそこだけ頑張っても意味がない 何で「負け」なのかと云うと、
IEEE754的な意味での「再現性」を担保する為に
(binary64の数値を有効桁17桁で10進文字列に変換して、
それをstrtod()とかするとbit perfectで元に戻るってやつ)、
strtod()とかは内部で多倍長演算をやってるので…。
(glibcの実装(GNU MPに丸投げ?)と、ルーセントの中の人
が書いたやつ(そのほか)の2系統あり)。
…なんとかズル出来ないのか?w 要するに牛刀割鶏感がでかい
いまさら気にしても仕方がなくもないけど そもそもコレ変数へ値をそんな自由に“セット”する方法がないんだよな
例えば値が10^(-30)として二進展開して
2^(-30)
=1.100_0010_1000_0010_0101_1111_...×2^(-103)
という巡回小数になる
単精度での内部表示は
0_00011000_100_0010_1000_0010_0110_0000
になる、なるとわかってもこの値を変数にセットす方法がない
おそらく整数0xc68660をセットして2^24で割ればいける時もあるかもしれないけどそれとて言語の保証外、浮動小数点型の変数に何か値をセットしてそれを2べきの整数で割ったとて、いくら“割る数”が2べきであっても仮数部わ変わらず指数部だけ変わってくれる保証をしてる言語の方が少ない
実験すればそれでうまくいくかどうかわかるかもしれないけどregulationでそれでうまくいくと保証されてるわけではない、せいぜい“多分うまく行ってる”くらいしかわからない
Cとかなら[char]型でa[0]a[1]a[2]a[3]に値入れてfloat &bにb=aするとかできるかもしれないけど最近の型にうるさい言語だとそれとてできない 0xc28260÷2^24乗ね
この計算をさせて本当に内部的に変数に0_00011000_100_0010_1000_0010_0110_0000
がセットされたかどうか確認する方法もない
もう一回2^24かけて0xc28260かけて戻ってくるかチェックするとかして間接的に確かめるしかない
Cとかputhonとかならできるのかもしれないけど お題: 入力として32ビット整数のビットマスクが与えられる。
ビットマスクに含まれる有効なビットの組み合わせをブルートフォースせよ。
例)
0x13
→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x45
→(0x1, 0x4, 0x5, 0x40, 0x41, 0x44, 0x45).
0x92C
→??? >>927
>→(0x1, 0x2, 0x3, 0x10, 0x11, 0x12, 0x13).
0x0 は含まないルール? >>928
あ、ゼロ忘れてた。ゼロもお願いします。 お題: ぶつかる迷路。
入力として与えられたフロア図の表すフロアのA地点にロボットRがあり、B地点にロボットSがある。しかし、RとSは同時に同じ場所を占有することはできない(衝突する)。
フロア図の例(上が北):
#######
#_A___#
#_#_###
#_#__B#
#######
#:カベ、_:空きスペース、A:A地点、B:B地点。
ロボットRとSは次の5つのコマンドが使用できる。
コマンド0:一つ待つ。
コマンド1:西に1つ動く。
コマンド2:東に1つ動く。
コマンド3:北に1つ動く。
コマンド4:南に1つ動く。
RがB地点に、SがA地点に到達するまで、RとSを最短のコマンドリストで動かせ。
到達できないときは「ERROR」と表示して終了せよ。 >>933
出力は題意のコマンドリスト2つです。
回答例)
((2, 2, 0, 0, 1, 4, 4, 2, 2), (1, 1, 3, 3, 1)) >>927 Perl5
for (qw(0x13 0x45 0x92C)) {
$n = eval;
@a = map{sprintf "0x%x", $_} grep{($_ & $n) == $_} 0..$n;
print "$_: @a\n";
}
※インデントは全角スペースに置換してあります。
実行結果
$ perl 21_927.pl
0x13: 0x0 0x1 0x2 0x3 0x10 0x11 0x12 0x13
0x45: 0x0 0x1 0x4 0x5 0x40 0x41 0x44 0x45
0x92C: 0x0 0x4 0x8 0xc 0x20 0x24 0x28 0x2c 0x100 0x104 0x108 0x10c 0x120 0x124 0x128 0x12c 0x800 0x804 0x808 0x80c 0x820 0x824 0x828 0x82c 0x900 0x904 0x908 0x90c 0x920 0x924 0x928 0x92c >>935 これだとコード書くの安直で楽だけど、効率悪いんだよね、特に値が大きいとき。
効率に配慮すると、こうか↓
sub f {
if (@_) {
my $b = shift;
@_ ? map{$_, $_ | 2**$b} f(@_) : ($_, $_ | 2**$b);
}
}
for (qw(0x13 0x45 0x92C)) {
$n = eval;
@b = grep{$n & 2**$_} 0..31;
@s = map{sprintf "0x%x", $_} f(@b);
print "$_: @s\n";
}
※インデントは全角スペースで置換してありま
実行結果:
$ perl 21_927_effective_bit_mask.pl
0x13: 0x0 0x1 0x2 0x3 0x10 0x11 0x12 0x13
0x45: 0x0 0x1 0x4 0x5 0x40 0x41 0x44 0x45
0x92C: 0x0 0x4 0x8 0xc 0x20 0x24 0x28 0x2c 0x100 0x104 0x108 0x10c 0x120 0x124 0x128 0x12c 0x800 0x804 0x808 0x80c 0x820 0x824 0x828 0x82c 0x900 0x904 0x908 0x90c 0x920 0x924 0x928 0x92c 仕事で書いたら怒られるやつw
(プラットホームや、ライブラリのバージョンとかに依存する可能性があるから)
tps://sagecell.sagemath.org/?z=eJy1krFqwzAQhneD3-FKhsjguFJsUmooHdK1UOjQsTi27BzYklEUkrxEpy6FQpcOfoi-Tto-RqTaISElzdSbdHe679fxK1eygirRU8CqlkpDLReuk9tqxlOsknLbuGlT13GdjOeA5iKjBL3YdcCEYaQG0mU20mTGYcBGYQw9GN-t9FSKMGAsiMgDikwuZjCKJqi93YgNxfVcCWDcjh7QhoYFJ2hwDvdJwW_tTmNelqREMV_CchRBUeIkhetjgsNfcozG_yjH6IFeSKOTekdgZrTtdBXjDmE0oD6gZy3rwef763fz8fXcrJ_e1i_NvouPtZJa6lXNd352nLyUiSad94QYHmG-Z6neDzeXChBQgEpEwckgpBe-2eNyi8G9nwJnV38I2qgVCk3si9tTP5OC970Noga8Nw==&lang=python&interacts=eJyLjgUAARUAuQ== >>933
・を「一つ待つ」として、最短のコマンドリストは>>934の
R: →→・・←↓↓→→
S: ←←↑↑←
の他にも、Sは同上で
R: →・・→←↓↓→→
R: →↓↑→←↓↓→→
R: →→←→←↓↓→→
R: →→→←←↓↓→→
もあり、あまりすっきりしない問題なので解く気が起きないな。 >>939
移動量も最短にする。また、動けるとき、かつ待てるときは待つよりも先に動く方を優先するという条件を追加します。 >>940
さらに次の3つの条件を追加します。
西か東か迷った場合は西を優先します。
北か南か迷った場合は北を優先します。
南/北の向きか東/西の向きかを迷った場合は東/西の向きを優先します。 >>927 Ruby
def solution( mk )
mb = 1
a = [0]
print "0x%X\n→(" % mk
while mk > 0
a.dup.each{|b| a << b + mb } if mk.odd?
mb <<= 1
mk >>= 1
end
puts a.map{|x| '0x%X' % x }.join(', ') + ')'
end
solution( 0 ) # 0の場合 0x0でいいのかな?
solution( 0x13 )
solution( 0x45 )
solution( 0x92C ) >>925
ツッコミどころが多すぎる
正しくはこうでは?
10^(-30)
=1.010_0010_0100_0010_0101_1111_...×2^(-100)
さらに、...部分は1111...と続くので、単精度にするなら切り上げになって、
1.010_0010_0100_0010_0110_0000×2^(-100)
よって、単精度での内部表示は
0_00011011_010_0010_0100_0010_0110_0000
整数0xa24260をセットして2^123で割ればいける
2のべき乗での割り算すら信用できないなら、ldexpあたりを使うのはどうか。pythonならこちら
(pythonは単精度が無いので結果は少しずれる)
from math import ldexp
print(ldexp(0xa24260, -123))
もしくは、バイト列経由で直接変換もあり。pythonならこちら
from struct import pack, unpack
print(unpack('f', pack('I', 0b0_00011011_010_0010_0100_0010_0110_0000))[0]) 今からIEEE754に準拠してない処理系が制作される事は無いでしょうから
(ホビーや学習用途は別ね)、
今日の処理系で、2のべき乗での割り算で仮数部が変わるって事は
無いと思われます(アンダーフローやオーバーフローは除外)。
…IBM hexadecimal floating-pointって基数が16だったな。
(仮数部が変わらないのは16のべき乗での乗除算のみ)
あれを常用してる人ってまだ居るのか?w
>>943
FORTRANならEQUIVALENCE文で… そもそも浮動小数点ライブラリなら
x^y = exp( y * log 2 )
で実装してるんじゃないかな
そもそものexpやlogが“最近値”を与えてくれることなど規格にはないやろ
それは数値計算の理論勉強してたらすぐわかる、メチャクチャ難しくてほとんど実装不能になってしまう
だから規格上は“±その周辺の値で表示できる値の中では最良”、すなわち“表現可能な上界の最小値または表現可能な下界の最大値”、それならギリギリ実用可能な速度くらいは出せるけど、それとて難しい、そこまで今のライブラリが保証してくれてるかあやしい
まぁその手のライブラリ使わずに“最近値”を出すことはメチャクチャ手間かかるけどできなくはない、しかしそれが限界、その値を変数に確実にセットする方法がない x^y = exp( y log (x))ね
この計算に入る前に「x=2, yが整数であるかどうか検査する、その場合には仮数部は弄らず指数部だけyに応じて増減させる」なんて処理してるライブラリはないやろ
有無を言わさずy log(x)計算、→exp計算、丸め誤差上等でやってるやろ、そこで単精度計算ならちょっと余裕もってビット幅大きめのアキュムレータに入れてるかもしれんけどどんなに大きな精度のアキュムレーターを用意したとて出てくる値が“最近値”になる保証はない、そこまで保証しようとすると恐ろしくコストがかかってしまう
汎用の数値計算ライブラリでそこまで保証されてるわけないと思う、単精度計算なら±2^(-24)=単精度の内部表現で可能な幅までは保証するのが限界だと思う、それとてかなりコストがかかるし
まぁどのみち2^(-23)以上の精度が必要ならそもそも言語の標準ライブラリなんか使わんからな >>946
規格で正確な値(を最近値に丸めたもの)を求められてるのは
加減乗除とsqrt()とfma()でしたっけ?
pow()は、glibcが誤差0.523ulpとか(0.5ulpが限界値)、
イイ線行ってるそうですね。
tps://members.loria.fr/PZimmermann/papers/accuracy.pdf >>949
llvmの多くの項目がNA(non available)なのは、
実装されてないからではないかと。
この中では、OpenLibmがfdlibmの「血」を残してる方なのかな?
tps://www.netlib.org/fdlibm/ うん、多分実装されてない分は自分でやれと
実装されてるところは軒並み0.5
まぁこれも本当に確率100%で必ず最近値出すんではなくて外れる確率が0.000001%とかなんだろうな
例えば単精度演算は毎回倍精度にキャストして計算してから丸めればほぼほぼ最近値にならない確率0.0000001%とかになるからな
逆に言えば他のライブラリはその手のキャストも何もしないで“丸め誤差上等”でやってるんやろな >>951
ちゃんとやろうとすると、CRlibmみたいに、部分的にでも
6倍精度とかで計算しないとならないっぽいです。
glibcのexp()は768bitで計算する場合があるそうで。
…世間的には、それ程の精度を求めない用途もあって、
実際、libmのhypot()(じゃなくてもいいのですが)が遅いので自分で
実装しますたと云う報告がネット上でも散見されます
(もちろん精度は落ちる) まじですか
768bitって何をどう計算してるんやろ?
結果が24bitで768bitなら求める答えの72倍のアキュムレーター使うのかな?
そんな事ないよな、アキュムレータは48bitくらいで36回計算するからのべ768bitとかいう事なのかな?
まぁそれだけの事やって「末尾の最後の1ビットの正確性を求める意味あんのか問題」は発生するわな
”みんなが使う汎用ライブラリ”だとどうしてもそういう“誰も求めてない精度”に無意味にこだわってしまう部分があるんかも >>953
丸めて切り上げ/切り捨てのぎりぎりのとこを精査するのに
768bitで計算する場合もあるそうです(そういう
ぎりぎりのとこでない場合はやらないので、それなりに速い)。 >>954
まじですか?
そんな最後の1ビット正確に決定するために768bitもの無駄な計算するくらいなら誤差±2^(-23)でいいからとっとと値返してくれた方がいいのに
なので当然通常“最後の1ビット”の正確性までは規格に入れてないんだよな、それでもライブラリ作成者は自己満のために誰も求めない“最後の1ビット”にこだわる
これは高校くらいまでの近似計算の「小数第××位まで求めよ」のノリが抜けてない事の現れでもあるんだよな
もう計算論の近似計算の世界ではゲームチェンジが起こってる事に気づけてない >>955
誤差なし(±0.5ulp以内)を追及する人達(CORE-MATH)も居れば、
double-double演算とかの「飛び道具」を使うのをよしとしない人達も居て、
えーっと、みんな違ってみんないい(こなみ) まぁしかし“払うコスト”に対する“リターン”が少なすぎる気はする
例えば内部表現の精度が2^24まである単精度の計算をする場合、もちろん理想は“誤差±1/2×2^(-24)”で返してくれるとありがたい
しかし現実できるか?
例えばアキュムレータをを32ビット用意して計算する、マクローリン展開で求めるとして100回で打ち切るとする、打ち切り誤差は入力のサイズによるけど十分小さい、丸め誤差は2^(-32)×100で誤差トータルは2^(-25)程度、返すのが24bitだから丸められる2^8の可能性のうち真値のポジションから最大100ずれたところでウロチョロしてるわけでその“ウロチョロ”が二項分布、真値の分布が256個の箱の一様分布として外れ値になるの確率がどのくらいやろ?暗算ではできないけど言うほどない、この言うほどない誤差を返さないただそれだけのために768bitも計算繰り返すとかどうなんって感じ >>957
768bitの話は、倍精度(53bit精度)のexp()の過去のバージョンでした。
glibcでも問題になったんでしょう(たぶん) でしょうね
流石に768bitはない
せめてそこまで行けば完全に最近値が決定できるならともかくそこまで行っても最近値を100%決めるのは無理なんじゃないでしょうか?
24ビットの値返すのに768bitまで計算するなら744bit、2^744の可能性につきあってそこまで行っても両端の100通りの可能性は残り、最近値を返せない可能性は0にはなってない、まぁほとんど0だけど
多分llvmの実装は単精度でも最初からアキュムレータに64bit(レジスタ2個分)で計算するんやろな、あまりのビットが40bitあって100/2^40とか1000/2^40とかはほとんど0だからほぼ確率1で最近値返しますよ、それで十分でしょって実装なのではなかろかと、実際それで十分
最近のcpuはなんかレジスタ2個分に分けて計算してもレジスタ1個で計算するのと時間大して変わらないという話もききますしね >>959
以前は最近値だったそうです(その代わり遅い)
tps://sourceware.org/git/?p=glibc.git;a=commit;h=6fd0a3c6a887a91b1554730c977657a7e65334cc その記事はglibcで色々実験してみたの報告ですね
どっかに“旧glibcは最近値をとことんまで出す”って別資料の記事見かけました?
もちろん入力された有理数xに対してexp(x)を時間無制限ならその与えられた桁数までの最近値を計算するアルゴリズムはすぐ作れるので(一般にGaussの超幾何関数からくる連分数表示が可能な実数ならそのような事が可能)そういうライブラリを実装するのはまぁ無理ではないんですけどね
実際円周率をリソースが食い尽くされるまで延々と計算し続けるプログラムとかよくネットで転がってますし、確か昔のrubyのサンプルプログラムにも収録されてたような >>962
難しいお題だったので、簡単に解説お願いします。 >>927
Rust
fn foo(input: u32) -> impl Iterator<Item = u32> {
(0..=input).filter(move |n| n & input == *n)
}
ただしこれではループがO(n)
ループをO(log N)にするならこちら
fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input).map(|p| 1 << p).collect();
(0..(1 << table.len())).map(move |bits| bits_iter(bits).map(|p| table[p as usize]).sum())
}
補助bitsイテレータ
fn bits_iter(n: u32) -> impl Iterator<Item = u32> {
let mut n = n;
std::iter::from_fn(move || {
(n != 0).then(|| {
let p = n.trailing_zeros();
n &= !(1 << p);
p
})
})
} >>964
rustfmtがギリギリ2行にまとめてしまうが見にくいので手動で以下へ補正
(改行の違いだけでコード自体は同じです)
fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input)
.map(|p| 1 << p)
.collect();
(0..(1 << table.len()))
.map(move |bits| {
bits_iter(bits)
.map(|p| table[p as usize])
.sum()
})
} 見やすさどうこうならオンラインの実行環境に入れたほうが見やすい >>963
まず
@Rを自由に動かしてコマンドリストを得てから、SをRと衝突しないように動かしてコマンドリストを得る。
次に優先権を逆転させ、
ASを自由に動かしてコマンドリストを得てから、RをSと衝突しないように動かしてコマンドリストを得る。
そして、@とAでコマンドリストが短い方を解として採用する。
コマンドリストを得る方法は基本的には>>856と同じ幅優先探索だが、>>856のように2次元の数値配列を作り
各マスへ最短何個のコマンドで到達できるかを記録するだけでは今回の問題の複雑な動きには対処できないから、
3次元の論理配列を作り1個のコマンドで各マスへ到達できるか否か、2個のコマンドで各マスへ到達できるか否か、
3個のコマンドで〜、…を記録していくように変えた。
26行目はB[Q]が何回も現れてごちゃごちゃしているので、変数をもう1個作って
b <- B[Q]
A[i + 1, , ][Q[b != Inf & b != i + 1 & (b != i | b[1] != i + 1), , drop = FALSE]] <- TRUE
と書く方が行数は増えるがすっきりする。36行目も同様。 >>967
三次元の論理配列。。。なんかすごい。
これって衝突回避システムに応用できるかな? >>966
なるほど!
専ブラではなくWebブラウザから見るとインデントスペースが消えてしまうのですね
>>927
Rust全文
https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=f627f3a5de4a0c467f015a8b1527c141
抜粋 (全角スペース使用)
fn foo(input: u32) -> impl Iterator<Item = u32> {
let table: Vec<u32> = bits_iter(input)
.map(|p| 1 << p)
.collect();
(0..(1 << table.len())).map(move |bits| {
bits_iter(bits)
.map(|p| table[p as usize])
.sum()
})
} 山下の乱で速攻作ったのがCUIのやつだった
GUIにしたらこんなんだろうな
https://i.imgur.com/f4xau5O.jpg スレ違いなんだけど今回の騒動出遅れてよくわからんのわけとこの山下ってのが5chに対して反乱分子起こしたん?
それは何故?
もうニュー速+とかでも過去の話でスレも立ってないしググっても出てこない
何がどうなったん? お題: 化学の共有結合。
x, y, zをそれぞれ任意の自然数とする。入力(x, y, z)に対して炭素原子(C)x個、酸素原子(O)y個、水素原子(H)z個のすべてを
共有結合で連結するときの連結結果の組み合わせをすべて出力するプログラムを書け。
出力形式は自由とする。
入力例)
(0, 1, 2)→?
(1, 1, 4)→?
(1, 0, 4)→? >>931
ごめんなさい、わからない
例えば上の例ではFooは単相型なの?
具体的に何型?
ちょっと昔からのweb情報ではできないと書いてあるページはあるけど上の例ではできてるでしょ? まず共有結合とはどんなものなのかを調べてからでないと作れないが、今のところ調べてまで作りたいとは思わない。 情報科学的元素共有結合の勝手な定義を書いとかなければ問題にならない 共有結合について高校化学でよく言われるのは、次の通り。
炭素原子は「結合の手」を4個持っている。
酸素原子は「結合の手」を2個持っている。
水素原子は「結合の手」を1個持っている。
結合の手を余らさないように連結する。
分子の右手型左手型の区別は考えなくてよい。
連結のときの他の原子との重なりは考えなくてもよい。 お題: パソコン、スマホ、またはタブレットに大きな顔を表示して、音声入力と
音声出力で会話ができるようにする。 >>983
1. Skype をインストールする。
2. 友達と動画で通話する。
ただし、掛ける相手が居ない場合は実現できない。 H2Oってなんで真っすぐじゃなくてくの字に折れてるんだろ >>984
スマホが2台あれば解決
PC+スマホでもOK お題: 気体の状態方程式より温度を求める。
半径ゼロで70000個の水素分子のみが底面半径4[cm]、高さh[cm]の円すい形の密閉空間内をまんべんなく飛び回る。
密閉空間の高さh[cm]を入力とするとき、圧力P=1.013*10^5 [Pa]、密閉空間の体積V[m^3]、水素分子の物質量n[mol]、気体定数R=8.31について、
気体の状態方程式PV=nRTより導かれる絶対温度T[K]を出力せよ。
入力例)
10→?
20→?
50→? >>988
そりゃあ、一つ一つ丁寧にピンセットでつまんで容器に入れたんでしょう。 現代の地球人の技術力ではT=0にでもしないと無理そうだし
もしそうなら水素は固体化してて
Vの大部分は真空でPはほぼ0なんじゃないかな T = PV/nR
= 1.013*10^5 * (4.000)^2*3.142*h/1000
/( 70000*8.314 * 6.022*10^23 *10^3 )
= 1.453*10^(-29)*h ( K ) 分子が多すぎて現実的なシミュレーションは難しいね。 T = PV/nR
= 1.013*10^5 * (4.000)^2*3.142*h/1000
/( 70000 / (6.022*10^23) *10^3 * 8.314 )
= 5.269*10^18*h ( K ) そもそも分子の運動をシュミレーションしてp,v,nTの関係を調べさせるつもりなら出題がおかしい
それなら入力が温度、分子量、体積で出力が圧力やろ このスレッドは1000を超えました。
新しいスレッドを立ててください。
life time: 262日 18時間 32分 12秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。