AtCoder Beginner Contest 256 メモ(A-D)

今回の結果

3AC

C問題が解き方が分からず。
D問題を見たら頑張れば解ける範囲かなと思ったのでCを飛ばす判断をして、時間ギリギリでなんとかACできた。

A - 2^N

https://atcoder.jp/contests/abc256/tasks/abc256_a

Difficulty: 7

問題文

$N$ が与えられます。$2^N$ を出力してください。

制約

• $0≤N≤30$
• $N$ は整数である

入力

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

$N$

出力

答えを出力せよ。

入出力例

入力例 1

3

出力例 1

8

入力例 2

30

出力例 2

1073741824

参加中に考えたこと

256回目だから、2のN乗に関する問題は出るだろうなという予想はしてた。A問題で出てきたのでシンプルな問題になってる。
pow関数を使うのが一番楽だけど誤差が出るのが心配。制約の最大値30で試して誤差はなかったので大丈夫だろうということでpow関数を使って提出。
powはdouble型なので整数型でキャストしてあげる。答えの後ろに $.00000$ とかついてると多分WAになる。
pow関数を使わずループでも解けるけど、N=0の時には1となるようにちょっと工夫は必要。
あとNが大きいと答えがint型に収まらないのでlong long型を使うこと。

B - Batters

https://atcoder.jp/contests/abc256/tasks/abc256_b

Difficulty: 81

問題文

高橋君は野球をモチーフにしたゲームを作ろうとしましたが、うまくコードが書けなくて困っています。
高橋君の代わりに次の問題を解くプログラムを作ってください。

マス $0,$ マス $1,$ マス $2,$ マス $3$ の $4$ つのマス目があります。はじめマスの上には何もありません。
また、整数 $P$ があり、はじめ $P=0$ です。
正の整数からなる数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられるので、$i=1,2,\ldots,N$ について順番に次の操作を行います。

1. マス $0$ に駒を $1$ 個置く。
2. マス上のすべての駒を番号が $A_i$ 大きいマスに進める。言い換えると、駒がマス $x$ にあればその駒をマス $x+A_i$ に移動する。
   ただし移動先のマスが存在しない (すなわち $x+A_i$ が $4$ 以上になる) 駒たちに関しては、それらを取り除いて $P$ に取り除いた個数を加算する。

すべての操作を行った後の $P$ の値を出力してください。

制約

• $1≤N≤100$
• $1≤A_i≤4$
• 入力される値はすべて整数

入力

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

$N$
$A_1 A_2 \ldots A_N$

出力

操作終了時点での $P$ の値を出力せよ。

入出力例

入力例 1

4
1 1 3 2

出力例 1

3

入力例 2

3
1 1 1

出力例 2

0

入力例 3

10
2 2 4 1 1 1 4 2 2 1

出力例 3

8

参加中に考えたこと

問題文の説明の通りにコードを書くだけ。
マスは4つしかないけど配列で持っておいたほうが処理は楽。操作1と操作2を続けてすることから、1つのマスに2つ以上の駒が入らないことは分かる。

C - Filling 3x3 array

https://atcoder.jp/contests/abc256/tasks/abc256_c

Difficulty: 541

問題文

$6$ 個の整数 $h_1,h_2,h_3,w_1,w_2,w_3$ が与えられます。
縦横 $3×3$ のマス目に、以下の条件をすべて満たすように各マスに正の整数を $1$ つずつ書きこむことを考えます。

• $i=1,2,3$ について、上から $i$ 行目に書きこんだ数の和が $h_i$ になる。
• $j=1,2,3$ について、左から $j$ 列目に書きこんだ数の和が $w_j$ になる。

例えば $(h_1,h_2,h_3)=(5,13,10),(w_1,w_2,w_3)=(6,13,9)$ のとき、以下の $3$ 通りの書きこみ方はすべて条件を満たしています。(条件を満たす書きこみ方は他にもあります)

さて、条件を満たす書きこみ方は全部で何通り存在しますか？

制約

• $3≤h_1,h_2,h_3,w_1,w_2,w_3≤30$
• 入力される値はすべて整数

入力

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

$h_1$ $h_2$ $h_3$ $w_1$ $w_2$ $w_3$

出力

条件を満たす書きこみ方が何通りあるかを出力せよ。

入出力例

入力例 1

3 4 6 3 3 7

出力例 1

1

入力例 2

3 4 5 6 7 8

出力例 2

0

入力例 3

5 13 10 6 13 9

出力例 3

120

入力例 4

20 25 30 22 29 24

出力例 4

30613

参加中に考えたこと

魔法陣の一片は高々30なので答えはそんなに大きな数にはならなそう。
各マスに入るのは正の整数であることと制約の制約から整理すると、各マスの値に入り得る数値1～28であることは分かる。
ここから先の進め方が閃かなかったのでスキップ。

考察・感想

数字が小さいので全探索でも解けるのかを考えてみた。
純粋に9重ループで計算すると計算量は $O(N^9) = 30^9 \approx 10^{13}$ でTLEする。
少し考えてみると、各行または列において2箇所の値が決まっていると、もう１つはhあるいはwからその2つの値を引いた値となる。

このあたりは公式解説のほうが詳しく書かれているが、結論として左上の4つの値が決まれば、残りの5つのマスは自動的に決まる。右下については、途中に求めた4つの値を使って計算ができ、その値が作ることができる場合にカウントする。
左上4つのマスを4重ループにして、ループの中で判定する処理を行なう方法であれば計算量は $O(N^4) = 30^4 = 810,000$ なので実行時間制限内に収まる。
途中考えたように多重ループの中の範囲をシビアにする必要はなく、4重ループの全て1~30としてもACできた。

D - Union of Interval

https://atcoder.jp/contests/abc256/tasks/abc256_d

Difficulty: 546

問題文

実数 $L,R$ に対して、$L$ 以上 $R$ 未満からなる実数の集合を $[L,R)$ と表します。このような形で表される集合を右半開区間といいます。
$N$ 個の右半開区間 $[L_i ,R_i)$ が与えられます。これらの和集合を $S$ とします。$S$ を最小の個数の右半開区間の和集合として表してください。

制約

• $1≤N≤2×10^5$
• $1≤L_i<R_i≤2×10^5$
• 入力に含まれる値は全て整数である

入力

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

$N$
$L_1$ $R_1$
$\vdots$
$L_N$ $R_N$

出力

$S$ が最小で $k$ 個の右半開区間の和集合で表せるとする。そのような $k$ 個の右半開区間 $[X_i ,Y_i)$ を $X_i$ の昇順で以下のように $k$ 行出力せよ。

$X_1$ $Y_1$
$\vdots$
$X_k$ $Y_k$

入出力例

入力例 1

3
10 20
20 30
40 50

出力例 1

10 30
40 50

入力例 2

3
10 40
30 60
20 50

出力例 2

10 60

参加中に考えたこと

$N≤2×10^5$ かつ $R_i≤2×10^5$ なので、$1$ から $2×10^5$ までの数直線の配列を作って、N個の半開区間の範囲を順に埋めていくという方法ではTLEすることが予想される。

以前解いた数直線の問題で、区間の両端のデータだけを使って解く方法があったので、同じ方法で解くことを考えた。L,Rをpairで持たせて、左から処理したいのでソートしておく。
和集合を求めるにあたって何を用いるのかに悩んだ。スタックとかも考えたが値によって取り出す順番が違うので失敗。左端の値で比較したいので最終的にはLとRの２つのmapを用いることにした。
また、この問題では右半開区間しかないので、ある半開区間のRともう１つの半開区間のLが同じ値の場合は1つの区間とみなせる。

ソートした右半開区間を左から順に読んでいってシミュレーションしていけばよさそう。
区間の範囲内か範囲外かで和集合を分けるか分けないかを決めていくという方法で提出したらWAになった。
数直線のケースのどれかの考慮が漏れてるので整理し直す。

２つの右半開区間 $A[L_1,R_1), B[L_2,R_2)$ の位置的な関係性のパターンは、

1. $L1 < R1 < L2 < R2$　交差していない
2. $L1 < L2 < R1 < R2$　交差している
3. $L2 < L1 < R2 < R1$　※ソート済なのでこのケースはない（2と同じとみなす）
4. $L1 < L2 < R2 < L1$　交差していないが、１つの範囲の中に他方が含まれている

のどれかのはず。
4の考慮が抜けてそう、、と思ったらその通りだったのでこのケースの処理を直して再提出するとACできた。
書いたコードがかなりゴリ押し感がある。

考察・感想

LとRをペアで持たないと整合性が崩れるかと思ったけど、この問題ではその心配は必要なくて、(1)位置、(2)LかRか、の２つをペアで持たせることで事足りる。
左から見ていくと Lの数 < Rの数 となることはないと考えていい。
あとは公式解説にある「問題の読み替え」が分かりやすい。