YSF(J)H Beginner Contest 006　感想&解説 - Ruteのプログラミング日記

Nanashi(@WrongAccept)とcitrus(@citrus_WA)さんがWriterの、

"YSF(J)H Beginner Contest 006"が2020/5/6 20:00 - 21:30の間で行われましたー。

皆さん、お疲れ様でしたー。

そしてWriterのNanashi(@WrongAccept)さんとcitrus(@citrus_WA)さん、問題提供ありがとうございました！

私は　3完700点でした(ACD完)

では、問題を振り返っていきましょう

A問題 A - HelloWhiter

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/helloworld-16

問題概要:

"HelloWorld" と出力してから、改行し,"LoveNanashi" と出力せよ。

もはや解説不要です。"Hello World"、"LoveNanashi"と出力すればよいです

コード:

f:id:Rute_programming:20200512170402j:plain — ▲A問題のコードです(Python3)

B問題 B - highway

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/nan1

Nan君は誰なのでしょうか...

問題概要:

以下のデータが与えられます。

ゲートの数 $N$ と車の台数 $T$
$i (1≦i≦N)$ 番目のゲートを通るのにかかる時間 $A_i$ のリスト
$j (1≦j≦T)$ 番目の車がインターチェンジに差し掛かる時間 $B_j$ のリスト

このデータをもとに一台も待つことなく車がインターチェンジに入れるかどうかを判定しなさい。

まず、 $N$ > $T$ の時、"Yes"と出力すればいいです。

理由としてはゲートの数が車の数より多いため、一台も待つ状況を考える必要がないからです。

$N$ ≦ $T$ の時

$A_i$ のリストを降順に並べ替えます

$B_j$ のリストを昇順に並べ替えます

以下のような処理を考えました。

各ゲートの所要時間をまとめたリストをls[0]*Nとして定義
$T$ 回以下のループを行う(初期値i = 0 now = 0)
ls[now]にA[now]+B[i]を加算
now に1を加算し、now = $N$ なら now = 0とする。
後は、リストの値の種類をcollections.Counterなどで集計し、リストの値の種類が1種類なら"Yes",そうでなければ"No"を出力する。

おそらくはこのような空いたゲートから順番に入れる貪欲法が想定解だと思ったのですが、全ケースACとはなりませんでした

解説を見て精進しようと思います！(追記:Priority Queueでした)

C問題 C - Triangle with five sticks

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/5-23

問題概要:

長さがそれぞれ $A_1,A_2,A_3,A_4,A_5$ である棒がある。(棒の長さはそれぞれ異なる)

この5本の棒のうち3本の棒を使って三角形を作成できる棒の組み合わせの数は何通りかを求めよ。

三角形の成立条件を考えます。

長さが $a,b,c$ である3本の棒があるとします。このとき $a,b,c$ について

$a+b ＞c , b+c ＞a, c+a ＞b$

の3つの条件式が成り立っていればこの3本の棒で三角形を作成することが出来ます。

この時考えるのはこの5本の棒のうち3本を用いて三角形を作成する組み合わせ、

つまり5C3 = 10通り について上の式が成り立っているかどうかを考えればよいです。

よって、この問題は全探索により $O(10)$ で解くことが出来ました。

コード:

f:id:Rute_programming:20200512170414j:plain — ▲C問題のコードです(Python3)

D問題 D - Error detection

https://www.hackerrank.com/contests/ysfjh-beginner-contest-006/challenges/1-241

問題概要:

5個の整数 $N_1,N_2,N_3,N_4,N_5$ が与えられます。

これらは、ある等差数列の相次ぐ数値であるはずだが、どれか1個の数値が間違っているようです。

間違っている数値が何番目かを出力し、また末尾に改行をいれ出力してください。

パターンで考えます。

以下、差のリストlsを

$N_2-N_1 ,N_3-N_2 ,N_4-N_3 ,N_5-N_4$ で考えることにします。

$N_1$ が間違っている時、 $N_2-N_1$ の値のみがlsの他の要素と異なっています。
$N_2$ が間違っている時、 $N_2-N_1$ の値と、 $N_3-N_2$ の値の両方がlsの他の要素と異なっています。
$N_3$ が間違っている時、 $N_3-N_2$ の値と、 $N_4-N_3$ の値の両方がlsの他の要素と異なっています。
$N_2$ が間違っている時、 $N_4-N_3$ の値と、 $N_5-N_4$ の値の両方がlsの他の要素と異なっています。
$N_1$ が間違っている時、 $N_5-N_4$ の値のみがlsの他の要素と異なっています。

よってこの問題は、以上の5パターンを考察することにより解くことができました。

コード:

f:id:Rute_programming:20200512170423j:plain — ▲D問題のコードです

E問題はよく分かりませんでした。 $6^{1000}$ を考えるとおそらくオーバーフローするのでDPか何かだと思います。

以上、YSF(J)H Beginner Contest 006　感想&解説でした！

最後になりますが、Writerの皆さん　問題提供&コンテスト開催ありがとうございました＾＾