AtCoder Beginner Contest #038 (Nim-langの練習帳)
いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library
- A - お茶
末尾がTに等しいかを見るだけ
pythonだとhoge[-1]と書くところをNimではhoge[^1]と書く
- B - ディスプレイ
全部検査すればOK
- C - 単調増加
尺取法
単調増加な部分を求めて、その長さをLとすると、答えにL*(L-1)//2を加えていく
- D - プレゼント
x_i < x_(i+1) かつ y_i < y_(i+1)となる最も長い点列の長さを答える問題。本番では解けなかった。
これは、dp[y_i] := (iまで使ったときの最長の点列) として、dp[y_i] = max{dp[y_j] | x_i < x_j かつ y_i < y_j} + 1 で更新するDPで解けるが、愚直にやるとO(長さ^2)かかるのでダメで、segment treeを使ったDPが必要。詳しい説明は割愛するけども、yの大きい方から調べていくことで、それよりも小さいyのsegment treeの値が0になっていることがポイント。
あと、今回は真に大きいものしか選択できないので、segment treeの更新は高さが同じものを一気に行わないといけない。
もっと楽な方法として、x座標でソートしておくと、y座標の列の最大増加部分列問題に帰着できる。こちらの方がずっと短いし楽。
DみたいなDPは以前codeforcesでも見ていたのに解けなかった
Dの3次元パターンがICPCで出たことがあり(Longest Chain | Aizu Online Judge)、名前のついてない典型テク(skyaozoraの日記 - TopCoder部)らしい。
九州大学プログラミングコンテスト2014 D. 切符分割
研究室のプロコンでQUPC2014を1時間で解こうとしたら、3問しか解けなかった。
問題
D: 切符分割 - 九州大学プログラミングコンテスト2014 | AtCoder
電車の路線図が重み付き無向グラフG=(V, E)としてが与えられる。駅vから駅uまでの距離がd_vuであるとする。このとき駅v-u間の切符の値段は、要素数Kの数列x, fについて、1=x[0] <= d_vu < x[1]ならf[0]円, x[1] <= d_vu < x[2]ならf[1]円, ..., x[K-2] <= d_vu < x[K-1]ならf[K-2]円, x[K-1] <= d_vuならf[K-1]円とする。
このとき、2枚まで切符を使って良いとすると、スタート地点Sからゴール地点Gまで最小何円でたどり着けるか?
制約
2 <= |V| <= 30000
1 <= |E| <= 60000
1 <= K <= 100
x[i] < x[i+1] ならばf[i] < f[i+1]
Codeforces Round #345 Div.2 E / Div.1 C - Table Compression
久し振りにRatedなコンテストに出て、div1で2問なんとか解いたけど、遅かったのでレートは微減した
div1は厳しい
問題
Codeforces Round #345 Div.1 C - Table Compression
要素が全て正のN行M列の行列Aが与えられる。これを各行・列の相対的な大小関係が等しい行列のうち、最大の要素が最小となるような行列A'を求めよ。
ここで行列AとA'の各行の相対的な大小関係が等しいとは、Aの要素a_{i,j}と行が同じ要素a_{i,k}と、それに対応するA'の要素a'_{i,j}とa'_{i,k}について、a_{i,j} < a_{i,k} ならば a'_{i,j} < a'_{i,k}、a_{i,j} = a_{i,k}ならば a'_{i,j} = a'_{i,k}、a_{i,j} > a_{i,k} ならば a'_{i,j} > a'_{i,k} が成立することである。(列に関しても同様)
制約
1<= N*M <= 10^6
1<= a_{i,j} <= 10^9
AOJ2067 Flame of Nucleus
問題
Flame of Nucleus | Aizu Online Judge
頂点数N、枝数Mの重み付き単純無向グラフが与えられる。枝i(i=1, ..., M)の重みD_iは頂点間を移動する日数を表す。
現在の頂点i(i=1, ..., N)に滞在している人数P_iが与えられる。頂点i(i=1, ..., N)にL日後にK_i人以上住んでいる場合、K_i人以外は死ぬとする。
最適に移動した場合、最大何人生き残れるか?
制約
SRM528 div.1 500 SPartition
問題
SRM528 div.1 500 SPartition
偶数長の文字列sが与えられる。ここからsの各文字を、前から順番にX,Yのどちらかに振り分けていったとき、XとYが一致するような振り分け方は何通りか?
制約
SRM659 div.1 250 ApplesAndOrangesEasy
問題
SRM659 div.1 250 ApplesAndOrangesEasy
各要素がリンゴかミカンである、要素数がNの列を考える。ここで、[i, i+K-1]の区間で列に含まれるリンゴの数を個以下に制限することとする。列において、要素が必ずリンゴであるインデックスの情報infoが与えられるので、制限を満たす列でリンゴは最大何個列に含まれうるか?
制約
Codeforces Round #210 Div.2 D / Div.1 B - Levko and Array
練習会に参加して1完だった。
問題
Codeforces Round #210 Div.1 B - Levko and Array
要素数nの数列aが与えられる。数列のうちk個まで値を変更して、を最小にするとき、その値を求めよ。
制約
Codeforces Round #336 Div.2 D / Div.1 B - Zuma
問題
Codeforces Round #336 Div.2 D / Div.1 B - Zuma
長さNの数列cが与えられる。cから回文となっている部分列を除去する操作を行ったとき、最小何回の操作で全て数を除去できるか?
制約
pythonで競技プログラミングをする際に便利な関数とか5選
この記事は Competitive Programming Advent Calendar 2015 の11日目の記事です。*1
昨日は @yuizumi_y5iさんでABC を bash で解いた話 - yuizumi’s diaryでした。