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

sakura_neko

前に出したのと合わせて解答例を出しておきます。
#183 ハブ空港検索解答例
https://scratch.mit.edu/projects/614157368/
#223 Complex Anagram 解答例
https://scratch.mit.edu/projects/670396673/

Last edited by sakura_neko (April 6, 2022 13:25:29)

NT_ZZzz

sakura_nekoさん #87 ナベアツアツ数(H) Accepted!正解です！
作問者想定よりだいぶ実装が簡潔だし実行も高速ですごい

hirayuu1414

百人一首の達人実行時間制限: 5秒
とある王国で、百人一首大会が行われることになりました。
その百人一首大会で出てくる上の句はリストaに格納されていて、上の句の数はxで表されます。
（日本の一般的な百人一首と同じとは限りません）
さて、あなたは、もちろん優勝したいと思っていますが、そのためにはできるだけ早く札を取らなければいけません。
そこで、最高でも何文字（これをnとする）読まれれば全ての上の句を特定できるかを調べることにしました。
nを出力するプログラムを作ってください。
※ただし、ひらがなとカタカナなどは区別します。
制約
aの要素一つの長さは20文字以下
aに全く同じ要素は含まれない
1≦x≦100
結果例
x…5 a…[abc,acd,aac,bac,cab]の場合
n=2
1文字読まれただけでは特定できませんが、2文字読まれれば特定できます。

x…1 a…[ひとつしかない]
n=0
札は一つしかないのですから、読まれるまでもなく特定できます。

x…3 a…[aaac,back,aaab]
n=4
残念ながら、4文字全て読まれないと特定できません。

Last edited by hirayuu1414 (April 22, 2022 09:46:33)

00giri

#229
これでどうでしょうか？

Last edited by 00giri (June 16, 2022 02:27:46)

hirayuu1414

正解です。FA!

NT_ZZzz

#180 リスト加算操作の解説を公開しました。
https://scratch.mit.edu/projects/683171090/

この問題は数学的な解法も存在します。00giriさんの解答も見てみると良いです。
https://scratch.mit.edu/projects/611523939/

sakura_neko

リンゴの林実行時間制限: 8秒
リンゴの木がN本並んで立っています。木の高さはすべて整数で、しかも1mからNmまでのすべての高さが揃っています。
このとき、「a番目からb番目の木の高さを並べ替えると、連続な整数になっているか」を答えてください。
＊aとbは大量に渡されます。
入力&制約
・木の本数N：1≦N≦600
・木の高さのリストL（番号順に入力）：1~Nの整数の並べ替え
・aとbの組の数Q：1≦Q≦10000
・区間の端の番号a,b：1≦a≦b≦N
・出力：各a,bに対して、上の条件が成り立つか(true, false)
結果例
N=6、L=1,2,4,6,5,3、Q=3、(a,b) = (1,2),(1,3),(3,6)
→true, false, trueが出力リストに入ればOK
N=7、L=4,6,2,3,7,1,5、Q=4、(a,b) = (3,4),(1,6),(5,5),(1,7)
→true, false, true, true

Last edited by sakura_neko (May 7, 2022 16:25:09)

dannkuru

#233に解答します
https://scratch.mit.edu/projects/686823923/
追記:Lが入力だったことを見落としていたので、最初の入力部分を訂正しました

Last edited by dannkuru (May 8, 2022 02:45:43)

00giri

#233
これでどうでしょうか？

Last edited by 00giri (June 16, 2022 02:24:38)

sakura_neko

#234 TLEです
撃墜ケース：N=600, L=1,2,3,…,N, Q=10000, (a,b)をすべて(1,600)としたときにこちらの環境では50秒以上かかりました。

Last edited by sakura_neko (May 8, 2022 03:17:24)

sakura_neko

#235 ACです！おめでとうございます！

massa-g

Factorial Sum Remainder 実行時間制限: 5秒
整数a,bがこの順に与えられる。
0!+1!…………a!をbで割った余り、つまり

をbで割った余りを求めよ。
制約
【Easy】
0≦a≦10,1≦b≦100000
【hard】
0≦a≦10^308,1≦b≦200000
結果例

入力:4,15
出力:64

0!+1!+2!+3!+4!=1+1+2+6+24=34を15で割った余りは4である。
このケースはEasy,hardの制約を満たす。

入力:3141592653589793238462643383279502884　3
出力:1

このケースはHardの制約を満たす。
(結果例に間違いがあったので、修正しました)

Last edited by massa-g (Aug. 9, 2022 09:09:27)

sakura_neko_sub

#238 Factorial Sum Remainder(easy, hard) に解答します。
https://scratch.mit.edu/projects/720505158/

massa-g

ミスのため削除

Last edited by massa-g (Aug. 9, 2022 09:02:09)

massa-g

@sakura_neko_sub さん
Factorial Sum Remainder(easy, hard)
正解です。FA!!
解説は後日公開します。

00giri

#238に解答します。
https://scratch.mit.edu/projects/720507359/

massa-g

#242
正解です!!

sakura_neko

風変わりな旋律実行時間制限: 1秒
N個の音を並べて旋律を作ります。
3つの音が連続している（ドレミ、シラソなど）部分が存在しない旋律を「風変わりな旋律」と定義します。
与えられる条件の中で、風変わりな旋律はいくつ存在するかを出力してください。
制約
旋律のk番目の音は、「ド」を1、「レ」を2、…のように数字を割り当てたとき、その値が1以上M(k)以下になっている必要があります。
入力:自然数N, M(k) (k=1,2,3,…,N)
easy:1≦N≦4, 1≦M(k)≦8
（「ド」から「高いド」までの1オクターブ）
hard:1≦N≦10, 1≦M(k)≦32
（4オクターブ）
出力:風変わりな旋律の数
結果例
入力:N=3, M(1)=M(2)=M(3)=3
出力:25
風変わりでない旋律は「ドレミ」「ミレド」の2つなので、3*3*3-2=25(通り)
入力:N=4, M=3,2,5,4
出力:107
入力:N=10, M=3,1,4,1,5,9,2,6,5,3
出力:84492
入力:N=8, M=32,32,32,32,32,32,32,32
出力:1087764911262

Last edited by sakura_neko (Aug. 11, 2022 21:59:38)

NT_ZZzz

#244 風変わりな旋律に解答します
https://scratch.mit.edu/projects/721166652/
問題文を誤読してMは全てのkで共通だと思っていて結果例の入力を読みながら首を傾げていました

sakura_neko

#245 @NT_ZZzzさん風変わりな旋律(easy, hard) 正解です。FA!!

入力のところなんかおかしくなってました。
訂正します。
(誤)入力:自然数N,M(k) (1,2,3,…,k)
→(正)入力:自然数N, M(k) (k=1,2,3,…,N)

解答例です。
https://scratch.mit.edu/projects/720754101/

Discuss Scratch