X



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

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2020/11/30(月) 00:04:05.21ID:TF2Czp0y
プログラミングのお題スレです。

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

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

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

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

※前スレ
プログラミングのお題スレ Part18
https://mevius.5ch.net/test/read.cgi/tech/1594702426/
0620蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/20(火) 14:33:35.54ID:fjai9OEL
お題: 依存関係のあるソート。与えられたいくつかの項目について、各項目ごとに依存関係が指定される。依存対象が先に来るように項目のリストをソートしなさい。
依存関係に循環がある場合は「ERROR」と出力しなさい。依存関係がない場合は名前の順でソートしなさい。

例1) {A, B, C}
AはB, Cに依存する。
BはCに依存する。
Cは何にも依存しない。

例2) {A, B, C, D}
AはCに依存する。
BはDに依存する。
CはB, Dに依存する。
Dは何にも依存しない。
0621蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/20(火) 14:57:48.16ID:fjai9OEL
例3) {A, B, C, D, E}
AはEに依存する。
BはDに依存する。
CはBに依存する。
Dは何にも依存しない。
EはBに依存する。
0622デフォルトの名無しさん
垢版 |
2021/04/20(火) 19:18:30.05ID:4HfXomGv
例ってそれぞれの入力してでどう言う出力なのか答え出さないと例にならんやん?
0624蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/20(火) 20:07:07.92ID:fjai9OEL
全順序じゃないから、単純なソートアルゴリズムじゃダメみたいだね。
0630デフォルトの名無しさん
垢版 |
2021/04/21(水) 11:28:35.43ID:feIJLTYL
例えば>>821の時は順序の生成元が
E<A, D<B, B<C, B<E
この中で先頭に持ってきて良いものを探す
それはつまり「何かに依存していないもの」
この状態ではA,B,C,Eは何かに依存しているのでダメ
よってこの場合Dしかない
残りA,B,C,Eの順序を決める
その際順序の生成元からD<Xの形は取り除く
つまり
E<A, B<C, B<E
依存していないものはBのみなのでBが2番目
残りA,C,Eで順序の生成元はE<Aのみ
依存してないのはC,Eでどちらがきても良い

数学的には“何かに依存していない”はその“半順序”における“極小元”
そして極小元になり得る必要十分条件がまさに「順序の生成系の中でそれより小さいものがないもの」、すなわち「何かに依存してないもの」とわかる(証明も簡単)
そしてこの作業に於いて順序の生成系にループが有れば、例えばx<y,y<z,z<xのようなものが有ればx,y,zは最後まで取り除かれず、最後には「まだ元は残ってるけど極小元なし」の状態に到達してしまうのでその時点でerror判定して終了すれば良い
0632デフォルトの名無しさん
垢版 |
2021/04/21(水) 12:03:04.18ID:v7jA28gl
お題が気持ち悪い

単に有向グラフの辺となるものだけ指定すれば良いのに
依存とか書いちゃうから以下みたいな間接依存が許されない雰囲気

AはBに依存
BはCに依存
0635デフォルトの名無しさん
垢版 |
2021/04/21(水) 19:48:52.11ID:Y7fj3JnX
順序集合の定義自体は超簡単じゃね?
順序集合の定理なんか使わないから順序集合なんて言葉を使う必要もないけど

アルゴリズム的には
極大(極小)元の中で名前順の先頭である元を取り出す
を繰り返すだけで良い
取り出せなくなってまだ残っていたらERROR

>>630みたいに無駄に長く説明しなくて良い
0637デフォルトの名無しさん
垢版 |
2021/04/21(水) 20:12:32.68ID:rPf7kV48
そりゃーC++には半順序がバンバン出てくるから選ばれた人間向けの言語だよ。
0638蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/21(水) 22:08:22.58ID:OiYnhzgp
>>634
ちゃんと理解して実装したぜ。
https://github.com/katahiromz/OleBow/commit/f65c774b625385e855971adb1275de1fd6ebee0c

循環参照の例がうまくいかないけど。
// :: IBindCtx: IRunningObjectTable
// :: IEnumMoniker: IMoniker
// :: IMoniker: IBindCtx
// :: IMoniker: IEnumMoniker
// :: IRunningObjectTable: IEnumMoniker
// :: IRunningObjectTable: IMoniker
// :: PartitionMoniker: IMoniker
// :: SoapMoniker: IMoniker
ポインタ型とかは後回しでいっかな。
0640デフォルトの名無しさん
垢版 |
2021/04/22(木) 07:08:36.76ID:DXDf8hNh
>>620 Ruby
# Array

rule = []
while gets
break unless m = /^\s*(\w)は(\w)?(?:,\s*(\w))*/.match( $_ )
rule << m.to_a[1..] - [nil]
end
solution = []
loop {
free = []
break if rule.delete_if{|a| a.size == 1 && free << a[0] && solution << a[0] }.empty?
free.each{|d| rule.each_index{|i| rule[i] -= [d] } }
}
puts (rule.empty?)? "(#{solution.join(', ')})." : "ERROR"
0641デフォルトの名無しさん
垢版 |
2021/04/22(木) 07:09:10.65ID:DXDf8hNh
>>620 Ruby
# Bit演算

rule = []
while gets
break unless m = /^\s*([A-Z])は([A-Z])?(?:,\s*([A-Z]))*/i.match( $_ )
rule << [ m[1].upcase, m.to_a[2..].inject(0){|r,c| (c)? r | (1 << c.upcase.ord - ?A.ord) : r } ]
end
solution = []
loop {
free = []
break if rule.delete_if{|a| a[1] == 0 && free << a[0] && solution << a[0] }.empty?
free.each{|d| rule.each_index{|i| rule[i][1] &= ~ (1 << d.ord - ?A.ord) } }
}
puts (rule.empty?)? "(#{solution.join(', ')})." : "ERROR"
0642デフォルトの名無しさん
垢版 |
2021/04/22(木) 20:40:45.65ID:euTe4E7l
お題
JSONでシリアライズされた未知のm×nの行列が与えられる。
転置行列を返せ。転置行列はシリアライズされていなくてもよい。

入力
"[[1,2],[3,4]]"
出力
[[1,3],[2,4]]
0645デフォルトの名無しさん
垢版 |
2021/04/23(金) 13:43:38.22ID:Vuss2QH6
>>642 J

smoutput |: ". @ }: @ }: ;. _1 }. stdin ''
入力
[[1,2,3].[4,5,6]]

出力
1 4
2 5
3 6
0646蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 15:35:20.99ID:CrWxBL6F
お題: コマンドラインで動作するエクセルもどきを作れ。入力テキストの中身に特定の形式の「フィールド」(field: 欄)を埋め込んでおく。今回はフィールドは以下のような形式で表現される。

(1) {{=数式}}
(2) {{フィールド名:文字列}}
(3) {{フィールド名:=数式}}

フィールドは{{ }}で囲んだ文字列で指定される。
数式にはフィールド名を変数とする式を指定できる。フィールド名は半角英数字の組み合わせとする。
式は少なくとも、丸カッコと、整数の四則演算と、整数から文字列への変換と、文字列の連結をサポートすること。
入力テキストのそれぞれのフィールドを評価後の値に置き換えたテキストを出力せよ。フィールドの循環参照や式のエラーがあった場合はその場所に「ERROR」と出力せよ。
その他の仕様についてはエクセルをできる限りまねること。
0647蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 15:52:00.73ID:CrWxBL6F
>>646 追記。
フィールド名は英字で始まるものとする。

(入力例)
こんにちは、{{NAME:蟻人間}}さん。
今年は{{:=Y}}年です。来年は{{:=Y+1}}年です。

A={{A:=1}}.
B={{B:=2}}.
A+B+4={{=A+B+4}}.
A*B-2={{=A*B-2}}.

日付: {{Y:=2021}}年{{M:=4}}月{{D:=27}}日
{{:="<"&NAME&">"}}
0650蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 17:02:02.42ID:CrWxBL6F
>>649
代入文か代入式を許容することか。{{A=3}}
そっちの方がいいかもね。

エクセルは数式の先頭で=を書いてるだけで、それ以外に代入式や代入文はなかったはず。
0651蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 17:08:35.63ID:CrWxBL6F
>>646 お題を書き直します。

お題: コマンドラインで動作するエクセルもどきを作れ。入力テキストの中身に特定の形式の「フィールド」(field: 欄)を埋め込んでおく。今回はフィールドは以下のような形式で表現される。

(1) {{数式}}
(2) {{フィールド名=数式}}

フィールドは{{ }}で囲んだ文字列で指定される。
数式にはフィールド名を変数とする式を指定できる。フィールド名は英字で始まる半角英数字の組み合わせとする。
式は少なくとも、丸カッコと、整数の四則演算と、値の比較と、整数から文字列への変換と、文字列の連結をサポートすること。等号は二文字の==とする。
入力テキストのそれぞれのフィールドを評価後の値に置き換えたテキストを出力せよ。フィールドの循環参照や式のエラーがあった場合はその場所に「ERROR」と出力せよ。
0652蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 17:10:52.46ID:CrWxBL6F
>>651

(入力例)
こんにちは、{{NAME=蟻人間}}さん。
今年は{{Y}}年です。来年は{{Y+1}}年です。

A={{A=1}}.
B={{B=2}}.
A+B+4={{A+B+4}}.
A*M-2={{A*M-2}}.

日付: {{Y=2021}}年{{M=4}}月{{D=27}}日
{{"☆ "&NAME&" ☆"}}
0654蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 22:28:29.02ID:CrWxBL6F
>>653
くっさ、くっさわらたんよ。ははは。

お題: 5chに粘着して、トリップ付きのコテハンを罵倒し続けるボットを作れ。
0655蟻人間 ◆T6xkBnTXz7B0
垢版 |
2021/04/27(火) 22:30:28.43ID:CrWxBL6F
人間がボットみたいなことやってたらカバみたいだね。ほんとほんと。
0656デフォルトの名無しさん
垢版 |
2021/05/03(月) 17:08:04.28ID:meUcD9ks
お題
ファイルパスを入力として受け取り、そのサブパスをすべて出力してください

入力: A/B/B/B
出力:
A
A/B
A/B/B
A/B/B/B
0658デフォルトの名無しさん
垢版 |
2021/05/03(月) 20:05:34.50ID:vJY6tWsE
>>656
haskell

import Data.List

subPathes p = [ str |
str' <- tail $ inits $ p ++ "/",
last str' == '/',
let str = ( reverse $ inits str' ) !! 1 ]

main = mapM print $ subPathes "A/B/B/B"
0659デフォルトの名無しさん
垢版 |
2021/05/03(月) 22:24:37.21ID:v5K6mFSj
>>656 C
char *str = "A/B/B/B";
int i = 0;
while (str[i]) {
if (str[i] == '/') {
char c[i + 1];
memcpy(c, str, i);
c[i] = 0;
printf("%s\n", c);
}
i++;
}
printf("%s\n", str);
0663デフォルトの名無しさん
垢版 |
2021/05/04(火) 02:03:51.93ID:BGUDbBhh
文字列をPATHの区切り文字で後ろから検索しないで先頭から検索しても同じと気付いたのでこっそり直した。
0664デフォルトの名無しさん
垢版 |
2021/05/04(火) 18:30:10.36ID:0HSekrvc
>>656 Ruby
def f(s)
a=s.split("/")
(0..a.size-1).map{|i| a[0..i].join("/")}
end
p f("A/B/B/B")
実行結果
["A", "A/B", "A/B/B", "A/B/B/B"]
0665デフォルトの名無しさん
垢版 |
2021/05/06(木) 18:06:27.01ID:b7Mkjg0R
>>656
Elixir

list = String.split( "a/bc/d", "/" ) # 分割

# 第2引数は、蓄積変数の初期値
%{ list: result } = Enum.reduce( list, %{ list: [ ], word: "" }, fn( str, acc )->

tmp_str = acc.word <> str # 文字だけを連結する。/ は連結しない

acc = %{ acc | list: acc.list ++ [ tmp_str ] } # 連結
acc = %{ acc | word: tmp_str <> "/" } # 連結
acc
end )

IO.inspect result
#=> ["a", "a/bc", "a/bc/d"]
0667デフォルトの名無しさん
垢版 |
2021/05/06(木) 20:53:31.79ID:DSX8dnAp
ここに練習用のいいファイルあるわ
https://tackle57.base.ec/
0672デフォルトの名無しさん
垢版 |
2021/05/06(木) 22:23:58.98ID:wWHyWlvf
>>668
#include <studio.h>
0673行間を読みなさいw
垢版 |
2021/05/07(金) 13:48:08.72ID:H+I+sfZ3
WHEREコマンドはReactOSに既に実装されています。
なので、(あえて作る場合でも)それを基にしてく
ださい(よ、頼むからさ。失礼だと思わないの?)

>コマンドではなく機能です。そして(既に実装されている)
>それは、この目的に対して便利ではありません。

貴方は公開されている(ReactOS実装の?)関数の
コードをパクって、独立したアプリケーションにしたと
いうわけですね。
というのであれば(我々の)メインストリームコードと
同期しているサードパーティコードみたいな感じを
装う必要はありません(はっきり言わせてもらえば
「しないで下さい」)
0674デフォルトの名無しさん
垢版 |
2021/05/07(金) 13:57:45.37ID:H+I+sfZ3
システムで色々な箇所で使用される短縮名称
を正式名称と(相互)変換する機能なんて
アルゴリズムとかの題材とかには不適。
泥臭い部分がかなりあるシステム固有の設計
の話になるしたとえコードは公開しているに
せよ部外者の立ち入りは歓迎されないのは
当然。 実情を詳しく知らない外部の人に
任せられる部分じゃなかったりするから。
0675デフォルトの名無しさん
垢版 |
2021/05/07(金) 19:10:13.55ID:FdFZQv1E
>>656 JavaScript
"A/B/B/B".replace(/^\/|\/?[^\/]*/g, (_, o, s) => console.log(s.substring(0, o)));
0676Mb
垢版 |
2021/05/07(金) 22:02:57.18ID:P+8SzjSX
読み仮名(ひらがな、カタカナ)から、単純なコード順の整列キーを
生成するルーチンを書く。
単純にコード順で整列すると、「ガレージ」は「カレー」の直後には
こなくて、「か(蚊)」の後ではなく、「ガ(蛾)」の後に
来てしまう。
比較関数を定義しようとすると、順序関係が一意に決まらなくなって
整列ルーチンが止まらなくなる。また、SQL などの整列機能が利用できない。
業務系のシステムだと、企業名だとか個人名だとかの読みで整列する
要求があるので、読みの入力時に整列用のキーを生成しておくのが
吉と思われる。
0681デフォルトの名無しさん
垢版 |
2021/05/09(日) 21:15:00.81ID:1F2i56L2
お題:
N 人が一列に並んでおり、左から i 人目の人は色 C[i] の服を着ています。

あるチームは次の条件を満たすとき、良いチームであると言います。
- 0 人以上が所属している。
- すべての色 i について、色 i の服を着た人がチームに偶数人所属している。

N 人から "連続する" 0 人以上を選んで良いチームを作るとき、
チームに所属する人の数としてあり得る最大値を求めて下さい。

制約:
1≦N≦10^6
1≦C[i]≦60

入力:
N
C1 C2 ... CN

入力例 1
5
1 2 3 3 1

出力例 1
2

入力例 2
5
1 2 3 4 5

出力例 2
0
0682デフォルトの名無しさん
垢版 |
2021/05/09(日) 22:47:51.84ID:YYfh4rSr
>>681
Haskell

import Data.List

mxLenGoodTeams cs = let
teams = [ take j $ drop i $ cs |
i <- [ 0..( length cs - 1) ],
j <- [ 2 .. ( length cs - i ) ] ]
isGoodTeam team
= all ( even . length ) $ group $ sort $ team
in maximum $ ( 0 : ) $ map length $ filter isGoodTeam teams

main = do
print $ mxLenGoodTeams $ [ 1,2,3,3,1 ]
print $ mxLenGoodTeams $ [ 1,2,3,4,5 ]
0686デフォルトの名無しさん
垢版 |
2021/05/11(火) 00:16:24.82ID:sq5XRTcM
>>681
問題の意味がわからない。

> - すべての色 i について、色 i の服を着た人がチームに偶数人所属している。

とはどういう意味なのか?
「すべての色 i 」とは何か?
「色 i の服を着た人がチームに偶数人所属」というのはどういう意味なのか? 同じ色の服を着た人は存在しないのだよな?
0687デフォルトの名無しさん
垢版 |
2021/05/11(火) 05:10:59.51ID:TUYWs3v7
毎度ながら日本語も問題作成も入出力例もクッソ下手だとは思うが
おまえはおまえで読解力無さ過ぎ
連続した (1≦10^6)個のデータ
データ内容は 1≦60
データ内容が偶数個となる連続した部分の最大長
1 2 2 3 3 4 4 5 → 2 2 3 3 4 4 → 6
1 2 3 4 2 3 4 5 → 2 3 4 2 3 4 → 6
1 2 3 4 5 2 3 4 → - → 0
1 2 3 3 2 4 5 4 → 2 3 3 2 → 4
1 2 3 2 2 3 2 4 → 2 3 2 2 3 2 → 6

まあ例に関しては俺も人のこと言えない
陥りやすいミスを確認しやすいキラーサンプル的な例がいくつかあればベスト
0688デフォルトの名無しさん
垢版 |
2021/05/11(火) 20:07:35.50ID:m1fDyeBb
入出力例は不親切だとは思うが
問題文自体は問題ないでしょう
あれが理解できないというのであれば理解できない側の能力に問題がある
0693デフォルトの名無しさん
垢版 |
2021/05/11(火) 20:30:24.67ID:AKHuOMpp
別にiが添え字の自然数と宣言しているわけでもなし文法的にも間違ってない
アスペでもない限り理解できる
0698デフォルトの名無しさん
垢版 |
2021/05/12(水) 10:57:02.98ID:xHZdId+E
プログラミング言語が使えても日本語が使えないのでは話が伝わらない。
それだったらプログラミング言語でそのまま書いてくれた方がここのスレでは話が通じる。
0699デフォルトの名無しさん
垢版 |
2021/05/12(水) 12:28:32.10ID:kJR81pbU
・左から100番目の人はC[100]の色の服を着ていると読める
・列を自由に入力して良いのなら、最大値はN以下の偶数となり自明
0701デフォルトの名無しさん
垢版 |
2021/05/12(水) 16:05:32.13ID:ASs2TDTE
>>681
出題者です
問題文がわかりずらかったみたいですいません

想定解法書きます (配列はすべて 0-index です)
A[0] = 0
A[i] = A[i - 1] xor (2^(C[i - 1] - 1)) (1≦i≦N)
な配列 A を考えます

ある区間 [L, R) がいいチームであるならば、A[R] xor A[L] = 0 です (累積和と同じ発想です)
両辺に A[R] を xor すると A[L] = A[R] になります

R を全探索しながらあり得る L のうちで一番左側のものを連想配列などで求めることで
N = 10^6 などのケースでも高速に答えを得ることができます
0702デフォルトの名無しさん
垢版 |
2021/05/13(木) 13:08:14.73ID:tJiNVUVY
問題文の他例が二つしかないから分かりにくい
>>687の説明みるまで何が良いチームなのか分かりにくい
0703デフォルトの名無しさん
垢版 |
2021/05/13(木) 19:07:49.38ID:3W7MB1VC
> 一列に並んでおり、左から
左てなんだ?先頭末尾なら分かるが
> 良いチームであると言います
なんだそのモヤる日本語。普通にチームで良いだろ
チームの条件として色が偶数があれば良いんだから
> i 人目の人は色 C[i] の服を着て
あとの制約見るまで一意かと勘違いする。説明でいちいち C[i] と置くのもイミフ

説明をただただややこしくしてるだけ
仕事で仕様の説明でこんな喩え話してきたらキレるわ
0705Mb
垢版 |
2021/05/13(木) 21:42:39.21ID:kEXKw6jf
>>693
> アスペでもない限り理解できる
「アスペルガー症候群」というのは、昔は「高機能広汎性発達障害」といって、
わりと馬鹿にしたもんでもない。かくいう私も、いわゆる「アスペ」の
一人だ。

ここで問題。日本語の(現代語の)動詞のうち、アルゴリズム的に押さえこめる
動詞(規則活用動詞)"以外の" 動詞はいくつあるか。
なお、「長尾の法則」(頭から見ていって、非・漢字から漢字に変化するところで、
文節は切れる)は使ってよし(「お」とか「ご」とかは名詞につくから、
このさい関係はなし)。
とりあえず六つはあって、サ変とかカ変とかは既知だけど、「そもそも、
どれだけあるのか?」っつー話になると、かなり面倒。
0706デフォルトの名無しさん
垢版 |
2021/05/13(木) 21:45:18.19ID:B4CYAsif
>>705
> アルゴリズム的に押さえこめる

これどういう意味? 意味わかんなすぎてキレそうなんだけど
0708デフォルトの名無しさん
垢版 |
2021/05/13(木) 23:36:26.05ID:mWio4uhK
さっさとPythonやらせれ
ちょっとでいいから
20年前に覚えたPerlに変わるマクロがいるんじゃああああああ

VBAでいいとかいわない
0709デフォルトの名無しさん
垢版 |
2021/05/14(金) 11:54:50.47ID:l/Mcr9Yu
バカの書いた不適切な文書は不和をもたらす
>>681のことな
0710デフォルトの名無しさん
垢版 |
2021/05/14(金) 13:21:20.02ID:23AH7lhZ
もうこれからは出題するときは頭に馬鹿には理解できない問題
ってとりあえず書いておけばいいのに
そうすれば荒れることもなくなるだろうから
0711デフォルトの名無しさん
垢版 |
2021/05/14(金) 13:38:00.72ID:f3dsViZI
【コミュニティの一生】

面白い人が面白いことをする

面白いから凡人が集まってくる

住み着いた凡人が居場所を守るために主張し始める

面白い人が見切りをつけて居なくなる

残った凡人が面白くないことをする

面白くないので皆居なくなる
0712デフォルトの名無しさん
垢版 |
2021/05/14(金) 14:08:14.84ID:4R64iY9Y
問題を作るのは難しいからしゃあない
どんな入力で、求めるのが値なのかアルゴリズムなのかを明示すればいい
0713デフォルトの名無しさん
垢版 |
2021/05/14(金) 15:59:25.59ID:BwDBHw+5
お題: join関数を自作せよ
join関数は第2引数の配列を第1引数の文字列で連結する関数である

func join(sep, array)

s = join(':', ['1', '2', '3'])
puts(s)
# 1:2:3

sepは文字列で、文字列で無かった場合の動作は未定義である
arrayは長さが0以上の配列で要素は文字列である。それ以外の構造は未定義である
0714デフォルトの名無しさん
垢版 |
2021/05/14(金) 16:23:22.95ID:WbiXCFQ1
先に解答例を作ってそこから試験問題作る先生のように
逆にたどって問題作れば分かり易い問題作れるのに

イキって、よーし、ぼくちゃん問題作っちゃるぞー!って、
解答未定のまま問題から作り始めるから今回のようにアフォなことになるんよ
0715デフォルトの名無しさん
垢版 |
2021/05/14(金) 16:35:13.82ID:cn5v//cT
python
def joint(s,x,y=""):
if len(x) == 1:
print(f"{x[-1]}{y}")
else:
joint(s,x[:-1],f"{s}{x[-1]}{y}"))
■ このスレッドは過去ログ倉庫に格納されています

ニューススポーツなんでも実況