AtCoder Beginner Contest 174の感想
100-200-300-400-500-0で0ペナ5完1500点。
A - Air Conditioner
が以上かどうかで条件分岐したいので、if文を用いて実装する。計算量は。
B - Distance
個ある点それぞれについて、「原点からの距離が以下か?」という質問に答える。原点からの距離が以下であるような点がいくつあるかを記憶する変数を一つ作ると実装しやすい。今回のA問題のような判定を回繰り返すイメージ。
計算量は。
C - Repsept
説明のため、問題文で与えられたというような数列を、が個続く数をとする。このときの第項はである。
数列について、第項の数から第項の数へ遷移する方法を考える。これは、
- を倍して
- それにを足す
とすれば良いことがわかる。「を足す」とも解釈できるが、上記の方法は変数に寄らず一意に表現できるので何かと都合が良い。
さて、今回はがの倍数かどうか知りたいが、初項から順番にで割って行って割り切れるかどうか見る方法をとると、途中での値がオーバーフローしてしまう可能性がある(Pythonなどでも計算速度が非常に遅くなりTLEする可能性が高い)。ここで、今回は「をで割った余り」がいくつなのかわかれば十分であるので、先ほどの遷移式に
- で割った余りをとる
という操作を追加する。この操作を追加しても正しい値が求まることは剰余算の性質よりわかる(わからない場合は検索してみてください)。
あとは、で割った余りがとなるようなが存在しないとき、第何項まで見れば良いのかという問題がある。ところで、先ほどの遷移方法を見ると、とをそれぞれで割った時の余りが等しければ、とは等しくなることがわかる(ここで「変数に寄らず一意に表現」した恩恵が来る)。よって、あるについて計算した余りが今までに登場していたところで探索を打ち切ればよい。もっと言えば、鳩ノ巣原理より、「をで割った余り」を鳩、「以上未満の整数」を鳩ノ巣と見れば、高々第項までみれば良いことがわかる。
計算量は。
D - Alter Altar
「石を個選び、それらを入れ替える」という操作は、「石を個選び、石の色を変える」という操作を回行ったのと同値なので、できれば石を入れ替える操作を優先して行いたい。最小手数を考えることは一度置いておく。石を入れ替える操作のみで、文字列の中でWR
という連続部分文字列が存在しないようにするためには、WR
という連続部分文字列を見つけたらそれをRW
に置換すればよい。この操作を繰り返すと、最終的にRRR...WWW
という文字列に落ち着くことがわかる。逆に、この形式の文字列は問題の条件を満たす。
よって、文字列中のR
の個数をとすると、先頭から文字目までの中でW
という文字はいくつあるかを数えれば、それがそのまま答えとなる(そのW
を後半のR
と入れ替える操作を行えばよい)。計算量は。
E - Logs
長さの丸太に対して、切った後の長さがそれぞれ以下となるように切るのに必要な切る回数の最小値はで求められる。もしが固定されているなら、本の丸太全てに対して上記の計算をすることで丸太の長さを以下にするために必要な切る回数の最小値がわかる。あとはを以上の範囲で二分探索して解を求めればよい。計算量は。
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減るという法則を見つけることが出来れば、が答えになることがわかる。こういうのを等差数列と言ったりする。
どちらの方法でも、計算量は。
B
B - Magic 2
色々な解法がありそうな問題。
最低何回操作すれば条件を満たせるかを求められれば、それをKと比較した結果を返せばよいことになる。ここで、A,B,Cの制約が極端に小さいので、どんな組み合わせの入力が来ても高々10回程度操作すれば条件を満たせそうだということがわかる。(補足:操作するごとに数値は2倍になっていくので、操作回数に対して数値の増加速度がとても速そう、という予想を立てている。)
なので、実際に操作を行って操作回数をカウントするシュミレーションを行う。まずの条件を満たすようにBの数値を増加させて、その後の条件を満たすようにCの数値を増加させる。
計算量は。
C
C - Marks
i学期の評点はで求められる。同様に、(i-1)学期の評定はである。純粋にこの値を計算しようとすると、という制約よりオーバーフローしてしまう可能性がある。ここで二つの式を見比べるとという部分は重複しているので、大小関係を比べるだけならとを見るだけで良い。(補足:各学期で行われる期末テストの点数A_iは全て正である。)これを回繰り返せばよい。
計算量は。
D
D - Road to Millionaire
問題文を理解するのにしばらく時間がかかった。
M君が所持しているのは「金」「株」の2つのパラメータであるが、このうちの「金」の最終的な値をできるだけ多くしたいということ。i日目において、金→株の変換と株→金の変換は同じコストで行えるので、A_iが小さい時に金→株の変換を行い、A_iが大きい時に株→金の変換を行うと所持金が多くなりそうという予想が立つ。この考えをもとに、i日目から見てかつなるjがあるなら金→株の変換をできるだけ行い、かつなるjがあるなら株→金の変換をできるだけ行うというような貪欲法を思いつく。実際この貪欲法は正しい(詳しい証明は解説PDFがわかりやすい)。
計算量は。
ちなみにのdpでも解けるが貪欲法の方が直感的でわかりやすいかもしれない。dpに慣れている人なら形式的に落とし込むだけなのでdpの方が楽か。
E
E - M's Solution
解けなかった。
集落の数を表すNが小さいので、全探索解を考える。鉄道を建設するならどれかの集落を通るようなものの方が良いので、「どの集落」を通る「縦・横どちら向きの鉄道」を建設するかを考える。N個の集落それぞれについて、その集落を通る鉄道を建設する・しないをbit列で割り振り、その中でさらに縦・横を選ぶ。そして実際に各集落からの歩行距離を算出してその解を現時点での最小解と比較し、更新する。この解法での計算量だが、これはおよそとなるため間に合わない。困った
F
F - Air Safety
こちらの方が解いた人の数は多いらしい。座標を45度回転させるっていう概念がよくわからない
感想
E問題を解きたかった…。解説PDFにもあるように問題を小さくして考えると上手くいきそう?
エイシング プログラミング コンテスト 2020の感想
(タイトル間違ってたのを修正。ABCではない。)
NoSub。Cから解くと決めていて、Cが解けなかった。
A
atcoder.jp
以上以下の範囲にある整数のうち、の倍数であるようなものの個数はで求められる。累積和的な考えを使うと、答えはである。
また、普通にループを使って以上以下の整数をで割って行ってもOK。だが、制約がなので余裕をもって間に合う。
B
atcoder.jp
ループを使ってすべての要素を見ていく。「前から奇数番目」と「が奇数」を同時に満たす場合だけカウントする。奇数か否かは、で割った余りで判定できる。一番最初の要素は番目ではなく番目である点に注意。
C
atcoder.jp
問題文を見たとき、まず等式
を思いつくが、良い変形が思いつかず断念。
とりあえず愚直に解くことを考えると、各に対して、変数の値を決め打ちして実際に等式が成り立つならカウントを増やす、という解が思いつく。の上限は指定されていないが、これらは全て正の整数なので、この変数のうちどれか一つでもを超えると明らかに式が成り立たなくなる。よってであることがわかる。愚直解の計算量はで、制約からだいたい回の計算が必要となる。
ここで、を決めるとの値は一つに定まる(∵未確定の変数が1つしかない)ことを利用すると、式変形して
となり、この2次方程式の解を求めればよいことになる。
(追記:ここの式変形が間違っていた!!正しくは、
です。)
は以上の整数であることに気を付けて実装すると答えが求まる。計算量が、制約から回と(ギリギリではあるが)時間内に終わるよう改善された…
と思って実装したのだが、なぜか答えが合わなかった。
(追記:この解法でも一応882msで通りました。)
Submission #15187699 - AIsing Programming Contest 2020
フォロワーさんから聞いた解法を一応残しておく。一度を考えず単純にを全探索して左辺の値を求め、その値がからの範囲内なら配列でカウントしていき、最後に配列の値を順番に出力すると計算量が、回で求まる。確かにこちらの方が計算量も少ないし、スッキリとした解法である…。
D
atcoder.jp
まず愚直解を考える。ある数に対して、 → は必ず減少する。さらに言うと、2進数で表現したときの桁数はだから、は最大でもである。余りをとる計算の性質からで割った余りは以下になるので、一度の操作で大きさが倍になる。
つまり、二進数で表現したときの桁数がであるような数に対して、を求めるには回桁を見れば良いことになる。まあ大体で求まると考えて問題ない。
全てのに対してこれをやると計算量はとなり間に合わないので、高速化を考える。
よく見ると、もとの数とを比べると高々bitしか違わない。ということは、ともしか違わない。具体的には、の値はか、かの2択である。どちらの値になるかは、桁目がかかを見れば決まる。
また、をそのまま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円になったりして結構大変だった。
B
atcoder.jp
AC
WA
TLE
RE
の順で配列に保存しておくと最後の出力の時に少しだけ楽をできる。文字列がこの4種類と合致するかどうかを試していけばよい。実は1文字目が全て違うのでそこだけで判定してもいけるが、特に意味はない…。
C
atcoder.jp
元のマス目に存在している黒いマスのうちどの個を残すか、という考えだと少し複雑になる。
ここで制約を見るとマス目は最大でもの大きさにしかならないと書いてある。このことより、各行・列について塗る/塗らないを全探索して実際にマスを赤色に塗り、黒いマスがいくつ残るかを数えることが可能だとわかる。こういう全探索はbit全探索と呼ばれている。最近のC問題で普通に要求されてるけど、bit演算をすらすら書けるようになったら相当すごいと思う。
bit生成に、実際に塗った後黒いマスを数えるのに、最終的な計算量はとなる。制約の最大値の場合でも程度となり、十分間に合う。
D
atcoder.jp
実験してみると以下のことが見えた。
フレンドリーさが大きい順にソートしておき、大きい順に到着させる。この時、ある人を到着させた時点で人より前に到着していた人たちはフレンドリーさが人以上であるので、人の右隣と左隣に別の人を到着させれば、人のフレンドリーさ分の心地よさを獲得できる。
…つまり何が言いたいかと言うと、フレンドリーさが大きい人の隣にバンバン突っ込んでいけば人1人のフレンドリーさを2回心地よさとして獲得できるので、(おおざっぱに)降順で並べたときの前半の人達のフレンドリーさの2倍が答えとなる。(説明がむずかしい!!)
E
atcoder.jp
見た目は簡単そうだが、考察をしっかりしないと実装で詰むタイプの問題。「余りを答えよ」に引っ張られて余り同士で大小比較したり、負の数やゼロの扱いをおざなりにしたりすると、すぐコーナーケースにはじかれてペナが出る。
負の数を2回かけると正の数になる、という性質を利用して、正の数のうちの一番大きい値と2番目に大きい値の積、負の数のうちの一番小さい値と2番目に小さい値の積、の2値を比較して、貪欲に大きい方を取っていけば基本的には正解となる。が、
・どう選んでもゼロを含んでしまう→答えはゼロ
・正の数が1つもない→Kが奇数の時答えは必ず負の数になる…ようにみえるが、ゼロが1つでもあれば答えをゼロにできる(もちろん負の数よりゼロのほうが大きい)
・正の数や負の数が奇数個あり、実装でバグらせる
等というようなコーナーケースがたくさん考えられる。実装に入る前に考察をしっかりまとめておくと、バグがあっても発見しやすいかも。
F
atcoder.jp
辺が1つもないときの答えはで出せる。このグラフに辺を一本ずつ加えていくことを考える。を満たす頂点とを結ぶ辺を追加したとき、以下のと、以上のに対する関数の値が1ずつ減少する。辺により連結となる成分が1つ増えるからだ。これを満たすの組は、組ある。これをすべての辺に対して計算して最初の答えから引き算していけば答えが求まる。これも、脳内でのイメージを文章化するのが難しいタイプ…。
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
みたいに愚直に書く。
B
atcoder.jp
操作回数の最小値を求めるということは、なるべく操作回数を少なくしたいという事。S[i]とT[i]が同じ時、S[i]を変更する必要はない。逆にS[i]とT[i]が異なるときはS[i]を変更しないと問題の条件を満たせない。
つまりS[i]とT[i]を比較したとき、異なる文字となっているようなiの個数を求めればよい。
C
atcoder.jp
最初stackを書いてそれぞれのtopを見て読むのにかかる時間が短い方を取る愚直解を書いていたが、どちらも同じ時間かかるときにその下に積まれている本によってどちらの机から読めばよいかが変わってくることに気付き一度全消し(10分ロス)。
それぞれの机A, Bについて、積まれた本を上からi冊読んだ時かかる時間を累積和の要領で配列に保存する。
机Aに対して上からi冊読むと仮定すると、机Bに積まれている本のうちあとどれだけ上から読めるかは二分探索で求められる(境界値の扱いに注意)。iを全探索して、読める本の冊数の最大値を求める。
D
atcoder.jp
以下の解法でTLE:
素数をエラトステネスの篩により[O(N\log \log N)]で列挙する。Kから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で出来る操作をまとめた表を示します。ここではpriority_queueの要素数とします。
操作 | 計算量 |
---|---|
任意の要素へアクセスする | 出来ない |
任意の要素を追加する | |
任意の要素を削除する | 出来ない |
最大値を取得する | |
最大値を削除する |
このように、「追加された要素の集合の中での最大値」を常に高速に求めるのに長けているのが長所です。ただ、追加した要素を途中で削除したくなったとしても、その要素が集合の中のどこに位置するかは外から見てもわかりません。効率よく要素を削除する方法を2つ紹介します。
方法1:priority_queueを2つ用意する
最大値を取得したい要素を追加する(いわゆる普通の用途での)priority_queueと、削除したい要素を追加するためのpriority_queueをそれぞれ用意する方法です。便宜上、前者のpriority_queueを(Queue)、後者を(Remove)として話を進めます。
まずは通常の場合と同じようにに要素を追加していきます。ここで、削除したい要素をに追加します。この時点では、まだの中にが含まれています。
ではいつ削除されるのかというと、の最大値を取り出そうとしたときです。ここで工夫をして、から最大値を取り出す際に、の最大値も取り出して両者の要素を比較するようにします。もし2つの要素が一致するならば、その要素はに含まれている削除したい要素ということになるので、それぞれのpriority_queueからその要素を削除して、もう一度最大値を取得するようにします。2つの要素が異なるならば、削除したい要素ではないということなので、そのまま取り出した要素を最大値として処理を進めます。
この方法のメリットは、priority_queueの性質を保ったまま少し工夫をすることで削除操作もできるようになる点です。次に紹介する方法と比べると、定数倍早いこともメリットとして挙げられます。
方法2:代わりにmultisetを使う
priority_queueと同じ操作を同じような計算量で行えて、さらに削除操作もできるmultisetを使う方法です。multisetは、同じ要素を複数追加できるような多重集合を扱えます。実装には赤黒木という平衡二分木を用いられていることが多いです。
multisetで出来る操作をまとめた表を示します。
操作 | 計算量 |
---|---|
任意の要素へアクセスする | |
任意の要素を追加する | |
任意の要素を削除する | |
最大値を取得する | |
最大値を削除する |
multisetを使うことで最大値の取得を高速に行いつつ、要素の削除も行えるようになりました。ただし、という同じ計算量に見えますが、実装に用いられているデータ構造が違うため、実際はmultisetの方が定数倍遅いです。極端に遅くなるというわけではないので、実行時間に余裕がある場合はこちらの方法がわかりやすいかと思います。
ちなみに、C++のmultisetで要素の削除をする際は少し注意が必要です。削除したい要素をとして
multiset<int> ms; // 中略 ms.erase(x);
としてしまうと、multisetの中にが複数含まれる場合に、それらが全て削除されてしまいます!!! 複数あるのうち一つだけを削除したいときは、引数に削除したい要素が存在するイテレータを渡してあげれば良くて、例えば
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行も使ってられない。