ケーキ同好会でも、プログラミングは必須スキルです！

ケーキ同好会6

私と哀先輩も家庭科室に行って、ひまり先輩が作ったガトーショコラを食べてます。

何というか、学校でスイーツを食べるのは中々新鮮だけど、罪悪感もある。

本当にプログラミングの大会で成果を出したら部活として認められるの？

ちょっと心配になってきた......

ひまり先輩は全然気にしてないみたいだけど。

あれは悩みのない純粋な瞳。わっ、こっち向いた。

見てないふり見てないふり。

「そういえば、私がガトーショコラ作りに行った後、どこまで進んだの？」

「えっと、for文と配列を教えてもらって、そのあと競プロの問題を初めて解きました」

「え、すごい！あ、でも、ゆいちゃんが初めて競プロするの見たかったなー」

ひまり先輩が哀先輩のことを横目で見ながら言う。

「ガトーショコラおいしい」

「哀ちゃんが超強引な話題転換をしている......」

「ゆいちゃんはfor文まで書けるから、コンテスト当日は最初の問題くらいは任せられそうだね」

「もしかしたら、次の問題まではできるかも？」

今週はプログラミングの勉強頑張ったもんね。

なんとか大会までにプログラミングが一通りできるようになったみたいで一安心。

「最初の問題と、次の問題ですね、頑張ります！」

「もしかしたら、それ以外の問題もやってもらうかもね」

「え」

「解法は難しいけど、プログラミングの経験はあまり要らない問題は結構あるからね。構築問題とか」

「構築問題は「天才パズル」とか言われてるけどね......最初から解けるのはひまりちゃんくらいだよ」

「そうなの？」

どうやら、私はとんでもない問題を解かされそうになっていたらしい。

下校時間になったので、職員室まで部室の鍵を返しに行く。今日はみんな一緒についてきた。ケーキ同好会、職員室に襲撃だー。おりゃー。

「ゆいちゃん、for文までできるなら、今週のPBCに参加できるけど、どうする？」

「PBCって何ですか？」

「競プロを始めたての人向けのコンテストだよ、競プロに慣れるのにちょうどいいかなーって思って」

「時間内に全部解けるなら茶色になれるくらいの難易度」

「茶色ってどのレベルでしたっけ？競プロのランク順って覚えにくいですよね......」

哀先輩とひまり先輩がどっちも苦笑いしてる。

「競プロ始めたてが灰色で、茶色はその次のランク」

「ノービスとかマスターとかの名前だったら説明しやすいんだけどね。冠位十二階とかの色も全然覚えてないもん」

「懐かしい単語だ、紫が一番偉いことしか覚えてない」

「一色でも覚えてるのすごいなー」

哀先輩は歴史が得意だったりするのかな？もしかしたら、文系科目も理系科目もどっちもできる人かもしれない。

「話を戻すと、PBCは言語標準の機能とかデータ構造に慣れるのにちょうどいいかな？

解き方は分かるけど、プログラムを書くのに時間がかかる人向けのコンテストだね」

「やってみますね」

「月曜にどうだったか教えてねー」

●

夕食を食べた後、自分の部屋に戻ってノートパソコンを出す。

今夜はひまり先輩から教えてもらった競技プログラミングのコンテストに出てみようと思う。

初心者向けだって言ってたし、そんなに難しくないはず。

コンテストの名前、PBCだったっけ？あんまり自信ないけど、調べたら出てくるかな？

「PBC コンテスト」と検索。一番上に出てきたものがそれらしかった。

Programming Beginner Contest 028

コンテスト時間:60分(21:00～22:00)

レーティング更新対象:0～400

配点

A 100

B 100

C 150

D 200

E 250

F 300

初めて参加される方は、まずアカウントを作成してください。

このコンテストはインターネットでの検索や、書籍の参照を認めております。

私は初めて参加する方なので、アカウントを作る。

うっ、私ニックネームとか考えるの苦手なんだよね......

思いつかないから本名でいいか。困ることがあったら後から変えよう。

確認。コンテストは21時から22時までの1時間。

時間内に解いた問題の合計得点で順位が決まる。

得点が同じ人同士は解いた時間が短かった方が良い順位になる。

そして、順位表はリアルタイムで見ることができるらしい。

定期試験と違って、自分の答えが合っているかがコンテスト中に分かるのが新鮮で面白いね。

始まるまであと3分はある。Pythonの本持ってきた方がいいかな。

先輩方には競プロをする分には十分にプログラミングができるって太鼓判を押してもらったけど、この本まだ全然見てないページばっかりだし。

あ、プログラミングしないといけないから、コードエディタも開いとかないと。

気づいたらコンテストが始まるまであと30秒だった。そういえば、初めて参加する人はどのくらい解けるんだろう。

コンテスト時間は一時間あるから、一問あたり20分くらいだと考えたら三問目までは解けるかな？

ひまり先輩に聞いておけば良かった。

あと10秒。時計の秒針を見つめる。窓の外で夏の虫が鳴いているのがよく聞こえる。

壁掛け時計の秒針が真上を向く。私はA問題のページを開いた。

A - First Collatz

実行制限時間:$2$sec/メモリ制限:$1024$MB

配点:$100$点

問題文

$1$以上$100$以下の整数$N$が与えられます。

$N$が偶数の場合、$N$を$2$で割った値を出力してください。

$N$が奇数の場合、$N$を$3$倍してから$1$を足した値を出力してください。

制約

入力はすべて整数

$1 \leq N \leq 100$

入力形式

$N$

入力例1

14

出力例1

7

7.0のように、小数点以下が表示されていると正答と判定されないため注意してください。

入力例2

31

出力例2

94

良かった。昨日哀先輩が見せてくれたページと同じウェブサイトっぽい。

問題を急いで読む。

まず、数字を受け取るんだね。

数を受け取るから普通のinput()じゃだめで、

int()をつけてn = int(input())と書かないと。

そのあとは、受け取った数が偶数、つまり2とか14とかみたいに

\[2\times \text{なんとか}\]

と書ける数なら、その数を2で割ったものを出力する。

「もし～なら」だから、if文で書ける！

受け取った数が奇数の場合は、3倍してから1を足したものを出力する。

奇数は偶数じゃない方だから、偶数のときのif文の後ろにelseと書いておけば大丈夫。

よし、できる！私は急いでプログラムを書き始めた。

まだキーボードで入力するのに慣れてないから時間がかかる。

=や()を入力するときはshiftキーも押さないといけないから大変。

キーボードで早く打つ練習もしないとね。

先輩方みたいにタッチタイピングしたい。

n = int(input())

if ...|( )

......あれ、受け取った数が偶数かって、どうやって判定すればいいんだろう？

偶数の一の位は$0,2,4,6,8$しかないからそれを判定する？

うーん、それをちょっとプログラムでどうやって書けばいいかパッと思いつかない。

あ、受け取った数が2で割り切れるかどうか判定するのはどうだろう。

偶数は

\[2\times \text{なんとか}\]だから必ず2で割り切れて、

奇数は必ず2で割り切れないから。

えっと、2で「割り切れる」ってことはどういうことだっけ？

2で割ったときに余りが出てこないってことだよね......？

あ、2で割ったときの余りが0になる、と言い換えられるね。

だから、割った余りを計算できれば良さそう。

\[13 \div 2 = 7~\text{あまり}~1\Rightarrow \text{奇数}\]

\[20 \div 2 = 10~\text{あまり}~0\Rightarrow \text{偶数}\]

Pythonで割った余りを計算するのってどうすればいいんだろう。

足し算記号とか掛け算記号とかの+, *は教科書で見たけど、そんなのあったかな。

そう言われると、割り算の下にもう一個何か説明があったような気がしてきた。

うーん、なんだったかな？絶妙に覚えてないな。

......そういえば、教科書とかで調べてもいいルールだったね。素直に教科書を読みます。

ふむふむ。割った余りを求めるのは%でできるらしい。

つまり、$n$を2で割った余りを求めるには、n % 2と書けばいい。

これを使えば n % 2が0と等しいときは偶数で、等しくないときは奇数と分かる！

プログラムで数が等しいか判定するのは普通にイコールでいいのかな？

ちょうど教科書開いたし、ついでに調べておこう。

えっと。

一致しているかの判定のときは、イコールを二つ使ってn % 2 == 0みたいに書くといいんだね。

たしかに、イコール一つだと、変数を宣言する x = 2 とかと見分けがつかないよね。

n = int(input())

if n % 2 == 0:

print(n / 2)

else:

print(n * 3 + 1)

よし、完成！あとは入力例を試してみよう。

>python main.py

>14

7.0

あれ、後ろの.0は要らないんだけど。割り算のときだけ小数点が出てくるんだっけ。

あ、整数にするには、int()で囲えば良かったね。

さっきinput()でやったばっかりだ。

n = int(input())

if n % 2 == 0:

print(int(n / 2))

else:

print(n * 3 + 1)

入力例を試すと、今度はちゃんと小数点なしで表示された。

プログラムはこれで完成かな。

提出するには、書いたプログラムをコピペすると良さそう。

言語をPythonにして、提出！

少しの間待つと、提出履歴に緑色でACと表示される。

よし、正解！せっかくなので順位表も見てみよう。

$

\begin{leftbar}

︙

3750 pencil728 100点

3751 灰崎ゆい 100点

3752 wannkoromoti 100点

︙

\end{leftbar}

$

3751位ってことは、自分が解くまでに3750人もこの問題を解いたってことか。

急いで次の問題を解かないと。

最初の問題からけっこう時間かかっちゃった。

......ちょっと待って、ユーザーネームを本名にしてるの私だけ？このコンテスト終わったら変えよう。恥ずかしい。

B - Dictionary Order

実行制限時間:$2$sec/メモリ制限:$1024$MB

配点:$100$点

問題文

英小文字からなる$2$つの文字列 $S, T$ が与えられます。

文字列を辞書式順序で小さいものから順に、改行区切りで出力してください。

制約

$S, T$ は英小文字からなる長さ$1$以上$100$以下の文字列

$S, T$ は相異なる

入力形式

$S$

$T$

入力例1

program

accepted

出力例1

accepted

program

入力例2

person

present

出力例2

present

present

辞書式順序は、辞書で出てくる順番って字面から想像できるけど、

文字列の辞書式順序で小さい(・・・)方ってどっちだろう？

小さいって書いてあるくらいだから、文字列にも不等号が使えないかな？試しにプログラムを書いてみて実験してみよう。

s = input()

t = input()

if(s > t):

print("SはTより大きい")

if(s < t):

print("SはTより小さい")

入力例1を試してみよう。programは文字列$S$で、acceptedは文字列$T$だね。

辞書だとacceptedの方が先に出てくるけど、どっちが小さくなるんだろう。

>python main.py

>program

>accepted

SはTより大きい

えっと、これが表示されたということはどっちが小さいんだっけ？

出力された「SはTより大きい」を言い換えると、$S$がprogramだったから

\[T < S\]

\[\texttt{accepted} < \texttt{program}\]

ってことだね。

だから、辞書式順序で小さい方というのは、辞書で先に出てくる方って意味っぽいね。

名前もそれっぽいから、実際にそういう意味なのかな。

小さい文字列から表示されてほしいから、$S > T$のときは文字列$T$から表示されるようにすれば完成だね。

まあ、文字列に使える不等号が本当に辞書式順序なのかは分からないけど。

s = input()

t = input()

if(s > t):

print(t)

print(s)

if(s < t):

print(s)

print(t)

コピペして提出してから、少し待つ。

結果が返ってくるまでの10秒くらいのこの時間めっちゃ緊張する。

緑色でACが表示された。

よし、これで二問目まで解けた。

あ、でも辞書式順序はあんまり分かってないから後で調べないとね。三問目のページを開いた。

C - Missing Parentheses

実行制限時間:$2$sec/メモリ制限:$1024$MB

配点:$150$点

問題文

括弧 '(' , ')' と英小文字からなる、長さ$N$の文字列$S$が与えられます。

'(' と ')' の個数が一致しているときは、"true"、

一致していないときは"false"と出力してください。

制約

$2 \leq N \leq 10^5$

$S$ は'(',')',英小文字からなる長さ$N$の文字列

入力形式

$N$

$S$

入力例1

7

print(x

出力例1

false

入力例2

4

())(

出力例2

true

要は、文字列の中の括弧の数を数えて、

左括弧と右括弧の個数が同じかどうか判定すれば良いんだよね。

文字列って配列みたいにs[0],s[1]ってやると、

前から一番目の文字とか二番目の文字が確認できるのかな？

それができるなら、あとはfor文で最初の文字から括弧の個数を数えていけばいいね。

個数を数えるから、変数の名前はcounterとかにしとこうかな。

左括弧を数える変数はcounter0にして、

右括弧を数える変数はcounter1にした。

最後に、(の数と)の数が一致するかをif文で判定すれば完成。

一致はさっき教科書で確認したようにイコール二つだね。

よし、この問題はそこまで詰まらずに考えられた。キーボードで打つのが遅いから、そこがもったいないんだけど。

n = int(input())

s = input()

counter0 = 0

counter1 = 0

for i in range(n):

if s[i] == "(":

counter0 += 1

if s[i] == ")":

counter1 += 1

if counter0 == counter1:

print("true")

else:

print("false")

入力例を試して、良さそうなので提出。また結果が出るまでちょっと待つ。

ACと表示されたから、正解だ。これで三問目まで正解したことになる。

初めて参加したにしては中々いいペースじゃないかなと我ながら思う。

そういえば、始まってからどのくらい時間が経ったんだろう。

ふと時計を見ると、ちょうど長針が8を指したところだった。

え、もう40分経ったの！？コンテストが終わるまであと20分しかない。

でも今のペースなら、四問目を解くのがぎりぎり間に合うかも。ここまで来たら間に合わせたい。