2021-05-08

ABC200

結果

A $\ : 02:42$

B $\ : 05:50$

C $\ : 55:27$

ノーペナ $3$ 完で，パフォは $503$ ，rating変動は $-23$ で $762 \to 739$ でした．

考察

A問題

基本的には( $100$ で割った商) $+1$ を出力すればOK．

ただし， $100$ の倍数の年だけ例外で，この時は $100$ で割った商をそのまま出力する．

B問題

やるだけといえばやるだけ．

$200$ で割り切れるなら $200$ で割って更新します．

$200$ で割り切れないなら， $1000$ 倍して $200$ を足します．文字列の連結とか難しいことは考えずに計算でできます．

C問題

差が $200$ の倍数になるペアは，ともに $200$ で割った余りが等しいことに着目します．

例えば $723, 123, 923, 523$ であれば， $200$ で割った余りは全て $123$ です．

$A[ \$ ]に出てくる数字を $200$ で割った余りで分類し，それぞれの余りに対して問題のような選び方が何通りあるかを計算します．

上の例で言えば， $723$ のペアは $123, 923, 523$ ， $123$ のペアは $923, 523，923$ のペアは $523$ です．

つまり，ある余りになるような $A[ \$ ]がnum個あるとすると，問題を満たすようなペアの数は

$({\rm num}-1) + ({\rm num}-2) + \cdots + 1 = \dfrac{({\rm num}-1) \times {\rm num}}{2}$

です．

感想

C問題で沼りました．累積和かな？って1回思ったらそこから抜け出せなかったですね...

1ヶ月半振りのABCでした．

久しぶりのコンテストで激冷えを覚悟していましたがこの程度でよかった()

少しずつ感覚を取り戻していきます．

2021-04-19

XOR World

ABC121-D "XOR World"

提出コード

atcoder.jp

考察

着目したのは以下の性質です．

任意の偶数 $n$ に対して， $n \oplus (n+1) = 1$

大雑把な証明をしておきます．

任意の偶数 $n$ に対して， $n$ の最下位ビットは $0$ です．

一方で $n+1$ を考えると，最下位ビットが $1$ で，その他のビットは $n$ と等しいです．

よって， $n$ と $n+1$ のXORをとると $1$ になることがわかります．

上の性質を用いると， $A$ から $B$ の中に偶数から奇数に切り替わるタイミングが何回あるか(numとおきます)を考えることで計算量を大幅に小さくできます．

また，num回の $1$ のXORについて，numが奇数であれば $1$ になり，numが偶数であれば $0$ になります．

私は $A$ が偶数か奇数か， $B$ が偶数か奇数かの $4$ 通りの場合分けをしました．

(i) $A$ が奇数で， $B$ が奇数

$A+1$ から $B$ までが繰り返し部分で，num $=\frac{B-A}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $A$ をXORすればOK．

(ii) $A$ が奇数で， $B$ が偶数

$A+1$ から $B-1$ までが繰り返し部分で，num $=\frac{B-A-1}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $A$ と $B$ をXORすればOK．

(iii) $A$ が偶数で， $B$ が奇数

$A$ から $B$ までが繰り返し部分で，num $=\frac{B-A+1}{2}$ です．

つまり，num回だけ $1$ をXORするだけでいいです．

(iv) $A$ が偶数で， $B$ が偶数

$A$ から $B-1$ までが繰り返し部分で，num $=\frac{B-A+1}{2}$ です．

つまり，num回だけ $1$ をXORした後，余った $B$ をXORすればOK．

以上により， $O(1)$ で解けました．

感想

久しぶりの精進ツイートです．新生活でバタバタしていました．

この問題のdiffは $1164$ ですが，今この問題が出たら $800$ ぐらいな気がしますね．

模範解答がきれいすぎて感動しました笑

2021-03-22

ABC196

コンテスト参加

結果

A $\ 01:51$

B $\ 03:23$

ノーペナ $2$ 完で，パフォは $344$ ，rating変動は $-39$ で $801 \to 762$ でした．

考察

A問題

$b-c$ を出力すればOK．

ただ，自分はコンテスト中はそれで本当にいいのか一瞬で判断できませんでした．

符号の問題があったりでそこを考察するよりは全探索をすることを優先しました．

よって， $a \leq x \leq b$ と $c \leq y \leq d$ を全探索し， $x-y$ の最大値を随時更新していくことでAC．

B問題

入力は非常にでかい可能性があるので，まずはstrigで受け取ります．

先頭から順番に出力していき，途中で ' . ' を読んだら終了します．(もちろん ' . ' は出力しない)

途中に ' . ' がなければ最後まで出力し続ければOK．

感想

最近では群を抜いてパフォが低かったです．

C問題なんで思いつかなかったんだろう...？

ちなみに，ABC194と195も参加していましたが記事を書くのが面倒で更新していませんでした()

2021-03-22

Coloring Dominoes

ARC081-D "Coloring Dominoes"

提出コード

atcoder.jp

考察

以下， $2 \times 1$ のドミノを縦ドミノ， $1 \times 2$ のドミノを横ドミノと呼びます．

問題の性質より，ドミノの並べ方は，縦ドミノそのもの( 以下 $D_{ver}$ )，または横ドミノを縦に並べたもの( 以下 $D_{hor}$ )のいずれかを横に並べていくことになります．

(ちなみに，vertical：垂直，horizontal：水平から名前を付けました)

ドミノの色の塗り方は，基準となるドミノが $D_{ver}$ か $D_{hor}$ か，そしてその左隣が $D_{ver}$ か $D_{hor}$ か，で4通りあります．

以下の場合分けでは，例えばあるドミノが $D_{hor}$ で，左隣が $D_{ver}$ のとき， $D_{ver} \to D_{hor}$ のように書くとします．

(i) $D_{ver} \to D_{ver}$ のとき

$D_{ver}$ が連続しているので，色の塗り方は2通りです．

(左隣の $D_{ver}$ の色以外を選ぶ2通りになります．)

(ii) $D_{ver} \to D_{hor}$ のとき

$D_{ver}$ に対して， $D_{hor}$ の色の塗り方は2通りです．

(左隣の $D_{ver}$ の色以外の2色のうち，どちらを上に塗るかで2!=2通りになります．)

(iii) $D_{hor} \to D_{ver}$ のとき

$D_{hor}$ に対して， $D_{ver}$ の塗り方は1通りです．

(既に左隣で2色使ってしまっているためです．)

(iv) $D_{hor} \to D_{hor}$ のとき

$D_{hor}$ に対して， $D_{hor}$ の塗り方は3通りです．

(これは説明がめんどいので省略...)

また， $0 \leq i \lt N$ に対して $S[ i ] = T[ i ]$ であれば $i$ 番目は $D_{ver}$ で，そうでなければ $i$ 番目から $i+1$ 番目にかけてが $D_{hor}$ であることがわかります．

1つ前のドミノが $D_{ver}$ か $D_{hor}$ かどちらかを持っておき，上の場合分けの数字をかけ算しながらmod $10^{9}+7$ をとっていくことで $O(N)$ で解けます．

感想

久しぶりにこれぐらいのdiff(これは1165)の問題をやりました．

記事の更新も久しぶり．

そこまで難しくないという気持ちがあって，最近のdiffに換算したら700ぐらいな気がします．

一発ACできてよかった．

2021-02-28

CADDYコン(ABC193)

コンテスト参加

結果

A $\ 02:00$

B $\ 09:14$

C $\ 33:49$

D $\ 78:33$

$1$ WAの $4$ 完で，パフォは $1057$ ，rating変動は $+28$ で $801 \to 829$ でした．

B問題で $1$ WAしたってマジ...？

考察

A問題

$100 - 100 \times \dfrac{B}{A}$

を出力すればOKです．

算数できなさすぎて割合計算で $2$ 分もかかりましたw

B問題

最終的な出力をする変数をansとして，始めはデカい数字を入れておきます．(私はlong longで変数をいつも宣言しているので $10^{18}$ で初期化しました．)

$0.5$ 分刻みでスヌケマシンは売れてゆくので， $0 \leq i \lt N$ の $i$ について， $A [ i ] \lt X [ i ]$ であればスヌケマシンは売れ残っていると見なせます．

このとき，現在の最小料金ansよりも $P [ i ]$ が小さければansを $P [ i ]$ で更新します．

なぜかめちゃくちゃ問題文の読み間違えをしていました．

始めは，残っているスヌケマシンを一番多く買ったときの料金を求めていましたw

C問題

$a^{b}$ の形の数はとても少ない気がするので，片っ端から列挙します．

$a$ の調べる範囲ですが， $b=2$ が最小であることを考えれば $2 \leq a \leq \sqrt{N}$ です．

このようなそれぞれの $a$ について， $N$ を超えるまで $2$ 乗， $3$ 乗，...としてmapやsetなどのデータ構造に突っ込んでいきます．

普通に数えていくと， $2^{4}$ と $4^{2}$ のように重複カウントがあるのでmapなどで管理しないといけません．

D問題

これは超絶ゴリ押しました．

$1$ から $9$ のカードがそれぞれ何枚残っているかを持っておきます．

何枚残っているかをsumとでもおくと，高橋くんと青木くんの裏向きのカードの組み合わせの総数はsum $\times ($ sum $-1)$ です．

次に，高橋くんの $5$ 枚目と青木くんの $5$ 枚目の数字が何かで全探索します．(最大でもたぶん $9 \times 9$ 通り)

つまり， $1$ から $9$ のカードがそれぞれ何枚残っているかを更新しながら場合の数を頑張って計算します．

例えば，高橋くんの裏カードが $5$ だと仮定して，青木くんの裏カードとして $8$ が条件を満たすとします．ここで， $8$ の残りの枚数だけ条件を満たす場合の数があります．

高橋くんが選んだカードの残り枚数を減らしておく必要があること，そしてそのカードを見終わったら残り枚数を元に戻しておく必要があります．

得点の計算方法ですが，気合です．

感想

B問題までで時間がかかったりWAを出したりめちゃくちゃ焦りましたが，Dまで解けてよかった...

コンテスト中に緑diff問題を解けたのでとても嬉しいです．

2021-02-17

Darker and Darker

精進

AGC033-A "Darker and Darker"

提出コード

atcoder.jp

考察

イメージとしては，既にある黒いマスから四方にどんどん黒いマスが広がっていくかんじです．

これにはキューを使ったBFSがよさそうです．

まずは，初期段階で黒いマスを全てキューにpushします．

キューの先頭要素に対して4近傍を見て，それが与えられたマスの外でなければキューにpushします．ただし，既に見たマスをキューに入れると同じ処理を永遠に繰り返すことになるので，各マスについて既に訪問したかを持っておく配列を作るといいでしょう．

また，問題文の1回の操作でどこまで黒いマスを広げられるかということが大事です．例えば，マス(2, 3)の右側(2, 4)を黒く塗ったとします．そして(2, 4)の右側(2, 5)も黒く塗ると，これは2回操作をしていることになります．

これを解決するには，各操作の初めにキューの大きさを見ておいて，その回数だけキューの先頭要素を見ていけばOKです．もちろんキューには後ろからどんどん次の探索点が追加されていきますが，操作初めのキューの大きさだけ見ることで，その操作でpushした点を見ることはないです．(次の操作で見ることになります．)

イメージ図は以下です．

f:id:chankilu23:20210217170315j:plain