Tea Break With Milk 001 参加記 - Ruteのプログラミング日記

Tea Break With Milk(以降teamとします)

(CafeCoder様主催のコンテスト)の第1回が終了しました。

が、やはりサーバートラブルの原因らしく、中止という形となりました。

この記事では、teamの問題について、1問ごとに解説を行います。

(注意)問題文などは覚えていないので、覚えている限りで問題文などを記載します。

なお、解説に準じたコードを見たい場合は、下のリンクより私のコードを閲覧することが出来ます。

https://github.com/rute-b/CafeCoder-Team001

A問題

$A,B,C,D,E$ というtaro君(仮称)の5つの試験の点数が与えられる。

これについて、合計が $X$ 点以上なら留年をまぬがれるという。

彼が留年をまぬがれるかどうかを判定せよ。

(留年をまぬがれるなら"Yes",そうでなければ"No")

入力: $X,A,B,C,D,E$

解法

$if (A+B+C+D+E)≧X$ がTrueなら"Yes"

そうでなければ"No"を出力

B問題

この学校には $N$ 人の生徒が存在する。

$i$ 番目の生徒の各教科のテストの点数が $A_i,B_i,C_i,D_i,E_i$ で与えられるので、 $i$ 番目の生徒のテストの点数の合計点を出力せよ。

入力:

$N$

$A_0,B_0,C_0,D_0,E_0$

$A_1,B_1,C_1,D_1,E_1$

・

$A_{N-1},B_{N-1},C_{N-1},D_{N-1},E_{N-1}$

解法

$sum(A_i,B_i,...E_i)$ を $N$ 行出力

C問題

古代文字の個数を以下のように定義する

アルファベットの小文字で、 $a$ に含まれる古代文字の個数を1とし、

それ以降、 $b,c,d...$ となるにつれその文字に含まれる古代文字の個数を+1ずつ増やす。

文字列 $S$ が与えられるので、この文字列に含まれる古代文字の個数の総和を出力せよ。

入力: $S$

解法

この問題については、いろいろな考え方をした方がいたと思います。

解法①

list_1= ["abcdefghijklmnopqrstuvwxyz"]とし、

それぞれの文字について、list_1の何文字目と一致するかを探索し、それを総和に加えていき出力する。

時間計算量は　最悪 $O(|S|*26)$ になります(あえて外しませんでした)

解法②

実は、これは文字コードというものを利用すれば計算量を減らすことが出来ます。

文字コードとは、いわゆるASCII文字コードです。

小文字の場合は"a"が97で、"z"が122です。

大文字の場合は"A"が65で、"Z"が90です。

今回の場合は、アルファベットが小文字なので

ASCII文字コードから96を引いたものを足し続ければ、

古代文字の個数の総和を求めることが出来るのです。

時間計算量は　 $O(|S|)$ になると思われます。

(pythonのordの時間計算量が分かってないので正しいとは言えません)

D問題

文字列 $S$ が与えられる。

このとき、 $S$ を文字コードが小さい順番に並べて出力せよ。

入力: $S$

解法

さきほどと同様に、文字コードを利用する方法があります。

list2 = (空のリスト)とします。

それぞれの文字を文字コードの値に変換し、それをlist2に入れて、

list2をソートし、あとはlist2のそれぞれの値を再び文字コードから文字に直して連結して出力すればよいのです。

時間計算量は $|S|$ です。

(筆者は別の方法を利用して解きました)

E問題

弁当箱の大きさを縦 $2N-1$ ,横 $2N-1$ と定義する。

この時、完璧な日の丸弁当を以下のように定義する。

・真ん中の部分が"#"である

・それ以外の部分が"."である。

整数 $N$ と、日の丸弁当を示した文字列 $S$ が $2N-1$ 行与えられる。

日の丸弁当を示した文字列が完璧な日の丸弁当かどうかを判定せよ。

(完璧な日の丸弁当なら"Yes",そうでなければ"No")

解法

整数、日の丸弁当を示した文字列を入力します。

次に、各S[i][j]成分について以下の判定を行います:

　　もしS[i][j] == "."がTrueなら、変数xに1を加算します

あとは、S[N-1][N-1]が "#"であり

変数Xが $(2N-1)^{2}-1$ と等しければ"Yes",そうでなければ"No"を出力すればよいです。

時間計算量は $O(N^2)$ となります

(制約を見ていなかったので正しいとは言い切れません)

一応、20分時点で全完してました。

何か分からない点などがありましたら、コメントなどで教えて下さい。

(RuteはPython3を主言語としていますので、C++などを利用している方の質問は答えられない場合があります)