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

**デフォルトの名無しさん** · 2018/04/24(火) 20:45:14.49

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

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

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

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

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

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

**デフォルトの名無しさん** · 2018/09/13(木) 14:17:54.21

>>911 >>932
%h;
while(<>){
chomp;
($f, $s) = split / /;#first, second

undef $keyf;
undef $keys;

for $k (keys %h){
$keyf = $k if grep /$f/, @{$h{$k}};
$keys = $k if grep /$s/, @{$h{$k}};
}

if(!defined $keyf and !defined $keys){
push @{$h{$.}}, $f;
push @{$h{$.}}, $s;
}elsif( (defined $keyf and defined $keys) and !($f eq $s) ){#merge
push @{$h{$keys}}, @{$h{$keyf}};
delete $h{$keyf};
}else{
push @{$h{$keys}}, $f unless defined $keyf;
push @{$h{$keyf}}, $s unless defined $keys;
}
}

map{print join " ", (sort{$a cmp $b} @{$h{$_}}), "\n"} sort{$a <=> $b} keys %h;

**デフォルトの名無しさん** · 2018/09/13(木) 20:39:52.56

>>932
あー。なるほど。そういうことか。
また考えよう。

**デフォルトの名無しさん** · 2018/09/14(金) 03:38:24.35

>>927
>>926は修正した。(URL同じ)

**デフォルトの名無しさん** · 2018/09/14(金) 04:53:58.08

>>935
差し支えなければ修正前のコードも別URLで再掲載してもらえますか？
あるいは公開バージョンの履歴や差分を参照する機能がpaoza.ioにあったら教えてください

くしくもマージを考慮「しない版」と「する版」が出揃ったのでどういう修正で対処したか調べると
それぞれの言語の（あるいはアルゴリズムの）特徴が際立って面白いのではないかなぁとふと思ったので

**デフォルトの名無しさん** · 2018/09/14(金) 08:32:54.25

>>936
すまん。前の版はもうない。paiza.ioはそういう機能はない。
思い出して時間があったらなんとかする。

**デフォルトの名無しさん** · 2018/09/14(金) 09:31:32.78

>>937
あーいやそこまでしなくても結構です。ありがとうございます！

**デフォルトの名無しさん** · 2018/09/14(金) 12:57:38.55

わざわざ書こうとしてくれるなんて良いやつだな

**デフォルトの名無しさん** · 2018/09/14(金) 18:45:13.33

>>936
>>932が>>926の古いコードのコピペ

**デフォルトの名無しさん** · 2018/09/14(金) 20:03:21.13

>>940
おおありがとう！

**デフォルトの名無しさん** · 2018/09/14(金) 20:39:39.94

>>940
おお。ナイス。

**デフォルトの名無しさん** · 2018/09/14(金) 20:50:46.38

結構みんな人の書いたコード読んでるんだな
いい意味でびっくり

**デフォルトの名無しさん** · 2018/09/14(金) 23:34:38.18

逆になんで読まないの？

**デフォルトの名無しさん** · 2018/09/15(土) 00:06:11.66

>>911
Rubyで。
https://ideone.com/MEO7XO

**デフォルトの名無しさん** · 2018/09/15(土) 08:52:18.54

>>945
訂正。Rubyで。
https://ideone.com/er8XUC

**デフォルトの名無しさん** · 2018/09/15(土) 18:55:39.79

>>946　とは別の戦略。
Rubyで。
https://ideone.com/osABKT

**デフォルトの名無しさん** · 2018/09/15(土) 19:09:51.94

>>947
ソート忘れてんよ

**デフォルトの名無しさん** · 2018/09/16(日) 00:15:22.99

>>948
付けといて。

**デフォルトの名無しさん** · 2018/09/16(日) 08:13:10.07

>>911
Rubyで。ソート、コメント付き。
https://ideone.com/9RyjEF

**デフォルトの名無しさん** · 2018/09/18(火) 20:26:30.74

https://www.rco.recruit.co.jp/career/engineer/entry/
↑
この問題どうですか？

自分でも書いてみたのですが合ってるかちょっと分かりません
C# https://ideone.com/KNpwLL

**デフォルトの名無しさん** · 2018/09/18(火) 20:38:45.88

こういうのって答え公開してもいいんか？

**デフォルトの名無しさん** · 2018/09/18(火) 20:48:39.65

企業がやってるのって大体駄目だったと思うで

**デフォルトの名無しさん** · 2018/09/18(火) 20:49:39.59

>>952
あくまでも過去の出題例、だからいいんじゃないですか？

**デフォルトの名無しさん** · 2018/09/19(水) 00:29:21.73

アウトかセーフか分からないときは答え公開しないほうが無難

**デフォルトの名無しさん** · 2018/09/19(水) 01:18:48.14

>>955
アウトになる条件は、「エントリー後メールにて送付されるコーディング試験問題は、当社への応募以外の目的で無断使用しない」…①
だが、>>951 のリンクの問題は「エントリー後メールにて送付されるコーディング試験問題」ではないから①に反しない…②
さらに、無条件に誰でも見ることのできる問題であること…③
②よりアウトではないと断定できるし、③が②の結論を補強する
結論として、>>951 のリンクの問題を公開しても問題ない

>>955 「アウトかセーフかわからない」という結論にどういう道筋で到達したの？

**デフォルトの名無しさん** · 2018/09/19(水) 19:43:34.67

お題：コンプリートパネル(出展：高校生クイズ2018)

5×5のパネルが与えられる。各パネルは赤色か白色である。
各パネルに侵入すると、そのパネルの色が赤なら白、白なら赤に変化する。
最初のステップは、場外(左下のパネルの左隣)から左下のパネルへ侵入することである。
以降のステップでは、上下左右に移動することができる。
ただし、ひとつ前のパネルや場外に移動することはできない。

すべてのパネルを白色にするための移動経路を構成せよ。

WWWRR
WWWWR
WWWWR
WWWRR
RRRRW
=> 10 RRRRURUUUL (→→→→↑→↑↑↑←)

WWWWW
WWWWW
WWWWW
WWWWW
WWWWW
=> 0 (移動の必要なし)

WWWWW
WWWWW
WWWWW
WRWWW
WWWWW
=> 21 RRRRULULLDDRULURRDRDL (必ずしも最短経路である必要はない)

**デフォルトの名無しさん** · 2018/09/19(水) 19:51:24.03

>ひとつ前のパネルや場外に移動することはできない

全部踏めばいいんだからライツアウトの解法の亜種で解けるんじゃねえの

**デフォルトの名無しさん** · 2018/09/19(水) 19:59:02.78

状態を変えずに任意の場所まで移動できるなら
6箇所だけそれぞれ1つだけRだった場合を計算してあとは回転なりなんなりして重ね合わせればいけるな

**デフォルトの名無しさん** · 2018/09/19(水) 20:34:03.00

↑
□□□
□□□→

２＊３の全パターンで、この二つの方向のどちらかに抜ける経路が存在すればいい
あとは合成で何とかなる

**デフォルトの名無しさん** · 2018/09/19(水) 21:11:11.50

うーん。これはブルートフォースでやろうとするとかなり無駄が多くなって時間とメモリを山盛りに食いそうな予感。

**デフォルトの名無しさん** · 2018/09/19(水) 23:00:29.71

5x5=25マスの赤or白の2値だから25bit、現在位置25通り(5bit)に前回位置相対で4通り(2bit)、あわせて32bitパターン？

**デフォルトの名無しさん** · 2018/09/19(水) 23:25:52.07

５ｘ５は序の口で、１００ｘ１００くらいが本命でしょう
ついでに最短の最適解も

問題も作るだけならラクだから１０００ｘ１０００だって0.1秒程度で作れる
もちろん解くのは面倒

**デフォルトの名無しさん** · 2018/09/20(木) 01:27:25.92

>>957
手でしか試してないけど
解けないパターンとかありそうな予感
https://i.imgur.com/u8zgEum.png

**デフォルトの名無しさん** · 2018/09/20(木) 09:43:56.68

プログラム考える以前に解くためのいいアルゴリズムが思い浮かばん

**デフォルトの名無しさん** · 2018/09/20(木) 12:37:05.73

辺の長さが3以上の時は戻るの禁止ってルールは実質的に無視できそうだな
というのも閉路を2周すれば元通りに戻るわけだから

xxx
x↓x
x↑x
上に行ってまた下に戻るって進みたいときは

→↓x
↑←x　// 中央「←」を3回目に踏むときは下に進む
x↑x
ってすればいいわけで
2*2 かどちらかの辺が 1 の場合以外は任意のパターンで解があることになる

**デフォルトの名無しさん** · 2018/09/20(木) 23:43:04.82

RWWWR
WRWWW
RWRWW
RWWRW
WRRWR

全てのパターンが解けて最長がこの形で44手かかる

となったけどできたばかりだからまだまだバグがありそう

**デフォルトの名無しさん** · 2018/09/21(金) 23:11:26.91

https://ideone.com/S7UA0k
表示までできるようになったので
ここでは5秒超えるので結果表示されないみたい
10年前のノートで2分半かかる
結果はこんな感じ

- - - - -
- - - - -
- - - - -
- x - - -
- - - - -

RRRRULDRULLDL 13

x - - - x
- x - - -
x - x - -
x - - x -
- x x - x

RRRRRUUUULLLLDDDDRRRURUULDLDDLUURDLURRUULLDL 44

**957** · 2018/09/22(土) 13:39:38.33

最適解ではないが、人間にも実行可能なアルゴリズムを考えた
上のラインから順番に確定させていく感じ
https://ideone.com/nUgNh3

**デフォルトの名無しさん** · 2018/09/23(日) 05:22:08.89

解法全然分からないけど
枝狩りもメモ化もせず愚直に全探索すると44手目で10760814742109228通りになるのか…ヤバイな
http://codepad.org/JXkGjMKb

**デフォルトの名無しさん** · 2018/09/23(日) 06:45:48.27

>>970
メモ化のみの全探索でも厳しいね
https://ideone.com/TpZyFM

**デフォルトの名無しさん** · 2018/09/23(日) 07:02:07.82

>>962の理屈上なら>>971のstepの累積和が3,355,443,200(=25<<27)になった時点で全通り出たことになって最短の上限になるのかな？

**デフォルトの名無しさん** · 2018/09/23(日) 10:53:27.77

ttps://cdn-ak.f.st-hatena.com/images/fotolife/m/motcho/20180127/20180127034515.png
連続殺人犯が全ての目撃者を消して完全犯罪を目論む

**デフォルトの名無しさん** · 2018/09/23(日) 12:36:34.31

文字列のペアがn対与えられる。
s(1),t(1)
...
s(n),t(n)

この時、ペアを適切な数選び適切な順番で並べる事で
s(a1)s(a2)...s(ak) = t(a1)t(a2)...t(ak)
とできるかどうか判定せよ
(ペアを重複して選ぶのもOK)

**デフォルトの名無しさん** · 2018/09/23(日) 12:41:57.26

>>974
それって｢s(i)=t(i)となるiが1つ以上存在するか｣というだけのように思えるけど、違うかな？

**デフォルトの名無しさん** · 2018/09/23(日) 12:42:44.79

>>975は勘違いでした。取り消します

**デフォルトの名無しさん** · 2018/09/23(日) 13:27:09.60

>>975
最初全く同じこと思ったわｗ
でもこれって十分条件に過ぎないんだな

a ab
bc c
s(1)s(2) = t(1)t(2) = 'abc'

**デフォルトの名無しさん** · 2018/09/23(日) 17:12:26.93

応用だけは思い付いた

ATCGTTGTAC, AAATTTCTCTCTTTCT
GTGATGCGTTGCAGGT, ATGCCATGTGAC
AAATTGCTGAC, ATGTTGCGTC
ATGCGTACCCACG, AGTGCGTTCGTAC
...（以下、1万行続く）

**デフォルトの名無しさん** · 2018/09/24(月) 12:45:56.45

>>974
空文字列は含むの？

**デフォルトの名無しさん** · 2018/09/24(月) 14:31:45.91

重複しても良いってなっているのでどうやっていいか分からなくなった。
重複なしなら単に順列の問題で全パターン調べれば良いだけなんだけどな。

**デフォルトの名無しさん** · 2018/09/24(月) 14:56:44.30

>>979
含むと何も並べなければOKって事になりそう

**デフォルトの名無しさん** · 2018/09/24(月) 15:56:26.13

>>981
結果じゃなくて入力に

一つも選ばないのがOKならそもそも問題として成立しないだろ

**デフォルトの名無しさん** · 2018/09/24(月) 16:14:35.67

>>974
Kotlin
但し、重複選択は考慮していない。
https://paiza.io/projects/iRHJjFRj9BJIydX10SIn0Q

**デフォルトの名無しさん** · 2018/09/24(月) 19:57:46.70

>>969
ルール合ってるのかどうか知らないけど
ゲーム風にしてみた (Win専用)
http://fast-uploader.com/file/7093342064119/
PASS:11957

慣れると何となく解き方のコツが見えてくる
今まで解けなかった例は無さげ

**デフォルトの名無しさん** · 2018/09/24(月) 20:25:58.77

任意のパターンで解けることはここですでに言及されてるよ

**デフォルトの名無しさん** · 2018/09/25(火) 00:18:48.94

エビングハウスの忘却曲線っていって人間のベストな復習間隔があるんだけど
例えば今日勉強したことは明日復習して3日後、1週間一ヶ月ごとに復習すると完全に長期記憶になる
これをスマホアプリで管理するプログラミングしたい
理屈は簡単、カレンダーに今日覚えたことを「○○の20-40ページ」とか記入して
明日になったら今日やる復習を表示してくれるシステム

プログラミングのプの字も知らんのだ
どの言語を使うとかもわからんmacとxcodeはある
どういう作り方すればいいかわからない教えてください個人用に使う

**デフォルトの名無しさん** · 2018/09/25(火) 02:12:07.33

ここはそういうスレではないよ

**デフォルトの名無しさん** · 2018/09/25(火) 02:40:25.79

>>986
このスレはそういう質問するスレではなく、誰かがお題を出して回答したい人がプログラミングして回答するスレだ。

そういう質問はまずは既存のソフトでそういうことが出来るのがないか以下のスレで聞いた方が良いと思う。

気軽に「こんなソフトありませんか？」Part.176
https://egg.5ch.net/test/read.cgi/software/1529929775/

それからどうしてもプログラムを自分で作ってみたいというのであれば何らかの言語を覚える必要があるが、
MacやiPhoneの場合は何が良いのか俺はよく知らない。この頃だと Swift なんだろうか? Swift は確か xcode
使って作れたと思うが、詳細は今の俺には分からん。MacOSやiOS関係のスレを探して聞いてくれ。

**デフォルトの名無しさん** · 2018/09/27(木) 22:18:07.66

お前らってファイルそのものへの参照を禁止したうえでquineを自力で書ける？

**デフォルトの名無しさん** · 2018/09/27(木) 23:09:56.51

もう少し詳しく

**デフォルトの名無しさん** · 2018/09/28(金) 01:19:09.36

次スレは

**デフォルトの名無しさん** · 2018/09/28(金) 10:09:57.20

次スレ
プログラミングのお題スレ Part12
https://mevius.5ch.net/test/read.cgi/tech/1538096947/

**デフォルトの名無しさん** · 2018/09/28(金) 21:10:47.83

埋め

**デフォルトの名無しさん** · 2018/09/28(金) 21:28:45.12

うめ

**デフォルトの名無しさん** · 2018/09/28(金) 21:28:53.05

うめ

**デフォルトの名無しさん** · 2018/09/28(金) 21:29:01.92

う

**デフォルトの名無しさん** · 2018/09/28(金) 21:29:15.02

め

**デフォルトの名無しさん** · 2018/09/28(金) 21:29:28.35

あさうめ

**デフォルトの名無しさん** · 2018/09/28(金) 21:29:36.27

うめ

**デフォルトの名無しさん** · 2018/09/28(金) 21:29:44.58

うめ

**1001** · Over 1000

このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 157日 0時間 44分 30秒