競プロがんばりたい

BootCamp Brown(つづき)

前回やったバチャ，BootCamp Brownで残した問題があったのでやりました．

chankilu23.hatenadiary.com

3 - Ice Tea Store

必要な金額を最小化したいので， $x$ リットルを買う最適な方法を探します．( $x=0.5, 1, 2$ )

$x$ リットルサイズの値段 $C_1$ と， $\dfrac{x}{2}$ リットルサイズ $2$ つ分の値段 $C_2$ を比べます．

もし， $C_2$ が $C_1$ より小さいなら， $C_1$ を $C_2$ で置き換えても差し支えありません．

なぜならこれは同じ $x$ リットルという量をより安く買うことを意味し，また在庫は無限にあるからです．

また，購入するボトルの個数を聞かれてるわけではないので， $C_1$ を $C_2$ で置き換えたことで購入したボトルが $2$ つ分増える，とかは考えなくてOKです．

$x=0.5, 1, 2$ の順で置き換えていかなければいけないことに注意します．

具体的に1つやってみると，

もし $2 \times Q \lt H$ ならば， $H = 2 \times Q$ とします．

$(H, S), (S, D)$ でも同様の操作をします．

購入する金額は最適化できたので，あとは実際にボトルの容量が大きい物から買えるだけ買っていきます．(省略)

5 - Modulo Summation

これは気づけばとても簡単な問題です．(気づかんけど)

結論から言うと，各 $i=1, 2, \cdots, n$ について， $a_i -1$ を全て足したものが答えです．

上手く $m$ を選んだとき， $m$ mod $a_i$ が最大になるのは， $m=a_i -1$ のときです．

言い換えると， $a_i$ と互いに素である $a_i$ 以下の整数のうち最大のものです．

これを任意の $i$ で考えると $m$ は， $a_1, a_2, \cdots, a_n$ の全てと互いに素であり， $a_1, a_2, \cdots, a_n$ を超えない整数のうち最大のものを考えればよいです．

つまり， $m=$ lcm $(a_1, a_2, \cdots, a_n) -1$ です．(lcmは最小公倍数)

この $m$ に対して $f(m)$ を計算すると， $\displaystyle \sum_{i=1}^n (a_i-1)$ です．

ちなみに， $m$ は求めなくてもいいです．(というかデカすぎてオーバーフロウするかも？)

ABC208

結果

A $\ 05:20$

B $\ 15:15$

C $\ 24:02$

D $\ 40:29$

2WAの4完で，パフォは1432，rating変動は $+92$ で $738 \to 830$ でした．

考察

A問題

$N$ 個のサイコロで表せる和の最大は $6 \times N$ なので， $6 \times N \lt K$ ならば確実にNoです．

$K \leq 6 \times N$ ならばYesかというと実はそうではないです(そのせいで2WAした)．

$N$ 個のサイコロで表せる和の最小は $1 \times N$ なので， $K \lt N$ ならばNoです．

逆に $N \leq K$ ならばYesです．

B問題

支払う硬貨の枚数を最小化するので，硬貨はできるだけ高価なものを使いたいです．

よって， $n=10, 9, \cdots, 1$ と見ていき， $n! \leq N$ ならば $N \lt n!$ となるまで $n!$ 円硬貨で払い続けます．

ちなみに問題文の $100$ 枚というのは気にしなくてもよいです．

$10! \times 100 \gt 10^{7}$ なので硬貨が足りないこともないし， $n!$ 円硬貨が $100$ 枚あると $(n+1)!$ を超えますが，既に $(n+1)!$ 硬貨未満まで支払いをしているためです．

C問題

$N \leq K$ ならば，とりあえず全員に $K/N$ 個ずつお菓子を配っておき，お菓子の個数 $K$ を $K \% N$ で更新します．

( $K/N$ は切り捨て除算， $K \% N$ は剰余演算)

次に， $i$ 番目という情報を持ったまま国民番号についてソートします．(私はpairで実装しました．)

あとは国民番号が小さい方から $N$ 人分だけ，持っておいた $i$ 番目という情報によってお菓子を $1$ つ増やします．

D問題

Warshall Floydです．

Warshall Floyd法では，経由してもよい頂点が $k$ 以下であるという制約で最短経路を更新していきます．

よって，最短経路を持つ隣接行列を $k$ の更新ごとに毎回見て，INFでないものは全て答えに加算していきます．( $0$ は足しても $0$ なので足しとけばOK．)

感想

A問題で2WAしたときはどうしようかと思いましたが，D問題で大挽回しました．

最短経路は何回か書いたことがあったので，Warshall Floyd法の性質を覚えていたおかげで爆速でDを解けました．

BootCamp Bworn

バチャ

BootCamp Bworn

Boot Campの茶色の問題5問でバチャを組みました．

https://kenkoooo.com/atcoder/#/contest/show/29f4c347-76f8-4cb5-9e17-9501452d0282

考察

1 - 文字列大好きいろはちゃんイージー

先頭の文字列に着目して $N$ 個の文字列をソートし，先頭の文字が若い順に出力します．

先頭の文字が同じならば2文字目を見，2文字目も同じなら3文字目を見る，という基準でソートします．

2 - AtCoder Group Contest

$3N$ 個の整数をソートし，小さいほうから数えて $N+1, N+2, ... 3N-1$ 番目の数値のみを加算したものが答えです．

まず，強さが一番小さい方から $N$ 人を選び， $N$ 個のグループに振り分けます．

できれば一番強さが大きい人の強さをチームの強さにしたいですが，明らかにそれは不可能なので適当なチーム $i$ に入れておきます．

次に二番目に強さが大きい人ですが，先ほどのチーム $i$ に入れることで二番目に強さが大きい人の強さをチームの強さとすることができます．

このようにして強さが大きい人から順にチームを決めることでチームの強さの和を最大化できます．

3 - Ice Tea Store

時間内にできなかったのでまた今度．

4 - To Infinity

1以外が出てきたら，5000兆日後には必ず $K$ の値より多い数に変化しています．1の場合は5000兆日後にも変化していません．

よって，まずは左から数えて初めて1でない数字が出てくる場所，leftを探します．

leftが $K$ 番目よりも大きければ，5000兆日後の $K$ 番目は1です．

leftが $K$ 番目以下であれば，5000兆日後の $K$ 番目はleft番目の数字です．

5 - Modulo Summation

時間内にできなかったのでまた今度．

感想

一回はやったことあるから早く終わると思ってたけど意外と時間かかりますね．

4問1時間でもいいかも？

ABC206

結果

A $\ 02:21$

B $\ 03:57$

C $\ 28:03$

ノーペナ $3$ 完で，パフォは $661$ ，rating変動は $-8$ で $746 \to 738$ でした．

考察

A問題

通常の整数型の変数で $N \times 1.08$ を計算して場合分けをします．

B問題

$i=1$ を初期値とし，変数sumに $1, 2, 3, ....$ と足し込んでいきます．

それが $N$ を超えたら $i$ を出力すればOKです．

C問題

全体から， $A[ i ] = A[ j ]$ となるような $i, j$ の組の数を引きます．

それぞれの数字が何回出てくるかを数えておいて， $1$ からその数値 $-1$ までの和を数えていく，というのを足していったものを全体から引けばよいです．

例えば入力例3では， $1$ は $4$ 回出てきます．ということは， $1$ だけで見ると $A[ i ] = A[ j ]$ となるのは $3 + 2 + 1$ 通りあります．

一般的には，ある数値が $n$ 回出てくるならば， $A[ i ] = A[ j ]$ となる $(i, j)$ の数は， $\frac{(n-1)n}{2}$ 通りです．

これを他の数値でも見ていけばOKです．

ちなみに， $(i, j)$ の選び方の総数は $\frac{n(n+1)}{2}$ ではなくて， $\frac{(nｰ1)n}{2}$ であることに注意しないとだめです．

感想

C問題で沼りました．

同じ数字が $n$ 回出てくるなら， $A[ i ] = A[ j ]$ になるのは $n$ 通りやろ！とかやってたので無限に時間が溶けました．

激冷えではないのでヨシ！(前回の上昇分が消えた)

gray-brown

gray-brown

灰色3問，茶色3問でバチャをしました．

https://kenkoooo.com/atcoder/#/contest/show/922d4620-1d56-405f-9cff-e4c0d4dc3d7e

考察

1 - i18n

先頭の文字，文字列の長さ $-2$ ，末尾の文字

を出力します．

2 - Indeedなう！

文字列 $S [ i ]$ について，登場するアルファベットの数を数えます．

それが"indeednow"と一致すればYES，1つでも一致しないもしくは過剰な文字があればNOを出力します．

mapとかでやると楽です．

3 - 2点間距離の最大値 ( The longest distance )

全探索して最大の距離のものを探します．

比較するときは平方根を取る必要はなくて，答えの出力の時だけでOKです．

4 - Count Order

next_permutationで頑張ります．

一致したら辞書順で何番目かを保持しておきます．

一致するかどうかの判定は線型的に調べるしかないですが， $N$ の最大は $8$ なので間に合います．

5 - Remainder Minimization 2019

$R$ が $L+2019$ より大きい場合，同じ計算を繰り返すだけなので $R=L+2019$ として $L$ と $R$ の間の $i, j$ を全探索します．

$R$ が $L+2019$ より小さい場合，普通に全探索します．

6 - RGB Triplets

時間足りませんでしたねー．

恐らく，例えばRとGの位置を全探索して，条件を満たすBの位置がどこかを $O(1)$ で出すかんじだと思います．

累積和とかでいけそうな気がします．

感想

初のバチャ記事！

6の問題はコンテスト中に解いたことあるのに今日は解けませんでした．

コンテスト中の集中力ってすごいね．

Even Relation

ABC126-D "Even Relation"

提出コード atcoder.jp

考察

DFSをします，以上．

というのは嘘で，例えば初期値は全頂点 $0$ で塗り，DFSで木を舐めながら距離を逐次計算，距離が奇数であればその頂点は $1$ で塗り替える．

という操作を実装すればOKです．

ちなみに，始めの頂点はどこでも一般性を保つので，僕は頂点 $0$ から始めています．

BFSだと距離の管理が面倒そうなので，再帰で書くのが一番楽です．

特に書くこともないシンプルな問題なのでこれぐらいでいいですか（）

感想

久しぶりにグラフ探索をしました．

かなりシンプルなDFSで，思い出すのに良い問題でした．

シンプルなBFSも解きたいな～

Colorful Hats 2

精進

三井住友信託銀行2019 "Colorful Hats 2"

提出コード

考察

色の種類を一般的に，X，Y，Zと表します．これらは帽子の赤，青，緑のいずれかです．

まずは， $0$ が $4$ 回来ることはないです．

$A[ i ] = 0$ ということは，前に自分と同じ色の帽子をかぶった人がいないということです．

帽子の色は $3$ 種類なので， $0$ と言った人が $4$ 人いる時点で答えは $0$ です．

言い換えると， $A[ i ] = 0$ となってもよい回数をrestとすると， $A[ i ] = 0$ を見つけるごとにrestを減らし，rest $=0$ で答えを $0$ とすればよいです．

人 $i$ の前に人 $i$ と同じ色の帽子をかぶった人がいないとき，人 $i$ の帽子の色の選び方はrestだけ分岐するのでかけ算ですね．

$A[ i ]$ の値を見ながら，色X，Y，Ｚのうちどの色の帽子をかぶるかをカウントしていきます．ただし，帽子の色の選び方が複数あるときはアルファベットが若いほうを選ぶとします．(計算上はそれで問題ない)

例として， $0 \ 1 \ 0 \ 1 \ 2$ のようなものを考えます．以下では，色Ｘ，Ｙ，Ｚの帽子をかぶった人数を $(X,Y,Z)=(1, 2, 3)$ のように表すとします．

$A[ 0 ] = 0$ なので，帽子の色の選び方は $3$ 通りで色Ｘを選びます．このとき， $(X,Y,Z)=(1, 0, 0)$ です．

$A[ 1 ] = 1$ なので，色Ｘを選びます．このとき， $(X,Y,Z)= (2, 0, 0)$ です．

$A[ 2 ] = 0$ なので，帽子の色の選び方は $2$ 通り(YかZのどちらか )で色Yを選びます．このとき， $(X,Y,Z)=(2, 1, 0)$ です．

$A[ 3 ] = 1$ なので，色Yを選びます．このとき， $(X,Y,Z)=(2, 2, 0)$ です．

$A[ 4 ] = 2$ なので，帽子の色の選び方は $2$ 通り(XかＹのどちらか)で色Xを選びます．このとき， $(X,Y,Z)=(3, 2, 0)$ です．

このように考えていくと， $O(N)$ で答えが出ます．

感想

場合の数の問題でした．

正直こういう問題は苦手なので克服しないとですねー

週一で精進したいけど意外と時間がないです...