足跡-sokuseki-

りかの日進月歩の記録

ABC065/ARC076 D Built?

D - Built?

問題概要

 N 個の街があり、  i 番目の街は座標  ( x_i , y_i ) にある。
座標  (a, b) にある街と座標  (c, d) にある街の間に道をつくるのに、コストが  min(|a-c|, |b-d|) 円かかる。
任意の2つの街の間を道を通って行き来できるようにするための最低コストを求めよ。

制約
 1 \le N \le 10^5
 0 \le x_i, y_i \le 10^9

解法

3つの街が  (a, b), (c, d), (e, f) にあるとする。
 a < c < e かつ  b < d < f のとき、 (a, b)  (c, d) の間、 (c, d)  (e, f) の間の2つの道を作るならば、  ( a, b)  (e, f) の間に道を作る必要はない。
このことから、 x 座標または  y 座標が最も近い街同士だけの辺を考えれば良いことがわかる。

また、任意の2つの街を行き来できるというのは、街を頂点、道を辺としたグラフが連結であり、連結グラフの辺のコストを最小化するのは、グラフの最小全域木を構成するということになる。

よって解法は

  •  x 座標でソートして隣り合う街に辺をはる
  •  y 座標でソートして隣り合う街に辺をはる
  • 最小全域木を求め、コストを出力する

辺は高々  2(N-1) 本しかないので、計算量は  O(NlogN) になる。

Submission #1994769 - AtCoder Regular Contest 076

CODE FESTIVAL 2017 Final B Palindrome-phobia

B - Palindrome-phobia

問題概要


'a', 'b', 'c' の3種類の文字からなる文字列  S が与えられる。
文字列  S を自由に並び替えて、部分文字列に2文字以上の回文を含まないようにできるかどうか判定せよ。

制約
 1 \le |S| \le 10^5

解法

2文字以上の回文が含まれないとき、並べ替えた文字列は
…abcabcabc…
または
…acbacbacb…
のどちらかになる。
なので、各文字が含まれる個数を計算し、最も多く含まれる文字の文字数と最も少なく含まれる文字の文字数の差が1以下であるかを調べればよい。


Submission #1992543 - CODE FESTIVAL 2017 Final (Parallel)

DDCC2016 予選 C ロト2

C - ロト2


問題概要

 N 個の整数があり、  i 番目の整数は  A_i である。

 A_i \times A_j  K の倍数となるような  i  j の組み合わせ  ( i , j ) が何通りあるか求めよ。

制約
 2 \le N \le 200000
 1 \le A_i \le 10^9
 1 \le K \le 10^9

解法

積が  K の倍数になればいいのだから、 それぞれの  A_i において必要な情報は、  K の約数のうちどれが含まれているか。
よって、それぞれの  A_i について、  gcd(A_i , K) を求める。
あとはそれらを2つかけて  K の倍数にできるかを判定して数え上げればいい。

ってことまで自力で思いついて、具体的な方法が思い浮かばなかった。ので解説を見た。

 1 \le K \le 10^9 だから、  K の約数の個数は高々1500個くらいらしい。よって、連想配列か何かに  gcd(A_i , K) を記録していって、2重ループで全探索すれば良い。

連想配列は滅多に使わないので、範囲forというものを初めて知った。
範囲for文 - cpprefjp C++日本語リファレンス



Submission #1988558 - AtCoder Grand Contest 013

AGC013 Hamiltonish Path

B - Hamiltonish Path


問題概要

 N 頂点  M 辺の、連結な単純無向グラフが与えられる。 頂点には  1 から  N までの番号がついており、辺には  1 から  M までの番号がついている。 辺  i は、頂点  A_i と頂点  B
_i を結んでいる。 次の条件を満たすパスを  1 つ見つけて出力する(あり得る答えのうちどれを出力しても良い)。

  • 2個以上の頂点を通る
  • 同じ頂点を2度以上通らない
  • パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

制約
 2 \le N \le 10^5
 1 \le M \le 10^5
 1 \le A_i < B_i \le N

解法

条件3の「パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる」が具体的にどういうことかについて考えてみる。
パスの少なくとも一方の端点と直接辺で結ばれている頂点がパスに含まれていないという状態は、パスの端点からその頂点に対して、パスを伸ばすことができるということを意味する。つまり、条件3が言いたいことは、あるパスがあったときに、条件2を満たした上で、そのパスをできるだけ長く伸ばしたものを出力しないといけないということ。

よって解法の方針は

  • 好きな頂点を選んで、そこから辿れる頂点をパスに含まれる頂点として配列などに入れておき、辿れなくなったら順に出力する

となる。
計算量は、各頂点についてパスの端点として追加される回数が高々1回であり、端点から辺で結ばれている頂点がパスに含まれているかを調べるので、  O(N+M)

Submission #1988558 - AtCoder Grand Contest 013

ABC080 D Recording

D - Recording

問題概要

 N 個のテレビ番組を録画したい。
テレビが受信できるチャンネルが  C 個あり、1から  C までの番号がついている。
録画したいテレビ番組のうち、  i 個目のテレビ番組は、時刻  s_i から時刻  t_i までチャンネル  c_i で放送される(時刻  s_i を含み時刻  t_i を含まない)。同じチャンネルで複数のテレビ番組が同時に放送されることはない。
また、録画機は、あるチャンネルの時刻  S から時刻  T までを録画するとき、時刻  S − 0.5 から時刻  T までの間、他のチャンネルの録画に使うことができない(ただし時刻  S − 0.5 を含み時刻  T を含まない)。
必要な録画機の最小個数を求めよ。

制約
 1 \le N \le 10^5
 1 \le C \le 30
 1 \le s_i < t_i \le 10^5
 1 \le c_i \le C

解法

はじめは  C  c_i を無視してimos法したら解けるんじゃないかと思ったけど、2ケースWA。

いろいろ考えてるうちに、
2 1
1 2 1
2 3 1
のケースでダメなことがわかる。
この例でいくと、時刻1から時刻3までを録画したいから、時刻0.5から時刻3までを1つの録画機で録画したいけど、「時刻0.5から時刻2」「時刻1.5から時刻3」の2つを録画することになって、2個の録画機が必要という答えが出てしまう。
つまりチャンネルの情報は不要じゃなかった。

ということで、
v[  i ][  j ] := チャンネル  i で時刻  j に録画機を使う
という配列を作って、各チャンネルでimos法をする。
このときは、開始時刻を  S - 0.5 ではなく  S と考えてimos法をして、あとから録画開始時刻を1だけ早める(これで、同じチャンネルで連続して録画するときに重複をなくせる)。

あとは各時刻について、いくつのチャンネルで録画機が必要かを計算する。
計算量は  O(NC)


Submission #1986276 - AtCoder Beginner Contest 080

ABC076 D AtCoder Express

小数きらい

D - AtCoder Express

問題概要

次のような列車を運行する。

  • 走行開始時と走行終了時には列車は止まっていなければならない。
  • 列車の走行時間は  t_1 + t_2 + … + t_N 秒である。
  • 最初の  t_1 秒間は列車は速度  v_1 m/s 以内で走行しなければならない。また次の  t_2 秒間は列車は速度  v_2 m/s 以内で走行しなければならない。次の  t_3 秒間、またそれ以降も同様である。
  • 最後の  t_N 秒間は列車は速度  v_N  m/s 以内で走行しなければならない。
  • 列車の性能上、加速度は  \pm 1  m/s^2 以内でなければならない。

このとき、列車が発車してから停車するまでに走れる最大の距離を求める。

制約
 1 \le N \le 100
 1 \le t_i \le 200
 1 \le v_i \le 100

解法

  • 累積和をとって、発車時刻を0としたときの各区間の最初の時刻と最後の時刻を求めておく
  • 各時刻における最大速度を計算する(速度が大きいほど走行距離が長くなるので)
  • 総和を計算して出力する

各時刻における最大速度を計算するのが面倒で、

  • 「速度は  1 m/s ずつしか増やせないけど、速度を落とすのは一瞬」というルールでの各時刻における最大速度
  • 「速度を落とすのは  1 m/s ずつだけど、速度を上げるのは一瞬」というルールでの各時刻における最大速度

を計算し、minをとればよい。


また、入力例4からわかるとおり、1秒きざみではうまくいかないので、最大速度を0.5秒きざみで考える必要がある。

Submission #1982561 - AtCoder Beginner Contest 076

AGC018 A Getting Difference

数学的な問題ほど解けないの、どうすればいいんでしょう…?
(解説を読んだ後、フォロワーさんたちにもいろいろ教えていただいた)

A - Getting Difference

問題概要

箱に  N 個のボールが入っていて、  i 番目のボールには整数  A_i が書かれている。
「箱から2つのボールを取り出し、その2つのボールに書かれている整数の差の絶対値を書いた新しいボールとともに箱に戻す」という操作を好きな回数行うことができる。
整数  K が書かれたボールが、箱の中に入っている状態にできるかどうかを判定する。

制約
 1 \le N \le 10^5
 1 \le A_i \le 10^9
 1 \le K \le 10^9

解法

(自分が理解したとおりに書いているので冗長でわかりにくいかも)

 M = max \{ A_i \} とする。

 M < K のときは不可能であることは明らかなので、  K \le M の場合を考える 。

 G = gcd \{ A_i \} とする。

 M  A_i のうちのどれかなので、 M  G の倍数である。

 K  G の倍数ならば、 M から  G を繰り返し引けば、かならず  K ができるので、 G が書かれたボールを作れればよい。

 G が書かれたボールがどんなときでも作れるのは互除法の考え方からわかる*1


また、 K  G の倍数でないなら、 K の書かれたボールはつくることはできない(  A_i はすべて  G の倍数であり、  G の倍数同士の差は必ず  G の倍数になる) 。



よって、この問題は

  •  K  A_i の最大値以下であるか
  •  K  A_i のgcdで割り切れるか

の2点を確かめさえすれば良い

Submission #1967366 - AtCoder Grand Contest 018

*1:2つの整数  x, y ( x > y とする) の差を繰り返し計算していくと、整数  x \% y ( = r )(  x  y で割ったあまり ) を作ることができる。つぎに  y, r の差を繰り返し計算していくと、整数  y \% r を作ることができる。これらの操作はユークリッドの互除法と同じで、最終的には  x, y のgcdを求めることができる。 N 個の整数のgcdを求める操作は2個の整数のgcdを求める操作の繰り返しでできるので、この問題で与えられた操作を使って、 A_i のgcdが書かれたボールを作ることができる