読者です 読者をやめる 読者になる 読者になる

鬱! 鬱すぎてうつほ物語になった!w

主に食べたラーメンについて記録を残すために開設されたブログです。他のことも書くかもしれません。

AtCoder 連続ACチャレンジ 2017/2

競技プログラミング

AtCoderで1日1AC

メモ:2016/12/04スタート

AtCoder Problems

2/01 (60th)

1

D: バスと避けられない運命 - AtCoder Beginner Contest 012 | AtCoder

要するにWarshall-Floydで全頂点対最短経路を求めた後、各頂点から他の頂点への距離の最大値のうち最も小さいものを選べばよい
計算量 { O \left( N ^ 3 \right) }

2/02 (61st)

1

A: カードと兄妹 - AtCoder Regular Contest 038 | AtCoder

自明
計算量 { O \left( N \log N \right) }

2/03 (62nd)

1

B: P-CASカードと高橋君 - AtCoder Regular Contest 005 | AtCoder

適当にシミュレーションすればよい

2/04 (63rd)

AGC010 オンタイム
頭がいい人向けのセットだった

1

A: Addition - AtCoder Grand Contest 010 | AtCoder

簡単

2

B: Boxes - AtCoder Grand Contest 010 | AtCoder

必要条件をドカドカ追加していったら十分条件も満たしていたパターン
そのままでは考えづらいので、石を取り除くのではなく、逆の操作、すなわち1個も石が置かれていない状況から置いていくと考える
まず、数列の総和が1回の操作で追加される個数の倍数になっていない場合 NO
ここで、何回操作が実行されたかが分かる( { M } 回とする)
1回の操作で、 { i } 番目の箱と { i + 1 } 番目の箱の差は { 1 } だけ大きくなる──選択された箱が { i + 1 } 番目でない限りは.
つまり、1回も選ばれなかった箱( { k } 番目とする)には { k - 1 } 番目の箱よりも { M } 個多い石が入っている
そうでない場合、その箱は1回以上選択されたことになり、 { M } との差から、何回選択されたかも分かる
ここで差を { d } としたとき、 { M - d } が5の倍数でない場合 NO
選択された回数の合計が { M } でない場合 NO
以上の条件を全て満たせば YES
計算量 { O \left( N \right) }

2/05 (64th)

1

C: Cleaning - AtCoder Grand Contest 010 | AtCoder

なぜ時間内に通せなかったのか……死罪レベル、木に慣れてなさすぎる
まず次数が2以上の適当な頂点を根として根付き木を構成する
ある頂点を引数とし、その頂点から根へと向かう辺を通る回数を返す関数 { f } を考える
{ i } については明らかに { A_i } が戻り値である
葉でも根でもない頂点 { i } については、子を引数とした { f } の戻り値の集合と { A_i } によって戻り値を計算することができる
このとき、 { A_i } の値によっては答えが NO となる
根についても同様の判定を行う
計算量 { O \left( N \right) }

2/06 (65th)

1

D: Decrementing - AtCoder Grand Contest 010 | AtCoder

解説放送を見た
偶奇の性質に気付けるか、とかいう地頭の良さを問われるので本当にダメ
手番の管理

2/07 (66th)

1

B: アメーバ - AtCoder Regular Contest 041 | AtCoder

範囲外アクセスに注意しながら上から見ていけばいい

2/08 (67th)

1

B: メタ構文変数 - AtCoder Regular Contest 033 | AtCoder

特に難しくない
計算量 { O \left( \left( N_A + N_B \right) \log \left( N_A + N_B \right) \right) }

2/09 (68th)

1

C: 01文字列 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 | AtCoder

0と1が切り替わるところ(先頭と末尾を含む、 { N } 個とする)を起点として、 { N } パターンのコストを比較すればよい
計算量 { O \left( T \right) }

2/10 (69th)

1

D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder

(editorialを見るとものすごく実装が軽い方法が書いてある)
偶数メートルで行き来できる街の集合をUnion-Findで管理する
各集合に、奇数辺が含まれるかどうか(つまり2部グラフでないかどうか)の情報を持たせておく(HasOddとする)
以下のフローチャートを上から辿る

  1. x, yの間に偶数辺が追加される場合
    1. 既に同じグループのとき、変化なし(終了)
    2. x, yの間が奇数辺で接続されているとき、x, yをUniteし、HasOddをTrueにする(終了)
    3. x, yのいずれかのHasOddがTrueのとき
      1. x, yのいずれにも奇数辺で接続された集合が無いとき、Uniteし、Unite後の集合のHasOddをTrueにする(終了)
      2. x, yのいずれかに奇数辺で接続された集合が有るとき、その集合も含めてUniteし、Unite後の集合のHasOddをTrueにする(終了)
    4. x, yのいずれかに奇数辺で接続された集合が有るとき
      1. x, yのいずれにも奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
      2. x, yのいずれか片方にのみ奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
    5. x, yのいずれにも奇数辺で接続された集合が無いとき、普通にUniteする(終了)
  2. x, yの間に奇数辺が追加される場合
    1. 既に同じグループのとき
      1. 奇数辺で接続された集合が有る場合、その集合をUniteする
      2. 集合のHasOddをTrueにする(終了)
    2. x, yの間が奇数辺で接続されているとき、変化なし(終了)
    3. x, yのいずれかのHasOddがTrueのとき
      1. x, yのいずれにも奇数辺で接続された集合が無いとき、Uniteし、Unite後の集合のHasOddをTrueにする(終了)
      2. x, yのいずれかに奇数辺で接続された集合が有るとき、その集合も含めてUniteし、Unite後の集合のHasOddをTrueにする(終了)
    4. x, yのいずれかに奇数辺で接続された集合が有るとき
      1. x, yのいずれにも奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
      2. x, yのいずれか片方にのみ奇数辺で接続された集合が有るとき、適切にUniteし、Unite後の2つの集合を奇数辺で接続する(終了)
    5. x, yのいずれにも奇数辺で接続された集合が無いとき、普通にx, yを奇数辺で接続する(終了)

2/11 (70th)

ABC054 オンタイム

1

A: One Card Poker - AtCoder Beginner Contest 054 | AtCoder

.

2

B: Template Matching - AtCoder Beginner Contest 054 | AtCoder

4重ループでOK
KMP法とやらで { O \left( N ^ 3 \right) }
FFT{ O \left( N ^ 2 \log N \right) }
らしい(解説放送より)

3

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

next_permutation関数を使ってみたかったので使ってみた

4

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

40という数字を見て反射的に半分全列挙を実装したが実は初めてだった
あとDPらしい
半分全列挙: { O \left( 2 ^ \frac{N}{2} N + N ^ 2 Max \left( a_i \right) Max \left( b_i \right) \cdot Max\left( a_i, b_i \right) N / Max \left( M_a, M_b \right) \right) }
DPはやってないので解説放送のメモ
簡単なほうのDP: { O \left( N ^ 3 Max \left( a_i \right) Max \left( b_i \right) \right) }
難しいほうのDP: { O \left( N ^ 2 Max \left( a_i + b_i \right) \right) }

2/12 (71st)

1

C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder

叙述トリック: 「カメがウサギより速いことはないだろう」という無意識な思い込みにより時間を溶かした
Dijkstra法 + 尺取法でOK (尺取しなかったけど)
{ O \left( N M \log N \right) } (想定解っぽいけど結構ギリギリ)

2/13 (72nd)

1

E: Rearranging - AtCoder Grand Contest 010 | AtCoder

※まず解説放送を見る

  1. 入力をsortする
    • 以降の処理はここで確定させたインデックスで行う
  2. gcdが1でない組に辺を張る
    • 辺は隣接リストで管理し、各リストはsortしておく
      • これにより、一貫して昇順で各要素を扱うことができる
  3. 各連結成分について、木を構築する
    • 逐次、最小のノードを辿っていくDFS
    • このとき、各連結成分のうち最小の要素を根として関数を呼ぶ必要があるが、前述のsort済みのデータ構造により、訪問済みでないものを前から順に見ていけばOK
      • 後述の理由のため、根としたものは set<int, greater<int> > に保存しておく
    • 同じ連結成分の要素は、上手い順序で並べることによってそれより辞書順で小さくすることができないような状態にすることができる、ということが重要
  4. 木から最終的な配列を構築する
    • 各ノードについて再帰的に子ノードを引数として関数を呼び、各配列をマージした配列を返すのだが、この配列は以下の要件を満たすもののうち辞書順最大のものでなければならない:
      • 0番目は呼ばれたノードである
      • 各配列の相対的な順序は不変である
  5. 答えを出力する
    • 異なる連結成分どうしは自由にswapできるので、各連結成分に対応する配列を根の要素について降順に出力すればよい

{ O \left( N ^ 2 \right) } だと思うけどpush_back多用してたり再帰してたりするせいか遅い

知見:
この問題のような出力形式はほんの少しだけ面倒だが、行末にスペースが付いていても別に問題ない

2/14 (73rd)

1

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

※まずeditorialを見る

ビットDPをする
うさぎの部分集合があって、これに属する各うさぎがこの部分集合の中で最下位であるときの場合の数をメモ化再帰で求める
{ O \left( 2 ^ N N \right) }

2/15 (74th)

1

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder

※まず解説動画とeditorialを見る

Union-Findを使えないか考えて上手くやって使う
(およそ) { O \left( \left( M + Q \right) \alpha \left( N \right) \right) }

2/16 (75th)

1

D: 三角形の分類 - AtCoder Beginner Contest 033 | AtCoder

※まずeditorialを見る

固定した点からの偏角を列挙するとき、前後1周分、合計 { 6 \pi } の大きさの区間が必要 (前後0.5周、合計 { 4 \pi } で十分かと思うがバグ取りできなかった)
誤差吸収は必要
上記の提出は高速化のための再提出5回目のもので、二分探索→尺取法のオーダー改善(全体では定数倍改善に留まる)はいいとして、 push_backの順番を変えて3周分の偏角のsortを削除したらかなり速くなった:
L.65〜69 → L.65~73
今回のように、sortが支配的になってしまうような場合は考える価値がある
コード量の割にメモリを使っていないらしいのでまだまだ高速化できそう
{ O \left( N ^ 2 \log N \right) }

2/17 (76th)

1

D: 破れた宿題 - AtCoder Regular Contest 007 | AtCoder

分からなかったし解説が無かったのでググった 頭がいい人向け
初項が即決定でき、あとは意外と多い場合分けを淡々と書いていくと通せる
こういう数値と文字列の相互変換が多かったり、数値の桁数が不明な問題はPython使うのが手っ取り早いと思う
25行目、これでOKなのは、初項が2桁以上であるならば、必ず10の倍数であるという事実による
(主にPythonを使ったために)計算量はよく分からないが { O \left( N \right) }{ O \left( N ^ 2 \right) }

2/18 (77th)

ARC069 オンタイム
競プロ引退

1

C: Scc Puzzle - AtCoder Regular Contest 069 | AtCoder

Sをなるべく多く使う

2

D: Menagerie - AtCoder Regular Contest 069 | AtCoder

4通り試す

2/19 (78th)

1

E: Frequency - AtCoder Regular Contest 069 | AtCoder

前から狭義単調増加な部分だけ拾ってリストアップしておく
次に後ろから見ていってリストのどこに属すべきか計算する
{ O \left( N \log N \right) }

2/20 (79th)

1

A: 掛け算の最大値 - AtCoder Beginner Contest 026 | AtCoder

Go言語の練習

2/21 (80th)

1

B: N重丸 - AtCoder Beginner Contest 026 | AtCoder

Go言語の練習

Divide by Zero 2017 and Codeforces Round #399 (Div. 1 + Div. 2, combined)

4問提出 ゼ ロ 点

rating
1603 -> 1461 (-142) (Became Specialist)

A

Problem - A - Codeforces

慢心した コーナーケース考えてなかった

B

Problem - B - Codeforces

慢心した コーナーケース考えてなかった

C

Problem - C - Codeforces

80分くらい着席してたと思う
適当に書いて出したらpretestは通った(今回pretestガバガバだったらしい)
周期を持つっぽいが計算量とか正当性とか本当にこれでいいのか分からんし未だ解けた気がしない

D

Problem - D - Codeforces

よく考えると簡単なDPなのでわ?w っつって意気揚々と出したのだが問題文の謎の { \epsilon } に惑わされた

2/22 (81st)

1

D: あまり - AtCoder Regular Contest 042 | AtCoder

愚直な計算を実行するならば、計算量は { O \left( \log A + \left( B - A \right) \right) } となる
また { X = 1 } または { A = 0 } または { P - 1 \leq B - A + 1 } の場合も自明
よって { X \geq 2 } かつ { A \geq 1 } かつ { \left( B - A \right) \gg 10 ^ 8 } かつ { P > 2 \times \left( B - A \right) } のとき、ある種の工夫が必要となる
解を { P }{ B - A } の比から推定し(解説スライド)、推定した解が { B - A }区間を平方分割した区間のいずれかに属しているかどうかを、 推定した解に { X ^ {-1} \pmod P }{ \sqrt { B - A } } 回掛けることで判定する
このときの計算量は推定する解の個数を { M } として、 { O \left( \sqrt { B - A } _ { \left( 1 \right) } \log \sqrt { B - A } _ { \left( 1 \right) } + M \sqrt { B - A } _ { \left( 2 \right) } \log \sqrt { B - A } _ { \left( 1 \right) } \right) }
ただし、(1)が付されているのは区間の個数、(2)が付されているのは区間の幅である
第1項は区間の区切れ目を計算しsortする時間、第2項は実際にその近傍の区間に推定した解が存在するかどうかを確認する時間であり、 他に { X ^ {-1} \pmod P } などを前もって計算しておく必要がある
しかし今回、テストケースが弱すぎるのでこのようなアルゴリズムは必要なかった

2/23 (82nd)

1

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

頂点の集合をUnion-Findで管理しておいて、各連結成分に存在する辺の個数を適当な方法で数えればOK

ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined)

4完 / 7問

rating
1461 -> 1615 (+154) (Became Expert)

Publish Rating Change - Codeforces

A

Problem - A - Codeforces
Submission #24919305 - Codeforces

シミュレーション

B

Problem - B - Codeforces
Submission #24923123 - Codeforces

素数を1で塗って合成数を2で塗る
コーナーケースに気をつける

C

Problem - C - Codeforces
Submission #24940185 - Codeforces

{ k } の累乗を絶対値 { 10 ^ {14} } 程度まで計算しておき、与えられた { a _ i } の累積和を計算しておく
あとは後ろから、順次累積和をキーとする要素をmapに追加していき、区間の始まりを固定し、 検索すべき累乗から固定された区間の始まりに対応する累積和(offset)を足した値をキーとしてmapで検索し、個数を数える(分かりづらい)
{ O \left( n \log \left( Max \left( a _ i \right) n \right) \right) } (検索がlogオーダーの場合)

知見:
mapでOKだったものをunordered_mapにすると衝突して遅くなる場合がある(まあそれはそう)

D

Problem - D - Codeforces
Submission #24934995 - Codeforces

各スイッチを頂点とし、いずれかの照明に共有されているスイッチ同士を辺で接続したグラフを構成した
初めに照明がONである場合はグラフの重みは1、そうでなければ0として、 スイッチが押されるか否かで分類される2部グラフであるかの判定をDFSで行った
(AtCoder偶数メートル思い出した)
これは充足可能性問題の特殊なケースである2-SATと呼ばれる問題で、蟻本にも載っているらしい
参考:
充足可能性問題 - Wikipedia
2-SATと強連結成分分解 - naoya_t@hatenablog

(ライブラリを書く) (蟻本をやる)

2/24 (83rd)

1

C: 飛行機乗り - AtCoder Beginner Contest 030 | AtCoder

普通にシミュレーションすればOK
{ O \left( N \log N + M \log M \right) }
尺取すれば{ O \left( N + M \right) }

2/25 (84th)

Mujin Programming Challenge 2017 オンタイム

1

A: Robot Racing - Mujin Programming Challenge 2017 | AtCoder

よく考えると簡単な問題で、前から順に"詰まっている"ところを見ていけばOK
具体的には、奇数番目に必ずロボットが存在しているように、基本は一つ空けで左詰めする処理をしてから、偶数番目に存在しているところを見ていく
{ O \left( N \right) }

2

B: Row to Column - Mujin Programming Challenge 2017 | AtCoder

個人的にAより簡単な問題で、普通に盤面を埋めようと考えれば自然に解ける
ただしちょっと注意が必要なケースがあって、盤面に一つも黒が存在しないケースと、目的の列に初めに一つも黒が存在しないケースは考慮する
シミュレーションしても時間的に余裕だったがたぶん必要ない
{ O \left( N ^ 2 \right) }

2/26 (85th)

Codeforces Round #402 (Div. 2)

4完 / 6問 今回は惜しかった……

rating
1615 -> 1644 (+29) (Became Expert)

A

Problem - A - Codeforces
Submission #25033372 - Codeforces

やるだけ

B

Problem - B - Codeforces
Submission #25034720 - Codeforces

英語をよく読む(必ず解が存在するって書いてある)

C

Problem - C - Codeforces
Submission #25036357 - Codeforces

全て後で買うと仮定して、最低でも { k } 個は今買わなければいけないので差額をsortして、k個は必ず今買い、または差額が負であればk個を超えても今買う

D

Problem - D - Codeforces
Submission #25049077 - Codeforces

クッソくだらないミスで落とした
二分探索
{ O \left( | t | \log | t | \right) }

E

Problem - E - Codeforces
Submission #25046561 - Codeforces

実装ゲー
アルゴリズムとしては1ビットずつ見ていけばいいだけ 特に落とし穴もない
(だいたい) { O \left( nm \right) }

1

A: A - AtCoder Beginner Contest 013 | AtCoder

気付いたら23:59だったので

2/27 (86th)

1

C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

正直まだよく分からない 特に逆変換
まず複素数が絡む時点でやばい、あとすごい誤差が大きくなって最終的に小数点以下を四捨五入した
計算量はたぶん { O \left( N \log N \right) }

2/28 (87th)

1

B: 名前の確認 - AtCoder Beginner Contest 011 | AtCoder

Go言語の練習