AtCoder Beginner Contest 135の復習

プログラミング

どーも、masukenです。

遅くなりましたが先日の土曜日に開催された、AtCoder Beginner Contest 135の復習をしたいと思います。

その時の結果はC問題まで正解して2792位でした。

それでは、復習をしていきたいと思います。

スポンサーリンク

A- Harmony

ABC 135 A Harmony より

この問題では、2つの整数A,Bとの差の絶対値が等しくなるような整数Kを探す問題です。

標準入力は、整数A,Bが与えられているため、
map関数を使って複数の数字を読み込みます。

差の絶対値が等しいというのは、図で書くとこのようになります。

つまり、整数Kの位置はAとBの真ん中にあると考えられるため
K = (A+B)/2 と表すことができます。

また、Kは整数であるという条件もあるため、AとBの和が偶数でなければ、
整数Kは存在せず出力は’IMPOSSIBLE’となります。

B- 0 or 1 swap

ABC 135 B 0 or 1 swap より

僕は最初問題文を見逃していたのですが、この問題において整数を入れ替えるのは1回のみです。
そのため、pを昇順にできる場合というのは、最初から昇順になっている場合と、
昇順から2つの数字が入れ替わっている場合のみです。
最初から昇順になっている場合を忘れないようにしましょう。

標準入力は、最初に数列の長さNをint型でinputするのと、
数列pはリスト形式で読み込みたかったため、list(map(…))の形にしました。

数字が入れ替わっているというのは、数列pと数列pを昇順にソートしたものを比較して判断しました。

C- City Savers

ABC 135 C City Savers より

この問題では、i番目の勇者がi番目とi+1番目のモンスターを倒すことができるという点が、
問題を複雑にしています。そのため、端の勇者から考えていきましょう。

最初はif文で書いてみました。
i番目のモンスターの数と勇者がモンスターを倒すことのできる数の大小によって
後々のストーリーが異なってきます。

Ai > Bi の場合、i番目の勇者はこれ以上モンスターを倒すことができないため
i+1番目の勇者の方に移動します。

Ai < Bi の場合、i番目の勇者はi+1番目のモンスターを倒しにいきます。
この時、i番目の勇者はAi体のモンスターを倒したため、その分Biから引いておく必要があります。
また、i+1番目では、i番目の勇者が倒したモンスターをAi+1から引いて、
i+1番目の勇者への移動する必要があります。

僕はif文をメインに書きましたが、pythonの組み込み関数を使えばもっと簡単に書くことができました。

この解法はAtcoderでの解説を元に作成しました。

left = min(a[i], b[i]) でどのような操作を行なっているかというと、
変数leftにa[i], b[I]のうち小さい方の値を代入しています。

D- Digit Parade

ABC 135 D Digit Parade より

D問題は動的計画法(DP)を使う問題のようです。
DPに関しては今勉強中なので、また追記したいと思います。

まとめ

今回はAtCoder Beginner Contest 135のA~C問題(D問題は時がきたら更新)の復習、解説をしました。

ABC135では、条件の漏れのために2回WAを出してしまい、記録が伸びませんでした。
一応コードを書いた後にはテストをしているのですが、、、

また、他の人のコーディングを見ていると、とても参考になるものがあります。
そのようなコードを出来るだけ吸収して自分のものにしていきたいです。

今後の計画としては、
・A~C問題を素早く解けるようにする。
・D問題にも対抗できるように、D問題も少しずつ手を出していく。

ことをしたいと考えています。

それでは、また。

コメント

タイトルとURLをコピーしました