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

n-knuu's logs

憧れ駆動。だいたい競プロ

CODE FESTIVAL 2016 Elimination Tournament Round 1 B. 数字列をカンマで分ける問題

AtCoder Suffix Array 二分探索
続きを読む

AtCoder Beginner Contest 009 D. 漸化式

AtCoder きたまさ法 線形漸化式
続きを読む

AtCoder Beginner Contest 004 D. マーブル

AtCoder 最小費用流

最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した

続きを読む

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C. アメージングな文字列は、きみが作る!

Suffix Array AtCoder

Suffix Arrayのライブラリ整備のために解いた

続きを読む

京都大学プログラミングコンテスト 2016 E. 柵

AtCoder 最小カット
続きを読む

天下一プログラマーコンテスト2015予選A C. 天下一美術館

二部マッチング AtCoder
続きを読む

AOJ2594 Reverse Roads

AOJ 最大フロー
続きを読む

AtCoder Beginner Contest 010 D. 浮気予防

グラフ 最小カット AtCoder
続きを読む

AOJ2328 Mobile Network

最大フロー AOJ

Mobile Network | Aizu Online Judge

問題

無向フローが与えられるので頂点1からNへの最大フローを求めよ。
ただし、枝の重みがxの多項式で与えられるものとする。

制約

2 <= 頂点数 <= 50
0 <= 枝数 <= 500
多項式の次数 <= 50
0 <= 係数 <= 100 (ただし係数が0の項は与えられる多項式に含まれない)

続きを読む

yukicoder No.177 制作進行の宮森あおいです!

最大フロー yukicoder

8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。

続きを読む

SRM696 div.1 300 Gperm

bitDP topcoder

寝坊したので出れなかった。

問題

50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけコストを支払う。支払うコストの合計が最小になるような順番で頂点を塗りつぶしたときのコストを求めよ。

制約

1 <= M <= 20

続きを読む

Codeforces Round #367 (div. 2)

二分探索 codeforces

Codeforces Round #367 (div. 2)に参加した。
officialだと230位くらいでレートが下がりそうな順位だった。

A. Beru-taxi

  • 問題

タクシーiが(x_i, y_i)にいて、速度v_i(1 <= i <= N)で走ることができる。(a, b)に向かってまっすぐ走ったとき、(a, b)に最も速く着くタクシーの着く時間を求めよ。

  • 解法

距離/速度を計算するだけ

  • 計算量

O(N)

  • コード


B. Interesting drink

  • 問題

N個の商品が与えられ、その値段がx_1, x_2, ..., x_Nであるとする。これに対して、Q個の金額m_1, ..., m_Qが与えられるので、各m_iで買える商品の種類数を答えよ。

  • 解法

数列をソートすると、m_i で upper bound を取ったときのインデックスが答えとなる。

  • 計算量

O((N+Q)logN)

  • コード


C. Hard problem

  • 問題

N個の文字列が与えられ、各文字列を逆順にするためのコストc_iが与えられる。幾つかの文字列を逆順にして、文字列を先頭から辞書順になるようにするとき、逆順にするコストの合計を最小化せよ。どのように逆順にしても辞書順にならない場合は-1を出力せよ。

  • 制約

2 <= N <= 10^5
0 <= c_i <= 10^9
文字列の長さの合計 <= 10^5

  • 解法

DP。dp[i][j] := (i-1番目までを辞書順にして、i番目が(j=0→逆順にしない/j=1→逆順にする)場合の最小のコスト)とおくと、
dp[i+1][0] = min(dp[i][0], dp[i][1]) (if (i番目の文字列) < (i+1の文字列) かつ (i番目の逆順の文字列) < (i+1番目の文字列))
dp[i+1][1] = min(dp[i][0], dp[i][1]) + 逆順にするコスト (if (i番目の文字列) < (i+1の逆順の文字列) かつ (i番目の逆順の文字列) < (i+1番目の逆順の文字列))
とする(片方しか逆順になっていない場合はそちらだけで更新する。詳しくはコードを参照)

  • 計算量

O(N+sum(文字列の長さ))

  • コード


D. Vasiliy's Multiset

  • 問題

初め、multisetには0が1つ入っている。これに対して、1. xをmultisetに追加する、2. xをmultisetから削除する、3. xとmultisetの要素yの中で、x^yが最大になるものを出力する、という3種類のクエリがQ個与えられるので処理せよ。

  • 解法

xとXORを取ったときに、上位bitを立てるようなものがmultisetに入っている場合は、下位ビットがどうなろうとそれを取った方がいいということが分かる。
よって、上位からビットを立てるか決めていく二分探索を行う。

0. left = 0, right = INFとする
1. for i in 30 to 0 do
1.1 multisetに対して、mid=left + 2^iのlower boundを求める
1.2 xのiビットが0の場合、mid以上の値がmultisetにある場合は、iビット目を立てることができるので、left = midとする。もしない場合は、right = midとする。
1.3 xのiビットが1の場合、midより小さくなる値がmultisetにある場合は、iビット目を立てることができるので、right = midとする。もしない場合はleft = midとする。
2 答えをx xor leftとする

  • 制約

1 <= Q <= 2×10^5
1 <= x <= 10^9

  • 計算量

O(QlogQlogx)

  • コード


感想

Dはもっと複雑なことをしないといけないと思って詰まっていたのがダメだった。
想定解はTrieを使うらしい。

技術室奥プログラミングコンテスト#2 D - エンブレム(Emblem)

数学 AtCoder

問題: D: エンブレム(Emblem) - 技術室奥プログラミングコンテスト#2 | AtCoder
解説: http://www.slideshare.net/maroonrk/ss-64770318

続きを読む

AtCoder Beginner Contest #041 (Nim-langの練習帳)

bitDP AtCoder

いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library

abc041.contest.atcoder.jp

A - 添字

echo(s[i-1])

B - 直方体

A*Bしたあとに一度modを取らないと1<<63を超えるので注意(pythonで解こう!)
A*B mod 10^9+7 * C mod 10^9+7

C - 背の順

(高さ, 出席番号)でソートして高さの降順に出席番号を出す。
出力するものが多すぎて、codeforcesだとprintfを使わないとTLEする問題。

D - 徒競走

bitDP
dp[state] := (stateの1が立っているところを既にゴールしたうさぎとしたときの、うさぎの着順の組合せ)
とすると、うさぎvがまだゴールしていない、かつ、vより先にゴールするべきうさぎが全てゴールしている場合、dp[state | v] += dp[state]とできる。

制約から解法を思いつくタイプの問題。

SnackDown 2016 Online Elimination Round

codechef

SnackDown 2016 Online Elimination Roundにe-monさんと出た
361位でTシャツラインにあと61位届かなかった

VCake

  • 解法

制約から、切るのは2回だけなので、切り方は2回に対して[縦に切る, 横に切る]の2通りあるから、計4通りある。
また、どの大きさのケーキから切り出して行くかで、3!=6通りあるので、4*6=24通りについて全て調べていけばよい。

  • コード


Chocolates for Everyone

  • 問題

初項と公差が正の整数で、等差数列のN項の和がCになるような列について、初項と公差を1つ答えよ
もしなければNoと出力せよ

  • 解法

等差数列の初項をa0, 公差をdとおくと、等差数列の和の公式より、N*(2*a0 + (N-1)*d)/2 = Cが成り立つ
よってまず、2*C%N=0が必要となる
式を整理すると、2*a0 = 2*C/N - (N-1)*d
左辺が偶数でないとダメなので、dを2*C/Nと(N-1)の偶奇によって場合分けして考える

  1. 2*C/Nと(N-1)がともに偶数、もしくは奇数のとき
    • dは何であっても右辺は偶数になる
    • ここでa0が正の整数になるためには、dはできるだけ小さい正の整数であったほうがよい
    • よって、d=1として、a0が正になるか計算すれば良い
  2. 2*C/Nが偶数、(N-1)が奇数のとき
    • 右辺が偶数になるには、(N-1)*dが偶数でないといけないので、dは偶数
    • (i)の場合と同様、dはできるだけ小さい正の整数であったほうがよいので、d=2として、a0が正になるか計算する
  3. 2*C/Nが奇数、(N-1)が偶数のとき
    • 右辺は偶数にならないので、条件を満たす等差数列は存在しない
  • コード

Coloring A Tree

  • 問題

N頂点の木が与えられ、木の各頂点をK色塗ることを考える
同じ色を塗ったあとの木を、違う色が接続している枝で切断したときに、同じ色の頂点が全て連結になるような塗り方は何通りあるか

  • 解法

切断の仕方と、切断してできたグループの色塗り方を考えるだけでよい(入力が木なので、切断する枝が決まれば、切断後のグループが一意に決まる)
よって、i種類の色を使うときは、N-1の枝からi-1本選んで切断し、K種類からi個の色を塗るので、このときの場合の数は(N-1) C (i-1) * K P i 通りであり、これを、i=1からi=min(N, K)まで和をとれば良い

  • コード


感想と反省

  • チーム戦難しい
    • チームメイトに問題を任せる判断とか、問題概要の伝え方とか
  • 問題概要を伝えるのが苦手っぽい
    • わかりやすくなるように、と思ってやってはいるものの、いくつか抜け落ちたりしていることがあった
    • e-monさんに聞いた問題は自分で殆ど読まずに解いてたし、なんとか上手く伝えられないか考えたい
      • そのためにブログ書いてるはずなんだけど、おざなりになったりすることもあるし、かといって時間かけすぎるのも厳しいし、なんとも...