🐈

AtCoder Beginner Contest 250 メモ(A-D)

2022/05/09に公開約5,400字

今回の結果

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) の上下左右いずれかの方向に対して1つずらしたものが (c,d) になるということのようだけど、使う必要ないかな?

入出力例にある図を見れば分かるんだけど、上下左右それぞれに1つずらして 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 ij 文字目は .であり、黒く塗られているならば # である。

入出力例

入力例1

4 3 2

出力例1

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

参加中に考えたこと

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

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

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

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

縦を見ると、A=3、N=4なので行数は12。
3つおきに.#が変わっているので、Aでの剰余の偶奇で判定できる。
横についても同様のことができる。
で、縦と横を組み合わせるにはどうするかだけど、これは i \; mod \; A の偶奇と j \; mod \; B の偶奇の2つの偶奇を見て、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;
    }

考察・感想

公式解説には実装例が2つあるけど、実装例2のほうで解いた。
公式の実装例2のように二重ループの中の判定部分は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 を空白区切りで出力せよ。

入出力例

入力例1

5 5
1
2
3
4
5

出力例1

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

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

  1. コマンド x_i を受け取る
  2. x_i の配列上の位置をマップから探す。これを mi とする
  3. a[mi+1]Xi が配列の最右の場合は a[mi-1] )の値を取得。これを ai2 とする
  4. マップから ai2 の値の位置を取得する。これを mi2 とする
  5. a[mi]a[mi+1]Xi が配列の最右の場合は a[mi-1] )をswapする
  6. m[x_i]mi2
  7. 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 に似た数」は全部でいくつありますか?

制約

  • N1 以上 10^{18} 以下の整数

入力

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

N

出力

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

入出力例

入力例 1

250

出力例 1

2

入力例 2

1

出力例 2

0

入力例 3

123456789012345

出力例 3

226863

参加中に考えたこと

未着手。

考察

(作成中)

Discussion

ログインするとコメントできます