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

massa-g

Sum of gcd 実行時間制限: 10秒
整数aが与えられます。この時、数列{1,2…….a}を並び替えた数列のスコアの最大値と最小値を求め、この順に出力してください。
ただし、ここでのスコアとは、数列の中で隣り合う2つの項の最大公約数の和とします。
例えば、数列{2,4,7}のスコアは、gcd(2,4)+gcd(4,7)=2+1=3となります。
制約
Easy:2 ≦ a ≦ 5
Hard:2 ≦ a ≦ 20
(aは整数)
結果例
入力

2

出力

1 1

数列{1,2}の並び替えとしては、{1,2}と{2,1}があります。それぞれのスコアを計算すると、
{1,2}=gcd(1,2)=1
{2,1}=gcd(2,1)=1
となり、最小値も最大値も1となります。

Last edited by massa-g (Aug. 17, 2022 11:41:00)

massa-g

ミスのため削除

Last edited by massa-g (Aug. 17, 2022 12:00:36)

00giri

#247に解答します。

massa-g

@00giri さん
Sum of gcd(easy, hard)
正解です。FA!
Factorial Sum Remainder(easy, hard)の解説です。
https://scratch.mit.edu/projects/720502427/

sakura_neko_sub

#247 Sum of gcdに解答します。
貪欲法（適切な数から初めて、“スコアが最大になる最小の数”を繋げる）を使ってみました。a<500くらいまで10秒で間に合います。
しかし最適解が得られることは証明していない()（与えられた範囲では正しいことを確認しました）

sakura_neko

Travel Across Desert 実行時間制限: 4秒
あなたは砂漠を横断しようとしています。
xy平面上にある砂漠にはN個の砂山があり、砂山はすべて底面が正方形、その頂点は正方形の中心の真上にある四角錐とします。
正方形の辺はx軸と45°の角度を成しています。（上から見ると◇のような形）
i番目の砂山のx座標はXi、正方形の対角線の長さはLi、砂山の稜線（底面の頂点と砂山の頂点を結ぶ辺）の長さはHiです。
砂山はその底面も含めて0≦y≦Y（入力では与えられない）の範囲に分布し、各砂山が重なっていることはないとします。
あなたはx軸上の0≦x≦Rにある点からスタートし、常にy軸に平行に移動してy座標Yまで向かうとします。
砂山を登るとその分移動距離が増えてしまうので、道のりが最小となるように出発するx座標を決めてください。
制約
入力 N, R, Xi, Li, Hi (1≦i≦N)
入力はすべて整数で、1≦N≦5000、1≦R≦10^5、各iについて0≦Xi≦R、1≦Li≦R、Li/2≦Hi≦R
出力出発するx座標（複数存在する場合は一つのみでよい）
結果例
入力：N=6、R=240、(X,L,H)= (190,60,40), (0,50,40), (120,40,40), (130,80,50), (240,60,40), (60,100,60),
出力：160（このときY=180まで向かう時の道のりは185で最小となる。）
入力：上記の入力において、4番目の（X,L,H)の組を(150,80,50)に置き換えた場合
出力：100（このときY=180まで向かう時の道のりは184で最小となる。）

Last edited by sakura_neko (Aug. 24, 2022 07:16:21)

hirayuu1414

トーナメントの2位実行時間制限: 5秒
長さnのリストA = (A1,A2,…,An) があります。
Aの1番目と2番目、3番目と4番目…という風に対戦し、Aiの値が大きいほうが残り、小さいほうは消えます。(ただしAiの値が同じ場合はランダムに片方消える)
最後の1つが余った場合、それはシードで確実に残る、ということにします。
(詳しい流れは「結果例」の欄をご覧ください。)
このような流れを踏んだ時、決勝戦で負けた(すなわち最後に消えた)Aiを出力してください。

制約
2≦n≦200000
0≦Ai<n
(ただしいずれも自然数非負整数)

結果例
A(1,2,0,3)のとき…
1回戦で1と2、0と3というように対戦し、2と3が残る。
2回戦(決勝戦)で2と3が対戦し、2が負けるため、その2を出力する。

A(7,0,3,0,5,6,4)のとき…
1回戦で7と0、3と0、5と6が対戦し、7と3と6が残る。さらに、余った4はシードで残る。
2回戦で7と3、6と4が対戦し、7と6が残る。
3回戦(決勝戦)で7と6が対戦し、6が負けるため、その6を出力する。

補足
この問題はEasyとHardに分かれます。
Easyではnは2^iとします。(ただしiは自然数)

非常にわかりにくい問題ですみません。質問があったらお気軽にどうぞ。
しかもまずい、問題がかぶってしまった

Last edited by hirayuu1414 (Jan. 28, 2023 03:22:58)

00giri

>> #253
EasyとHardの両方への解答です。

hirayuu1414

正解です、FA!

sakura_neko

#252について、さすがに時間が経ちすぎてしまった気がするので、解答例を出しておきます。忙しくてなかなか投稿できずすみませんでした

sakura_neko

残った自然数実行制限時間: 1秒
a, b, cのみからなる文字列Sと自然数kが与えられます。自然数の列1,2,3,4,5, …に対して、「Sのi文字目がaならば偶数番目の項を削除し、bならば3の倍数番目の項を削除し、cならば5の倍数番目の項を削除する」という操作をi=1, 2, 3, …, |S| (|S|は文字列Sの長さ)について行ってできる数列のk番目の値を出力してください。

制約
Easy: 1≦|S|≦10, 1≦k≦10
Hard: 1≦|S|≦40, 1≦k≦1000

結果例
S=abca, k=4のとき自然数の列は 1,2,3,4,5, …→a→1,3,5,7,9, …→b→1,3,7,9,13, …→c→1,3,7,9,15, …→a→1,7,15,21,31, … と変化するので、21を出力すればよい。
S=ccbbaa, k=2のとき自然数の列は1,2,3,4,5, …→c→1,2,3,4,6, …→c→1,2,3,4,7, …→b→1,2,4,7,9, …→b→1,2,7,9,14, …→a→1,7,14,21,28, …→1,14,28,42,57, … と変化するので、14を出力すればよい。

akinarin

#257残った自然数のHardEasyの解答です
計測しなおしたら実行時間を大幅に超えていました。

Last edited by akinarin (Feb. 18, 2023 14:18:40)

watashida

#257 残った自然数に解答します
https://scratch.mit.edu/projects/806246706/

Last edited by watashida (Feb. 18, 2023 14:24:57)

00giri

#257 残った自然数の解答です。

sakura_neko_sub

#258 TLEです。数列の変化を逆から考えてみるとわかるかも知れません。
#259 @watashidaさん残った自然数(Easy, Hard) 正解です!! FA!
#260 @00giriさん残った自然数(Easy, Hard) 正解です!! AC!!

解答例も置いておきます。

akinarin

残った自然数、Hard出来ました。
実行時間を大幅に超えてしまいました。
Easyは出来たと思います。
https://scratch.mit.edu/projects/806745355/

Last edited by akinarin (Feb. 20, 2023 23:01:23)

kakurenbo

もうかなり前になりますが、#219 Egotistical Dictionary? の略解を落としておきます。
今読み返すと冗長な問題文ですね…嫌いです

使える文字を頂点，「文字 X は文字 Y よりも前に現れなければならない」という条件を X → Y の有向辺として表したグラフ G を構築します．
G の頂点列のトポロジカル順序のうち辞書順で最大のものを答えればよいです．
これは貪欲に解くことができます．

入次数が 0 の頂点のうち辞書順で最大のものを答えとなる列に追加しその頂点から出る辺を全て削除する，といった操作を全ての頂点が列に追加されるまで繰り返せばよいです．途中で詰んだ (G の頂点が追加され切っていないのに追加できる頂点がなくなってしまった) 場合は不可能です．(詳細はトポロジカルソートなどの単語で検索すると良いと思います．)

今回の問題では制約が非常に小さいので，以上を愚直に行うことができますが，「入次数が 0 の頂点のうち辞書順で最大のもの」を選ぶ処理に優先度付きキューなどと呼ばれるデータ構造を用いることでより入力が大きな場合にも現実的な時間で答えが求められます．

また，A が入力として与えられるので，(大小比較のために) これを一度数値に変換する必要があるありますが，その際は二分探索を用いると (制約が大きな場合でも) 高速です．(座標圧縮の一種に該当する気がします．)

解答例

Easy のみ
Hard および Easy 今見たら昔の自分が頑張って二分ヒープを実装していました．もうしたくない．

ということでド典型問題でした。つまんないですね。

Last edited by kakurenbo (Feb. 25, 2023 11:51:55)

Atridott

きれいな回答を思いついたのでage兼ねて出題します。

イコール判定ロボット実行時間制限: 5秒

あなたはあるロボットを作るよう言われています。
このロボットにAとBという二つの文字列を与えたとき、ロボットはAとBが等しければ1と言い、等しくなければ何も言いません。
実際に「と言う」ブロックを使ってこのロボットを作ってください。
注意：「何も言わない」で空文字列ではなくスペースなどを使うと不正解になります。

制約
条件分岐のブロックを使わない。

結果例
Aが「りんご」のとき、以下のように言います。

Bが「りんご」→「1」
Bが「ばなな」→「」

Last edited by Atridott (March 7, 2023 09:34:32)

Catapult-

#264に回答
https://scratch.mit.edu/projects/814854517/
これでいいんですか?

newmomizi_txt

#264
https://scratch.mit.edu/projects/814855353/
解答。10ブロックです。

Discuss Scratch