AtCoder 連続ACチャレンジ 2017/3
AtCoderで1日1AC 2016/12/04スタート
AtCoderの問題の解法に関するネタバレを含みます。見たくない方はご注意ください。また、このページは得られた知見っぽいものを自分用にメモしておくものです。解法を知りたい場合は、まずAtCoderの大半の問題ページに掲載されている解説、あるいは解説放送を参照してください。
- 3/01 (88th)
- 3/02 (89th)
- 3/03 (90th)
- 3/04 (91st)
- 3/05 (92nd)
- 3/06 (93rd)
- 3/07 (94th)
- 3/08 (95th)
- 3/09 (96th)
- 3/10 (97th)
- 3/11 (98th)
- 3/12 (99th)
- 3/13 (100th)
- 3/14 (101st)
- 3/15 (102nd)
- 3/16 (103rd)
- 3/17 (104th)
- 3/18 (105th)
- 3/19 (106th)
- 3/20 (107th)
- 3/21 (108th)
- 3/22 (109th)
- 3/23 (110th)
- 3/24 (111st)
- 3/25 (112nd)
- 3/26 (113rd)
- 3/27 (114th)
- 3/28 (115th)
- 3/29 (116th)
- 3/30 (117th)
- 3/31 (118th)
3/01 (88th)
1
D: タコヤキオイシクナール - AtCoder Regular Contest 008
問題概要
一次関数が $N$ 個並んでいる。各関数は最初 $f(x) = x$ で初期化されている。関数のうちの一つを変更するクエリが $M $ 個与えられる。各クエリが順に実行されたとき、全ての関数を合成した関数に $1$ を入力したときの出力の最大値と最小値を出力せよ。
- $1 \leqq N \leqq 10 ^{12}$
- $0 \leqq M \leqq 10 ^5$
考察
分からなくてググったら、1次関数を複数回くっつけた合成関数は変わらず1次関数であることが分かった いや、なぜ気付かなかった(アホだから)(2次関数とかになると思い込んでた)
実装は、以下のリンクからパク 写経 参考にしました
データ構造と代数
記事中でも触れられているけど、こういう形でテンプレート化しておくと非常に再利用性が高く、競プロのライブラリとして最適であると感じる
RMQやRSQといった単純なモノイドは用意しておけばいいし、多少複雑なモノイドでもその単位元と演算のみに注目すればよいので、変なミスをしなくて済む
Segment Tree本体の操作については、図があって分かりやすいのでこちらも参照:
Efficient and easy segment trees
今回は $N$ が大きすぎるので座標圧縮を行う
クエリの先読みが出来ない場合(対話形式)は、動的構築というのを行うらしい(また別に用意する必要がありそう)
Segment Treeの練習をする:
http://hogloid.hatenablog.com/entry/20121227/1356608982
3/02 (89th)
1
C: データ構造 - AtCoder Regular Contest 033
問題概要
std::set に、小さい方から $X$ 番目の要素へのアクセスおよび削除を高速に行う処理を追加したデータ構造を実現せよ。クエリは $Q$ 個与えられる。
- $1 \leqq Q \leqq 2 \times 10 ^5$
- 要素 $N$ は、$1 \leqq N \leqq 2 \times 10 ^5$
方針
SegTreeかBIT+二分探索
計算量はおそらく $O \left( Q \left( \log N \right) ^2 \right)$
3/03 (90th)
1
D: ARCたんクッキー - AtCoder Regular Contest 017
問題概要
長さ $N$ の配列 $a_i$ が与えられる。区間に定数を足すクエリ、もしくは区間のGCDを求めるクエリの2種類のクエリが $M $ 個与えられるので、処理せよ。
- $1 \leqq N \leqq 10 ^5$
- $1 \leqq M \leqq 10 ^5$
- 常に $1 \leqq a_i \leqq 10 ^9$
方針
これは結構悩んだ SegTreeっぽいのは分かるが、実装しようと考えるとうまく行かない
区間更新区間アクセスSegTreeでは、区間Addを行うとき、各セグメントのGCDが定数時間で更新できる必要があるが、それは(単純には)不可能である
結局、区間Addによって、配列の要素の差分は高々2要素しか変化しないことを考えて、単一更新区間GCD、区間Add単一アクセスの2種類のSegTreeを併用した
後者は実際の配列 $a_i$ を表し、前者はその差分 $a_{i+1} - a_i$ を表す
区間GCDクエリに対して、その区間に含まれる全ての差分のGCDと、区間に含まれるいずれかの要素とのGCDが求めるGCDであるので、十分高速に処理できる
一応注意点としては、差分は正とは限らず、かつ単位元は $0$ である上、コンパイラ組み込みの__gcd関数では非正整数を入力したときの動作がよく分からなかったので、モノイドの演算をちゃんと定義して使用した
区間更新 SegTree について
以下のように考えると、(それが厳密に正しいかどうかはさておき)とりあえずコードを追えると思う
モノイドについてはまあいいとして、これを作用素モノイドと呼ぶことにする
次に作用演算子(と呼ぶことにするもの)を考える
その定義イメージは次の通り: 作用素モノイドの元 $m$ に対して、作用される集合の任意の元 $a$ があって、 $m(a)$ と表記できる作用が考えられるとき、この $m$ を作用演算子とする
今回の例では、二項演算が和であるモノイドに対し、そのモノイドの任意の元から生成される、作用される集合(整数)を引数とする作用Addを定義している (ただし、実装においては後者も二項演算の形になっている)
つまりモノイドの定義に演算が含まれ、演算が作用を規定するので、モノイドが作用を規定するとも言え、これを作用素モノイド、つまり作用のもととなるモノイドと呼ぶのも妥当である
前述の通り、実装においては作用も二項演算の形で表現しているため、遅延伝播を実現するdeferred_actionには、作用演算子そのものではなく、作用させるべきモノイドが置かれている
3/04 (91st)
RCO presents 日本橋ハーフマラソン 予選 オンタイム
マラソン形式は初挑戦だったかも
1
A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選
問題概要
$0$ から $9$ までの整数が書かれた $H$ 行 $W$ 列のグリッドが与えられる。このグリッドからいくつかのオクトミノを切り出すことを考える。ただし、各オクトミノは重複してはいけない。各オクトミノはスコアを持ち、書かれた8つの整数の積がスコアである。全てのオクトミノのスコアの和が得点となる。
方針
まず9が書かれたマスを核として、隣接するマスのうち最大のものを結合させる。ピースどうしがマージされることもあるかもしれない。9のマスが完了したら次は8について、その次は7について……というように順次オクトミノを作っていく。大きい数字はなるべく大きい数字どうしで組み合わせた方が総得点が大きくなるだろうという推測に基づく。
なおオクトミノの全列挙が可能だったらしい
2
B: Food Collector - RCO presents 日本橋ハーフマラソン 予選
おみくじ をしました
反省
A問題の方針は開始30分で思いついたのだが、実装に異常に時間がかかってしまった
実行時間10秒をフルに使って山を登るようなことをしたことがないので、端的に言えば慣れが足りない
3/05 (92nd)
みんなのプロコン オンタイム
1
2
3
問題概要
$N$ 個の文字列 $S_i$ が与えられる。このうち $A_i$ ( $1 \leqq i \leqq K$ ) 番目の文字列のみがヒットするような検索ワードのうち、長さが最小のものを出力せよ。
- $1 \leqq N \leqq 10 ^5$
- $1 \leqq K \leqq N$
方針
まず文字列をソートして、ヒットさせたい文字列が連続しているかどうかを確認する
あとは何か細々としたサムシングを行う(がんばる)
3/06 (93rd)
1
問題概要
毎日 $K$ 個ずつ製品を生産する工場がある。 $D$ 日目に $A$ 個の注文が入るというクエリと、D日目までに合計で何個の製品を売ることができるかを出力させるクエリの2種類のクエリが $Q$ 個与えられるので処理せよ。ただし各注文に対しては、在庫の個数を超えない限り $0$ 以上 $A$ 以下の範囲で売る個数を自由に選択できる。
- $1 \leqq Q \leqq 10 ^5$
- $1 \leqq K \leqq 10 ^9$
- $1 \leqq D \leqq 10 ^9$
- $1 \leqq A \leqq 10 ^9$
方針
座標圧縮はいいとして、SegTreeに落とし込むためにどういうモノイドを定義するかというのが難しく、コンテスト中は着席してしまった
結局、<1つ前の日にち, 今の日にち, これまでに売った個数の合計, $A - {}$(今回の注文で売った個数), 今回の注文の処理後に残っている在庫の個数> の5つの変数をまとめたものをモノイドとした
今回のように、モノイドは数学的な定義に厳密に従ったものでなくても問題ない
3/07 (94th)
1
D: 旅行会社高橋君 - AtCoder Regular Contest 039
問題概要
$N$ 頂点 $M $ 辺からなる連結な単純無向グラフが与えられる。同じ辺を2度以上通らずに、頂点 $A, B, C$ をこの順で辿ることができるかどうかを判定させるクエリが $Q$ 個与えられるので処理せよ。
- $3 \leqq N \leqq 10 ^5$
- $1 \leqq M \leqq 2 \times 10 ^5$
- $1 \leqq Q \leqq 10 ^5$
方針
まず橋を検出し、橋以外の辺によって接続されている頂点をUnion-Findでuniteする
こうすると橋によって接続される各領域を頂点とした木を形成できる
この各領域内部には橋が存在しないため、任意の3頂点(重複していてもよい)を同じ辺を2度通らずに任意の順番で辿ることができるのではないかと推測でき、これはおそらく正しい
あとは適当に高速な方法で $A, C$ の経路上に $B$ が存在するかどうかを確かめればよい
雑記
二重辺連結成分分解と呼ぶらしい
有向グラフだと強連結成分分解？
橋を列挙するにはlowlink以外にもimos法というのがあるらしい(解説スライド参照)
LCAを求める方法もいろいろあって、今回のはDoublingと呼ばれるものだが、Heavy-Light Decomposition してからLight edge を辿って求めるという方法もあるらしい(2chで見た)(理解はしてない)
3/08 (95th)
1
D: 経路 - AtCoder Beginner Contest 037
問題概要
$H \times W$ のマス目があり、各マスには整数が書かれている。スタートを自由に決め、上下左右に隣接しているマスのうち、今いるマスより大きい整数が書かれたマスに移動することを0回以上繰り返す。このときの経路の総数を出力せよ。
- $1 \leqq H, W \leqq 1000$
- マス目の整数の範囲は、 $1 \leqq a \leqq 10 ^9$
方針
簡単で、各マス目から辿ることのできる経路の数をメモ化再帰で計算し、全ての合計を出力すればよい
3/09 (96th)
1
D: 塗り絵 - AtCoder Beginner Contest 036
問題概要
$N$ 頂点の木がある。各頂点を白または黒で塗り分けるとき、塗り分けるパターンは何通りあるか出力せよ。ただし、隣り合う2頂点がいずれも黒く塗られることは許されない。
- $2 \leqq N \leqq 10 ^5$
方針
簡単で、適当な頂点を根として根付き木にした後、葉からボトムアップに、各頂点が白または黒で塗られた場合、その頂点を根とする部分木の塗り分けが何通りあるか、というのを順次計算すればよい
3/10 (97th)
1
D: へんてこ辞書 - AtCoder Beginner Contest 030
問題概要
面倒なので略
方針
ステップ数が $N$ 以下であるような場合は普通にシミュレーションすれば十分で、$N$ よりも大きい場合は、シミュレーションを行う中で必ず同じ単語を2度調べることになる
これを適当な方法で検出し、あとはループになるので普通に余りを計算すればよい
3/11 (98th)
1
D: Big Bang - AtCoder Beginner Contest 022
問題概要
2次元座標平面上に、点が $N$ 個与えられる。これらの全ての点に対して、以下の操作を順に実行する。
- 同じ向きに同じ距離だけ平行移動させる
- 原点を中心に同じ角度だけ回転させる
- 原点を中心に $P$ 倍に拡大する
この結果の $N$ 個の点の座標が与えられるので、 $P$ を計算し出力せよ。
- $1 \leqq N \leqq 10 ^5$
- $1 \leqq P$
方針
仮に全点間距離を計算できれば、 $P$ はそれらの和の比である
一般的に言えば、ある点の集合、およびそれらの位置関係が部分的にでも特定できれば、 $P$ を計算するために必要な要素数は少なくなる
この要素数が少なくなるような、都合よく対応関係が分かるものというと、凸包、となる
雑記
これ、まあ典型なんでしょうけど、分かったときは感動しました
一見無理っぽいものが、凸包という考え方を知っているだけで解決できる、という
3/12 (99th)
AGC011 オンタイム
1
A: Airport Bus - AtCoder Grand Contest 011
頑張ってシミュレーションする
2
B: Colorful Creatures - AtCoder Grand Contest 011
累積和をとって上手いことやる
3/13 (100th)
1
D: Half Reflector - AtCoder Grand Contest 011
まあいろいろ実験してみて、挙動がなんとなく分かって、時間内に実装はできなかった
deque<int> に連続したセクションの情報を格納する手法にした
最終的にBABA…BABAみたいな形で固定される
3/14 (101st)
1
C: Squared Graph - AtCoder Grand Contest 011
問題の読み込み、言い換えができず解説放送を見て実装した
Union-Findと二部グラフ判定でOK
3/15 (102nd)
1
D: レースゲーム - AtCoder Regular Contest 001
解説スライドを見て、幾何に関する操作が分かっていれば解ける
本質的なところは凸包が高速に計算できるということと、この問題特有の部分で言えば交差したときの処理だと思う
知見:
変数の参照は便利！ ただしアドレスの再代入は不可能
3/16 (103rd)
1
D: 多重ループ - AtCoder Beginner Contest 021
コンビネーション
3/17 (104th)
1
D: 大ジャンプ - AtCoder Beginner Contest 011
問題概要
2次元座標平面の格子点上を原点から上下左右に移動することを $N$ 回繰り返したとき、座標 $(X, Y)$ にいる確率を出力せよ。
- $1 \leqq N \leqq 1000$
- $-10 ^9 \leqq X, Y \leqq 10 ^9$
方針
結局コンビネーションを計算することになって、オーバーフローまたはアンダーフローしないように適度な範囲になるように$4$を割ったり掛けたりして最終的に確率が求まるようにしたら通った
たぶん大丈夫だけど、TLEになる可能性も微妙にあるような気もする
3/18 (105th)
ARC070 オンタイム
rating 1901 -> 1976
1
C: Go Home - AtCoder Regular Contest 070
問題概要
$\frac{ \left( n - 1\right ) n } {2} \lt X \leqq \frac { n \left( n + 1 \right) } {2}$ を満たす整数 $n$ を出力せよ。
雑記
あ、ついこないだコドフォでやったやつだ！
2
D: No Need - AtCoder Regular Contest 070
問題概要
正整数が書かれた $N$ 枚のカードがある。カード $i$ に書いてある正整数を $a_i$ とする。カード $i$ について、このカードを要素に含むカードの集合のうち、合計が $K$ 以上 $K + a_i - 1$ 未満のものが存在するとき、またこのときのみ、カード $i$ は"必要である"とする。この条件を満たさない、すなわち"不必要な"カードの枚数を出力せよ。
- $1 \leqq N \leqq 5000$
- $1 \leqq K \leqq 5000$
- $1 \leqq a_i \leqq 10 ^9 \left( 1 \leqq i \leqq N \right)$
方針
あるカード $i$ が不必要かどうか判定したいとき、そのカード以外のカードからなるの集合のうち、集合の和が $K$ 未満であるようなものを列挙すればよいので、 $O \left( N K \right)$ で可能である
$N$ 枚について判定するには愚直にやって $O \left( N ^2 K \right)$ となるので、間に合わない
ここで、カードがソート済であるものとして、カード $i$ が必要であるならば、カード $j \left( i \lt j \leqq N \right)$ も必要である、という性質から、二分探索によって $O \left( N K \log N \right)$ まで落とすことができ、次に述べる方法では $O \left( N K \right)$ まで落とすことができる:
大きいカードから順に見ていき、部分集合によって $0$ 以上 $K$ 未満の和を作ることができるかどうかを順次更新していく
あるカード $i$ について、それまでに $K - a_i$ 以上 $K$ 未満の和を作ることができていれば、そのカードは必要である
今までに作ることのできた和の最大値を持っておけば、この判定は $O \left( 1 \right)$ である
この操作を行うことにより、いくつかの必要なカードを検出することはできないかもしれないが、必要なカードのうち最も小さいものは必ず検出できるので、結局この問題を $O \left( N K \right)$ で解くことができた
3
D: NarrowRectangles - AtCoder Regular Contest 070
方針(部分点のみ)
DPをする
長方形の幅を $W$ とすると $O \left( N W ^2 \right)$
3/19 (106th)
1
A: 25個の文字列 - AtCoder Beginner Contest 025
3/20 (107th)
1
D: 覚醒ノ高橋君 - AtCoder Regular Contest 009
問題概要
$A$ 個のそれぞれ連結な重み付き無向グラフが与えられる。各グラフの頂点数は $2$ 以上 $7$ 以下である。全てのグラフから全域木になるまで辺を取り除く操作を行う。この操作において、取り除いた辺の重みの和をコストとする。考えられる操作のうち、 $k$ 番目に小さいコストを出力せよ。
- $1 \leqq A \leqq 77$
- $1 \leqq k \leqq 7,777,777$
- 辺の重みは、 $1 \leqq cost \leqq 77$
考察
問題概要は簡略化して書いたが、問題を読んでもらえば分かる通り、まず一つのグラフをいくつかのグラフに分割し、各グラフについて全域木にするためのコストの一覧を計算しなくてはならない
一覧を計算し終えたら、DPで $k$ 番目に小さい和を計算するだけである
総パターン数は、最大で $7 ^5 = 16807$ の $77$ 乗もあるので、 $k$ より大きい適当な数で丸める必要がある
DPの計算量は、辺の重みを $c$ 分割後のグラフの頂点数を $M $ として、 $O \left( A \cdot c M A \cdot c M \right) = O \left( \left( A c M \right) ^2 \right)$ となり、厳しいのでは、と思いきや、C++は思っていたよりもかなり速かったようで、むしろunordered_mapを使うよりも速かった(ハッシュの衝突が発生していたと考えられる)
3/21 (108th)
1
D: サプリメント - AtCoder Beginner Contest 017
問題概要
略
方針
DPっぽいのでDPをする
ある日に $i$ 番目までのサプリメントを摂取し終わるとして、その最終日に摂取する最も番号の小さいサプリメントは何か、ということを考えれば、$i$ 番目までのサプリメントの摂取方法の数が分かる
これは累積和を取ることで $O \left( N \right)$ で計算できる
SegTreeを使えば $O \left( N \log N \right)$ となるが、累積和を取らなくてよいぶん楽になる
3/22 (109th)
1
D: マス目と整数 / Grid and Integers - CODE FESTIVAL 2016 qual A
問題概要
縦 $R$ 行、横 $C$ 列 のマス目があり、そのうち $N$ 箇所のマス目には非負整数が書かれており、具体的にはマス $\left( r_i, c_i \right)$ に $a_i$ が書かれている $\left( 1 \leq i \leq N \right)$ 。このとき、残りのマス目に非負整数を書き込むことによって、隣り合うマス目どうしの差分が全ての行において完全に等しくなるようにできるかどうかを判定せよ。
- $2 \leq R, C \leq 10 ^5$
- $1 \leq N \leq 10 ^5$
- $\left( r_i, c_i \right)$ は全て相異なる。
- $0 \leq a_i \leq 10 ^9$
方針
既に書かれている整数によって差が固定される列番号の集合をUnion-Findによって保持する
事前に各部分集合の差分の情報を示す連結なグラフを作成しておき、DFSを行い、初期状態で矛盾が生じていれば検出する
最後に、各部分集合について、全ての行における最も小さいマスについて、そのマスが埋まっていようがいまいが決定することができるので、負であれば検出する
3/23 (110th)
1
D: 高橋くんの苦悩 - AtCoder Beginner Contest 015
問題概要
$N$ 枚のスクリーンショットがあり、 $i$ 枚目のスクリーンショットは幅 $A_i$ と重要度 $B_i$ を持つ。これらのスクリーンショットを幅の合計 $W$ 以下かつ枚数 $K$ 以下の制限のもとで選択したときの重要度の合計を最大化したい。最大値を出力せよ。
- $1 \leqq W \leqq 10000$
- $1 \leqq N \leqq 50$
- $1 \leqq K \leqq N$
- $1 \leqq A_i \leqq 1000$
- $1 \leqq B_i \leqq 100$
方針
DPをする
$O \left( W N ^2 \right)$
3/24 (111st)
1
D: バレンタインデー - AtCoder Beginner Contest 018
問題概要
略
方針
女子の選び方は高々 $_ {18} C _ 9 = 48620$ 通りで、各選び方について各男子の幸福度を計算し、大きいほうから $Q$ 人を選んだときの合計が、その女子の選び方における幸福度の最大値であるので、全ての選び方について計算すればよい
3/25 (112nd)
1
D: トランプ挿入ソート - AtCoder Beginner Contest 006
方針
要するにLIS(最長増加部分列)を求めればよい
雑記
LISの $O \left( N \log N \right)$ のアルゴリズム、賢すぎませんか
3/26 (113rd)
1
D: 禁止された数字 - AtCoder Beginner Contest 007
方針
余事象を考えて桁ごとに見ていく
雑記
std::string は存在しているだけで重い、それはそう
