プログラミングのお題スレ Part18
■ このスレッドは過去ログ倉庫に格納されています
お題: 左から右へ、1から10までの番号が付いたマスが順番に隙間なく並んでいます。 今日、訪問者N人があなたに会いにやってきます。各訪問者i(1≦i≦N)は時刻TiにマスPiを訪れます。 ここで、あなたが時刻TiにマスPiに居たのならば「訪問者iは満足した」とします。 最大で何人の訪問者を満足させられるか求めてください。 制約: 最初、時刻は0とする。 あなたは最初、マス1にいる。 あなたは隣り合うマスへの移動手段しか持たない。 1マス移動した場合にも、移動せずに現在マスに留まった場合にも時間1を消費する。 Ti == Tj で Pi == Pj ならば i == j 1≦N ≦10^5 1≦Ti≦10^5 1≦Pi≦10 入力: N T1 P1 T2 P2 ... TN PN 出力: (最大で何人を満足させられるか) 例1: 入力: 5 5 4 2 3 3 2 3 4 4 4 出力: 4 前回のお題はC++の方からしか回答を頂けなかったので、他の言語の方も考えていただけると嬉しいです Tが10^5のそれぞれのマスにいたときの点数を求める(客がいた場合1、いなかったら0) Tが10^5-1のときのマスの点数を求める(そこに客がいたなら1、いなかったら0 更にそこから次の時間に移動可能なマスの最大の点数のものを加える) Tが1までくり返す これで良さそうな気がするけど書くのがめんどくさい >>453 「この文字列の文字数を求める」んじゃないの? バイト数だったらUTF-8だろうがSJISだろうが関係なく, バイトの個数を数えればいいだけになってしまうが……。 文字コードまわりの難しさにぶつかったことないから何が何やら >>453 Ruby 文字数とバイト数を適当に出力 require "cgi" require "cgi" str = CGI.unescapeHTML( "あaθ💀xΩ死🄫" ) sbs = str.bytes i = n = 0 while i < sbs.size case sbs[i] >> 4 when 0..7; i += 1 when 8..11; warn "Error" when 12,13; i += 2 when 14; i += 3 when 15 case sbs[i] & 0xF when 0..7; i += 4 when 8..11; i += 5 when 12,13; i += 6 else warn "Error" end end n += 1 end puts "#{n} chars\n#{str.size} chars" puts "#{str.force_encoding( Encoding::BINARY ).size} bytes\n#{sbs.size} bytes" puts str.bytes.map{|x| '%02X' % x }.join(' ') #=> 8 chars 8 chars 20 bytes 20 bytes E3 81 82 61 CE B8 F0 9F 92 80 78 CE A9 E6 AD BB F0 9F 84 AB 普通に処理系がchar配列にしたときサイズを入れてくれるからそれでわかっちゃうw 書いてある条件だけで、求めて下さい! 他の方法では、簡単すぎるので >>461 もう一度訊くけど, ほんとに「バイト数」を求めたいの? だったら $ echo ' あaθ💀xΩ死🄫 ' | wc -c これで一瞬だけど。 文字数なら,UTF-8を扱える言語で数えるか, POSIX shでやるなら……面倒だな……。 https://gist.github.com/cmplstofB/0b0ce2bf052b3bb64d091fc83504fc32#file-u8dec-sh こういうの使えばいいかな。 なお,wc -mはPOSIXでは必ずしも UTF-8文字列を扱えるとは既定されていないので今回の目的には適さない。 >>454 これ結構難しい。 まず普通に算法を考える段階で行き詰まってるw 頭悪いな〜 >>380 Perl5 ($H, $W) = split' ',<DATA>; @a = map{[split/\s*/]} <DATA>; for $h (0..$H-1) { for $w (0..$W-1) { $c = $a[$h][$w]; $S = "$h,$w" if $c eq 'S'; $G = "$h,$w" if $c eq 'G'; if ($c ne '#') { $e{($h-1).",$w $h,$w"}++ if $h and $a[$h-1][$w] =~ /[.SG]/; $e{"$h,".($w-1)." $h,$w"}++ if $w and $a[$h][$w-1] =~ /[.SG]/; }}} use feature qw{current_sub say}; no warnings 'experimental'; sub { my $p = @_[-1]; for my $q (map{s/ *$p *//; $_} grep{/$p/} keys %e) { if ($q eq $G) { $h{"@{[@_, $q]}"}++ } else { __SUB__->(@_, $q) unless grep{/$q/} @_ } } }->($S); say scalar keys %h; __DATA__ 5 5 S.... ##.#. ...#. ...#. ....G 実行結果 ~ $ perl 18_380_maze_paths.pl 12 >>466 今思うとエッジの表現は無向ではなく二重の有効グラフにしたほうが簡潔なコードになったかもしれない まぁいいや…二度書く気は起きない… >>395 Kotlin https://paiza.io/projects/N9X2CVAQj3NJ0RXPrk7i0g 区切りは文字列で指定出来るとか、大文字小文字無視とか、最大分割数を決められるだとか、色々と機能を追加してしまった。 お題 4999の逆数を小数点 以下48桁まで求める。 >>469 例外だけどbcコマンド scale=48 1/4999 .000200040008001600320064012802560512102420484096 >>469 Ruby puts ('%0.49f' % (1r/4999)).chop # => 0.000200040008001600320064012802560512102420484096 >>465 >>466 これって二つとも総当たりで解いてる? そうすると最悪3^(10^5)くらいの回数廻さないといけなくない? 1京くらいのループで解けるなら実用性はかろうじてある 競技性は無い >>465 はlast_time(10^5)回のループの中でCOL(10)回ループ入れてるし、10^6では? >>476 いや,総当たりなら,3^(10^5)。 時刻が1--10^5までの間に, 「留まる」「右/左に移動する」の計3通りを 互いに独立に(以前の行動に影響されずに) 行うから。 書いていて思ったけど,端に居るときは 行動可能性が2通りに減るけど, それでも2^N通りでは済まない。 >>474 >>466 は>>380 への回答なので その計算量の推定議論には該当しません >>478 1人が満足することで1点得るとする 点数の最大値は入力されたnの数しかないからn点で それぞれについて1点得るか得ないかの2^nしかない あとはそれを実現できるか移動があるかどうかが焦点になる なので全移動経路を総当りする必要性はない >>469 C++ #include <iostream> int main(){ const int d = 4999; int n = 1; std::cout << "0b0."; for( int i = 1; i <= 48; ++ i ){ n <<= 1; if( n >= d ){ n -= d; std::cout << '1'; } else { std::cout << '0'; } } std::cout << std::endl; return 0; } // STDOUT 0b0.000000000000110100011100000111010100101011010001 >>480 2^nも必要ないよ それぞれの時刻でホストが取れる状態はどのマスにいるかということだけ だから時刻xマスの数が全状態数 でその状態数の方が全経路数より圧倒的に少ないので 経路に沿ってではなくて状態について解いていく >>483 ん? ホストは隣合うマスにしか移動できないから, 単純にその場面での状態を考えるだけでは駄目なんでは? だから遡って計算していくときは隣り合うマスの結果しか参照しないよ >>465 のコードは多分バグがある気がする 51行目と57行目を a = score[j-1] + bit_test(timeline + i, j); a = score[j+1] + bit_test(timeline + i, j); こう変えて 43行目を for(i = last_time-1; i >= 0; i--){ こうするのが正しいと思う >>454 Perl5、人の訪問を待ち受け得るすべての場合を愚直に総当りで最大満足数を探す $T = <DATA>; use feature qw{signatures say}; no warnings 'experimental'; chomp $T; push @{$p{$$_[0]}}, $$_[1] for map{[split' ']}<DATA>; use List::Util 'max'; sub f($t, $p, $s) { if ($t++ < $T) { if (0 < $p and $p < 11) { $s++ if grep/$p/, @{$p{$t}}; $s += max(f($t, $p-1, $s), f($t, $p, $s), f($t, $p+1, $s)) } return $s } 0 } say f(0, 1, 0); __DATA__ 5 5 4 2 3 3 2 3 4 4 4 ~ $ perl 18_454_N_vztr.pl 4 >>454 python https://ideone.com/5qz7G8 満足させる人数の多い順から実現可能か探索する 既に不可能だと分かっている移動が含まれる場合は直ちに打ち切る >>490 perl読めないから間違ってたらごめんだが、 11 3 2 2 3 3 4 4 4 5 4 4 7 5 7 6 7 7 7 8 7 7 10 の入力で20を返してくる。(答えは5) >>492 はい、バグってました。投稿してから気がついた 時間あったら直します >>490 Perl5、>>489 のBug Fix、同じ所を何度も通るので漸化式かメモ化使って動的計画法で解けるようにできるかもしれない use feature qw{signatures say}; no warnings 'experimental'; $T = <DATA>; chomp $T; push @{$p{$$_[0]}}, $$_[1] for map{[split' ']}<DATA>; use List::Util 'max'; sub f($t, $p) { my $s = 0; if ($t <= $T) { if (0 < $p and $p < 11) { $s++ if grep{$_ eq $p} @{$p{$t}}; $t++; $s += max(f($t, $p-1), f($t, $p), f($t, $p+1)); } } $s } say f(0, 1); __DATA__ 11 3 2 2 3 3 4 4 4 5 4 4 7 5 7 6 7 7 7 8 7 7 10 >>494 誤記スマソ × >>489 のBug Fix ○ >>490 のBug Fix >>489 ご指摘の通りバグってたので再投稿します。 https://ideone.com/VxDLwz やりたかったことは>>456 が言っていることと全く同じです。 イメージとしてはhttps://imgur.com/j0azhSf.jpg (※お題を考えたい人は閲覧注意) >>465 のコードは大抵の場合なぜかうまくいくコードのようです。 >>454 Perl5、>>494 を動的計画法で解くように改良(但し再帰呼び出しを使っているので10^5など規模が大きい問題を解くなら下から上に計算してくる単純ループに書き換えた方が良い) no warnings 'experimental'; use feature qw{signatures say}; $T = <>; chomp $T; push @{$p{$$_[0]}}, $$_[1] for map{[split' ']}<>; use List::Util 'max'; sub f($t, $i) { my $s = 0; if (0 < $i and $i < 11) { return $m[$t][$i] if defined $m[$t][$i]; $s++ if grep{$_ == $i} @{$p{$t}}; $s += max(f($t+1, $i-1), f($t+1, $i), f($t+1, $i+1)) if $t < $T; $m[$t][$i] = $s; } $s } say f(0, 1); >>497 の実行結果 ~ $ cat 18_454_ex1.txt 5 5 4 2 3 3 2 3 4 4 4 ~ $ cat 18_454_ex1.txt | perl 18_454_N_vztr_DP_rec.pl 4 ~ $ cat 18_454_ex2.txt 11 3 2 2 3 3 4 4 4 5 4 4 7 5 7 6 7 7 7 8 7 7 10 ~ $ cat 18_454_ex2.txt | perl 18_454_N_vztr_DP_rec.pl 5 >>469 Perl5、小数点以下48桁で「丸め」 use bignum(p=>-48); print 1/4999, "\n"; 実行結果 $ perl 18_468_1_4999-48p.pl 0.000200040008001600320064012802560512102420484097 >>453 Elixir ary = for << byte <- "あaθ💀xΩ死🄫" >> do # 1バイトずつ、ループ << nibble::size( 4 ), _::size( 4 ) >> = << byte >> # 先頭の4ビット case nibble do n when n in 0..7 -> 1 n when n in 8..11 -> 0 n when n in 12..13 -> 2 14 -> 3 15 -> 4 end end res = Enum.reject( ary, fn n -> n == 0 end ) # 0 を削除する IO.inspect res # [3, 1, 2, 4, 1, 2, 3, 4] IO.puts( length res ) # 8文字 IO.puts( Enum.sum res ) # 20バイト >>454 go 動的計画法 package main import ( "fmt" ) var m [][]int func v(t int, p int) int { if 1 <= p && p <= 10 { return m[t][p] }; return 0 } func max3(n1 int, n2 int, n3 int) int { n := n1; if n < n2 { n = n2 }; if n < n3 { n = n3 }; return n } func main() { var n, t, p, i, T int fmt.Scan(&n) var a [][]int = make([][]int, n) for i=0; i<n; i++ { fmt.Scanf("%d %d", &t, &p) a[i] = []int{ t, p } if t > T { T = t } } m = make([][]int, T+1) for t=0; t<=T; t++ { m[t] = make([]int, 11) for p=1; p<=10; p++ { m[t][p] = 0 } } for i=0; i<n; i++ { m[a[i][0]][a[i][1]] = 1 } for t=T-1; 0<=t; t-- { for p=1; p<=10; p++ { m[t][p] += max3(v(t+1, p-1), v(t+1, p), v(t+1, p+1)) } } fmt.Println(m[0][1]) } >>502 の実行結果 ~ $ cat 18_454_ex1.txt 5 5 4 2 3 3 2 3 4 4 4 ~ $ cat 18_454_ex1.txt | go run 18_454_N_vztr_DP.go 4 ~ $ cat 18_454_ex2.txt 11 3 2 2 3 3 4 4 4 5 4 4 7 5 7 6 7 7 7 8 7 7 10 ~ $ cat 18_454_ex2.txt | go run 18_454_N_vztr_DP.go 5 >>454 Python3 n = int(input()) a = [list(map(int, input().split())) for i in range(n)] T = max([a[i][0] for i in range(n)]) m = [[0] * 11 for t in range(T+1)] for i in range(n): m[a[i][0]][a[i][1]] = 1 def v(t, p): return m[t][p] if 0 < p and p < 11 else 0 for t in reversed(range(T)): for p in range(1, 11): m[t][p] += max(v(t+1, p-1), v(t+1, p), v(t+1, p+1)) print(m[0][1]) 実行結果 (>>503 と同じテキストファイル 18_454_ex1.txt, 18_454_ex2.txt を入力に使用) ~ $ cat 18_454_ex1.txt | python 18_454_N_vztr_DP.py 4 ~ $ cat 18_454_ex2.txt | python 18_454_N_vztr_DP.py 5 >>504 for p in range(1, 11): m[t][p] += max(v(t+1, p-1), v(t+1, p), v(t+1, p+1)) を for p in range(1, 11): if t+1 < p: continue m[t][p] += max(v(t+1, p-1), v(t+1, p), v(t+1, p+1)) とか書くと、右上三角の不要な計算を省けるが10^5などtが大きいと大勢に影響はないな… お題 >>453 のルールに基いて、以下の3つの10進数のバイト列を、先頭(1バイト目)からチェックしていく時、 最初にルール違反となるのは、何バイト目か 129 130 120 169 240 159 146 206 184 お題:自然数nが現れる九九の表の最小サイズを求めよ octave https://ideone.com/JyIBOD お題: 「ジャンケンすたじあむ オンライン」というソーシャルゲームのウェブサイト、もしくはソフトウェアパッケージを制作・運営せよ。 ジャンケンをしたい人が集まって、ひたすらジャンケンをして、勝ち数を競うというソーシャルゲーム。 ジャンケン試合は2人組になり、お互いに出す手を事前に申告し、両者が申告したところでシステムが自動で勝敗を判定する。 動的計画法ってちゃんと勉強しないとなかなか思いつかないよな >>509 Haskell f x = head [ d | d <- [(ceiling $ sqrt $ fromInteger x)..], mod x d == 0] main = mapM_ print [(x,f x) | x<-[100..130]] お題: 沖縄の名物「シークワーサー」のことが書かれた記事のUTF-8日本語テキストファイル「input.txt」がある。 しかし、記事の執筆に多数の編集者が関わったため、シークワーサーの表記がぶれていることが分かった(次のリンクを参照)。 https://ja.m.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%AF%E3%83%AE%E3%83%BC%E3%82%B5%E3%83%BC 表記のぶれを「シークワーサー」に表記を統一したテキストファイル「output.txt」を出力せよ。 エンジニアが書いてるならシークワーサだな 間違いない >>516 input.txtの中身: 「シークヮーサーは、別名シイークワシャーと呼ばれ、シークヮーサーの香りがするシークヮーシャーのような柑橘系の果物である。シィークアーサーはアーサー王とは関係がないと思われる。」 "/シ(?:イ?ー|ィー?)ク[アワァヮ]ー?(?:サ|シャ)ー?/シークヮーサー/g" お題: お使いのプログラム言語で、COBOLに負けない最強の通貨型を設計せよ。 任意の桁数の10進整数を扱えること。 任意の有効桁数の10進小数を扱えること(10進浮動小数点数)。 加減乗除、剰余、任意桁での切り捨て・切り上げ・四捨五入が可能。 10進数表記で入出力できること。 比較的高速に演算できること。 蟻人間さんにお題:銀行丸めを整数型のみを使用して実装してください 昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな? 昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな? 分子や分母に分数が入ってきた場合 精度の面で面倒なことになるぞ >>516 sed -r 's/シ([イィ]ー?|ー)ク[アァワヮ]ー?(サ|シャ)ー/シークワーサー/g' -r は拡張正規表現を使うオプション。 これで >>518 の文を変換するとこうなる。 「シークワーサーは、別名シークワーサーと呼ばれ、シークワーサーの香りがするシークワーサーのような柑橘系の果物である。シークワーサ ーはアーサー王とは関係がないと思われる。」 現実問題では、long double型で十分な精度が出るから、独自の浮動小数点数は必要なさそう。 残りは四捨五入とか銀行丸めなどの端数処理。 bc コマンド使えば良い。 他の言語から使いたい場合はライブラリをリンクするか、またはこっそり裏で fork(), exec() してパイプで繋いで計算させるw >>535 とりあえずまあソースコードを読んで頂いてクレヨン。 ぶぶ漬けどうぞと言われて、美味しくいただいてさらに食レポまで始めてるような状態かな お題: (複数行のバックグラウンド、座標テキスト、座標)から合成テキストを返す関数を作れ 座標テキストとバックグラウンドは同じサイズ(とりあえず横4縦3とする) background ┏┓┏┓ ┃┗┛┃ ┗━━┛ 座標テキスト ab23 9014 8765 座標が 0なら ┏┓┏┓ ┃*┛┃ ┗━━┛ 6なら ┏┓┏┓ ┃┗┛┃ ┗━*┛ 11なら ┏*┏┓ ┃┗┛┃ ┗━━┛ あまり綺麗な実装が出来なかったから問題にした https://repl.it/@vip0/analogclock#index.js >>543 Ruby def analogClockStr( h, bg, positions ) (clockStr = bg.dup)[ positions.index( h.to_s(16) ) ] = '*' clockStr end background = ' ┏┓┏┓ ┃┗┛┃ ┗━━┛ '.strip.freeze positions = ' ab23 9014 8765 '.strip.freeze puts analogClockStr( 0, background, positions ) puts analogClockStr( 6, background, positions ) puts analogClockStr( 11, background, positions ) げっ確かに行ごとにreplace必要ないじゃん 何やってんだ俺 ありがとう >>543 くだらない質問スレか初心者質問スレ行け ほんとにどの問題よりもクソみたいな問題だと思っています 本当にすいませんでした ただ私は純粋にプログラミングが好きで 全く質問したかったわけじゃないのはわかってほしい 二次配列じゃないと処理できないものだと勘違いしていたのが甘いしシンプルにしすぎて問題が破綻してしまった 純粋にここにいる人たちが解法として書くコードは好きだし たまに驚くべき角度から解を出す人もいるしマイナーなアルゴリズムも知れて尊敬してる 今回もスマートなコードが見れるんじゃないかと純粋に期待して問題にしてみたんだ スレも今流れ遅かったし しかしお前らは牙を向いた 純粋に問題作成初心者の心を無碍にして 鋭い刃のような言葉を投げつけてきた お前らは今日から敵とみなす あばよ😎✋絶望しな >>551 奏ちゃん「自意識過剰なんじゃないですか?」 お題:文字列の末尾の数字をインクリメントしてください 入力 IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS 出力 IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.4 2024/05/19 Walang Kapalit ★ | Donguri System Team 5ちゃんねる