プログラミングのお題スレ Part19
■ このスレッドは過去ログ倉庫に格納されています
お題: 依存関係のあるソート。与えられたいくつかの項目について、各項目ごとに依存関係が指定される。依存対象が先に来るように項目のリストをソートしなさい。 依存関係に循環がある場合は「ERROR」と出力しなさい。依存関係がない場合は名前の順でソートしなさい。 例1) {A, B, C} AはB, Cに依存する。 BはCに依存する。 Cは何にも依存しない。 例2) {A, B, C, D} AはCに依存する。 BはDに依存する。 CはB, Dに依存する。 Dは何にも依存しない。 例3) {A, B, C, D, E} AはEに依存する。 BはDに依存する。 CはBに依存する。 Dは何にも依存しない。 EはBに依存する。 例ってそれぞれの入力してでどう言う出力なのか答え出さないと例にならんやん? >>622 例1の出力) (C, B, A). 例2の出力) (D, B, C, A). 例3の出力) (D, B, C, E, A). 全順序じゃないから、単純なソートアルゴリズムじゃダメみたいだね。 >>628 アルゴリズムを簡単に解説してくれますか? すみません。 例えば>>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判定して終了すれば良い お題が気持ち悪い 単に有向グラフの辺となるものだけ指定すれば良いのに 依存とか書いちゃうから以下みたいな間接依存が許されない雰囲気 AはBに依存 BはCに依存 >>631 お前全然分かってないだろ 理解できないくせに聞くな 順序集合の定義自体は超簡単じゃね? 順序集合の定理なんか使わないから順序集合なんて言葉を使う必要もないけど アルゴリズム的には 極大(極小)元の中で名前順の先頭である元を取り出す を繰り返すだけで良い 取り出せなくなってまだ残っていたらERROR >>630 みたいに無駄に長く説明しなくて良い 順序集合真面目にやるなら集合と位相について学ぶ必要があるわけで そりゃーC++には半順序がバンバン出てくるから選ばれた人間向けの言語だよ。 >>634 ちゃんと理解して実装したぜ。 https://github.com/katahiromz/OleBow/commit/f65c774b625385e855971adb1275de1fd6ebee0c 循環参照の例がうまくいかないけど。 // :: IBindCtx: IRunningObjectTable // :: IEnumMoniker: IMoniker // :: IMoniker: IBindCtx // :: IMoniker: IEnumMoniker // :: IRunningObjectTable: IEnumMoniker // :: IRunningObjectTable: IMoniker // :: PartitionMoniker: IMoniker // :: SoapMoniker: IMoniker ポインタ型とかは後回しでいっかな。 >>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" >>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" お題 JSONでシリアライズされた未知のm×nの行列が与えられる。 転置行列を返せ。転置行列はシリアライズされていなくてもよい。 例 入力 "[[1,2],[3,4]]" 出力 [[1,3],[2,4]] >>642 Ruby require "json" p JSON.parse(gets).transpose # => [[1, 3], [2, ,4]] 当然transpose標準で用意されてる言語はそうなるわなw >>642 J smoutput |: ". @ }: @ }: ;. _1 }. stdin '' 入力 [[1,2,3].[4,5,6]] 出力 1 4 2 5 3 6 お題: コマンドラインで動作するエクセルもどきを作れ。入力テキストの中身に特定の形式の「フィールド」(field: 欄)を埋め込んでおく。今回はフィールドは以下のような形式で表現される。 (1) {{=数式}} (2) {{フィールド名:文字列}} (3) {{フィールド名:=数式}} フィールドは{{ }}で囲んだ文字列で指定される。 数式にはフィールド名を変数とする式を指定できる。フィールド名は半角英数字の組み合わせとする。 式は少なくとも、丸カッコと、整数の四則演算と、整数から文字列への変換と、文字列の連結をサポートすること。 入力テキストのそれぞれのフィールドを評価後の値に置き換えたテキストを出力せよ。フィールドの循環参照や式のエラーがあった場合はその場所に「ERROR」と出力せよ。 その他の仕様についてはエクセルをできる限りまねること。 >>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&">"}} >>647 さらに追記。 {{=数式}}と{{:=数式}}は同じように解釈すること。 >>649 代入文か代入式を許容することか。{{A=3}} そっちの方がいいかもね。 エクセルは数式の先頭で=を書いてるだけで、それ以外に代入式や代入文はなかったはず。 >>646 お題を書き直します。 お題: コマンドラインで動作するエクセルもどきを作れ。入力テキストの中身に特定の形式の「フィールド」(field: 欄)を埋め込んでおく。今回はフィールドは以下のような形式で表現される。 (1) {{数式}} (2) {{フィールド名=数式}} フィールドは{{ }}で囲んだ文字列で指定される。 数式にはフィールド名を変数とする式を指定できる。フィールド名は英字で始まる半角英数字の組み合わせとする。 式は少なくとも、丸カッコと、整数の四則演算と、値の比較と、整数から文字列への変換と、文字列の連結をサポートすること。等号は二文字の==とする。 入力テキストのそれぞれのフィールドを評価後の値に置き換えたテキストを出力せよ。フィールドの循環参照や式のエラーがあった場合はその場所に「ERROR」と出力せよ。 >>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&" ☆"}} >>653 くっさ、くっさわらたんよ。ははは。 お題: 5chに粘着して、トリップ付きのコテハンを罵倒し続けるボットを作れ。 人間がボットみたいなことやってたらカバみたいだね。ほんとほんと。 お題 ファイルパスを入力として受け取り、そのサブパスをすべて出力してください 入力: A/B/B/B 出力: A A/B A/B/B A/B/B/B >>656 Ruby 'A/B/B/B'.gsub(/.+?(?<=\/|$)/).reduce(''){|s, a|p s + a} # => "A/" "A/B/" "A/B/B/" "A/B/B/B" >>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" >>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); >>656 Ruby gets.split( ?/ ).inject( [] ){|r,d| (r << d).tap{|t| puts t * ?/ } } python import sys from pathlib import PurePath for x in PurePath(sys.argv[1]).parents: print(x) >>656 Kotlin https://paiza.io/projects/KhmBe1ysOa3PIaPX7xJkDg 最初は再帰でやろうと思ったけど止めて、Kotlin らしく拡張プロパティ作って実現した。 文字列をPATHの区切り文字で後ろから検索しないで先頭から検索しても同じと気付いたのでこっそり直した。 >>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"] >>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"] a="ko/koh/oreo/n/eone" ['/'.join(a.split('/')[0:i+1]) for i in range(len(a.split('/')))] >>667 さりげなく妙に高い値段のソフトの販売サイトに誘導しないように。 >>668 #include <studio.h> WHEREコマンドはReactOSに既に実装されています。 なので、(あえて作る場合でも)それを基にしてく ださい(よ、頼むからさ。失礼だと思わないの?) >コマンドではなく機能です。そして(既に実装されている) >それは、この目的に対して便利ではありません。 貴方は公開されている(ReactOS実装の?)関数の コードをパクって、独立したアプリケーションにしたと いうわけですね。 というのであれば(我々の)メインストリームコードと 同期しているサードパーティコードみたいな感じを 装う必要はありません(はっきり言わせてもらえば 「しないで下さい」) システムで色々な箇所で使用される短縮名称 を正式名称と(相互)変換する機能なんて アルゴリズムとかの題材とかには不適。 泥臭い部分がかなりあるシステム固有の設計 の話になるしたとえコードは公開しているに せよ部外者の立ち入りは歓迎されないのは 当然。 実情を詳しく知らない外部の人に 任せられる部分じゃなかったりするから。 >>656 JavaScript "A/B/B/B".replace(/^\/|\/?[^\/]*/g, (_, o, s) => console.log(s.substring(0, o))); 読み仮名(ひらがな、カタカナ)から、単純なコード順の整列キーを 生成するルーチンを書く。 単純にコード順で整列すると、「ガレージ」は「カレー」の直後には こなくて、「か(蚊)」の後ではなく、「ガ(蛾)」の後に 来てしまう。 比較関数を定義しようとすると、順序関係が一意に決まらなくなって 整列ルーチンが止まらなくなる。また、SQL などの整列機能が利用できない。 業務系のシステムだと、企業名だとか個人名だとかの読みで整列する 要求があるので、読みの入力時に整列用のキーを生成しておくのが 吉と思われる。 >>651 C++ エクセル使ったことないから挙動が違ってたらごめんね 最後のほうはやっつけで書いたのでバグってるかもしれない https://wandbox.org/permlink/AfU4a1aLrkxhkErW >>677 うわー、1000行近い大作。しかもかなりモダンなC++。ひょえーー。 お題: 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 >>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 ] >>681 問題の意味がわからない。 > - すべての色 i について、色 i の服を着た人がチームに偶数人所属している。 とはどういう意味なのか? 「すべての色 i 」とは何か? 「色 i の服を着た人がチームに偶数人所属」というのはどういう意味なのか? 同じ色の服を着た人は存在しないのだよな? 毎度ながら日本語も問題作成も入出力例もクッソ下手だとは思うが おまえはおまえで読解力無さ過ぎ 連続した (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 まあ例に関しては俺も人のこと言えない 陥りやすいミスを確認しやすいキラーサンプル的な例がいくつかあればベスト 入出力例は不親切だとは思うが 問題文自体は問題ないでしょう あれが理解できないというのであれば理解できない側の能力に問題がある 色C[i]は「i番目の人が来ている服の色」 色iは単に色 正しくないんだから突っ込まれて当然 >>690 Fラン文系か? >>691 真面目に何がダメだったのかわからない 教えてください... 別にiが添え字の自然数と宣言しているわけでもなし文法的にも間違ってない アスペでもない限り理解できる C[blue]みたいな? iはインデックスじゃないんだ 出題の意図は>>681 で分かる >>681 はバカということも分かる >>686 が嫌味で書いたのか本当にわからなかったのかはわからない プログラミング言語が使えても日本語が使えないのでは話が伝わらない。 それだったらプログラミング言語でそのまま書いてくれた方がここのスレでは話が通じる。 ・左から100番目の人はC[100]の色の服を着ていると読める ・列を自由に入力して良いのなら、最大値はN以下の偶数となり自明 >>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 などのケースでも高速に答えを得ることができます 問題文の他例が二つしかないから分かりにくい >>687 の説明みるまで何が良いチームなのか分かりにくい > 一列に並んでおり、左から 左てなんだ?先頭末尾なら分かるが > 良いチームであると言います なんだそのモヤる日本語。普通にチームで良いだろ チームの条件として色が偶数があれば良いんだから > i 人目の人は色 C[i] の服を着て あとの制約見るまで一意かと勘違いする。説明でいちいち C[i] と置くのもイミフ 説明をただただややこしくしてるだけ 仕事で仕様の説明でこんな喩え話してきたらキレるわ >>693 > アスペでもない限り理解できる 「アスペルガー症候群」というのは、昔は「高機能広汎性発達障害」といって、 わりと馬鹿にしたもんでもない。かくいう私も、いわゆる「アスペ」の 一人だ。 ここで問題。日本語の(現代語の)動詞のうち、アルゴリズム的に押さえこめる 動詞(規則活用動詞)"以外の" 動詞はいくつあるか。 なお、「長尾の法則」(頭から見ていって、非・漢字から漢字に変化するところで、 文節は切れる)は使ってよし(「お」とか「ご」とかは名詞につくから、 このさい関係はなし)。 とりあえず六つはあって、サ変とかカ変とかは既知だけど、「そもそも、 どれだけあるのか?」っつー話になると、かなり面倒。 >>705 > アルゴリズム的に押さえこめる これどういう意味? 意味わかんなすぎてキレそうなんだけど さっさとPythonやらせれ ちょっとでいいから 20年前に覚えたPerlに変わるマクロがいるんじゃああああああ VBAでいいとかいわない バカの書いた不適切な文書は不和をもたらす >>681 のことな もうこれからは出題するときは頭に馬鹿には理解できない問題 ってとりあえず書いておけばいいのに そうすれば荒れることもなくなるだろうから 【コミュニティの一生】 面白い人が面白いことをする ↓ 面白いから凡人が集まってくる ↓ 住み着いた凡人が居場所を守るために主張し始める ↓ 面白い人が見切りをつけて居なくなる ↓ 残った凡人が面白くないことをする ↓ 面白くないので皆居なくなる 問題を作るのは難しいからしゃあない どんな入力で、求めるのが値なのかアルゴリズムなのかを明示すればいい お題: join関数を自作せよ join関数は第2引数の配列を第1引数の文字列で連結する関数である func join(sep, array) s = join(':', ['1', '2', '3']) puts(s) # 1:2:3 sepは文字列で、文字列で無かった場合の動作は未定義である arrayは長さが0以上の配列で要素は文字列である。それ以外の構造は未定義である 先に解答例を作ってそこから試験問題作る先生のように 逆にたどって問題作れば分かり易い問題作れるのに イキって、よーし、ぼくちゃん問題作っちゃるぞー!って、 解答未定のまま問題から作り始めるから今回のようにアフォなことになるんよ 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}")) >>713 C++ https://ideone.com/HCgb0A モダンなC++だともっと書き方違うんだろうか? 11, 14あたりしか知らないので不安 >>713 Haskell join x = tail . concat . map ( ( x : ) . return ) main = do print $ join ':' "123" print $ join ' ' "Hello" >>713 Lua function join(d, a) local r = a[1] for i = 2, #a do r = r .. d .. a[i] end return r end print(join(":", {"1", "2", "3"})) 実行結果 1:2:3 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる