忘れないうちにそれぞれの問題をどのように解いたかをまとめます。(D問題は解けませんでした)
問題を要約したものも記入していますが、正確ではないので、下記のリンクより問題文を確認していただけると幸いです。
Atcoder Beginner Contest 095
A問題
問題は1杯700円のラーメンに1個100円のトッピング3個のうち何個かトッピングするので、最終的なお会計はいくらか的な問題でした。
700円+入力された文字の"o"の数×１００で解きました。
B問題
問題はXグラムあるお菓子の素を使ってN種類のドーナッツ(一個作るのにお菓子の素miグラム必要)を最低1つずつ作る場合、最大何個のドーナッツが作れるか的な問題でした。
解き方は最初にXからすべてのmiの和を引きます。そのあとmiの中で最小のmiを求め、残ったXを最小のmiで割った場合の商を求めます。答えは先ほど求めた商+Nとしました。
言葉だと説明しづらいので、式で表すと以下の通りです。
N+(X-Σmi)//min(mi)
C問題
問題はピザ屋のメニューにAピザ、Bピザ、ABピザがありそれぞれA,B,C円である。
ここで、ABピザはA半分、B半分を組み合わせたもの。
AピザX枚、BピザY枚用意するのに必要な最低金額を求めよ。ただしABピザを組み替えた場合に、必要以上のピザが発生しても構わない。
解き方としては、まずABピザがAピザ、Bピザそれぞれ単体で買った場合よりお得かどうか判定しました。
判定は2*CとA＋Bを比較してA+Bの方が安かったら、それぞれ単体で購入した方が安いので、答えはA*X+B+Yです。２＊Cの方が安かったらABピザを購入した方が割安ということになります。ABピザが割安の場合はまずX,Yのうち小さい数字分ABピザを購入します。
そして残った必要なピザをAまたはBピザ単体で購入した方がいいか、それとも必要量以上にピザがあってもいいからABピザを購入した方がいいかを判定し、いい方を答えとして返します。
D問題
寿司屋には外周Cの円形のカウンターがあり、その上にN貫の寿司が置かれている。
そのうちi貫目はviキロカロリーで、xiメートル時計周りに進んだ位置におかれている。
満足したら好きな位置でお店を出ることができ、1メートル歩くと1キロカロリー消費する場合、摂取したカロリーから消費カロリーを引いた場合の最大値はいくらか？とりあえず、現在の位置を保存する変数と、時計周りした場合と反時計回りした場合のi巻目の距離を保存した配列を用意しました。そして、i貫目の寿司に行くための最小の距離を求めた配列を用意し、(カロリー-i貫目の寿司に行くのに必要な最小カロリー)が最大となるところに移動します。移動したらその場所のカロリーを0にし、その場所から見た時計回りをした場合と反時計回りした場合のi貫目の距離を再度計算します。これを(カロリー-i貫目の寿司に行くのに必要な最小カロリー)の最大値が0以下となるまで繰り返して答えを求めようとしましたが、実装が間に合いませんでした。
多分実装が間に合ったところでこのやり方だとTLEになりそうですが...
D問題については休みの日に解説を見て解法を勉強しようと思います。
.png)
0 件のコメント:
コメントを投稿