AtCoder Regular Contest 158 備忘録
コンテストページ: AtCoder Regular Contest 158 - AtCoder
コンテスト中AC: A
A - +3 +5 +7
3つの値を同じにする問題は割と良く見る気がします。そして、この系統の問題は、差をどのように詰めるのか、という視点で見ると解ける場合が多いです。
今回、及びをそれぞれとおきます。目標は、にすることです。
操作によってがどのように変化するか考えます。例えば、(+3, +5, +7)の操作の場合、はそれぞれ+2, +2されます。
操作として考え得る6通りについて、がどのように変化するか、その変化量を書き出します。
(+2, +2), (+4, -2), (-2, +4), (+2, -4), (-4, +2), (-2, -2)
ここからわかることとして、は偶数しか変化しません。
そこで、いずれかが奇数である場合、0にするのは不可能です。
以下、が偶数である場合を考えます。
わかりやすくするため、及び操作による変化量を全て2で割っておきます。
変化量は、
(+1, +1), (+2, -1), (-1, +2), (+1, -2), (-2, +1), (-1, -1)
です。
が異なる場合、(+2, -1), (-1, +2), (+1, -2), (-2, +1)のいずれかでにした後、(+1, +1), (-1, -1)のいずれかで0にすることになります。
そこで、次はとの差を考えます。とおきます。
(+2, -1), (-1, +2), (+1, -2), (-2, +1)では、は3の倍数ずつしか変化しません。そこで、が3の倍数でない場合、0にすることは不可能です。
以下、3の倍数であるとします。
このままだと変化量が多く、ややこしいので、適切に値を入れ替えて、が非負整数かつ、となるようにします。
[補足]
値を入れ替えてもよい理由を説明します。
例えばにそれぞれ(+3, +5, +7)するという操作を考えます。
値をと入れ替えた場合に、操作についても入れ替えて(+5, +3, +7)にすると、先程の操作を再現できます。
値を入れ替えることで不可能となるような操作が無いことから、値を入れ替えても問題ない、と言えると思います。
こうしておくことで、選ぶべき変化量は(+1, -2), (-1, -1)に限定されます。
になっていることから、最小の操作回数は以下のようになります。
- (+1, -2)を回して、すなわちにする。
- (-1,-1)を回して、すなわちにする。
AtCoder Beginner Contest 292 備忘録
コンテストページ: AtCoder Beginner Contest 292 - AtCoder
コンテスト中AC: A〜D
コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。
D - Unicyclic Components
Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。今回は、連結成分に属する辺の個数をデータとして持ちます。
辺が与えられた時、が同一の連結成分に属するなら、その連結成分の辺の個数を+1する。そうでないなら、をマージした後に+1すれば良いです。
マージする際は、辺の個数のデータを統合します。
データは常に、Union-Findの各連結成分における根に保持するよう調整が必要なので、その点は注意が必要です。
実装: Submission #39422939 - AtCoder Beginner Contest 292
E - Transitivity
公式解説の要点
ある頂点について、その頂点から(元々隣接していない)全ての到達可能な頂点に有向辺を新たに追加する必要がある。
ある頂点から辺を新たに追加しても到達可能な頂点の集合は変わらない。(ある辺を追加することで新たに辿り着ける頂点が増えるということはない)
以上から、全ての頂点からBFSして、到達可能であって距離が2以上の頂点をカウントすればよい。
実装: Submission #39524065 - AtCoder Beginner Contest 292
F - Regular Triangle Inside a Rectangle
公式解説では、正三角形の縦の長さはとなっていました(2023/3/9現在)が、自分の考え方ではだったので、それで書きます。
要点
正三角形の頂点のうち1つは、最も左下、右下、左上、右上のいずれかとなる(鳩の巣原理により、証明できる) 。正三角形に平行移動と反転を行うことで、長方形の左下の頂点と正三角形の頂点を一致させることができる。
長方形の下の辺と正三角形の下の辺の角度をとすると、辺の長さの正三角形の縦の長さ、横の長さ、角度の制約から以下の条件が得られる。
上記式に対して二分探索を行えばよい。角度の条件の範囲内において、は単調減少、は単調増加なので、とを同時に満たすのうち、最大のものがを満たすか判定する。
自分の補足
• とを同時に満たす最大のの求め方
において、は、です。
とを同時に満たす最大のは、
なら、解なし
なら、
なら、
です。
AtCoder Beginner Contest 289 備忘録
コンテストページ: Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289) - AtCoder
コンテスト中AC: A〜E
コンテスト後にFをAC。WAが出たので、解説を見たが、解法は合っていて実装が間違っていた。
E - Swap Places
高橋くんがいる頂点と青木くんのいる頂点の組について、その状態となるのに最小の操作回数のみを記録していればよく、逆に、同じ状態になるのに、それより操作回数が大きくなる場合は無視できます。
これより、全頂点の組について、その状態になるための最小の操作回数を調べていく解法が考えられます。
状態と遷移の関係を有向グラフとみなすことができるので、BFSにより最小回数を決定していくことができます。
この有向グラフの頂点数は全頂点対となるので個となるのはわかりますが、辺数はコンテスト中分かりませんでした。(ただ、解法として考えうるのがこの方法しかなかったので、提出しました。)
辺数は、公式解説で見積もり方が書いてありました。こちらにもメモしておきます。
- あるグラフの全頂点対について、頂点対から出る全ての辺の合計は以下となる
実装: Submission #38811108 - Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289)
F - Teleporter Takahashi
操作をシミュレートすると、下のような感じの各辺がx軸とy軸に平行な長方形領域が得られます。
oxoxoxo
xxxxxxx
oxoxoxo
xxxxxxx
oxoxoxo
上の1文字を長方形領域に含まれる格子点の1つとみなします。
oがが移動可能な場所、xが不可能な場所です。また、この領域の縦と横の長さは問題で与えられる長方形によって異なります。
この長方形領域の左端、右端のx座標をそれぞれ、下端、上端のy座標をとします。
oが現れるのは、この長方形領域内の格子点であって、格子点について、が2の倍数かつ、も2の倍数の時となります。
操作終了後にがoの場所に存在すれば、から移動可能ということになります。
回目の操作終了後のをとします。も同様とします。
回目の操作終了後にがoであるための条件は以下です。
問題文の条件から、回しても上記条件を満たすものが存在しない場合はNoです。
ところで、操作に従ってを計算できる必要があります。
これは、端から端への移動になるので、以下のように計算できます。
についても、がに変えて同じように計算できます。
では、Yesの場合に操作の列の構築方法を記載します。
前準備として、操作終了までのを全て記録しておきます。
番目の操作の直後の点をとします。番目の操作で上の格子点を選んだとします。
操作前の点は
同様に、
と計算できます。
ここで、が満たすべき条件は、
なので、
同様に、
ここで、、も満たす必要があります。従って、が満たすべき条件は、
です。この条件内ならどの点を選んでも良いので、x,yいずれも最小の座標を選ぶと、
とできます。
この計算を繰り返していくと操作の列を構築できます。
AtCoder Beginner Contest 291 備忘録
コンテストページ: https://atcoder.jp/contests/abc291
コンテスト中AC:A〜E
Fは大方の解法まではコンテスト中に辿りついたが、最後の詰めと実装が間に合わず。コンテスト後に自力AC。
D - Flip Cards
カードの状態は表か裏かの2通りしかなく、状態数が少ないです。また、先頭(または末尾)から順に表裏を決めていくことができます。これより、DPが使えます。
番目のカードの状態がの時の、番目までのカードの表裏の状態の総数。但し、であり、の時はカードは表向き、の時はカードは裏向き
イメージとしては後述する数列の個数を数え上げる問題とみなすと良いです。
数列について、なら番目のカードは表向き、なら裏向きとします。例えば、1〜4番目のカードについて、表、裏、裏、表ならです。
この状態で、5枚目のカードを表向きにしたとすると、となり、裏向きにしたとすると、となります。
この考え方で遷移を考えると、例えば、なら、番目が表の全ての数列について、数列の末尾にを追加(すなわち、を表向きに)して新たな数列ができるので、
dp[i][0] += dp[i-1][0]
という感じで遷移できます。
初期値は、の時、との2つの数列があるので、とし、あとは0にします。
答えは、です。
実装: Submission #39251335 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)
E - Find Permutation
小さい順に数列の値を決定していくことを考えると、問題で与えられる大小関係に従って、決定順序を規定できます。そこで、この順序関係を有向辺とみなし、という有向辺がある有向グラフを考えます。
まず、閉路を含む場合は矛盾が生じるため解なしとなりますが、制約上このケースはありません。(余談:この記事を書いているときに制約に気づきました。)
次に、順序が同列のものが存在すると、どちらから先に値を決定してもよくなるので、を一意に特定できなくなり、Noとなります。
順序が同列のものが存在する例として、最もシンプルな形が入力例2です。
順序が同列のものが存在することの判定方法ですが、トポロジカルソートが利用できます。トポロジカルソートの詳細な説明はWebなどで検索すると出てくるため、ここでは割愛します。
トポロジカルソートで入次数0の頂点をキューに追加する際、同時に2つ以上の頂点がキューに入った場合、それらの順序を規定できません。従って、トポロジカルソートにおけるキューのサイズが2以上となったら、その時点で答えをNoにすれば良いです。
実装: Submission #39259983 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)
F - Teleporter and Closed off
自分より番号が大きい頂点にしか辺が無く、更に辺が各頂点で最大でも10本しかないことを利用します。
頂点を通らないことにした場合、を飛び越えるような移動は、大雑把に考えてもの範囲の頂点から、となるような頂点への移動に限定されます。つまり、
→→→
という移動経路を考えれば良いです。この際のからへの最短距離を
からへの最短距離+からへの移動距離+からへの最短距離
と分解すれば、
- 頂点から各頂点への最短距離
- 頂点からの最短距離
を予め求めておくことで、
求めたい最短距離をとして、で計算できます。
は元のグラフをBFSする事で求められ、は元のグラフの有向辺を全て逆向きにしてからBFSすることで求められます。
を固定した時の最短距離はとから出る辺を全探索すればよいです。
この計算量はのときがワーストケースですが、それでもであり、の全てについて調べてもくらいなので、間に合います。
コンテスト中は大雑把に考えていましたが、正確にはの範囲はだと思います。辺数もなので、計算量はになると思います。
実装: Submission #39279264 - AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS)
AtCoder Beginner Contest 288 備忘録
コンテストページ: Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288) - AtCoder
コンテスト中AC: A〜C
コンテスト後自力AC: D〜F
D - Range Add Query
0-indexedとします。
を愚直に全て0にできるか試すときどうするかを考えると、端から順に0にしていく方法が思い浮かびます。
例えば、としてシミュレートしてみます。
まず、を0にするため、にを足します。
次はにを足す…としたいところですが、足される項が増えてややこしいので、まず、をに足しておきます。
それでは先程と同様に、にを足し、にを足します。
これを繰り返しと、最終的に以下のようになります。
このようにシミュレートしてみると以下がわかります。
- にが足され、末尾項にが等しいものの累積和が構築される
最終的に末尾項が等しい場合には、を0にすることが可能です。
これより、各クエリのについて、が等しいの累積和が全て同じかを判定すればよいです。
が等しいものについてのの累積和を予め計算しておけば、区間の累積和はで求められます。
よって、各クエリで判定できます。
実装: Submission #38649675 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)
E - Wish List
まず、
- 状況が変化していき、複雑なこと
- が小さいこと
から、貪欲法よりもDPっぽいなと当たりをつけます。
をとることを考えたとき、より前が何個取られているかで、どのとなるか変化します。また、前に取られた個数が同じなら、どれが取られていても状況は同じなので、情報をひとまとめにできます。
ここから、以下のようなDPを考えます。
までを個取った時の金額の最小値
を更新することを考えます。
より前は既に個取られていたとしたら、は番目に移動しているはずなので、の金額が必要なはず、と思ってしまいますが、これは誤りです。
なぜなら、より前が個のいずれかが取られた直後にを取ることも可能だからです。
ここが重要なポイントで、番目より前に個とられているような状況について、どのタイミングでを取ったことにしてもよいです。
理由は直感的になりますが、まず、をとるタイミングを変えてもより前のとる順番には影響を与えません。
次に、をとることで、より後ろがずれて、とりたい位置でとれなくなってしまうのではないかと心配になります。
その場合は、先に後ろのものをとっておけば良いです。その後ろのものをとることで、その後ろより更に後ろがずれるなら、更にその後ろを先に取れば良いです。これを繰り返せば、最終的に一番後ろになるので、いつかは矛盾なくとれるはずです。
以上から、番目までで個取られている状況で、を取って個取られている状況にする場合、かかる金額は、
とできます。
これはSegment TreeでRMQを処理すればよいです。
以上から、DPテーブルをの順に以下のように更新できます(初期値は、が0でそれ以外は)。
をとる場合
をとらない場合
但し、がに含まれる場合はとらない選択をできません。
実装: Submission #38728052 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)
F - Integer Division
説明のため、乗算の×を挿入することを仕切りを挿入すると表現します。
例えば、は、です。
を10進数とみなしたものをとします。これは、の後ろに仕切りを入れ、その後番目まで仕切りがない場合の10進数と捉えることができます。
の順に見ていくとき、最後に仕切った場所が同じものについては、同じ10進数をかけることになります。
具体例を示します。として、を考えたとき、最後にの後ろで区切ったものを考えます。
の後ろで区切った時のそれ以前の区切り方は、
の4通りとなりますが、それより後の区切りが無いためこれらには全てが掛けられることになります。
今回は、総和を求める問題なので、以下のように解釈できます。
これを式変形すると、
カッコ内は番目まででできる全ての区切り方の積の総和です。そこで、
番目までできる全ての区切り方の積の総和
とおけば、
と表現できます。
例示したで最終的に求めたい値は、
です。なお、はの前に区切りを入れたと考え、便宜上とします。また、と考えます。
ところで、
なので、
から、
に変化させることができれば、からを計算できます。
この方法ですが、からを計算する場合、
として計算できます。
例の場合、であることから、
式変形すると、
の累積和をとすれば、
となります。
一般化すると、
となり、この漸化式を解いていけば、答えを求めることができます。
実装: Submission #38705016 - Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)
AtCoder Beginner Contest 287 備忘録
コンテストページ: https://atcoder.jp/contests/abc287
コンテスト中AC: A〜E
C - Path Graph?
パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。
以上から、以下がパスグラフである条件です。
- 次数1の頂点がちょうど2つ存在し、その他の頂点の次数は全て2
- 連結成分がただ1つ
上は、次数をカウントしていくことで判定でき、下はUnion Findにより、判定できます。
D - Match or Not
の先頭及び末尾からの何文字目までが一致させられるかをあらかじめ計算しておき、その情報を合体させます。
具体的には、bool型の配列を以下のように定義します。
の先頭から文字目との先頭から文字目までを一致させられるならtrue、一致させられないならfalse
とし、同様に、先頭を末尾に言い換えたものをとします。
ここで、便宜上とします。
の場合には、一致できるかをとして判定できます。
は、先頭または末尾の端から順に調べていき、番目のについて、
となったらそれ以降は全て一致させられなくなるので、全てfalseで、それまでは全てtrueとします。
E - Karuta
少し前の問題でRolling Hashを使っていたので、Rolling Hashで解きました。
の文字目までのハッシュ値をとします。
全てのについて、の個数を連想配列でカウントします。
改めて、番目の文字列について、の個数が全体で何個あるかを調べていき、ハッシュ値の数が2以上であるものは自分以外にもそのハッシュ値を持つ文字列が存在することを示しているので、その中で最大のものが答えになります。
(コンテスト後に実装見直し)
AtCoder Beginner Contest 286 備忘録
コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder
コンテスト中AC: A〜E
D - Money in Hand
公式解説とは異なる方法でとする方法を書いておきます。
Sliding Window Agrregationを使います。
DP遷移の一例を示します。
の時、番目ののDP値を集めて配列とします。
同様に番目ののDPテーブルの更新を考えると
このように、が等しいものだけを集めると、最初の方を除いては値を求めるための区間は、長さが一定のまま1つずつ右にずれていくだけということがわかります。
そのため、スライド最小値を一般化したSliding Window Agrregationが使えます。
半群やモノイドが乗せられるはずだったと思いますが、実装はモノイドにしました。モノイドの型はbooleanを、二項演算は論理演算のORを、単位元はfalseにしておけば良いです。
コンテスト中の実装: Submission #38204795 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)
Sliding Window Agrregationの実装: Submission #38292225 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)
E - Souvenir
が小さいので全点対間最短経路をワーシャル・フロイド法によって求めることが可能です。
お土産の価値も最短経路の求め方と似たような感じで求めることができます。
二次元配列を、
間のお土産の価値
とおきます。
初期値として、
- 頂点間に有向辺があるなら、
- 頂点間に有向辺が無いなら、
このようにして求めていくと、ワーシャル・フロイド法の最短距離のテーブルの更新の際、
なら、
なら、
と更新すれば良いです。
なお、このままだと始点の価値が足されていないので、の始点の価値を足して、が求める価値です。
実装: Submission #38211470 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)