3匹の猫

みみねこの競プロ精進メモ

AtCoder Beginner Contest 174の感想

100-200-300-400-500-0で0ペナ5完1500点。

A - Air Conditioner

X30以上かどうかで条件分岐したいので、if文を用いて実装する。計算量はO(1)

B - Distance

N個ある点それぞれについて、「原点からの距離がD以下か?」という質問に答える。原点からの距離がD以下であるような点がいくつあるかを記憶する変数を一つ作ると実装しやすい。今回のA問題のような判定をN回繰り返すイメージ。
計算量はO(N)

C - Repsept

説明のため、問題文で与えられた7,77, 777, \dots というような数列をA7i個続く数をA_iとする。このときAの第n項はA_nである。
数列Aについて、第i項の数から第i+1項の数へ遷移する方法を考える。これは、

  • A_i10倍して
  • それに7を足す

とすれば良いことがわかる。「7\times 10^{i}を足す」とも解釈できるが、上記の方法は変数iに寄らず一意に表現できるので何かと都合が良い。
さて、今回はA_iKの倍数かどうか知りたいが、初項から順番にKで割って行って割り切れるかどうか見る方法をとると、途中でA_iの値がオーバーフローしてしまう可能性がある(Pythonなどでも計算速度が非常に遅くなりTLEする可能性が高い)。ここで、今回は「A_iKで割った余り」がいくつなのかわかれば十分であるので、先ほどの遷移式に

  • Kで割った余りをとる

という操作を追加する。この操作を追加しても正しい値が求まることは剰余算の性質よりわかる(わからない場合は検索してみてください)。
あとは、Kで割った余りが0となるようなA_iが存在しないとき、第何項まで見れば良いのかという問題がある。ところで、先ほどの遷移方法を見ると、A_iA_jをそれぞれKで割った時の余りが等しければ、A_{i+1}A_{j+1}は等しくなることがわかる(ここで「変数に寄らず一意に表現」した恩恵が来る)。よって、あるA_iについて計算した余りが今までに登場していたところで探索を打ち切ればよい。もっと言えば、鳩ノ巣原理より、「A_iKで割った余り」を鳩、「0以上K未満の整数」を鳩ノ巣と見れば、高々第K項までみれば良いことがわかる。
計算量はO(K)

D - Alter Altar

「石を2個選び、それらを入れ替える」という操作は、「石を1個選び、石の色を変える」という操作を2回行ったのと同値なので、できれば石を入れ替える操作を優先して行いたい。最小手数を考えることは一度置いておく。石を入れ替える操作のみで、文字列の中でWRという連続部分文字列が存在しないようにするためには、WRという連続部分文字列を見つけたらそれをRWに置換すればよい。この操作を繰り返すと、最終的にRRR...WWWという文字列に落ち着くことがわかる。逆に、この形式の文字列は問題の条件を満たす。
よって、文字列中のRの個数をRとすると、先頭からR文字目までの中でWという文字はいくつあるかを数えれば、それがそのまま答えとなる(そのWを後半のRと入れ替える操作を行えばよい)。計算量はO(N)

E - Logs

長さA_iの丸太に対して、切った後の長さがそれぞれL以下となるように切るのに必要な切る回数の最小値は(A_i-1)\div Lで求められる。もしLが固定されているなら、N本の丸太全てに対して上記の計算をすることで丸太の長さをL以下にするために必要な切る回数の最小値がわかる。あとはL1以上\max (A_i)の範囲で二分探索して解を求めればよい。計算量はO(N\log \max (A_i))

F - Range Set Query

解法はあっていたが実装で躓いてしまった。詳しいことは後日追記します。ネム

5完までのスピードは速かったが、問題の難易度が全体的に易しめだったせいかパフォはそこまで高くなかった。

M-SOLUTIONS プロコンオープン 2020の感想

100-200-300-400-0-0 で4完1000点。早解きで良いパフォが付いてもあまりうれしくない。

A

A - Kyu in AtCoder
if文で条件分岐を書いてもいいが、8通りもの分岐を手打ちするのは面倒だし時間がかかる。ここで、レーティングが200変わるごとに級が1減るという法則を見つけることが出来れば、10-X\div 200が答えになることがわかる。こういうのを等差数列と言ったりする。
どちらの方法でも、計算量はO(1)

B

B - Magic 2
色々な解法がありそうな問題。
最低何回操作すれば条件を満たせるかを求められれば、それをKと比較した結果を返せばよいことになる。ここで、A,B,Cの制約が極端に小さいので、どんな組み合わせの入力が来ても高々10回程度操作すれば条件を満たせそうだということがわかる。(補足:操作するごとに数値は2倍になっていくので、操作回数に対して数値の増加速度がとても速そう、という予想を立てている。)
なので、実際に操作を行って操作回数をカウントするシュミレーションを行う。まずA\lt Bの条件を満たすようにBの数値を増加させて、その後B\lt Cの条件を満たすようにCの数値を増加させる。
計算量はO(\log (\max (A, B, C)))

C

C - Marks
i学期の評点はA_i \times A_{i-1} \times \dots \times A_{i-K+2} \times A_{i-K+1}で求められる。同様に、(i-1)学期の評定はA_{i-1} \times A_{i-2} \times \dots \times A_{i-K+1} \times A_{i-K}である。純粋にこの値を計算しようとすると、A_i\le 10^9という制約よりオーバーフローしてしまう可能性がある。ここで二つの式を見比べるとA_{i-1} \times \dots \times A_{i-K+1}という部分は重複しているので、大小関係を比べるだけならA_iA_{i-K}を見るだけで良い。(補足:各学期で行われる期末テストの点数A_iは全て正である。)これをN-K回繰り返せばよい。
計算量はO(N)

D

D - Road to Millionaire
問題文を理解するのにしばらく時間がかかった。
M君が所持しているのは「金」「株」の2つのパラメータであるが、このうちの「金」の最終的な値をできるだけ多くしたいということ。i日目において、金→株の変換と株→金の変換は同じコストで行えるので、A_iが小さい時に金→株の変換を行い、A_iが大きい時に株→金の変換を行うと所持金が多くなりそうという予想が立つ。この考えをもとに、i日目から見てi\lt jかつA_i\lt A_jなるjがあるなら金→株の変換をできるだけ行い、i\lt jかつA_i\gt A_jなるjがあるなら株→金の変換をできるだけ行うというような貪欲法を思いつく。実際この貪欲法は正しい(詳しい証明は解説PDFがわかりやすい)。
計算量はO(N)
ちなみにO(N^2)のdpでも解けるが貪欲法の方が直感的でわかりやすいかもしれない。dpに慣れている人なら形式的に落とし込むだけなのでdpの方が楽か。

E

E - M's Solution
解けなかった。
集落の数を表すNが小さいので、全探索解を考える。鉄道を建設するならどれかの集落を通るようなものの方が良いので、「どの集落」を通る「縦・横どちら向きの鉄道」を建設するかを考える。N個の集落それぞれについて、その集落を通る鉄道を建設する・しないをbit列で割り振り、その中でさらに縦・横を選ぶ。そして実際に各集落からの歩行距離を算出してその解を現時点での最小解と比較し、更新する。この解法でO(N2^{2N})の計算量だが、これはおよそ1.6\times 10^{10}となるため間に合わない。困った

F

F - Air Safety
こちらの方が解いた人の数は多いらしい。座標を45度回転させるっていう概念がよくわからない

感想

E問題を解きたかった…。解説PDFにもあるように問題を小さくして考えると上手くいきそう?

エイシング プログラミング コンテスト 2020の感想

(タイトル間違ってたのを修正。ABCではない。)
NoSub。Cから解くと決めていて、Cが解けなかった。

A

atcoder.jp
1以上x以下の範囲にある整数のうち、dの倍数であるようなものの個数はx\div dで求められる。累積和的な考えを使うと、答えはR\div d - (L-1)\div dである。O(1)
また、普通にループを使ってl以上r以下の整数をdで割って行ってもOK。O(R)だが、制約がR\leq 100なので余裕をもって間に合う。

B

atcoder.jp
ループを使ってすべての要素を見ていく。「前から奇数番目」と「a_iが奇数」を同時に満たす場合だけカウントする。奇数か否かは、2で割った余りで判定できる。一番最初の要素は0番目ではなく1番目である点に注意。O(N)

C

atcoder.jp
問題文を見たとき、まず等式
x^2+y^2+z^2+2xy+2yz+2zx=(x+y+z)^2
を思いつくが、良い変形が思いつかず断念。
とりあえず愚直に解くことを考えると、各Nに対して、変数x, y, zの値を決め打ちして実際に等式が成り立つならカウントを増やす、という解が思いつく。x, y, zの上限は指定されていないが、これらは全て正の整数なので、この変数のうちどれか一つでも\sqrt Nを超えると明らかに式が成り立たなくなる。よって1\leq x, y, z\leq 100であることがわかる。愚直解の計算量はO(xyzN)で、制約からだいたい10^{10}回の計算が必要となる。
ここで、x, yを決めるとzの値は一つに定まる(∵未確定の変数が1つしかない)ことを利用すると、式変形して
z^2+z(x+y)+(n-x^2-y^2-xy)=0
となり、この2次方程式の解を求めればよいことになる。

(追記:ここの式変形が間違っていた!!正しくは、
z^2+z(x+y)+(x^2+y^2+xy-n)=0
です。)

z1以上の整数であることに気を付けて実装すると答えが求まる。計算量がO(xyN)、制約から10^8回と(ギリギリではあるが)時間内に終わるよう改善された…

と思って実装したのだが、なぜか答えが合わなかった。

(追記:この解法でも一応882msで通りました。)
Submission #15187699 - AIsing Programming Contest 2020

フォロワーさんから聞いた解法を一応残しておく。一度Nを考えず単純にx, y, zを全探索して左辺の値を求め、その値が1からNの範囲内なら配列でカウントしていき、最後に配列の値を順番に出力すると計算量がO(xyz)10^6回で求まる。確かにこちらの方が計算量も少ないし、スッキリとした解法である…。

D

atcoder.jp
まず愚直解を考える。ある数Xに対して、Xpopcount(X)は必ず減少する。さらに言うと、2進数で表現したときの桁数は\log Nだから、popcount(X)は最大でも\log Nである。余りをとる計算の性質からpopcount(X)で割った余りはpopcount(X)以下になるので、一度の操作で大きさが\log N倍になる。
つまり、二進数で表現したときの桁数がNであるような数Xに対して、f(X)を求めるには(N+\log N+\log \log N+\dots)回桁を見れば良いことになる。まあ大体O(N)で求まると考えて問題ない。
全てのX_iに対してこれをやると計算量はO(N^2)となり間に合わないので、高速化を考える。
よく見ると、もとの数XX_iを比べると高々1bitしか違わない。ということは、popcount(X)popcount(X_i)1しか違わない。具体的には、popcount(X_i)の値はpopcount(X)+1か、popcount(X)-1かの2択である。どちらの値になるかは、i桁目が01かを見れば決まる。
また、Xをそのまま10進数に直そうとすると10^{2^{100000}}というとてつもなく大きい数字になってしまうが、最後に余りをとることがわかっているなら、最初から余りをとった値を扱えばよい。具体的には、「Xpopcount(X)+1で割った余り」と「Xpopcount(X)-1で割った余り」のデータがあれば、「X_ipopcount(X)\pm 1で割った余り」をO(1)で求められる。あとは数字がそこまで大きくないので、素直に操作を繰り返すことでf(X_i)の値をO(\log N)で求められる。
これをX_iの個数分(N回)繰り返すので、全体の計算量はO(N\log N)となる。popcount(X)-10になる場合、余りの計算が出来ないので例外処理を書く必要がある。

E

atcoder.jp
見ていない。ぱっと見、データ構造を駆使しそうなイメージ。

F

atcoder.jp
C問題の強化版みたいな見た目をしている。全体で見てもかなり難しいらしい。

感想

NoSubはなるべくしないように心掛けているけど、Cが解けないのはまずいと思って考えているうちに提出しないまま終わってしまった。反省。

AtCoder Beginner Contest 173の感想

100(1)-200-300-400-500(2)-600で3ペナ全完2100点、時間はペナルティ込みで98:33。

A

atcoder.jp
A問題を舐めていて、n%1000を出力してWA。サンプルの重要性を知る。
1000円ずつ払うと考えて、実際にループを使って1000円ずつ引いていった。こういう処理は割り算を使うと高速に行えるが考えることが多くなるので今回は引き算で書いた。払い切れたときにお釣りが1000円になったりして結構大変だった。O(N/1000)

B

atcoder.jp
ACWATLEREの順で配列に保存しておくと最後の出力の時に少しだけ楽をできる。文字列がこの4種類と合致するかどうかを試していけばよい。実は1文字目が全て違うのでそこだけで判定してもいけるが、特に意味はない…。O(N)

C

atcoder.jp
元のマス目に存在している黒いマスのうちどのK個を残すか、という考えだと少し複雑になる。
ここで制約を見るとマス目は最大でも6\times 6の大きさにしかならないと書いてある。このことより、各行・列について塗る/塗らないを全探索して実際にマスを赤色に塗り、黒いマスがいくつ残るかを数えることが可能だとわかる。こういう全探索はbit全探索と呼ばれている。最近のC問題で普通に要求されてるけど、bit演算をすらすら書けるようになったら相当すごいと思う。
bit生成にO(2^{H+W})、実際に塗った後黒いマスを数えるのにO(HW)、最終的な計算量はO(2^{H+W}HW)となる。制約の最大値H = 6, W = 6の場合でも1.4\times 10^5程度となり、十分間に合う。

D

atcoder.jp
実験してみると以下のことが見えた。
フレンドリーさが大きい順にソートしておき、大きい順に到着させる。この時、ある人iを到着させた時点で人iより前に到着していた人たちはフレンドリーさが人i以上であるので、人iの右隣と左隣に別の人を到着させれば、人iのフレンドリーさ分の心地よさを獲得できる。
…つまり何が言いたいかと言うと、フレンドリーさが大きい人の隣にバンバン突っ込んでいけば人1人のフレンドリーさを2回心地よさとして獲得できるので、(おおざっぱに)降順で並べたときの前半の人達のフレンドリーさの2倍が答えとなる。(説明がむずかしい!!) O(N\log N)

E

atcoder.jp
見た目は簡単そうだが、考察をしっかりしないと実装で詰むタイプの問題。「余りを答えよ」に引っ張られて余り同士で大小比較したり、負の数やゼロの扱いをおざなりにしたりすると、すぐコーナーケースにはじかれてペナが出る。
負の数を2回かけると正の数になる、という性質を利用して、正の数のうちの一番大きい値と2番目に大きい値の積、負の数のうちの一番小さい値と2番目に小さい値の積、の2値を比較して、貪欲に大きい方を取っていけば基本的には正解となる。が、
・どう選んでもゼロを含んでしまう→答えはゼロ
・正の数が1つもない→Kが奇数の時答えは必ず負の数になる…ようにみえるが、ゼロが1つでもあれば答えをゼロにできる(もちろん負の数よりゼロのほうが大きい)
・正の数や負の数が奇数個あり、実装でバグらせる
等というようなコーナーケースがたくさん考えられる。実装に入る前に考察をしっかりまとめておくと、バグがあっても発見しやすいかも。O(N\log N)

F

atcoder.jp
辺が1つもないときの答えはO(N)で出せる。このグラフに辺を一本ずつ加えていくことを考える。u\lt vを満たす頂点uvを結ぶ辺を追加したとき、u以下のLと、v以上のRに対する関数f(L, R)の値が1ずつ減少する。辺により連結となる成分が1つ増えるからだ。これを満たす(L, R)の組は、u\times (n-v+1)組ある。これをすべての辺に対して計算して最初の答えから引き算していけば答えが求まる。これも、脳内でのイメージを文章化するのが難しいタイプ…。O(N)

A問題でペナを出したり、F問題を一発で通せたりといろいろ楽しいコンテストでした。
あと、このコンテストでのパフォーマンスが黄色(2096)で、初めての黄パフォとなりました!
さらにさらに、黄パフォのおかげで水色になりました!自分、凄いぞー!

AtCoder Beginner Contest 172の感想

Twitterに垂れ流すと遡るのが大変なのでブログに書くことにした

100-200-300-0(1)-0-0 で3完600点。

All Submissions - AtCoder Beginner Contest 172

A

atcoder.jp
式をそのまま書く。足し算よりかけ算の方が優先順位が高いのでa + a*a + a*a*aみたいに愚直に書く。O(1)

B

atcoder.jp
操作回数の最小値を求めるということは、なるべく操作回数を少なくしたいという事。S[i]とT[i]が同じ時、S[i]を変更する必要はない。逆にS[i]とT[i]が異なるときはS[i]を変更しないと問題の条件を満たせない。
つまりS[i]とT[i]を比較したとき、異なる文字となっているようなiの個数を求めればよい。O(|S|)

C

atcoder.jp
最初stackを書いてそれぞれのtopを見て読むのにかかる時間が短い方を取る愚直解を書いていたが、どちらも同じ時間かかるときにその下に積まれている本によってどちらの机から読めばよいかが変わってくることに気付き一度全消し(10分ロス)。

それぞれの机A, Bについて、積まれた本を上からi冊読んだ時かかる時間を累積和の要領で配列に保存する。
机Aに対して上からi冊読むと仮定すると、机Bに積まれている本のうちあとどれだけ上から読めるかは二分探索で求められる(境界値の扱いに注意)。iを全探索して、読める本の冊数の最大値を求める。O(N\log M)

D

atcoder.jp
以下の解法でTLE:
素数をエラトステネスの篩により[O(N\log \log N)]で列挙する。KからNまでの数全てに対して約数を求め、愚直に計算し総和を求める。一つの数に対して約数を求めるのにO(\sqrt N)かかるので、全体としてO(N\sqrt N)かかるためTLE。

ここで考えるのをやめた(この時点で600点獲得しており、他の問題を解けると仮定すればDを捨てるデメリットが存在しない)。

E

atcoder.jp
「ではない」という条件より「である」という条件の方が考えやすい、というところから包除原理が見えたが、詳しい解法を考える前にFを覗いた。F問題が解けそうだったのもあり、結局それきりE問題は考察していない。

F

atcoder.jp
いわゆるNimと呼ばれるゲームであり、ゲーム開始時点での石の数のXORをとると勝敗がわかるようになっている。
後者が勝つためには総XORが0である必要がある。また今回はA_1とA_2以外の数は変動しないのでA_3以降の数のXORをXとしておく。するとA_1とA_2の値を1ずつ増減させて実際にXORを取りXと一致するか全探索することを思いつくがA_i<10^12なので間に合わない。ところでA_1とA_2に操作を加えても総和は変わらないのでA_1+A_2をSとする。すると
P xor Q = X
P + Q = S
という式を満たすP, Qを求める問題となる(ほかにも大小関係などの条件はあるが省略)。イメージとしては、A_1,A_2がどんな値であるかは一旦忘れて条件を満たす数をある程度絞れないか考える感じ。あとはbitごとに独立に考えるのがXORの定石で…

というところでコンテストが終了した。DとFは解けそうで、Eはなにかめんどくさそうなオーラを感じる。

【C++】priority_queueのように最大値を取得しつつ、任意要素の削除もしたい!!

わがままをかなえるシリーズ

以下、競プロでの使用を想定しています。
C++をベースに書いていますが、データ構造についての話なので他の言語でも通用すると思います。

priority_queueで出来ること

priority_queueは、その名の通り優先順位付きキューで、追加された要素のうちの最大値を高速に取得できます。ヒープを用いて実装されています。
priority_queueで出来る操作をまとめた表を示します。ここでnはpriority_queueの要素数とします。
 

操作 計算量
任意の要素へアクセスする 出来ない
任意の要素を追加する O(\log n)
任意の要素を削除する 出来ない
最大値を取得する O(1)
最大値を削除する O(\log n)

 
このように、「追加された要素の集合の中での最大値」を常に高速に求めるのに長けているのが長所です。ただ、追加した要素を途中で削除したくなったとしても、その要素が集合の中のどこに位置するかは外から見てもわかりません。効率よく要素を削除する方法を2つ紹介します。

方法1:priority_queueを2つ用意する

最大値を取得したい要素を追加する(いわゆる普通の用途での)priority_queueと、削除したい要素を追加するためのpriority_queueをそれぞれ用意する方法です。便宜上、前者のpriority_queueをQ(Queue)、後者をR(Remove)として話を進めます。
 
まずは通常の場合と同じようにQに要素を追加していきます。ここで、削除したい要素xRに追加します。この時点では、まだQの中にxが含まれています。
 
ではいつ削除されるのかというと、Qの最大値を取り出そうとしたときです。ここで工夫をして、Qから最大値を取り出す際に、Rの最大値も取り出して両者の要素を比較するようにします。もし2つの要素が一致するならば、その要素はRに含まれている削除したい要素ということになるので、それぞれのpriority_queueからその要素を削除して、もう一度最大値を取得するようにします。2つの要素が異なるならば、削除したい要素ではないということなので、そのまま取り出した要素を最大値として処理を進めます。
 
この方法のメリットは、priority_queueの性質を保ったまま少し工夫をすることで削除操作もできるようになる点です。次に紹介する方法と比べると、定数倍早いこともメリットとして挙げられます。

方法2:代わりにmultisetを使う

priority_queueと同じ操作を同じような計算量で行えて、さらに削除操作もできるmultisetを使う方法です。multisetは、同じ要素を複数追加できるような多重集合を扱えます。実装には赤黒木という平衡二分木を用いられていることが多いです。

multisetで出来る操作をまとめた表を示します。
 

操作 計算量
任意の要素へアクセスする O(\log n)
任意の要素を追加する O(\log n)
任意の要素を削除する O(\log n)
最大値を取得する O(1)
最大値を削除する O(\log n)

 
multisetを使うことで最大値の取得を高速に行いつつ、要素の削除も行えるようになりました。ただし、O(\log n)という同じ計算量に見えますが、実装に用いられているデータ構造が違うため、実際はmultisetの方が定数倍遅いです。極端に遅くなるというわけではないので、実行時間に余裕がある場合はこちらの方法がわかりやすいかと思います。
 
ちなみに、C++のmultisetで要素の削除をする際は少し注意が必要です。削除したい要素をxとして

multiset<int> ms;
// 中略
ms.erase(x);

としてしまうと、multisetの中にxが複数含まれる場合に、それらが全て削除されてしまいます!!! 複数あるxのうち一つだけを削除したいときは、引数に削除したい要素が存在するイテレータを渡してあげれば良くて、例えば

ms.erase(ms.find(x));

と書くことで操作を達成できます。

参考文献

Twitterで実装のアイデアを教えてくださったJoeさん、ぽかーん懐古DPさん、この場を借りて感謝いたします!!

priority_queue - cpprefjp C++日本語リファレンス
C++の日本語リファレンスです。削除操作を行えるメンバ関数は存在しないようです。

c++ - In std::multiset is there a function or algorithm to erase just one sample (unicate or duplicate) if an element is found - Stack Overflow
multisetの削除に関する投稿です。巷では「multisetの罠」と呼ばれているとかいないとか…

【C++】chmin(), chmax() は1行で書けるか?

オンライン授業ってリアルタイムで出席する必要ある?(愚痴)





事の発端

以下は競プロの話である。

.clang_formatによる自動フォーマットの設定を弄っていて、
AllowShortFunctionsOnASingleLine: All
とかの設定をすることで、短い関数をそのまま改行せず1行で表示することが出来る。if文やfor文なども似たような設定をすることで、1行表示ができる。

短い関数というのはつまり、戻り値がある関数の場合『return文だけで構成される』ということで、例えばif文を使ってchminを書いてしまうと、

template<typename T> inline bool chmin(T &a, T b) {if(a<b){a=b;return true;}return false;}

と表示したいところが、フォーマットすると

template<typename T> inline bool chmin(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

という風に改行されてしまう。競プロをやるうえで非常に見づらいし、chminごときに7行も使ってられない。

続きを読む