Scratchで競技プログラミング！(初めての人は最初の投稿をお読みください)

nyankodaisensou-suki

#264
https://scratch.mit.edu/projects/814879847/
回答です。

Sky_Thunder

#264 に回答します:
https://scratch.mit.edu/projects/814957828/

Atridott

トピックのフォローを間違えて外してままにすると言うミスを犯しました(
みなさん大正解です！FAはCatapult-さんですね、おめでとうございます。
またリストを使ったnyankodaisensou-sukiさんの回答も拡張性の高い回答で素晴らしいです。

Sky_Thunder

誕生日パーティー
実行時間制限 … Easy: 10秒, Hard: 1秒
問題文
Aさんは、友達であるBさんの誕生日パーティーで食べる予定のお菓子を買いに来ています。
ですが、Aさんはどのお菓子を買うか考えているうちに、友達が何人来るか忘れてしまいました。
厳密に言うと、記憶には残っていますが記憶は曖昧な状態で、記憶に残っているのは実際の“友達が来る人数”が反転した数列の可能性があります。
記憶に残っている数列aが与えられるので、
Aさんの代わりに、どちらの人数でも余りなくお菓子を配れるように最小で何個お菓子を買えばよいかを考えてあげてください。
制約
1 ≦ a ≦ 1000

入力例1

出力例1

入力例2

出力例2

入力例3

出力例3

Last edited by Sky_Thunder (March 7, 2023 14:20:21)

yukku

#270(Hard) に回答します。
https://scratch.mit.edu/projects/815349579/

00giri

>> #270
誕生日パーティー(Easy,Hard)に解答します。

souta_

Good Pair 実行時間制限…3秒

問題文
数直線上に10000本の線分があります。
線分には左端の点と右端の点があり、それらの点の間にある部分をその線分の範囲とします。
また、異なる2つの線分の範囲が重なっているとき、
その2つの線分は「良いペア」といいます。
10000本の線分から2つを選ぶ選び方のうち、
「良いペア」となっているものは何通りあるか調べて、変数answerに格納してください。

制約
リストaに10000本の線分の情報が入っています。
aの2*i-1番目にはi番目の線分の左端の点の座標が、
aの2*i番目にはi番目の線分の右端の点の座標が格納されています。
(aの長さ) = 20000
0<= a(2*i-1) < a(2*i) <= 1000000000 ( 1<= i <= 10000 )
a(i) != a(j) ( i != j )
値はすべて整数

結果例
※これは説明のための入力であり、制約を満たしていません
入力
1 8 2 4 6 7
出力
2
1番目と2番目、1番目と3番目の線分が「良いペア」となっているので、答えは2通りです。

Last edited by souta_ (March 8, 2023 04:38:29)

Sky_Thunder

#271(@yukkuさん) FA!!おめでとうございます!
#272(@00giriさん) AC!
(ちなみに、解法については明日投稿する予定です)

nyankodaisensou-suki

面白そうなフォーラムを見つけので早速問題投稿
35 or Under 実行時間制限…0.1秒以内

問題文
38種類の文字があります。それを20個選んで(重複OK)文字列を作ります。
さらにその文字列を0~9の数列に変換します。
その数値を出力するプログラムを作ってください。
また、その数値から元の文字列を逆算するプログラムも作ってください

制約
・入力する時に使う文字は(0~9,a~z,+,-)です。
・タイトルにも書いてある通り、出力するのに36文字未満つまり、35文字以下で出力してください。

結果例
※これは例です。実際にそうならない場合があるかもしれません
入力
a65fc2xs-350cd73gd7+
出力
12323857392834672375637294017347293

Last edited by nyankodaisensou-suki (March 8, 2023 07:20:27)

yukku

#273に回答します。
https://scratch.mit.edu/projects/815473868/

sakura_neko

#273に回答します。
https://scratch.mit.edu/projects/815454001/

sakura_neko

#269に回答します。
https://scratch.mit.edu/projects/815476760/

Last edited by sakura_neko (March 10, 2023 07:44:23)

sakura_neko

#262、見落としていましたが @akinarinさん残った自然数(Easy) 正解です!! AC!!
細かい連投になってしまいすみません…

Last edited by sakura_neko (March 8, 2023 08:33:24)

souta_

#276 yukkkuさん
#277 sakura_nekoさん
正解です!

想定解
愚直に探索するとO(N^2) (Nは線分の個数) となり、3秒以内に終わらない。
線分Aの左端の点から見て線分Bの左端の点が左側にある時、
線分Bの右端の点が線分Aの左端の点より左にある⇔AとBは良いペア　といえる。
よって線分Aの左端の点よりも左端の点が左にある線分のうちいいペアとなっているものの個数は
(線分Aの左端の点よりも左側にある左端の点)-(線分Aの左端の点よりも左側にある右端の点)で求められる。
1. 線分の左端、右端の点をすべてソートする　answer=sum=0
2. for i in range(1,20000)
1. i番目の点が左端の点のとき、answer+=sum sum+=1
右端の点のとき、sum-=1
とすることで良いペアの個数はO(N log N)で求められ、
N=10000のとき3秒以内に終了できる。

Last edited by souta_ (March 10, 2023 12:53:31)

Poteto143

お知らせ
#2の問題リストを以下のように更新しました！

#213以降に投稿された問題とそのFA者を全て反映しました
投稿削除により登校番号がずれるケースがあるため問題の投稿番号を削除しました
最終更新日を書くようにしました(もともと編集したら自動で付きますがまぁ一応)

ここ最近、活動がかなり活発になってきていて正直驚いています。
いつも利用してくださりありがとうございます！

Sky_Thunder

Sky_Thunder wrote:
(#268)
#271(@yukkuさん) FA!!おめでとうございます!
#272(@00giriさん) AC!
(ちなみに、解法については明日投稿する予定です)

これ、解法の投稿を忘れていました ><
ということで、Easy,Hardそれぞれを解いたプロジェクトを張っておきます >>
Easy: https://scratch.mit.edu/projects/816905408/
Hard: https://scratch.mit.edu/projects/816905529/
ちなみに解法ですが、どちらの人数でも余りなく=どちらを割っても0になるような最小の数=最小公倍数と考えることができます。
ですが、総当たり等で最小公倍数を求めようとすると、かなり時間がかかります。
なので、最小公倍数を求める式a*b/dを使います。(※詳しくはここ)
ですが、上の式を使うためには2つの数の最大公約数が必要となります。
そこで、最大公約数を高速に求めるために、ユーグリッドの互除法を使います。
これで最大公約数が求まったので、最小公倍数を求める式に当てはめて、出力という感じです。

nyankodaisensou-suki

#272
@sakura_neko さん、FAです。おめでとうございます！

Last edited by nyankodaisensou-suki (March 10, 2023 12:10:52)

hirayuu1414

怪しいカジノ実行時間制限: 10秒
とあるカジノでは、コイントスに挑戦できます。
n%の確率で立ち、立たなかった場合は表裏が平等に出るコインを、A回以内に立てることができれば、その早さに応じて掛け金が戻ってくる、というものです。
具体的には、i回目に立てるとA-(i-1)倍の掛け金が戻ってきます。(1回目ならA倍、3回目ならA-2倍のように)
しかし、A回投げても全く立たなかったり、B回同じ面が連続して出てきた場合、掛け金は没収されます。
この賭け事の期待値が1倍より上ならTrue、1倍以下ならFalseを出力してください。

制約
0≦n≦100
0<A<200000
1<B<10
B<A
(nは実数、AとBは自然数)

結果例
n=10、A=3、B=2のとき…
1回目、10%の確率で立ち、残りの90%の確率で表か裏が出ます。
2回目、9%の確率で立ち、40.5%の確率で掛け金が没収されます。
3回目、4.05%の確率で立ち、これが最後なのでそれ以外(36.45%)の場合は没収されます。
よって、期待値は3*0.1+2*0.09+1*0.0405=0.4205。明らかに損なので出力はFalse。

n=0、A=20、B=5のとき…
言うまでもなくこのコインは立たないので、期待値は0です。よって出力はFalse。

n=99、A=1000、B=10のとき…
計算は省きますが期待値は明らかに1より大きいので、出力はTrue。

追記:前の条件だとどう頑張ってもできないパターンがあったので一部変更。

Last edited by hirayuu1414 (March 11, 2023 23:46:25)

akinarin

n進循環小数実行時間制限: 30秒

文字列aに文字列bを無限個連結させて出来る循環小数があります。
これを10進法の既約分数に変換して下さい。

制約
aは1個以上の数字またはアルファベットと1個の小数点から構成されています。
bは1個以上の数字またはアルファベットから構成されています。

Easy: 循環小数は10進数です。
Hard: 循環小数はn進数です。(nは2以上36以下の自然数)

結果例
Easy, a = “1.” , b = “3”のとき(つまり1.333333…)
結果 4/3

Easy, a = “4.41”, b = “6”のとき(つまり4.41666666…)
結果 53/12

Hard, a = “1.”, b = “01”, n = 2のとき(つまり2進法の1.010101…)
結果 4/3

(追記: 条件を少し変えました)
分数→既約分数
nは2以上の自然数→nは2以上36以下の自然数

Last edited by akinarin (March 11, 2023 14:35:56)

00giri

>> #279
n進循環小数Easy, Hardに解答します。※Easyのときはn=10を入力してください。

Discuss Scratch