Zenn
📚

AtCoder Beginner Contest 253 メモ(A-E)

2022/05/29に公開
AtCoder
tech

今回の結果

4AC

DよりCのほうが難しいと感じた。
今回のD問題は閃き系の問題でコードを書く量は少なかったので、早く閃いたのでかかった時間はC問題より短かった。
Difficulty を見たらCとDがほぼ同じ。
E問題に50分ほどかけたけど、ACするところまではいけなかった。

パフォーマンスのHighestを更新するとモチベーションに繋がる！

A - Median?

https://atcoder.jp/contests/abc253/tasks/abc253_a

Difficulty: 17

問題文

整数 a,b,c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

  • 1≤a,b,c≤100
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。

入出力例

入力例 1

5 3 2

出力例 1

Yes

入力例 2

2 5 3

出力例 2

No

入力例 3

100 100 100

出力例 3

Yes

参加中に考えたこと

b が3つの変数の中央値であるような並び順は、a≤b≤c と c≤b≤a の2通りしかない。
なので、この2つの条件でYes/No判定して解いた。

B - Distance Between Tokens

https://atcoder.jp/contests/abc253/tasks/abc253_b

Difficulty: 57

問題文

H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。

マス目の状態は H 個の長さ W の文字列 S_1,\ldots,S_H で表されます。S_i,j = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i,j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i,j} は文字列 S_i の j 文字目を指します。

一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？

制約

  • 2≤H,W≤100
  • H,W は整数
  • S_i (1≤i≤H) は o および - のみからなる長さ W の文字列
  • S_{i,j} = o となる整数 1≤i≤H,1≤j≤W の組がちょうど二つ存在する

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
\vdots
S_H

出力

答えを出力せよ。

入出力例

入力例 1

2 3
--o
o--

出力例 1

3

入力例 2

5 4
-o--
----
----
----
-o--

出力例 2

4

参加中に考えたこと

2つの o の位置さえ分かればよいので、H \times W の二次元配列を用意しなくてもよい。
2つの点を P_1(x_1, y_1),P_2(x_2, y_2) として、この4つの値さえ変数に格納すればよい。

「上下左右の隣接するマスに動かすことを繰り返す」というのは、上下と左右それぞに何マス動く必要があるかを求めるということで、これは |x_1 - x_2| + |y_1 - y_2| で求まる。

考察・感想

この |x_1 - x_2| + |y_1 - y_2| というのをマンハッタン距離っていうのか。
マンハッタン距離：各座標の差（の絶対値）の総和を2点間の距離とする。

C - Max - Min Query

https://atcoder.jp/contests/abc253/tasks/abc253_c

Difficulty: 518

問題文

整数の多重集合 S があります。はじめ S は空です。
Q 個のクエリが与えられるので順に処理してください。 クエリは次の 3 種類のいずれかです。

  • 1 x : S に x を 1 個追加する。
  • 2 x c : S から x を min(c,(S に含まれる x の個数 )) 個削除する。
  • 3 : ( S の最大値 )− ( S の最小値 ) を出力する。このクエリを処理するとき、 S が空でないことが保証される。

制約

  • 1≤Q≤2×10^5
  • 0≤x≤10^9
  • 1≤c≤Q
  • 3 のクエリを処理するとき、S は空でない。
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

Q
query_1
\vdots
query_Q

i 番目のクエリを表す query_i は以下の 3 種類のいずれかである。

  • 1 x
  • 2 x c
  • 3

出力

3 のクエリに対する答えを順に改行区切りで出力せよ。

入出力例

入力例 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

出力例 1

1
5
4

入力例 2

4
1 10000
1 1000
2 100 3
1 10

出力例 2

(出力なし)

参加中に考えたこと

与えられたクエリの順に処理をする必要があるから、1つ1つの処理自体を軽くする方法を考える。
x<10^9 まであるし、1~3のクエリが高速でできそうなのはと探して、連想コンテナに当たりをつける。
個数も持っておく必要があるのでmapを使う。
mapであれば1と2は簡単にできる。

問題は3だが、mapの最大値と最小値をどうやって取るのか。
max_element と min_element が使えるのでは？と思ったがやったことがないので、ネットで調べて確認する。すると、mapの場合は begin() 、 end() が使えることが分かったので、これを使うことに。ただし、 end() は末尾の次を取得するので、prev() を使って1つ前を取得することで最大値が取得できた。
これで最大値と最小値を取得できたので、後は * でイテレータから値を取得して最大値から最小値を引いて出力すればクエリ3が無事できた。

考察・感想

mapを使う場合の最大値の取得をもっと楽にすることができた。
rbegin() を使うとダイレクトに末尾のイテレータが取得できるのでこれを使えばよかった。

あと、公式解説を見たらmultisetを使えば高速にできると書かれてて、問題文の S のイメージにもあってるが、速度面でいえばmapとmultisetでの差はそれほど大きくはないかな？
自分はmultisetはまだ使ったことがなかったので、mapでできるならmapで解くのもありかなと思うし、mapで解いてる人も少なくない模様だった。

D - FizzBuzz Sum Hard

https://atcoder.jp/contests/abc253/tasks/abc253_d

Difficulty: 520

問題文

1 以上 N 以下の整数であって、A の倍数でも B の倍数でもないものの総和を求めてください。

制約

  • 1≤N,A,B≤10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N A B

出力

答えを出力せよ。

入出力例

入力例 1

10 3 5

出力例 1

22

入力例 2

1000000000 314 159

出力例 2

495273003954006262

参加中に考えたこと

N≤10^9 なので単純にループでAとBの倍数を除外していく方法ではTLEしてしまう。

求めたいものが「総和」ということから、この問題はすぐに方法が閃いた。
使うのは自然数の総和の公式で間違いないだろう。
自然数の総和の公式
\displaystyle\sum_{k=1}^nk = \dfrac{n(n+1)}{2}

これを利用すると、Aの倍数の総和、Bの倍数の総和も求められる。
Nの総和からAの総和とBの総和を引けば答えが求まる。

N,A,Bの自然数の関係を集合で考えると、全体集合を U として、
U - A - B + A \cap{B}
が求めたい部分となる。

ここで、Aの倍数かつBの倍数であるものをCとすると、CはAとBの最小公倍数なので、
C = lcm(A,B)
になる。それを使って、

\displaystyle\sum_{k=1}^nk - a \times \displaystyle\sum_{k=1}^{\frac{n}{A}}k - b \times \displaystyle\sum_{k=1}^{\frac{n}{B}}k + C \times \displaystyle\sum_{k=1}^{\frac{n}{C}}k

を計算すれば答えが求められる。

このCを求める時に短絡的にA*BとしてしまってWA1回出してしまった。

考察・感想

この問題で用いた考え方のことを包除原理っていう言い方があるのは知らなかった。
解説は１つだけだったし、解き方としてはこの1択だったのではないかと。

E - Distance Sequence

https://atcoder.jp/contests/abc253/tasks/abc253_e

Difficulty: 1073

問題文

長さ N の整数からなる数列 A=(A_1 ,…,A_N) であって、以下の条件を全て満たすものは何通りありますか？

  • 1≤A_i ≤M (1≤i≤N)
  • ∣A_i − A_{i+1}∣ ≥ K (1≤i≤N−1)

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

  • 2≤N≤1000
  • 1≤M≤5000
  • 0≤K≤M−1
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入出力例

入力例 1

2 3 1

出力例 1

6

入力例 2

3 3 2

出力例 2

2

入力例 3

100 1000 500

出力例 3

657064711

参加中に考えたこと

条件がよく分からなかったので、入出力例を見て理解する。
制約の数が多くはないとは言え、全探索はできなそうだというのは何となくわかる。
でもまずはこの通りの出力ができるよう、DFSでコードを書いてみる。
DFSの中の書き方、終了条件と反復の中身をどう書くかに悩んだが、なんとか作れたと思うのでテストしてみる。
（dfsの関数だけで40行ほどになった。。）

例1,2は期待する答えが得られたが、例3が時間がかかりすぎる。
そこでメモ化再帰を使ってみる。
i, A_i の2次元配列を使って計算結果をメモに入れるようにすると例3が1秒もかからずに処理が終わった。
が、答えが合わないのでどうするか考えているところでタイムアップ。

考察・感想

想定の回答はDPだったのか。
DPも考えたけど、計算量が O(NM^2) になるからTLEすると思ってDP以外の方法を探してしまった。DPを工夫して計算量を減らす方法には気付けなった。
メモ化再帰でも解けないかな？　時間ある時にリトライしよう。

Discussion