Ruteのプログラミング日記

競技プログラミング(AtCoder)の問題の解説や、過去問を解いた感想、また解けない過去問について共有したいと思ってます。

AtCoder Beginner Contest 166 感想 &解説

ABC参加記

AtCoder Beginner Contest 166が、先日5/3 21:00-22:40の期間で開催されました。

皆さん、お疲れさまでしたー。

私は3完で撤退。今回はD問題を落としたのがもったいない....

コンテスト成績証

ユーザ名	Rute
コンテスト名	AtCoder Beginner Contest 166
順位	5398th / 11684
パフォーマンス	642
レーティング	561 → 569 (+8) Highest更新！
段級位	8 級

発行日: 2020/05/03

今回、問題名を見てふと思ったのが、"あれ？これABC164の問題名に似ているぞ"という問題があったということでした(後述するD問題のことです)。問題名が似ていたので難しいと思ったのですが、実際は頭を捻れば解ける問題でした。(Difficultyも茶色だったので難しいとはいえないです)

A問題 A?C

https://atcoder.jp/contests/abc166/tasks/abc166_a

問題概要:

ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催されます。

先週開催されたコンテストを表す文字列 $S$ が与えられるので、今週開催されるコンテストを表す文字列を出力せよ。

(ほぼ問題文のままですが...)

単純です。 $S$ = "ABC"なら"ARC"を出力、 $S$ = "ARC"なら"ABC"を出力すればよいです。

コード: https://atcoder.jp/contests/abc166/submissions/12706874

B問題 B - Trick or Treat

https://atcoder.jp/contests/abc166/tasks/abc166_b

問題概要:

人数とお菓子の種類数を表す $N,K$ が1行、その後に

$i (1≦i≦K)$ 番目のお菓子を配った人数 $d$ 、

$K$ 種類のお菓子を配ったデータ $A_{i,1}, A_{i,2},...A_{i,d}$ が[それぞれ $d$ 個の要素で与えられ、これらが合計で $2K$ 行続けて入力されます。

$N$ 人のうち、お菓子が配られなかったのは何人かを出力せよ。

AtCoder Beginner Contestの問題では珍しいICPC形式の問題のように思いました。

問題を整理すると、

1～Nのうち、 $K$ 行の $A_{i,1}, A_{i,2},...A_{i,d}$ のデータに含まれない数字が何個あるか

という問題文に言い換えることができます。

よって以下のような実装を考えます。

snuke = [0]*Nとし、これをお菓子をもらったかどうかの判定に利用します。

$N,K$ を入力し、その後以下のようなループを $K$ 回実行します。
$d$ を入力する
$A_{i,1}, A_{i,2},...A_{i,d}$ のデータを見て、snuke[ $A_{i,j}-1$ ]に1を加算する。(1-Indexなのでこのような処理をします)
snukeのうち0の要素の個数を出力する。

計算量は合計のデータ数に依存するので、最大で $O(NK)$ です。

よってこれは制約上では十分高速です。

コード: https://atcoder.jp/contests/abc166/submissions/12714791

C問題 C - Peaks

https://atcoder.jp/contests/abc166/tasks/abc166_c

問題概要:

以下のデータが与えられます。

展望台の個数 $N$
展望台同士を結ぶ道の本数 $M$
展望台 $i(1≦i≦N)$ の標高 $H_i$ のリスト
$M$ 本の道のうち、 $j(1≦j≦M)$ 番目の道において結んでいる展望台の組 $A_j,B_j$ (ただし $A_j \neq B_j$ )

このデータをもとに、"いい展望台"がいくつあるかを求めなさい。

ただし、"いい展望台"の条件として

展望台 $i (1≦i≦N)$ から1本の道でたどり着く展望台のうち、展望台 $i$ より高い展望台がなければ、それは"良い展望台"である
一本の道を使ってたどり着ける展望台がない場合は、"いい展望台"である

という条件が与えられます。

問題を見て、実装ベースであると考えました。まず、この問題の出力例1について、簡単な図で示します。

f:id:Rute_programming:20200505153701p:plain — ▲入力例1を図で示すとこのようになります

それぞれの展望台について

展望台1は展望台3より低いです。よって"いい展望台"とは言えません。

展望台2は展望台3よりも、また展望台4よりも低いです。よってこれも"いい展望台"とはいえません。

展望台3は展望台2よりも、展望台2よりも高いです。よってこれは"いい展望台"です。

展望台4は展望台2よりも高いです。よってこれも"いい展望台"です。

よって、出力すべき答えである"いい展望台"の数は2となります。

つまり、この問題は展望台同士のつながりを「無向グラフ」として考え、

各 $i (1≦i≦N)$ に対してのつながりで、展望台 $i$ が最も高ければそれが"良い展望台"になるので、その個数を出力すればいいということになります。

実装:

書くと長くなりますので省略しますが、基本的には

ans = 0と定義する
入力されたデータで無向グラフ(連想配列)の作成
各 $i(1≦i≦N)$ のつながりに対して、つながっている部分の $H$ を参照し、 $i$ 番目の展望台が最も高いかどうかを判定する。最も高い場合はそれが"いい展望台"になるので変数ans に1を加える。
ansを出力する

という実装をすれば解けます。　計算量は $O(N+M)$ 程度になると思います

(この実装の計算量は正確にはわかりません、申し訳ないです....)

コード: https://atcoder.jp/contests/abc166/submissions/12728071

ところで、この問題のDifficultyを見たときに唖然としました。灰Difficultyだったのです。グラフ実装の問題をこれほど多くの方が解けているのを見て、参加者のレベルが高くなっていることを感じました。)

D問題 D- I hate Factorization

https://atcoder.jp/contests/abc166/tasks/abc166_d

問題概要:

$A^5-B^5 = X$ を満たす整数の組 $(A,B)$ を一つ示せ。

$120^5-119^5$ が約10億くらいです。よって、 $(-120,120)$ の範囲で $A,B$ を定め、全探索すれば良いです。

計算量は $-200≦A≦200, -200≦B≦200$ としたときに $400^2 = 160000$ 回の計算をすれば良いので、これは十分高速です。

(私はこの問題を解くときに愚直に式変形して解くことが出来ませんでした...)

コード: https://atcoder.jp/contests/abc166/submissions/12784477

以上、AtCoder Beginner Contest 166感想 &　解説でした。

今回も茶Difficultyの問題が解けませんでした...次回こそは4完を目指したいと思います！