AtCoder Beginner Contest 250 メモ(A-D)

今回の結果

2AC

C問題があと5分あれば解けた。
A問題やB問題は求めるコーディングスキルは変わってないが、
与えられた問題からどのようにコードに落とし込むかを考えさせているなー、と問題文を読んでて思った。

A - Adjacent Squares

問題

https://atcoder.jp/contests/abc250/tasks/abc250_a

Difficulty:25

問題文

縦 $H$ 行、横 $W$ 列のマス目があり、このうち上から $i$ 個目、左から $j$ 個目のマスを $(i,j)$ と呼びます。
このとき、マス $(R,C)$ に辺で隣接するマスの個数を求めてください。

ただし、ある 2 つのマス $(a,b),(c,d)$ が辺で隣接するとは、 $∣a−c∣+∣b−d∣=1$ ($∣x∣$ を $x$ の絶対値とする) であることを言います。

制約

• 入力は全て整数
• $1≤R≤H≤10$
• $1≤C≤W≤10$

入力

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

  H W
  R C

出力

答えを整数として出力せよ。

参加中に考えたこと

問題文の但し書きにちょっとびっくりした。
これって要は$(a,b)$ の上下左右いずれかの方向に対して１つずらしたものが $(c,d)$ になるということのようだけど、使う必要ないかな？

入出力例にある図を見れば分かるんだけど、上下左右それぞれに１つずらして $H × W$ の枠内に収まっていればカウントすればいいよね。
つまり、 $(R,C)$ が $H × W$ の枠に接しているかどうかを見ればいい。
というわけで、判定のところは以下の4つの分岐を並べて解いた。

    int ans = 0;

    if(R > 1) ++ans;
    if(R < H) ++ans;
    if(C > 1) ++ans;
    if(C < W) ++ans;

考察・感想

公式と同じ解き方でしたね。

B - Enlarged Checker Board

問題

https://atcoder.jp/contests/abc250/tasks/abc250_b

Difficulty:109

問題文

縦 $A$ 行、横 $B$ 列のマスからなるタイルを縦 $N$ 行、横 $N$ 列に並べてできた、縦 $(A×N)$ 行、横 $(B×N)$ 列のマス目 $X$ があります。
$1≤i,j≤N$ について、上から $i$ 行目、左から $j$ 列目のタイルをタイル $(i,j)$ とします。

$X$ の各マスは以下のように塗られています。

• 各タイルは白いタイルまたは黒いタイルである。
• 白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
• タイル $(1,1)$ は白いタイルである。
• 辺で隣接する $2$ つのタイルは異なる色のタイルである。ただし、タイル $(a,b)$ とタイル $(c,d)$ が辺で隣接するとは、$∣a−c∣+∣b−d∣=1$ ( $∣x∣$ を $x$ の絶対値とする)であることを言う。

マス目 $X$ を出力の形式に従って出力してください。

制約

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

入力

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

N A B

出力

次の条件をみたす $(A×N)$ 個の文字列 $S_1​ ,\dots,S_{A×N}$​
を改行区切りで出力せよ。

• $S_1 ,\dots,S_{A×N}$ はそれぞれ長さ $(B×N)$ の . または # からなる文字列である。
• 各 $i,j (1≤i≤A×N,1≤j≤B×N)$ に対し、マス目 $X$ の上から $i$ 行目かつ左から $j$ 列目のマスが白で塗られているならば $S i$ の $j$ 文字目は .であり、黒く塗られているならば # である。

入出力例

入力例１

4 3 2

出力例１

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

参加中に考えたこと

A問題に出てきた隣接の定義がまた出てきて、1つのコンテスト内でそういうのはなかった気がする。

問題文の3つ目の箇条書きから、タイル $(1,1)$ の白を初期値にして右と下に伸ばしていくのかと最初考えたが、出力例を見ると規則性があるので、そんな複雑なことはする必要がなさそう。
難しく考えすぎて時間を無駄にしてしまった。

$x$ の大きさが $(A×N, B×N)$ というのが少しややこしい。
ただ出力例を見るとその行列になっているので、外側の二重ループはこの２つを終了条件にするでよさそう。

$(i,j)$ の中身をどう判定するかがこの問題の肝になるのかな。
入力例１を見ながらここを考える。

縦を見ると、A=3、N=4なので行数は12。
3つおきに.と#が変わっているので、Aでの剰余の偶奇で判定できる。
横についても同様のことができる。
で、縦と横を組み合わせるにはどうするかだけど、これは $i \; mod \; A$ の偶奇と $j \; mod \; B$ の偶奇の２つの偶奇を見て、0なら.、1なら#とすればチェック柄が作れた。

ループと $(i,j)$ の判定部分のコードはこんな感じ

    rep(i, A*N){
        rep(j, B*N){
            int ax = i / A % 2;
            int bx = j / B % 2;
            if(ax == 1 && bx == 0 || ax == 0 && bx == 1){
                cout << '#';
            } else {
                cout << '.';
            }
        }
        cout << endl;
    }

考察・感想

公式解説には実装例が２つあるけど、実装例２のほうで解いた。
公式の実装例２のように二重ループの中の判定部分は1行でも書けますね。

C - Adjacent Swaps

問題

https://atcoder.jp/contests/abc250/tasks/abc250_c

Difficulty:517
灰色よりの茶色レベル問題なのでこれは解きたかった。。

問題文

$N$ 個のボールが左右一列に並んでいます。初め、左から $i(1≤i≤N)$ 番目のボールには整数 $i$ が書かれています。

高橋君は $Q$ 回の操作を行いました。 $i(1≤i≤Q)$ 回目に行われた操作は次のようなものです。

• 整数 $x_i$ が書かれているボールをその右隣のボールと入れ替える。ただし、整数 $x_i$ が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。

操作後において左から $i(1≤i≤N)$ 番目のボールに書かれている整数を $a_i$ とします。 $a_1 ,\dots,a_N$ を求めてください。

制約

• $2≤N≤2×10^5$
• $1≤Q≤2×10^5$
• $1≤x_i ≤N$
• 入力は全て整数

入力

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

N Q
x 
1
.
. 
x 
Q 

出力

$a_1,\dots,a_N$ を空白区切りで出力せよ。

入出力例

入力例１

5 5
1
2
3
4
5

出力例１

1 2 3 5 4

参加中に考えたこと

まずは計算量を考えるところから。
配列を使って問題分の通りに順次処理をすると、

• 配列の中から $Xi$ を探すのに $O(N)$
• swapの計算量は $O(1)$で、Q回操作するので $O(Q)$
• この2つの積になるので、$O(NQ) \fallingdotseq 10^{10}$

で、計算量が足りない。

探索を二分探索にすれば、$O(QLogN)$ で計算量は足りそうだけど、この問題ではソートができないので使えない。

配列とは別に、数値がどこにあるかのハッシュを持たせたらどうか？
そうすれば探索の部分が $O(1)$ になるので計算量が足りそう。

$Xi$ を取得したら、ハッシュから配列上の位置を取って、そこから配列の値を入れ替えるのとハッシュの値も同様に入れかえる、ということをすればうまくいくはず。

入力例1を使って、配列を $a$ 、マップ（ハッシュ）を $m$ とすると以下のような関係性ができる。
( $i=0$ は初期配置、太字は値が変更された箇所)

i	$Xi$	$a[0]$	$a[1]$	$a[2]$	$a[3]$	$a[4]$
0		1	2	3	4	5
1	1	2	1	3	4	5
2	2	1	2	3	4	5
3	3	1	2	4	3	5
4	4	1	2	3	4	5
5	5	1	2	3	5	4

i	$m[1]$	$m[2]$	$m[3]$	$m[4]$	$m[5]$
0	0	1	2	3	4
1	1	0	2	3	4
2	0	1	2	3	4
3	0	1	3	2	4
4	0	1	2	3	4
5	0	1	2	4	3

これを見ながら、この動きをするようなコードを書く。
処理を順番に書くと以下のようになる。

0. コマンド $x_i$ を受け取る
1. $x_i$ の配列上の位置をマップから探す。これを $mi$ とする
2. $a[mi+1]$ （ $Xi$ が配列の最右の場合は $a[mi-1]$ ）の値を取得。これを $ai2$ とする
3. マップから $ai2$ の値の位置を取得する。これを $mi2$ とする
4. $a[mi]$ と $a[mi+1]$ （ $Xi$ が配列の最右の場合は $a[mi-1]$ ）をswapする
5. $m[x_i]$ ← $mi2$
6. $m[ai2]$ ← $mi$

方針が決まってコードを書いていたが、バグから抜け出せずタイムアップ。

考察・感想

あと5分あれば解けてた。
けど、この方法が効率が悪い気がするのでもっといい解法がありそうと思って公式解説を見たら、同じ解き方だった。
ただ公式の実装例のほうが使ってる変数が1個多いが、こっちのほうが可読性は高そう。
変数が多くなると代入先を間違えやすくなるので、実は適した関数やライブラリがあるのかと思ったが、これくらいはできなきゃいかんってことですね。
あと値を管理するのはマップじゃなくて配列でもよかった。

D - 250-like Number

問題

https://atcoder.jp/contests/abc250/tasks/abc250_d

Difficulty:797

問題文

以下の条件を満たす整数 $k$ を「 $250$ に似た数」と呼びます。

• $k$ が素数 $p<q$ を使って $k=p×q^3$ と表される。

$N$ 以下の「 $250$ に似た数」は全部でいくつありますか？

制約

• $N$ は $1$ 以上 $10^{18}$ 以下の整数

入力

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

N

出力

答えを整数として出力せよ。

入出力例

入力例 1

250

出力例 1

2

入力例 2

1

出力例 2

0

入力例 3

123456789012345

出力例 3

226863

参加中に考えたこと

問題は読んだけど素数判定に使う部品を持ってなかったし、解法を探すのにも時間がかかりそうだったので解くのはあきらめた。。

考察

解説を見る前にもう一度考え直したけどACさせるまでは結構難しかった。

与えられた条件から、 $q$ の最大値は $\sqrt[3]10^{18} = 10^6$ 以下となる。
$1$ から $10^6$ までの中に素数がいくつあるのか数えてみる。
整数に関する部品をまだ持ってないので、素数を列挙するプログラム（エラストテネスの篩）を作ってみて確認すると $78498$ 個あった。
なお、 $10^6$ までの素数列挙に必要な時間はtimeコマンドで確認すると0.3秒だったので実行時間は問題なさそう。

この数に対して全探索をすると $O(N^2)$ でTLEしそうなのだが、例えば条件を満たすものを値の小さいものからチェックしていくと、条件を満たさなくなった時点でループから抜けてよく、また固定する方の値が大きくなれば条件を満たすものが少なくなるので全探索でもなんとか収まる。
どうしても不安なら二分探索で境界を探しても良い。

最大の値( $n=10^{18}$ )の場合の組み合わせの数は $11871859$ 個だったので二分探索は使わなくても計算量は足りる。

C++で解くにあたってはもう１つ考慮が必要な点があって、
$N$ の判定で $p × q^3 <= n$ の判定をそのまま使うと、左辺が最大で $10^6$ を4回かけて $10^{24}$ でlong long型では足りなくなってしまう。
そこの工夫までしないとこの問題はACできない。
ここは解説を見て確認した。
解決策としては2通りある。

1. $p = min(q-1,\dfrac{n}{q^3})$ でpを計算して、素数列から条件を満たす最大の値を探す
   p = n / (q * q * q) と書いた場合、 q がint型だとオーバーフローするので注意。
   p = n / q / q / q と書くほうが無難。
2. $p×q^3$ がlong long型に収まるかを予めdouble型で計算して見積もる