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

**デフォルトの名無しさん** · 2020/11/30(月) 00:04:05.21

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

【出題と回答例】
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/

**デフォルトの名無しさん** · 2021/01/10(日) 09:41:46.50

>>163 octave
https://ideone.com/GX9hjP
f = @() rand(randi([4 20]), 1);

**デフォルトの名無しさん** · 2021/01/10(日) 09:45:08.12

>>196
haskell

import Data.List

c = id
. map length
. map (\x -> takeWhile ( <= ( last x ) ) . reverse $ x)
. tail
. inits

main = do
print $ c [ 3, 1, 2, 6, 6 ]
----
[1,1,2,4,5]

**デフォルトの名無しさん** · 2021/01/10(日) 13:04:37.47

>>196
Java
https://paiza.io/projects/P5uIlZBMLt_cFSzjdkHApQ

**デフォルトの名無しさん** · 2021/01/11(月) 00:16:30.88

196読めた奴すごいな

**158** · 2021/01/11(月) 02:25:11.67

>>143
Kotlin

>>194のJavaのやつを見て>>158のKotlinのやつを改造した。

https://paiza.io/projects/iNRMUv2Annc6YFqJjAO4wg

要するに >>158 を作っている時に String#codePoints() に気付いていなくて自作してしまったということだが、
Java 8 から追加されたメソッドのようなので、>>158は古い JVM ライブラリでも動くということではある。

**デフォルトの名無しさん** · 2021/01/11(月) 02:44:15.64

お題
>>196を小学生にも理解できるぐらいのやさしい日本語に翻訳せよ。

**デフォルトの名無しさん** · 2021/01/11(月) 03:09:40.17

無理です
チンパンカンプン

**デフォルトの名無しさん** · 2021/01/11(月) 03:11:51.27

このスレの住人なら日本語分からなくても例だけ見れば普通に理解できるだろ
IQテストみたいなもんだ

**デフォルトの名無しさん** · 2021/01/11(月) 03:26:31.03

>>206
こういう事じゃない？
入力値が遡って比較する最大個数と値を兼ねてるんでしょ
同値ならindex(1始まり)の大きい方

入力:3 1 2 6 6 4
3　[(3)] →1
1　[3 (1)] →1
2　[3 (1 2)] →2
6　[(3 1 2 6)] →4
6　[(3 1 2 6 6)] →5
4　[3 1 (2 6 6 4)] →3

**デフォルトの名無しさん** · 2021/01/11(月) 03:36:50.19

>>209
最後の4違うぞ
入力:3 1 2 6 6 4
3　[(3)] →1
1　[3 (1)] →1
2　[3 (1 2)] →2
6　[(3 1 2 6)] →4
6　[(3 1 2 6 6)] →5
4　[3 1 2 6 6 (4)] →1

x_iは要素数。上の例でいうと()の中の数が何個あるかってこと。で、(右から)直近の要素の中での最大値が一番右の数字になるのは最大でいくつかってこと。
一番下の4のケースでは次の6を含んでしまうとMAXが4にはならないので要素数1で打ち止め。

**デフォルトの名無しさん** · 2021/01/11(月) 12:34:34.25

現在地から前に遡って見ていって自分と同じか小さい要素が続く数を
最初から最後まで求めるだけ
もっと早く一発で求める方法があるかは分からないけど

**デフォルトの名無しさん** · 2021/01/11(月) 12:57:43.66

>>206
長さ N の整数列 A が与えられる
A の連続した部分列であって、各 i (1≦i≦N) について次の条件を満たすものをすべて求めなさい
・整数 j (1≦j≦i) を max(A_j, A_{j+1}, ..., A_i) = A_i を満たす最小の j とし i - j + 1 の値

**デフォルトの名無しさん** · 2021/01/11(月) 13:02:19.99

最高水準位アルゴリズムで
最高値更新したら発表？

**デフォルトの名無しさん** · 2021/01/11(月) 14:52:41.81

>>196 C++ O(N log N)
セグメント木を使うと区間 max の二分探索を O(log N) で行える
atcoder の aclib を使用
https://wandbox.org/permlink/8rm8MsauDMJhvpAf

**デフォルトの名無しさん** · 2021/01/11(月) 15:14:59.89

>>214
しゅんごい

**デフォルトの名無しさん** · 2021/01/14(木) 09:22:07.11

お題
将棋のルールで可能な最初の2手を全て求める。

**デフォルトの名無しさん** · 2021/01/14(木) 11:00:00.08

なるほど
(∞,0)のみからなるリストから始めて(-値、インデックス)についての辞書式順序(ただしインデックスは降順)でリストに追加していくと考えればいいのか
i番目の要素(v,i)が来た時(u,h)<(w,j)の間に入るならvより大きい最大のインデックスはjだからi番目の出力はi-jになるのか

◆QZaw55cn4c · 2021/01/14(木) 18:33:59.62

>>216
すてきなお題ですね！

**デフォルトの名無しさん** · 2021/01/14(木) 19:35:36.96

>>216
先手後手ともに可能性が３０通りあるのでそれらを単純に組み合わせて出力すれば良い

**デフォルトの名無しさん** · 2021/01/14(木) 19:43:46.53

3手なら面白いけど2手ならつまらんな

**デフォルトの名無しさん** · 2021/01/16(土) 10:11:02.80

最初の初期状態の配置ならつまらんね
途中経過のどの状態からでもすべての2手(3手でもいいよ！）を出力とかなら
本格的な将棋プログラム組まないと導き出せない

**デフォルトの名無しさん** · 2021/01/16(土) 19:29:58.68

投了も一手ですか

**デフォルトの名無しさん** · 2021/01/19(火) 19:16:59.47

iZ-Cでサンプルログラムを書き始めました見てね
https://sunasunax.hatenablog.com

**デフォルトの名無しさん** · 2021/01/22(金) 23:33:42.04

お題：sortしてreverseしてforeachせよ
https://ideone.com/35HTkC
List(7, 8, 3, 6, 4).sorted.reverse.foreach(print)

**224** · 2021/01/22(金) 23:35:12.02

>>224 rust
https://ideone.com/SY2DMY
fn main() {
let mut v = [7, 8, 3, 6, 4];
v.sort();
v.reverse();
v.iter().for_each(|x| println!("{}", x));
}
>>224 dart
https://ideone.com/w26D8S
void main() {
var a = [7, 8, 3, 6, 4];
a.sort();
a.reversed.forEach(print);
}

**224** · 2021/01/22(金) 23:37:05.96

>>224 ocaml
https://ideone.com/bitFC6
List.iter print_int (List.rev (List.sort Pervasives.compare [7; 8; 3; 6; 4]))

>>224 ruby
https://ideone.com/K14REi
[7, 8, 3, 6, 4].sort.reverse.each(&method(:p))

>>224 octave
https://ideone.com/E2DoUr
arrayfun(@disp, flip(sort([7 8 3 6 4])))

**デフォルトの名無しさん** · 2021/01/23(土) 01:20:49.53

>>224 C++
for (auto i : multiset<int, greater<int>>({ 7, 8, 3, 6, 4 })) cout << i << endl;

9 · 2021/01/23(土) 02:47:09.23

>>224 Perl5

print reverse sort qw(7 8 3 6 4);

実行結果
$ perl 19_224.pl
87643

9 · 2021/01/23(土) 02:50:17.66

>>224 Perl5、foreach も要るんやったね…

print foreach reverse sort qw(7 8 3 6 4);

実行結果
$ perl 19_224.pl
87643

**デフォルトの名無しさん** · 2021/01/23(土) 08:37:55.12

>>224 Bash
cat <<EOS | sort -r | while read v; do echo ${v}; done
7
8
3
6
4
EOS

>>224 Ruby
[7, 8, 3, 6, 4].sort_by(&:-@).each{p _1}

**デフォルトの名無しさん** · 2021/01/23(土) 09:17:41.00

>>229
> print foreach reverse sort

perlってこんな気持ちいい書き方できる言語やったんけ
正直恐れ入った

**デフォルトの名無しさん** · 2021/01/23(土) 19:28:56.89

お題: 俺のチ〇コの長さ分だけfor文でカウントしてカウント変数を出力せよ

**デフォルトの名無しさん** · 2021/01/23(土) 19:32:36.06

print "9"

**デフォルトの名無しさん** · 2021/01/23(土) 20:01:06.10

>>232
perl

for ($i = 0; $i < 1; $i += 0.1) { print "$i\n" }

**蟻人間** ◆T6xkBnTXz7B0 · 2021/01/23(土) 21:37:12.62

お題: 日付をYYYYMMDD形式で表したとき、それを表す整数が今日より後に素数になる日付を求めなさい。

**デフォルトの名無しさん** · 2021/01/23(土) 23:19:53.94

それを表す整数とは？

**デフォルトの名無しさん** · 2021/01/24(日) 22:28:15.93

>>224
Kotlin script

kotlinc コマンドで REPL にして直接入力して実行した時のコピー。(>>> はプロンプト)
出力は println() を使って1つづつ改行させた。

>>> listOf(7, 8, 3, 6, 4).sorted().reversed().forEach { println(it) }
8
7
6
4
3
>>>

**デフォルトの名無しさん** · 2021/01/25(月) 14:58:49.27

お題:
整数 N が与えられます
長さ N の正整数列 A_1, ..., A_N であって以下の条件を満たす lcm(A_1, ..., A_N) が最小のものを求めなさい
・gcd(A_1, A_2) * gcd(A_2, A_3) * ... * gcd(A_{N-1}, A_N) * gcd(A_N, A_1) = lcm(A_1, ..., A_N)

制約:
3≦N≦4000

例:
入力: 5
出力: 6 15 35 77 22

**デフォルトの名無しさん** · 2021/01/25(月) 16:12:04.01

逆じゃね

**デフォルトの名無しさん** · 2021/01/25(月) 17:27:32.13

>>238 perl
print join ' ', (1) x $ARGV[0];

**デフォルトの名無しさん** · 2021/01/25(月) 17:53:44.58

A の全ては互いに異なる
を入れ忘れた

**デフォルトの名無しさん** · 2021/01/25(月) 17:58:02.52

Aiの制約で....

Aiが異なる正整数なら
　N=5 [1,2,4,8,64] ->lcm=64

Ai>=3 なら
　N=5 [5,7,14,6,15] -> lcm=210(=1*2*3*5*7)
　　　(同じlcmで数列は複数作れる)

※あの例はどういう条件だろう

**デフォルトの名無しさん** · 2021/01/25(月) 18:08:39.30

>>238
gcd とか lcm って何?

**デフォルトの名無しさん** · 2021/01/25(月) 18:09:29.39

すいません...
素数を小さい順に組み合わせて 2*3, 3*5, 5*7, 7*11, 11*2
とすると綺麗に数列が作れていいなーと思って投稿したのですが、最小ではなかったようです...
このお題は無かったことに

**デフォルトの名無しさん** · 2021/01/25(月) 18:10:17.78

あ、わかった。ググったら一発で出た。

**デフォルトの名無しさん** · 2021/01/25(月) 18:11:02.14

分かった途端に終了、か・・・

**デフォルトの名無しさん** · 2021/01/25(月) 18:14:04.63

没入感

**デフォルトの名無しさん** · 2021/01/25(月) 19:20:16.85

お題、灘中入試っぽい問題

開始点S から、終点G まで、最短距離9 で移動する方法は、何通りあるか？

移動は右か下へ、1ずつ移動できるが、* は通れない所である。
数字は通れる所で、単に分かりやすくするために座標を書いただけで、移動コストではない

S23456
12*456
1234*6
123456
12345G

**デフォルトの名無しさん** · 2021/01/25(月) 19:34:10.13

プログラムなら実際に駒動かしてかぞえるの？

なんか、足し算引き算で出来そうだよね、

**デフォルトの名無しさん** · 2021/01/25(月) 20:22:00.10

別名おねえさん問題

**デフォルトの名無しさん** · 2021/01/25(月) 20:24:55.52

∴>>250
その心は？

**デフォルトの名無しさん** · 2021/01/25(月) 21:25:54.70

>>248 sh
echo 48

#やっぱ計算しなきゃダメ？

**248** · 2021/01/25(月) 21:35:28.96

お姉さん問題なら、

Ruby で、そのライブラリを使って解いてみて

**248** · 2021/01/25(月) 21:48:23.33

超高速グラフ列挙アルゴリズム〈フカシギの数え方〉おねえさん問題

BDD/ZDD の湊真一が、北大から京大大学院の教授へと出世してる

**デフォルトの名無しさん** · 2021/01/25(月) 21:53:57.03

https://ideone.com/b2CQ5a
48ってなったからあってるのかな適当に作ったけど

**デフォルトの名無しさん** · 2021/01/26(火) 00:35:19.40

お題：
これ出題してみるか。

黒板に1～nの自然数が一つずつ書かれている。
二人でかわりばんこに次のルールで黒板に書かれた自然数を消していくゲームをする：
・自分の番のとき、黒板に残っている数から一つ選び、
　その数及びその数の約数をすべて消す。
・自分の番で黒板の数をすべて消し去ったとき勝者となる。

実はこのゲームはnによらず先攻必勝であるが、初手をどう打つかを判断するのは簡単でない。
1～30のすべての自然数nについて、後攻を勝たせないために初手で先攻が選ぶことができる数をプログラム中で5秒以内に計算し、すべて列挙せよ。

**デフォルトの名無しさん** · 2021/01/26(火) 00:44:35.83

1～30ならデータベース化してしまえばなんとかなるな

**デフォルトの名無しさん** · 2021/01/26(火) 01:03:48.09

>>255
簡単にするとこんな感じ？
https://ideone.com/UlFSdj

**デフォルトの名無しさん** · 2021/01/26(火) 05:34:51.12

>>248
9C4 - 3C1 * 6C3 - 6C2 * 3C1 + 3C1 * 3C1 * 3C1 = 48

**デフォルトの名無しさん** · 2021/01/26(火) 12:22:51.81

>>248
お受験風にdpで数え上げる

Haskell

test1 = ""
++ "┏┳━┳┳┓\n"
++ "┣┫ ┣┻┫\n"
++ "┣╋┳┫ ┃\n"
++ "┣╋╋╋┳┫\n"
++ "┗┻┻┻┻┛\n"

to01 = let
parseC c = if c == '\x2001' then 0 else 1
parseL = map ( parseC )
in map parseL . lines
cntRoots posCrs = let
z y x = zipWith ( * ) y $ zipWith ( + ) x $ ( 0 : ) $ z y x
rs = id
$ ( ( 1 : ( repeat 0 ) ) : )
$ zipWith z posCrs rs
in rs
nRoots = last . last . cntRoots

main = print $ nRoots $ to01 test1
----
48

**デフォルトの名無しさん** · 2021/01/26(火) 12:40:16.61

>>248
再帰で全パターンやらせるようなのは誰もがやりそうなので他の人に任せるとして、後はやるとしたらスレッド使ってやるぐらいかねえ。再帰は再帰だけど、うまくいけば速く動きそう。(スレッド作るコストが高くて遅くなるかも知れんが)。

ま、しかし、今は麻婆豆腐定食食ってる最中なのでできない。後で時間が空いた時にまだ覚えてたら作ろう。

**248** · 2021/01/26(火) 12:58:32.44

総当たりから、* で通る経路を引くぐらいしか、思いつかない

>>260
漏れも、そういう木を考えた

**デフォルトの名無しさん** · 2021/01/26(火) 13:12:00.37

ちなみに>>260はお受験で出てくる

1 1 1 1 1 1
1 2 x 1 2 3
1 3 3 4 x 3
1 4 7 11 11 14
1 5 2 23 34 48

と上から順に数える方法です
Haskellのdpは読みにくい
オレの書き方が下手なだけか？orz

**デフォルトの名無しさん** · 2021/01/26(火) 13:41:22.80

最短でなくどんな経路でもいいんならこれになる
http://www.lab2.kuis.kyoto-u.ac.jp/minato/index-j.html

**248** · 2021/01/26(火) 14:07:30.69

開始点から数え上げるので良かったのか

漏れは、終点から数え上げる方法を考えていた

**デフォルトの名無しさん** · 2021/01/26(火) 14:49:25.39

>>256
https://ideone.com/wuNBut
最初の方は多分あってるの確認できたけど

**デフォルトの名無しさん** · 2021/01/26(火) 16:29:06.62

お題：以下のパイプを実現するプログラムprogを作りなさい

$ echo "1 + a" | prog
1a

$ echo "b + 3" | prog
3b

$ echo "2 + d + 1 + c" | prog
12cd

**デフォルトの名無しさん** · 2021/01/26(火) 19:45:05.53

>>267
Kotlin
https://ideone.com/6Il455

いやー。スマホで入力するのは大変だな。画面は小さいはエディタはまともにうごかんはで非常に疲れた。

**デフォルトの名無しさん** · 2021/01/26(火) 20:34:09.94

>>267 Ruby
$ echo "1 + a" | ruby -e"$><<gets.scan(/\w+/).sort.join"
1a
$ echo "b + 3" | ruby -e"$><<gets.scan(/\w+/).sort.join"
3b
$ echo "2 + d + 1 + c" | ruby -e"$><<gets.scan(/\w+/).sort.join"
12cd

**デフォルトの名無しさん** · 2021/01/26(火) 20:56:27.12

**デフォルトの名無しさん** · 2021/01/26(火) 21:08:55.48

>>267
$ echo "2 + d + 1 + c" | sed "s/ *+ */\n/g" | sort | xargs | sed "s/ //g"
12cd

**デフォルトの名無しさん** · 2021/01/26(火) 21:28:58.74

ソートだなんて書いてないのに

**デフォルトの名無しさん** · 2021/01/26(火) 21:32:05.97

>>272
は？

**デフォルトの名無しさん** · 2021/01/27(水) 00:42:48.41

>>266
答えも解き方もあってるとおもう
総当たり以外の方法で解けないかなと思ってるところだけど

**デフォルトの名無しさん** · 2021/01/27(水) 01:36:50.37

先手必勝が分かってるのに具体的な勝つ手は簡単に分からないもんなの？

**デフォルトの名無しさん** · 2021/01/27(水) 07:22:52.84

>>275
必勝手を簡単に導くアルゴリズムが、どこかにあるといいなと思います
ただ、そのアルゴリズムがわからなくても先手必勝は証明できます

**デフォルトの名無しさん** · 2021/01/27(水) 07:33:58.36

必勝手を指すのと必勝パターン数を計算するのはまた別物だしな

**デフォルトの名無しさん** · 2021/01/29(金) 22:14:35.80

お題：
H×Wのマス目が与えられます。
始点'S'、終点'G'、通路'.'、壁'#'であり、壁や範囲外のマスは通ることができません。
また、始点と終点は隣り合っていないものとします。

いくつかの通路を壁に変更して、始点から終点に到達できなくするには
最小でいくつ壁が必要でしょうか？

[入力]
H W
(マス目を表す文字列)

[入出力例]
1 5
S...G
=> 1

3 3
S#.
#..
..G
=> 0

4 4
....
.S..
..G.
....
=> 4

**デフォルトの名無しさん** · 2021/02/02(火) 12:20:18.38

お題：ニセコインを見つけよ

半年毎に数学板で出てくるお題

n枚のコイン(n≧3)の中から重さの違うニセコインを見つけには何回天秤つかえばよいか
なおどのコインも最低一回は天秤に乗せてニセコインが重いか軽いかも判定するものとする

答えは
e = ceiling( logBase 3 ( 2*n+2 ) )

さてさてこの回数で可能はそんなに難しくない
実際e行n列の1,0,-1からなる配列で

①どの行も1の数と-1の数が等しい(右の皿と左の皿に同じ数乗せる)
②どの相異なる行u,vをとってもu ≠ ±v

となる配列が作れる
そこで n≧3 にたいしてこのような配列を出力するプログラムを作って下さい

例
3->
[[-1,0,1],[0,1,-1]]
10->
[[-1,0,1,-1,0,-1,1,1,-1,1],[0,1,-1,-1,0,0,0,-1,1,1],[0,0,0,0,-1,1,1,-1,-1,1]]

12->
[[-1,0,1,-1,0,-1,1,1,-1,0,0,1],[0,1,-1,-1,0,0,0,-1,1,-1,1,1],[0,0,0,0,-1,1,1,-1,-1,1,1,-1]

39->
[[-1,0,1,-1,0,-1,1,1,-1,0,0,-1,1,0,1,-1,-1,1,0,0,1,-1,-1,1,0,0,1,-1,-1,1,0,0,1,-1,-1,1,0,0,1],[0,1,-1,-1,0,0,0,-1,1,-1,1,-1,1,0,0,0,1,-1,1,-1,1,-1,-1,1,-1,1,-1,1,0,0,0,0,0,0,1,-1,1,-1,1],[0,0,0,0,-1,1,1,-1,-1,1,1,-1,-1,0,0,0,0,0,0,0,0,0,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1]]

**デフォルトの名無しさん** · 2021/02/02(火) 12:31:29.80

訂正
× ②どの相異なる行u,vをとってもu ≠ ±v
◯ ②どの相異なる列u,vをとってもu ≠ ±v

◆QZaw55cn4c · 2021/02/02(火) 20:23:20.94

>>279
偽コインは1枚ですか？複数ですか？

**デフォルトの名無しさん** · 2021/02/02(火) 20:40:30.09

>>279
最初しか読んでないが、その条件では軽い方が偽物なのか重い方が偽物なのか決定することが不可能

**デフォルトの名無しさん** · 2021/02/02(火) 22:41:03.50

>>281
ニセコインは一枚です

**デフォルトの名無しさん** · 2021/02/02(火) 22:52:21.15

>>282
今確かめてみたら合ってるようです

main = print $ [ ( n, ceiling $ logBase 3 $ fromInteger $ 2*n +2) | n<- [3..16] ++ [38..42]]

[(3,2),(4,3),(5,3),(6,3),(7,3),(8,3),(9,3),(10,3),(11,3),(12,3),(13,4),(14,4),(15,4),(16,4),(38,4),(39,4),(40,5),(41,5),(42,5)]

ちなみに軽重が確定しない＝一度も乗せないのもありにすれば13枚でも３回で可能です
12回のときの解に「一度も乗せないコイン」を入れればいいだけなので
ちなみにn=12とn=39のときの解でそれぞれ3回、4回で可能

[[1,0,1,-1,0,1,-1,0,0,1,-1,-1],[0,1,-1,-1,0,0,0,1,-1,1,-1,1],[0,0,0,0,1,-1,-1,1,1,-1,-1,1]]

[[1,0,1,-1,0,1,-1,0,0,1,-1,1,-1,0,1,-1,-1,1,0,0,1,-1,-1,1,0,0,-1,1,0,0,1,-1,-1,1,0,0,1,-1,-1],[0,1,-1,-1,0,0,0,1,-1,1,-1,-1,1,0,0,0,1,-1,1,-1,1,-1,-1,1,-1,1,0,0,0,0,0,0,1,-1,1,-1,1,-1,1],[0,0,0,0,1,-1,-1,1,1,-1,-1,1,1,0,0,0,0,0,0,0,0,0,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,-1],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1]]

**デフォルトの名無しさん** · 2021/02/05(金) 20:30:58.14

偽物が１枚ならそら可能だわな

**デフォルトの名無しさん** · 2021/02/06(土) 00:55:18.45

>>279
ちょっと盛り上がらないのでアルゴリズムの一例例示してみます
まぁここはプログラミングのスレだから数学部分はどうでもいいでしょう
構成法はほかにもいくつかあります
なお{1,0,-1}はうるさいので{1,0,2}にします
---
以下において{ }で囲まれた数は3進数表示とする
以下3進数表示した時
最高位が1でそれ以外が0であるものを10型、
最高位が2でそれ以外が0であるものを20型、
最高位が2で次に来る0でない数も1であるものを11型
‥
と定めていき、自然数全体を10型、20型、11型、12型、21型、22型と6型に分類する
与えられた自然数のうち
①何もしない
②最高位のみ1⇔2の交換をする
③最高位以外1⇔2の交換をする
④全桁1⇔2の交換をする
で11型の変換できる
例えば{2201}=73であれば④を適用して
f11(73)={1102}=38となる
同様にしてf12,f21,f22を定義しておく
では自然数eと3≦n≦(3^e-3)/2を満たす自然数nについて条件を満たす組みを構成する
まずn-eが奇数のときn-a-1をm、そうでないときはn-eをmとおく
前者のときケースA、後者のときケースBと呼ぶ
次にe桁以下の11型の数からケースAでは{111‥11}(e桁)を取り除いたものを、ケースBでは{111‥10}(e桁)を取り除いたものを並べたものを考える
(続く)

**デフォルトの名無しさん** · 2021/02/06(土) 00:55:35.94

(続き)
この列の最初のm/2個を2個ずつ並べてm個にした列
{11},{11},{101},{101},{110},{101},{111}‥
にf11,f12,r21,f22を順に作用させていく
ただし桁が上がるごとにf11に戻す
最初の方を例示すれば11型の数を2個ずつ並べたものが
{11},{11}
{101},{101},{110},{110},{111},{111},{112},{112},
{1001},{1001},{1010},{1010},{1011},{1011},‥
だから
{11},{12}
{101},{102},{210},{220},{111},{122},{212},{221},
{1001},{1002},{2010},{2020},{1011},{1022},‥
となる
この列は偶数番目のどこで切っても各桁に現れる1の個数と2の個数は同数か1の方が2個多い事に注意する
また最低位では常に1の個数と2の個数は同数になる
よってケースAではe個の10型、もしくは20型の数を追加する事によって全てのくらいで1の個数がちょうど一個多くなるようにできる
またこの時列の長さはm+e=n-1個である
最後に{222‥22}を追加して条件を満たす列ができる
また同じくケースBではe-1個の10型、20型の数を追加して最低位だけ同数でそれ以外の桁では1の個数がちょうど一個多くなるようにできる
この時の列の長さはm+e-1=n-1個である
最後に{222‥20}を追加すれば良い

**デフォルトの名無しさん** · 2021/02/08(月) 23:53:36.54

数学は盛り上がらんねえ

9 · 2021/02/09(火) 00:45:13.92

難問だけど
これ数学？

**デフォルトの名無しさん** · 2021/02/09(火) 01:03:59.69

盛り上がりませんね
解答例

https://ideone.com/cHEv2n

見栄え考えて"+ -"の三文字で表現してます
まぁ数学というわけでもないです
ただ数学板にはもう半年に一回くらい上がってくる
意外にネットでちゃんと解説してるサイトがない

**デフォルトの名無しさん** · 2021/02/10(水) 21:47:17.15

お題
整数 a_i が n_i 個ある。(1 <= i <= K)
このデータの中央値を求めよ。

[入力]
K
a_1 n_1
...
a_K n_K

[入出力例]
3
1 2
2 2
3 4
=> 2.5
{1, 1, 2, 2, 3, 3, 3, 3}の中央値は(2+3)/2=2.5

2
0 1000000000
1 999999999
=> 0

**デフォルトの名無しさん** · 2021/02/10(水) 21:54:19.38

こわれてる
K=3
i=4
K=3<4=i と i<=Kが矛盾

**デフォルトの名無しさん** · 2021/02/11(木) 04:13:33.16

>>292
ちゃんと問題文読め阿呆

**デフォルトの名無しさん** · 2021/02/11(木) 04:22:35.31

お題：機械翻訳しなさい

入力：this is a pen
出力：これはペンです
入力：is this a pen?
出力：これはペンですか？

**デフォルトの名無しさん** · 2021/02/13(土) 04:50:07.93

>>291
Kotlin
https://paiza.io/projects/wleCQVvUx_WksngQ-qYmRA

**デフォルトの名無しさん** · 2021/02/13(土) 16:08:30.01

>>295
間違ってね？
3
1 2
3 4
2 2
とか

**デフォルトの名無しさん** · 2021/02/13(土) 16:54:01.75

>>291
Java
https://paiza.io/projects/sHhz3SsiVN-26_86iQbJOg?language=java

**デフォルトの名無しさん** · 2021/02/16(火) 02:44:28.56

>>296
それだと3になるが、何か間違ってる?

**デフォルトの名無しさん** · 2021/02/16(火) 13:29:07.53

中央値は出現順の中央の値じゃないよ値の順の中央の値だよ

**デフォルトの名無しさん** · 2021/02/16(火) 15:39:23.69

1,2,3,100 の場合
中央値は 2.5 ですか？
それとも 2 または 3 ですか？