n-knuu's logs

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

AtCoder Regular Contest 075 E. Meaningful Mean

以下のことを考えて、やっぱり解説を書くことにした

  • 復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき
    • 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重要だと思う
  • どうせnim-langで解いているからコード貼ってもわからないでしょ、みたいなのが解説を書かない言い訳になっている状況は良くない
続きを読む

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

続きを読む

AtCoder Beginner Contest 009 D. 漸化式

続きを読む

AtCoder Beginner Contest 004 D. マーブル

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

続きを読む

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

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

続きを読む

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

続きを読む

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

続きを読む

AOJ2594 Reverse Roads

続きを読む

AtCoder Beginner Contest 010 D. 浮気予防

続きを読む

AOJ2328 Mobile Network

Mobile Network | Aizu Online Judge

問題

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

制約

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

続きを読む

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

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

続きを読む

SRM696 div.1 300 Gperm

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

問題

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

制約

1 <= M <= 20

続きを読む

Codeforces Round #367 (div. 2)

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)

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

続きを読む

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

いつも通り、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]とできる。

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