駆け出し競技ぷよグラマーの日記１
お久しぶりです！！おはこんばんにちは！かにころです！
実は今回の記事はPC上から書き込んでいます
いやー文字が入力しやすいのなんの
大学に入ってからPC触る機会多くなって、タイピング苦手だったんですけど、ちょっとだけはやくなりましたね！うれしい！
さて、今回プログラミングのコンテストAtcoderBeginnerContestに参加した話です
Atcoderというのは、オンラインで参加できるプログラミングコンテストを開催するサイトのことです
どんなんかっていうと、まず問題が与えられて、入力に対して正しい出力をするようなプログラムを作って提出すると得点が加算されるって感じです
クイズに答えていくイメージですね！レートもでるので楽しいよ！
問題にも難易度があって、例えば私が参加したAtcoderBeginnerContestはA,B,C,Dの四種類の問題があったDに近づくほど難しくなっていきます
どのくらい難しいかデレステで例えると、Aはdebut、BはMas☆23~25クリア、CはMas☆27~フルコン、Dは☆29～Mas+フルコンって感じです(Mas適正並感)
で、今回の結果↓
結果がACになってたら正解ってことです
こっからC問題の振り返りをします、というのも自分の考えた方法より楽な解き方あったんだけどちょっとわいの考えた方法も聞いてほしいから()
問題はこんな感じ、プログラミング未経験でも問題の意味はわかると思うのでみてみてね
入力例１みて、「一番体力低いやつが殴り続けたらOKだな！」ってまず考えて、入力例２でそれが間違いだって気づいた
入力例２の出力は1(つまりHP1のやつが最終的に残る)なんですよ、こうなるには
①HP5のモンスターが13を二回、８を一回、1000000000のやつを死ぬまで殴る
②5、3、3、0が残る
③HP3がもう一方のHP3とHP5を一回殴る
④2、3、0、0が残る
⑤HP2が3に攻撃→(2,1,0,0)→(0,1,0,0)
って感じにバトルが進んでほしい
だが！！
どんな入力でも対応できるようなプログラムを作って提出する必要があるので、いまの流れのままプログラムを作ってもだめ！何かしら普遍的な解法を見つける必要がある！！
そこでさっきの流れを再考してこう考える
①モンスターのHPが最も低いやつ(今回HP5)で死なない程度にほかのモンスターを削ると考える
要はほかのモンスターのHPを割った余り(剰余)を考える
すると(5,3,3,0)と②と同じ状況になる
③そして今度は同じように0じゃない一番HPの低いモンスター(HP3)で死なない程度にほかのモンスターを削る
すると(2,3,0,0)と④と同じ状況になる…
といったふうに一番小さい数字で剰余を考えていくという作業をモンスターが最後の一匹になるまで繰り返すという手法で上手くいくと考え正解にたどり着きました！
一応ソースコードはっときます
さて、どや顔で解説したところで別解はというと、じつはこれ、全てのモンスターのHPの最大公約数が出力されるようにすればいいみたいです
最大公約数はユークリッド互除法使えばでてくるから最初からそのプログラム(ググればたぶんでてくる)つくれば一発だったんだよね、思いつかんかった(勉強不足)
以上で終わりです、おまいらも興味あったらぷよグラミング、やろう！そんな難しくないから！
俺もやったんだからさ(同調圧力先輩)
