2017年振り返りと2018年の抱負

2017の抱負と結果

  • SRMで黄になる → LongContestで二桁安定 (30%)

Topcoderがアレなので途中で変更した抱負。二桁順位は30%くらいの確率なので達成率も30%。

  • 熱で寝込まない (100%)

風邪は引いても寝込んではいない。すばらしい成果。

  • ちゃんと寝る (20%)

連続で5時間睡眠を何度かやってしまった。



2018年の抱負

  • 一日7時間睡眠

いいかげん睡眠不足になっていい歳じゃない

  • 年収+15%

去年は+8%だったのでかなりアグレッシブ

  • 低レイヤ分野でレジュメにかけるレベルのアウトプットを何か

具体的には30日OS本と熱血アセンブラ本



プロコンはちょっと控えめにする予定。

HackerRank Week of Code 35 参加日記

1044位/9458人の酷い結果。以下、易問は省略。


3D Surface Area

HxWの平面上の各セル上に、立方体がいくつか積み重なっている。外部に面している面積を求めよ。

X面からみた面積、Y面からみた面積、Z面からみた面積をそれぞれ求めて足せば良い。
https://www.hackerrank.com/contests/w35/challenges/3d-surface-area/submissions/code/1304126485


Matrix Land

n行m列のマトリックスがあり、各セルには点数が設定されている。1行目の任意のセルから、n行目の任意のセルまで移動したとき、得られる合計得点の最大値を求めよ。ただし、セルの点数は通過後にゼロになる。また、セルからの移動は左右と下のみ可能である。
1 <= n x m <= 4 * 10^6

3日考えて解けなかったDPの問題。これは悔しい。
移動制約により、ある点に到着するルートは2通りしかない。
f:id:yambe2002:20171122071240p:plain
パターン1:ある点より左いずれかに降りてきて、点を通過して右から戻ってくる(通過しない場合も含む)
パターン2:ある点より右いずれかに降りてきて、点を通過して左から戻ってくる(通過しない場合も含む)
パターン1だけ考えてみる。
f:id:yambe2002:20171122071615p:plain
上の矢印で表されるのは、「その行だけを考えたときの、(x, y)より右の合計最大値」であり、
msr[x, y] = Max(msr[x, y + 1] + A[x, y], 0)
と表すことができる。
f:id:yambe2002:20171122071605p:plain
上の矢印で表される部分をmslit[x, y]と定義すると
mslit[x, y] = Max(mslit[x, y-1] + A[x, y], dp[x - 1, y] + A[x, y] + msr[x, y + 1])
と表すことができる(dp[x,y]は点(x,y)に来るルートの最大点)。
この合計値を求めて、最大のものを解答すればよい。パターン2も同様。

Codechef November Challenge 2017 参加日記

143位/8136人で目標の2桁順位は達成できず。回答人数の多いCSUBQで部分点だったのが痛かった。以下、易問は省略する。


Periodic Palindrome Construction

長さNの文字列Sについて、Nが整数Pの倍数であり、かつSをPごとに分割したときすべてのP[i]が一致しているものを、周期がPである、と定義する。NとPが与えられたとき、文字aとbのみを使って、周期がPかつ全体で回文になる、長さNの文字列を作れ。ただし、文字列にはaとbの両方を使う必要がある。
1 <= P, N <= 10^5

UnionFindを使う。最終的な文字列をSとすると、全体で回文なので、
S[0] = S[len-1]
S[1] = S[len-2]...
とグループ化できる。
また、各分割文字列A,B...について
A[0] = B[0] ...
A[1] = B[1] ...
とグループ化できる。
全ての文字が同一グループになってしまったらImpossible、そうでないならグループごと適当にabを当てはめればよい。
https://www.codechef.com/viewsolution/16049370


Chef Hates Palindromes

アルファベットの最初のA文字のみを使い、長さNの文字列Sを作成せよ。このとき、最長の回文部分文字列をなるべく短くせよ。
1 <= N <= 10^5

まず明らかな観察として、A=1のときはaのみの文字列を返すしかなく、A>=3ならabcabcabc...を返せばよいことがわかる。よって、A=2の場合のみ考えればよい。
なるべく部分的な回文を短くしたいので、Nがある程度大きいなら
a|ab|b|ab|a|ab|...
のように構築すれば、最長の回文文字は長さ4になって最小となる。
("ab"で囲んでしまえば、その内部にある文字を中心とした回文は、それ以上大きくは作れないので)
Nが小さい(<=8)場合の回答はすべて列挙してしまうのが早い。
https://www.codechef.com/viewsolution/16058582


Chef and Intersection Line

チャレンジ問題。整数の配列A[M][N][N]が与えられる。このとき、二次平面上の点P[1],P[2],P[3],...P[M]を回答せよ。ただし
・P[i] - P[i - 1]の線は、それ以前のいずれの線とも交差してはならない(隣の線と一点でのみ一致する)
・k番目の点に(i, j)ついて、得点A[i][j][k]が加算される
・合計点をなるべく多くするのが目標
N = 50
1 <= A[k][i][j] <= 100
M = 50のテストセットと、M = 500のテストセットがある
制限時間は2.5秒
(テストケースの生成ロジックは省略)

以下の方針で90点程度の結果だった。
・有効解を貪欲的に作成する(点数はあまり気にしない)
・ランダムに点を選んで山登り
・次の点は、M=50のセットでは盤面のほぼすべてから、M=500は狭いので上下3ポイント以内くらいから選ぶ
盤面が100x100しかないので、M=500はかなり狭くあまり改善の余地がなかったように思う。
https://www.codechef.com/viewsolution/16235791


Chef and Subarray Queries

長さNの整数列Aと、整数L、Rが与えられる。Aの初期値はすべてゼロである。次のクエリに答えよ。
・タイプ1:A[x]をyに更新する
・タイプ2:Aの範囲[l, r]にあるサブ配列すべてにおいて、最大値がL以上R以下となるものの数を出力
1 <= N <= Q <= 5 * 10^5
1 <= L <= R <= 10^9
1 <= x <= N
1 <= y <= 10^9

本番では平方分割と二分探索を駆使して52ptの部分点だった。想定解はセグメント木を使う。以下の解説がわかりやすかった。
hamayanhamayan.hatenablog.jp
セグメント木のノードごとに
・Count: 対応する要素数
・Answer:ノード単体での解答
・MinLeft/MinRight:ノード左(右)端に続く、連続するL未満の数の数
・MaxLeft/MaxRight:ノード左(右)端に続く、連続するR以下の数の数
の情報を持つ。すると、Answerは以下のように計算できる。

cur.Answer = left.Answer + right.Answer;
cur.Answer += left.Max_Right * right.Max_Left;
cur.Answer -= left.Min_Right * right.Min_Left;

MaxLeft/MaxRightを「連続するL以上R以下の数」にすると計算が面倒になってしまうようだ。
https://www.codechef.com/viewsolution/16282630


Product on the segment by modulo

長さNの整数列と整数Pが与えられる。以下のQ個のクエリに答えよ。
・区間[L, R]の要素すべての積 mod Pを出力
1 <= N <= 10^6
1 <= Q <= 2 * 10^7

本番では累積和(imos法?)的に解いたが、当然Pが素数でないと通らないので部分点だった。
想定解ではSparse tableのようにデータを持つ。
・A[k, i]: i以下で2^kの倍数となる最大のインデックスからiまでの積
・B[k, i]: iから、iより大きくて2^kの倍数となる最小のインデックスまでの積
こうすると、B[k, L]とA[k, R]で重複がないkを選ぶことができれば、各クエリに対してO(1)で回答できる。k=1から増やしていけば簡単に見つけることができる。(証明は公式Editorialにある:https://discuss.codechef.com/questions/116821/segprod-editorial)
Sparse tableはこちらが分かりやすかった。
http://tookunn.hatenablog.com/entry/2016/07/13/211148


Lovers Gift

N個の都市が、双方向に繋がった木の形のグラフで表される。都市はそれぞれ1からNでDistinctにスコア付けされる。次のクエリに答えよ。
クエリ1: 都市Cに銀行がオープンする
クエリ2: 都市Cから1つ以上の銀行を経由し、2番目にスコアの大きい都市を訪れる。ただし同じ道は通れない。このスコアを出力せよ
1 <= N, M(クエリ数) <= 100000

想定解は素集合を使って求める。この方法は本番でも思いついていたが、計算量が大きく不可能と判断してしまっていた。
・銀行がすべてオープンした状態にして、後ろからクエリを発行する
・銀行を経由しないグループを1つの集合とする
・集合ごと、「集合外で1番目と2番目に大きなスコア(m1とm2)」を管理する
・銀行がクローズするたび、集合をマージ
こうすれば、クエリ2ごとに
・Cに銀行があればN-2を解答
・それ以外ならm2を解答
すればよい。
マージ後のm1、m2は、単純にm1からデクリメントして探していく。これだと間に合わなそうだが、マージするたびにm1の初期値がどんどん小さくなるので問題ない。

Codechef October Challenge 2017 参加日記

78位/10487人。これくらいの順位で安定するのが今年の抱負(改)。
以下、易問は省略する。


Chef and a great voluntary Program

リンゴa個、バナナb個をn人にいずれか一個ずつ配りたい。このとき、リンゴを配られた人は、直前x人が続けてリンゴだったら不満に思う。同じように、バナナを配られた人は、直前y人がバナナだったら不満に思う。不満を解消するには、リンゴまたはバナナを配る直前にキウイを渡せばよい。キウイの数を最小にせよ。
1 <= n <= 10^5
1 <= x, y <= n

a<=bとすると、配布の方法は2パターンしかない。
1、a, bひとつ以上, a, bひとつ以上...
2、bひとつ以上, a, bひとつ以上, a...
よって、aを一個ずつに分けて、その間にbを入れていけばよい。
https://www.codechef.com/viewsolution/15764132


Chef and Cycled Cycles

無向グラフを考える。このグラフにはN個のサイクルがあり、それぞれA[i]個のノードで構成されている。各サイクルにおいて、i番目のノードは(i + 1) % A[i]のノードとつながっている。さらに、グラフ全体をみると、N個のサイクルによって大きな1つのサイクルを構成している。つまり、i番目のサイクルは、i % N + 1番目のサイクルと、いずれかのノードで繋がっている。
すべてのエッジに重みが付いているとき、サイクルc1のノードv1と、サイクルc2のノードv2の最小コストを求めよ
なお、クエリ(c1, v1, c2, v2の組み合わせ)はQ個発行される。
1 <= N, Q <= 10^5
1 <= A[i] <= 10^5
1 <= A[1] + A[2] + ... + A[N] <= 10^5

単純なノードのみで構成されるサイクルn[0], n[1], ... n[k]を考えたとき、次のようにエッジコストの累積和を求めておけば、任意の2点間の最小コストはO(1)時間で求めることができる。
n[0], n[0]+n[1], ... Sum(n[0:k]), Sum(n[0:k])+n[0], ... 2xSum(n[0:k])
これを小さいサイクルと外側の大きなサイクルに適用すればO(1)で回答できる。
https://www.codechef.com/viewsolution/15784456


Chef and Magic Arrays

N個の数列があり、それぞれの数列は好きなようにシフトすることができる。このとき、i番目の数列の末尾の値をx、次の数列の最初の値をyとしたとき、|x - y|*iの合計値を最大化せよ。
数列の長さの合計は10^6を超えない
1 <= 値 <= 10^6

まず自明な観察として、実際に数列をシフトする必要はない。使うのは数列の先頭と末尾だけなので、ある位置jを末尾に使うとすると、先頭になるのはi+1である。
あとは次のDPを立てれば求めることができる。
dp[i, j]: 0..iまでで、数列iについて位置jを選んだときの最大値
https://www.codechef.com/viewsolution/15799713


(Challenge) Connecting computers

チャレンジ問題。ノード数1000の連結グラフを構築したときの最小コストを求めよ。
・各ノード間のコストはすべてランダムに与えられる
・各ノードについて、Degreeに応じたコストがかかる(Degreeの大小とコストの大小は連動しない)
制限時間はT=5で5秒。

Editorial想定解は連結を保持したままの山登り法。これが正解かなとは思ったが、連結を保持したまま高速に回すやり方が分からず保留(したままコンテスト終了)。次点解がクラスカル法+αで、自分の実装もこれで平凡な得点に終わってしまった。


Shooting on the array

二次平面上にN本の部分直線がある。部分直線iは(i,0)から(i,A[i])へ引いてある。このとき、次のQ個のクエリに答えよ。
・+ i X => 直線iのA[i]をXだけ増やす
・? i L R => R-L+1本のX軸に平行なビームを発射する。j番目のビームは(i-0.5, L+j-1.5)から発射される。ビームは直線にぶつかると消える。このとき、ビームがあたる直線の本数をプリントせよ
1 <= N <= 10^6
1 <= Q <= 10^5
x <= X <= 10000
1 <= A[i] <= 10^9
1 <= L <= R <= 10^9

平方分割を使う。このとき、1つのセグメント内ではA[i]が増加している分のみ保持すればよい(それ以外のものはビームが当たりようがない)。するとセグメント内は単調増加になるので、現在のビーム範囲で当たる最も短い(左の)直線と、最も長い(右の)直線が二分探索で求められる。
計算量はO(QSqrt(N)LogN)でぎりぎり間に合う。
https://www.codechef.com/viewsolution/15803230

HackerEarch July Circuits '17 参加日記

HackerEarth初参戦。74位/6699人とまずまずの成績だった。
以下、易問は省略する。

Permutation and reverse

1~nの数字が書かれたn枚のカードがある。このランダムに並んでいるカードを、区間を指定して反転、を繰り返して昇順にソートせよ。
<採点方法>
配列a[]が与えられる。無限配列 { b_i = a_i \, mod\,n }と定義する。
i番目の作業区間の長さを {len_i} としたとき、 {len_i} と一致する次の {b} の位置をposとする。作業するごとposを更新したとき、最終的なposの位置が小さいほど、高得点となる。

上位10人くらいには入ったが、それでもトップの1/4程度のスコアだった。
<方針>
bの位置でループし、
・未ソート区間の左端または右端をうまく作れるときは作る
・それ以外なら、なるべく昇順または降順になるよう、一部を並び替える
を繰り返す
・候補手が複数あるときはランダムに選択
・時間いっぱいトライしてベストのものを回答する
https://www.hackerearth.com/submission/10398190/


Download file

サイズS(MB)のファイルをダウンロードしたい。時間t[i]におけるダウンロードスピードがD[i]で与えられたとき、ダウンロード時間を最小化せよ。
1 <= N <= 100,000
1 <= D[i], S <= 1,000,000
0 <= t[i] <= 1,000,000
t[0] = 0、tの値は昇順

必ず、ダウンロードの開始時間または終了時間がt[i]のいずれかになる。よって、t[i]をループして最短のものを探せばよい。ダウンロード時間は累積和を使えばO(1)で求められる。
https://www.hackerearth.com/submission/10349554/


Dreamplay and Upside Down

文字列Pがある。(1)末尾に文字を追加(2)文字を削除、のいずれかを繰り返し、なるべく少ないステップで回文を作れ。
1 <= Pの長さ <= 5000

文字位置でループ。その文字(もしくは文字間)を中心として回文を作り、最小ステップのものを回答する。あらかじめダミー文字('.'など)を挿入すると、文字間を考えなくてよいので楽。
https://www.hackerearth.com/submission/10285667/


Travelling Tom

n個の都市が双方向の道でつながっている。また、k種類のトークンがあり、それぞれ値段c[i]である。道にはそれぞれ、通過に必要なトークンの種類が設定される(トークンは使いまわせし)。すべての都市を訪れるために必要な、最小の金額を答えよ。
・すべての2<=i<=kについて、c[i] >= 2 * c[i-1]
・1 <= n <= 10^5
・1 <= m <= 10^5
・1 <= c[i] <= 10^18

本番では二分探索+UnionFindで解いて半分ほどTLEになっていた。
https://www.hackerearth.com/submission/10394484/
kの最大値が60程度なのがポイント。あるトークンだけが不足してるとき、全都市が連結でなければ、そのトークンは必須と判断していけばよい(実装は省略)。


MST revisited

ノード数N、エッジ数Nの無向グラフがある。エッジは重みづけされている。自己ループや並行エッジは存在せず、グラフは常に連結されている。エッジを1つ削除・追加するクエリをQ個実行する。このとき、クエリ実行ごとにMSTのコストを答えよ。
・3 <= N <= 300,000
・1 <= Q <= 300,000
・グラフは常に連結、かつ自己ループや並行エッジは存在しない
・1 <= エッジの重み <= 1,000,000

本番ではBICCで実装した。削除エッジがループ内かどうか判定し、計算量を節約してなんとか1サンプルのAC(3/4でTLE)だった。
https://www.hackerearth.com/submission/10374653/
上位陣はLink-cut木というデータ構造を使って解いていた。
https://www.hackerearth.com/challenge/competitive/july-circuits-17/algorithm/mst-revisited-3f9d614c/submission/10347662/
基本的には、ループを作ってしまう1つのエッジ(両ノードのrootが同じになっているもの)を保持し、他はLink-cut木で挿入・削除を繰り返しているようだ。そしてサブ木ごとにMaxコストを保持することで、ループ内の最大コストを算出する計算量を減らしている。
Link-cut木の解説はこちらが参考になる。
プログラミングコンテストでのデータ構造 2 ~動的木編~


Transportation network

n個の都市があり、1つのクエリで都市uとvを道路または鉄道で繋ぐ。クエリごとに、ネットワークがbalancedかどうかと答えよ。balancedなネットワークとは、
・すべての都市のペアu,vについて、u,vが道路で繋がれているときのみ、鉄道で繋がれている
ものをいう。
1 <= n <= 10^5
1 <= q <= 2x10^5
1 <= u, v <= n

本番ではUnionFindを2つ作り、グループに所属するノード数を比較して2/3ほどTLEだった。
https://www.hackerearth.com/submission/10375122/
2つのUnionFindの状態判定に工夫がいる。たとえば道路のネットワークに注目したときには、Queueに保持したエッジごとに鉄道側のUnionFindにおいて同じグループが判定する。分割は無いので同グループと判明したエッジは削除してOK。これを道路側・鉄道側両方で実施する。

var str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();
var n = str[0];
var q = str[1];

var uf1 = new UnionFind(n);
var uf2 = new UnionFind(n);
var que1 = new Queue<Tuple<int, int>>();
var que2 = new Queue<Tuple<int, int>>();

while (q-- > 0)
{
    str = Console.ReadLine().Split().Select(v => Int32.Parse(v)).ToList();

    (str[0] == 1 ? uf1 : uf2).Unite(str[1] - 1, str[2] - 1);
    (str[0] == 1 ? que1 : que2).Enqueue(new Tuple<int, int>(str[1] - 1, str[2] - 1));

    for (int i = 0; i < 2; i++)
    {
        var uf = i == 0 ? uf2 : uf1;
        var que = i == 0 ? que1 : que2;

        //balanced?
        while (que.Count() > 0)
        {
            var n1 = que.Peek().Item1;
            var n2 = que.Peek().Item2;
            if (uf.root(n1) != uf.root(n2))
            {
                break;
            }
            else
            {
                que.Dequeue();
            }
        }
    }

    Console.WriteLine(que1.Count() == 0 && que2.Count() == 0 ? "YES" : "NO");
}

CodinGame - Wondev Woman 参加日記

二度目のCodingGameコンテスト。ボードゲームAIの強さを競うもので、結果は世界310位/2299人、アメリカ17位/179人(ゴールドリーグ中位)だった。前回のCodinGame参加日記にも書いたが、このコンテストは

  • ランキングはリーグ制
  • ウッドリーグ3部からスタート
  • リーグボスを倒すごと、ウッド2→ウッド1→ブロンズ→シルバー→ゴールド→レジェンドとランクアップする
  • ランクアップとき、ルールが追加されることがある

の特徴がある。マッチを美しいグラフィックで観戦できるのが楽しい。
https://www.codingame.com/replay/243115997


ゲームルール概要

  • ターン制の2Dボードゲーム
  • お互い1つ(上位リーグより2つ)の駒を持つ
  • 初期配置はランダム
  • ボード上の各セルは、高さ(0~4)を持つ
  • また、ボード上には移動できないセルもある
  • 駒は上下左右および斜めの8か所に移動できる
  • ただし、移動できるのは現在より低い地点か、1つだけ高い地点のみ
  • また、高さ4のセルへは移動できない
  • 各ターンで1つの駒へ、次の命令を行う
  • MOVE&BUILD …移動して、移動先の隣接セルの高さを+1する
  • PUSH&BUILD(上位リーグより) …隣接する敵駒を押して移動させ、その場所の高さを+1する
  • 下位リーグ:高さ3のセルに最初に到達したほうが勝ち
  • 上位リーグ:高さ3のセルに到着した回数の多いほうが勝ち
  • 敵の駒情報は、味方に隣接してる場合のみ与えられる(上位リーグより)


実装

  • 1手だけ読む
  • ゴール回数、現在地と移動可能な隣接セルでスコアを付ける
  • 現在地・隣接セルともに、高いほどよいスコアにする
  • 敵に近かったらペナルティ
  • 動けなくなったらペナルティ

敵の場所の予想、狭い場所を嫌う仕組みなどは思いついたが実装せず。2手読みさせたら弱くなったのが原因不明。
https://bitbucket.org/yambe2002/codingame-wondev-woman


反省
こんな感じに「それっぽく不具合なく動く」程度でゴールド中位くらいになるようだ。Topcoder MMの黄色下位と同レベルくらいか。
レジェンドリーグからが本番の雰囲気があるので、次回はそこを目指したい。

Codechef June Challenge 2017 参加日記

966位/9366人の自己ワースト記録。追い上げが甘かった。以下、易しい問題(全体の正答率が高いもの)は省略する。

Chef and the Feast

N個の料理と、それぞれを食べたときの満足度A[i]が与えられる。次の条件ですべての料理を食べたとき、得られる満足度の合計を最大化せよ。
・料理からSubsetを選択
・Subsetを食べる。このときの満足度は、Subsetの数x各満足度の和
1 <= N <= 10^5
-10^8 <= A[i] <= 10^8

基本的に満足度が正の料理は1つのSubsetとして食べ、負の料理は1つずつ食べる。ただし、あまり負の値が大きくないものは、正のSubsetに加えたほうが良い場合もある。なので負のものを小さい順に正のSubsetに加えて試していけばよい。

public static long GetAns(long[] a)
{
    var negs = a.Where(v => v < 0).OrderByDescending(v => v).ToArray();
    var posCnt = a.Count(v => v >= 0);
    var posSum = a.Where(v => v >= 0).Sum();

    var ret = posCnt * posSum + negs.Sum();

    var allNegSum = negs.Sum();
    if (negs.Count() > 0)
    {
        var negsSum = 0L;
        for (int i = 0; i < negs.Length; i++)
        {
            negsSum += negs[i];
            var newRet = (posCnt + (i + 1)) * (posSum + negsSum) + (allNegSum - negsSum);
            ret = Math.Max(ret, newRet);
        }
    }

    return ret;
}


Pairwise union of sets

整数[1,K]のSubsetがN個与えられる。Subsetからペアを選んだとき、そのUnionが1~Kすべてを含む組み合わせ数を求めよ。
1 <= N, K <= 2500
1 <= len[i] <= K
1 <= len[1] + len[2] + ... + len[N] <= 10000
(len[i]はSubset[i]の長さ)

Subsetのペア組み合わせすべてを判定すればよい。各Subsetの状態(最大2500ビット分)をInt64型の配列で表せば、計算量はO(N^2 * K/64)程度なので間に合う。

static Bit[] bits = new Bit[2501];

public static long GetAns(int n, int k, List<int[]> sets)
{
    for (int i = 0; i < sets.Count; i++) bits[i] = new Bit(sets[i]);

    long ret = 0;
    for (int i = 0; i < sets.Count() - 1; i++)
    {
        for (int j = i + 1; j < sets.Count(); j++)
        {
            if (bits[i].Match(bits[j], k)) ret++;
        }
    }
    return ret;
}

public class Bit
{
    public ulong[] Data = new ulong[40];

    public Bit(int[] listData)
    {
        foreach (var data in listData) Set(data - 1);
    }

    public void Set(int idx)
    {
        Data[idx / 64] |= (1ul << idx % 64);
    }

    public bool Match(Bit b2, int k)
    {
        if (k % 64 != 0)
        {
            var idx = k / 64;
            var val = Data[idx] | b2.Data[idx];
            if (val != (1UL << k % 64) - 1) return false;
            k -= k % 64;
        }

        for (int i = 0; i < k; i += 64)
        {
            var d = Data[i / 64] | b2.Data[i / 64];
            if (d != ulong.MaxValue) return false;
        }

        return true;
    }
}


Triplets

3つの整数を引数にとる関数f(x,y,z)は、y>=xかつy>=zのときは(x+y)*(y+z)、それ以外ならゼロを返す。配列A、B、Cが与えられたとき、f(A[i], B[j], C[k])の合計を求めよ。解答は1000000007でMODして出力すること。
1 <= len(A), len(B), len(C) <= 100000
1 ≤ A[i], B[i], C[i] ≤ 1000000000

Bを固定値bで考える。さらに、A・Cからb以上の要素のみ取り出した配列をそれぞれa、cとする。
a: a[0], a[1], a[2],...
b
c: c[0], c[1], c[2],...
すると求める値は、
(a[0]+b)(b+c[0])+(a[0]+b)(b+c[1])+ ... +
(a[1]+b)(b+c[0])+(a[1]+b)(b+c[1])+ ....
...
となる。これを変形すると
(a[0]+b)*{(cの数)*b + (cの合計)}+
(a[1]+b)*{(cの数)*b + (cの合計)}+
...
それぞれの右辺が同じなので
{(aの合計)+(aの数)*b)}*{(cの数)*b + (cの合計)}
となる。
Aからb以上の要素を取り出すのには、予めAをソートして二分探索を使えばよい。
(a[]の合計)などは、予めAをソートし、合計していったものを配列で持っておけば簡単に求められる。
サンプルはC++。C#だとTLEになってしまうようだ。CodechefのC#はバージョンが低いせいか、Array.Sort()がちょっと遅い気がする。

long long MOD = 1000000007;
 
void getSumArray(long long *ar, long long *ret, int n)
{
    for (int i = 0; i < n; i++)
    {
        ret[i] = ((i == 0 ? 0 : ret[i - 1]) + ar[i]) % MOD;
    }
}
 
int main()
{
    int t;
    scanf("%d", &t);
 
    while ( t > 0 )
    {
        int p, q, r;
        scanf("%d %d %d", &p, &q, &r);
 
        long long a[p];
        long long b[q];
        long long c[r];
 
        for(int i = 0; i < p ; i++)
        {
            scanf("%lld", &a[i]);
        }
        for(int i = 0; i < q ; i++)
        {
            scanf("%lld", &b[i]);
        }
        for(int i = 0; i < r ; i++)
        {
            scanf("%lld", &c[i]);
        }
        
        sort(a, a + p);
        sort(c, c + r);
 
        long long aSum[p];
        long long cSum[r];
 
        getSumArray(a, aSum, p);
        getSumArray(c, cSum, r);
 
        long long ret = 0;
        for (int i = 0; i < q; i++)
        {
            long long y = b[i];
            int aUb = min(p - 1, lower_bound(a, a + p, y + 1) - a - 1);
            int cUb = min(r - 1, lower_bound(c, c + r, y + 1) - c - 1);
            
            if (aUb < 0 || cUb < 0) continue;
 
            ret += ((aUb + 1) * y % MOD + aSum[aUb]) * ((cUb + 1) * y % MOD + cSum[cUb]) % MOD;
            ret %= MOD;
        }
 
        cout << ret << endl;
        t--;
    }
} 


Chef and Prime Queries

長さNの整数列Aがある。整数L,R,X,YからなるクエリがQ個与えられるので、それぞれに対し次の疑似コード結果を回答せよ。

F(L, R, X, Y) {
     result := 0
     for( i = X to i = Y )  {
         if( isPrime(i) ) {
             for( j = L to j = R ) {
                  number := a[j]
                  exponent := 0
                  while( number % i == 0 ) {
                     exponent := exponent + 1 
                     number := number/i
                  }
                  result := result + exponent
              }
         }
     }
     return result
}

1 <= N, Q <= 10^5
1 <= L <= R <= N
1 <= X <= Y <= 10^6
2 <= A[i] <= 10^6

問題を言い換えると、
・Aの部分配列[L:R]を抜き出し、
・要素それぞれの素因数のうち、X以上Y以下の部分について
・階乗部分の合計を求めよ
となり、セグメント木で解くことができる。各セグメントには、範囲内の素因数分解した値を配列でもつ。たとえば
A[0]=12, A[1]=10, A[2]=18
だとすると、セグメントでもつ値は
Seg[0]=[2,2,3]
Seg[1]=[2,5]
Seg[2]=[2,3,3]
Seg[0:1]=[2,2,2,3,5]
Seg[1:2]=[2,2,3,3,5]
Seg[0:2]=[2,2,2,2,2,3,3,3,5,5]
となる。あとは対象セグメントからX以上Y以下の要素数を回答すればよい(二分探索)。

public static List<int> GetAns(int[] a, List<Tuple<int, int, int, int>> queries)
{
    var sieve = GetSieve(1000001);
    var factTable = GetFactTable(a, sieve);

    var segTree = new SegTree(a, factTable);

    return queries.Select(q => segTree.Query(q.Item1 - 1, q.Item2, q.Item3, q.Item4)).ToList();
}

public static List<List<int>> GetFactTable(int[] a, int[] sieve)
{
    var ret = new List<List<int>>();
    foreach (var v in a) ret.Add(GetFactList(v, sieve));
    return ret;
}

public static List<int> GetFactList(int value, int[] sieve)
{
    var ret = new List<int>();

    while (true)
    {
        if (sieve[value] == 0)
        {
            ret.Add(value);
            break;
        }
        ret.Add(sieve[value]);
        value /= sieve[value];
    }

    ret.Reverse();
    return ret;
}

public static int[] GetSieve(int n)
{
    var ret = new int[n + 1];
    for (int i = 0; i < ret.Length; i++) ret[i] = 0;
    ret[0] = ret[1] = -1;
    for (int i = 2; i < ret.Length; i++)
    {
        if (ret[i] != 0) continue;
        for (int j = i + i; j < ret.Length; j += i)
        {
            ret[j] = i;
        }
    }
    return ret;
}

public class SegTree
{
    int _n;
    SegNode[] _dat;

    public class SegNode
    {
        // sorted
        public List<int> Factors;

        public SegNode(List<int> factors)
        {
            Factors = factors;
        }

        public SegNode(SegNode s1, SegNode s2)
        {
            if (s1 == null && s2 != null)
            {
                Factors = s2.Factors;
                return;
            }
            if (s1 != null && s2 == null)
            {
                Factors = s1.Factors;
                return;
            }
                
            Factors = new List<int>();
            if (s1 == null && s2 == null) return;

            int l1 = 0, l2 = 0;
            while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count())
            {
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] < s2.Factors[l2])
                {
                    Factors.Add(s1.Factors[l1]);
                    l1++;
                }
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] > s2.Factors[l2])
                {
                    Factors.Add(s2.Factors[l2]);
                    l2++;
                }
                while (l1 < s1.Factors.Count() && l2 < s2.Factors.Count() && 
                    s1.Factors[l1] == s2.Factors[l2])
                {
                    Factors.Add(s1.Factors[l1]);
                    l1++;
                    Factors.Add(s2.Factors[l2]);
                    l2++;
                }
            }
            while (l1 < s1.Factors.Count())
            {
                Factors.Add(s1.Factors[l1]);
                l1++;
            }
            while (l2 < s2.Factors.Count())
            {
                Factors.Add(s2.Factors[l2]);
                l2++;
            }
        }

        public int Query(int x, int y)
        {
            var ret = LowerBound(Factors, y + 1);
            if (ret >= Factors.Count()) ret = Factors.Count();

            var xl = UpperBound(Factors, x - 1);
            if (xl > 0) ret -= xl;
            return ret;
        }

        public int LowerBound(List<int> ar, int val)
        {
            var lb = -1;
            var ub = ar.Count();

            while (ub - lb > 1)
            {
                var mid = (lb + ub) / 2;
                if (ar[mid] >= val)
                {
                    ub = mid;
                }
                else
                {
                    lb = mid;
                }
            }

            return ub;
        }

        public static int UpperBound(List<int> ar, int val)
        {
            var lb = -1;
            var ub = ar.Count();

            while (ub - lb > 1)
            {
                var mid = (lb + ub) / 2;
                if (ar[mid] <= val)
                {
                    lb = mid;
                }
                else
                {
                    ub = mid;
                }
            }

            return lb + 1;
        }
    }

    int[] _a;
    List<List<int>> _factTable;

    public SegTree(int[] a, List<List<int>> factFable)
    {
        _a = a;
        _factTable = factFable;

        _n = 1;
        while (_n < a.Count()) _n *= 2;
        ConstructTree();
    }

    void ConstructTree()
    {
        _dat = new SegNode[_n * 2];
        ConstructTree(0, 0, _a.Count());
    }

    void ConstructTree(int k, int l, int r)
    {
        // bottom-most
        if (l == r - 1)
        {
            _dat[k] = new SegNode(_factTable[l]);
            return;
        }

        ConstructTree(k * 2 + 1, l, (l + r) / 2);
        ConstructTree(k * 2 + 2, (l + r) / 2, r);
        _dat[k] = new SegNode(_dat[k * 2 + 1], _dat[k * 2 + 2]);
    }

    public int Query(int a, int b, int x, int y)
    {
        return Query(a, b, 0, 0, _a.Count(), x, y);
    }

    int Query(int a, int b, int k, int l, int r, int x, int y)
    {
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return _dat[k] == null ? 0 : _dat[k].Query(x, y);
        else
        {
            var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2, x, y);
            var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r, x, y);
            return vl + vr;
        }
    }
}


Saboteur (Challenge)

ノード数N・エッジ数Mからなる連結の無向グラフがある。ノードの破壊にはcost[i]の費用がかかる。なるべく少ないコストで、グラフからループを取り除いたときのトータルコストを求めよ。ただし、最終的なグラフは連結でなければならない。
1 <= N <= 10^4
N-1 <= M <= 5*10^4
1 <= cost[i] <= 10^5
テストケースは、(1)N<=20(2)N<=40(3)M=N(4)M<=N+3(5)完全グラフ(6)ランダム、のいずれかの条件で作成される。

次の方針で平均より少し上くらいの結果だった。
1、完全グラフのとき(M=N*(N-1)/2)は、最もコストの大きい2ノード以外をすべて破壊して終了
2、次数1のノードを、隣のノードにまとめてしまう(コストは合算する)。これでループの一部となるノードのみとなる
3、次数とコストの降順+乱数でノードを並び替える
4、ノードをひとつずつ取り出して、閉ループができないようにグラフを作っていく
5、あまったノードは破壊対象とし、解答の候補に入れる
6、時間があるなら3へ戻る
実装:https://www.codechef.com/viewsolution/14190840
上位陣は完全グラフかどうかだけでなく、6つのデータタイプのそれぞれを判断して別のロジックを用意しているようだ。
例:https://www.codechef.com/viewsolution/14237992