こんにちは、しほみんです。今日はお昼更新にします。ちょっと昨日は眠すぎました。
今日は久々に競技プログラミングについてお話しします。年末に行われたABC149についてです。
年末ちょっとした事情で参加できなかったので特にレートとかついてないです。ただ、D問題までは自力で時間内に解けた感じなので上々の出来です。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは650前後の茶色です。まずは700目指します。
＜Atcoderでのスタンス＞
・アルゴリズムについては未学習。問題を通じて学習中。
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約25回参加、7か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
早速問題に移っていきます。話もコードもD問題まで載せます。
A問題
2つの文字列S,Tが与えられます。それをつなげてTSとして出してください。
例 S=oder, T=atc →atcoder
文字の入出力の話です。string型でS,Tを読み込みます。
その後Console.Writeで出力します。
ConsoleのWriteとWriteLineの違いは改行するかどうかです。
Writeだと単純に出力して連続で出せます。
WriteLineだと出力して、そのあと改行を加えます。
B問題
2人がA,B枚のクッキーを持っています。A枚持っている人から先にクッキーを食べて、A枚持っている人のクッキーがなくなれば、B枚持っている人のクッキーを食べます。これをK枚分やったときあまりはどうなりますかって問題です。
これも状況を整理すれば一目瞭然です。
状況は以下の通りです。
・A枚持っている人からK枚食べてもA枚持っている人のクッキーが余る。
つまり、A>Kのときは、A枚持っている人はA-K枚、B枚持っている人はB枚になります。
・A枚持っている人からK枚食べてもA枚持っている人のクッキーが余らない。
つまり、A<=Kのときは、A枚持っている人は0枚、B枚持っている人はB+A-K枚になります。ただし、B+A-K<0だと、食べれるクッキーがないのでB枚持っている人も0枚になります。
よってこれをif文で分岐して出力します。
C問題
素数問題です。合成数であれば、それを除外します。
x以上で一番近い素数なのでxから一つずつ検討すればいいです。
また、xが素数かどうかはxを2,3,4,...と割れるかどうか検討します。sqrt(x)までで割り切れなければよいです。
なぜ、sqrt(x)なのか。
もし、素数でない場合だとその数はa×bみたいに表せます。
つまり、2つの積で現れます。
a×bもb×aも同じですので、a<=bとします。ここでaで割れれば、bはおのずと出るので、素数でないとわかります。
また、a<=bなので、a=bが最大で考えられる数です。
よって、x=a×aが最大なので、sqrt(x)までで十分です。
D問題
じゃんけん機に勝って得点を得るゲームです。最大得点を求めます。
ただし、以下の制約があります。
・K回前と同じ手は出せない。
前の制約がなければ、常に勝てば得点を最大化できます。ただし、K回前っていうのがプログラム上厄介です。
なので、Kこのブロックを作ってしまいましょう。つまりこうします。（K=5の場合）
下矢印でforループします。そのあと、右矢印で動けばいいので、けっきょく2重ループをうまく使えばよくなります。あとはそのブロックごとに一つ前と被っているかどうかを見ればよいです。
最後に...
D問題までくると一工夫しないと解けないなって感じです。最近はアルゴリズム的にいかにうまく解けるかを考えるようになりました。最後の2重ループもそういう工夫です。工夫をすればプログラムの量は一気に減らせます。工夫してコードを書いていきたいですね。ではでは。
