1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

javaでAtCoder Beginner Contest 160を解く

Last updated at Posted at 2020-08-15

AtCoder Beginner Contest 160お疲れ様でした!
公式ページ

今回の自分の書いたコードはこちら
結果はA-EまでACできました。久しぶりの5問ACでテンション上がります^^

以下簡単に解説します。

##問題A

引数にStringで6文字のものが渡されてくるので、
String.charAt()
で指定文字のcharacterを取り出して、比較すればOKです。

##問題B

金額が与えられて、それを適切に500円硬貨と5円硬貨に両替する問題です。
答えの出力が「嬉しさ」になっていて、500円硬貨をもっていると1000の嬉しさが手に入るので、与えられた金額を2倍しないように注意。
また、5円硬貨についても5の嬉しさが入るからといって、単に余った金額を足せばよいってもんではないので注意です。

long happy = (x / 500) * 1000;
x = x % 500;
happy = happy + (x / 5) * 5;

みたいな感じでACできました。

##問題C

池の周りに家が建っていて、とある地点からの距離が与えられます。
全ての家をまわるのに最小の距離を求める問題です。

今回の家は池の周りに建っているので、実際に通る経路としては視力検査のアイツのような形になるはずです。
円を少し切り取ったような形。

なので、家と家の間が一番遠い距離を求めることができれば、池の外周からその距離を引くことで最小距離が算出できます。

基本的には前の家の距離を覚えておいて、入力のたびに計算でOKです。
最初の家と最後の家も隣り合っているので、忘れずに比較しましょう。

##問題D

N個の頂点を持つ無向グラフで、距離がkのものはいくつあるかを出力する問題です。
無向グラフとか難しい言葉でてきてびびりますが、今回のグラフは単純です。

せいぜい直接向かうか、X-Yの間の道を通るかの2通りしかありません。

TLE起こしそうだなぁ・・・と思っても、以下を見て安心します。

3 ≤ N ≤ 2 × 10^3

コードで表現すると以下のようになります。
二重forループで、直接行くのとX-Yの間通るのとどちらが近いかを計算して、答えの配列に追加しています。

for (int i = 1; i <= n; i++) {
	for (int j = i; j <= n; j++) {
		int direct = j - i;
		int shortCut = dist(i, x) + 1 + dist(j, y);
		int dist = Math.min(direct, shortCut);
		answer[dist]++;
	}
}

distっていうメソッド以下のような感じです。

public static int dist(int p, int q) {
	return Math.max(q - p, p - q);
}

##問題E

X個の赤いリンゴとY個の緑色のリンゴを食べます。
赤いリンゴのおいしさと緑色のリンゴのおいしさを与えられて、おいしさが最大になるように食べます。
無色のリンゴもあり、こいつは着色できます。

自分は以下のようなアルゴリズムで解きました。

  • 赤いリンゴと緑色のリンゴをおいしい順に並べる
  • 赤いリンゴをおいしい順にX個、緑色のリンゴをおいしい順にY個取得して配列APPLEに加える
  • 配列APPLEに無色のリンゴを全て加える
  • 配列APPLEをおいしい順に並べる
  • 配列APPLEからX+Y個所得して足し算していく

で、無事ACできました。
無色のリンゴも配列APPLEに足す発想ができたのが勝因ですかね、、よかったぁ。

個人的にはE問題の中では難易度は低めかな・・・?

##問題F

5分考えて、無理だなってなったので残りの20分はぼーっとしていました笑


感想

久しぶりの水パフォ(1411)出せまして、
レーティングは936→1003と初めての1000突破です!!:blush:

E問題がちょっと簡単めなのもありましたが、なんとか解けてよかった・・・
A-EのACにはこだわりをもって安定させていきたい。これできてればそのうち水ネームなれるはず!:raised_hands:

最後まで読んでくださり、ありがとうございます!

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?