MM102 & ふみこん

感想

勉強になりました。
少しだけ復習したので一時メモ。続きをやったら更新したいね。

ふみこん

思考

  • 超自明な方針として区間1だけの操作に限ってみる。
    すると上げるところと下げるところを貪欲に組み合わせていけば最適(?)解が求まる。
  • そこから区間を広げてみる。このとき区間内の上げ下げしたい量は一定ではないため増減させる量の決め方は自明ではないが、区間のいずれも目標値を超えないようにするだけでそれなりに上がるらしい。
  • 最上位に行くにはもう少し工夫が必要。

todo

  • コード読む

Future Meets You Contest(Open) - Future Meets You Contest(Open) | AtCoder

MM102

思考

  • 貪欲も難しい
  • トラックにいくつ乗せても運送料変わらないので纏められるなら纏めたほうが良い(もちろんこれはトラックのコストなどにより変わってくるので、本来はコンテスト時に調査するべき内容)
  • 配達先はフィールド全体に点在しているので、トラックに全荷物纏めたあとにフィールドをぐるっと回りつつ配達する
  • これでそこそこのスコア

todo

  • 上位3人wleite氏の解を読む

MM 102 - Togetter

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=68860&rd=17264

SRM 736 Div1

DigitRotation

問題

整数が文字列で与えられる。 この整数の3桁を選んでローテーション操作を行い生成される全ての整数の和をmod 998244353で求めよ。

メモ

n \leq 500なのでO(n^3)の全探索。

SRM 736 Div1 Easy · GitHub

MinDegreeSubgraph

問題

n,m,kが与えられる。 ALL, SOME, NONEのいずれか判別せよ。

  1. ALL : n頂点m辺の全ての単純グラフが最小次数kのサブグラフを持つ。
  2. SOME : n頂点m辺のいくつかの単純グラフが最小次数kのサブグラフを持つ。
  3. NONE : n頂点m辺の全ての単純グラフが最小次数kのサブグラフを持たない。

メモ

まず少なくとも一つの最小次数kのサブグラフを持つ条件を考える。 K_{k}を含むグラフは最小次数kのサブグラフを持つので頂点数がk+1以上、辺数が\frac{k(k+1)}{2}以上ならALL or SOME、そうでなければNONE。

残るはALLかSOMEの判別。 任意のサブグラフの最小次数がk未満となるようなグラフは、元のグラフに次数k未満の頂点が存在し、その頂点を取り除くとまた次数k未満の頂点が現れ、それを取り除くとまた現れ…これを繰り返し頂点数が0となるようなグラフ。 f(n,k)n頂点で最小次数k未満のとなる最大の辺数とすると、1頂点だけk-1の頂点があり、それを取り除くとまた1頂点だけk-1となるようなグラフが最大の辺数となるので

f(n,k)=f(n-1,k)+k-1

f(k+1,k)=\binom{k+1}{2}-1

SRM 736 Div1 Med · GitHub

参考

Subpolygon

問題

メモ

CEOI 2018 Day 1

https://csacademy.com/contest/ceoi-2018-day-1/summary/

Cloud Computing

https://csacademy.com/contest/ceoi-2018-day-1/task/cloud-computing/

問題

周波数f_{i}のコアc_{i}個をv_{i}円で仕入れることができる。 周波数F_{i}以上のコアC_{i}個をV_{i}円で購入する注文がくる。 各注文は受けても受けなくてもいい。 最大の利益はいくらか。

メモ

dp[][i] : コアi個余っている時の最大の利益、というdpで解ける。 https://csacademy.com/submission/1710230

Global Warming

https://csacademy.com/contest/ceoi-2018-day-1/task/global-warming/

問題

数列が与えられる。 数列の任意の区間d(-x \leq d \leq x)を足すことができる。 LISの最大値を求めよ。

メモ

任意の区間に足す必要はなくi以降の要素に足すとしてよい。 Benqの解を参考にした。

https://csacademy.com/submission/1715714

Lottery

問題

メモ

Benqの解を参考にした。 Javaで2次元配列用意するとMLEになってしまうので1次元配列に潰した。

https://csacademy.com/submission/1716086

Codeforces Round #503 (by SIS, Div. 1)

Dashboard - Codeforces Round #503 (by SIS, Div. 1) - Codeforces

A. Elections

問題

政党がm個ある。 n人の有権者の投票先と、投票先を変えるために必要な金額が渡される。 党1の得票数が厳密に最多となるために必要な最小の金額を求めよ。

解法

党1の得票数で全探索する。 党1の最終的な得票数をxとする。 x以上の得票数を持つ政党への投票者をx未満にするために買収し、その後得票数がxに満たない場合はxになるまで貪欲に買収する。

B. The hat

問題

インタラクティブ問題(いつからかリアクティブとは呼ばれなくなったね) n人円卓に並んでいる。 i番目に座っている人は数x_{i}を持っている。 隣り合う人が持つx_{i}の値の差は\pm 1x_{i}を最大60回問い合わせることができるので x_{i} = x_{i+\frac{n}{2}} となるiを求めよ。 そのようなiが存在しない場合-1を出力せよ。

解法

f(i)=x_{i}-x_{i+\frac{n}{2}}という関数を考える。 f(i)=0となるiが解である。 まずn=4m+2の場合、f(i)は必ず奇数なので解なし。 そうでない場合解は必ず存在する。 f(i)=-f(i+\frac{n}{2})かつf(i)は連続なので中間値の定理よりf(i)=0となるiが存在が示され、それを二分法で求めることができる。

C.

D.

E.

TCO18 R3A Medium ProductThreshold

http://community.topcoder.com/stat?c=problem_statement&pm=14949 TCO18 Algorithm Round 3A Editorials - Topcoder 2.0

問題

積がlimit以下になるような連続した部分列の数を求めよ

解法

0を含む区間は条件を満たすので、0を含む区間だけ先に計算し、以後0を含まない区間のみ計算する。 ある区間の積を考えたときに条件を満たさない可能性があるのは区間の積が正のときだけ。

cnt(s,i)[0,i)の積の符号がsとなるiの数とする。 積が負になる場合は必ずlimit以下となるので、s[0,i)の積の符号とすると、積の絶対値がlimit超えないように尺取りしつつ\displaystyle \sum_{l,r} cnt(-s,r)+cnt(s,r)-cnt(s,l)で条件を満たす区間の数が求まる。

一言

配列は乱数で生成するので手を抜いても大丈夫かと思ったが駄目なケースがあった。

package main.tasks;

import java.util.*;

public class ProductThreshold {
    public long subarrayCount(int N, int limit, int[] Aprefix, int spread, int offset) {
        long[] ary = new long[N];
        for (int i = 0; i < Aprefix.length; i++) {
            ary[i] = Aprefix[i];
        }
        long seed = Math.abs(ary[Aprefix.length - 1]);
        for (int i = Aprefix.length; i < N; i++) {
            seed = (seed * 1103515245 + 12345) & ((1L<<31)-1);
            ary[i] = seed % spread + offset;
        }
        return solve(N, limit, ary);
    }

    long solve(int N, int limit, long[] ary) {
        List<Integer> zero = new ArrayList<>();
        zero.add(-1);
        for (int i = 0; i < N; i++) {
            if (ary[i] == 0) zero.add(i);
        }
        long ans = 0;
        for (int idx = 1; idx < zero.size(); idx++) {
            long i = zero.get(idx - 1);
            long j = zero.get(idx);
            long k = zero.get(idx);
            ans += (N - k) * (j - i);
        }

        sum = new long[2][N+1];
        zero.add(N);
        for (int i = 0; i + 1 < zero.size(); i++) {
            ans += solve(zero.get(i) + 1, zero.get(i + 1), limit, ary);
        }
        return ans;
    }

    long[][] sum;
    long solve(int l, int r, int limit, long[] ary) {
        long ans = 0;
        sum[0][l] = sum[1][l] = 0;
        long mul = 1;
        for (int i = l, j = l, p = 0; j < r; j++) {
            sum[p][j+1]++;
            for (int k = 0; k < 2; k++) sum[k][j+1] += sum[k][j];
            if (ary[j] < 0) p ^= 1;
            mul *= ary[j];
            for (; Math.abs(mul) > limit; i++) {
                mul /= ary[i];
            }
            ans += sum[p^1][j+1] + sum[p][j+1] - sum[p][i];
        }
        return ans;
    }

    static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); }
}

ARC094 D - Worst Case

本番解けず。 1ステップでも考察入ると解けなくなるのは克服したい。

解法

自分より上位にn人存在しうるか、を二分探索して解いた。この問題は

  • n人の人が上位にいるとき、自分の順位を除いて、1回目に1位だった人は2回目n位、1回目2位だった人は2回目n-1位…という順位をとるのが最善

という単純な事実に気づけば後は二分探索で簡単に答えが求まる。 n人全員調べるとTLEなので、順位の積が最大になるのは真ん中あたりの人なので真ん中あたりの人だけ調べればいい。

Submission #2787487 - AtCoder Regular Contest 094

TCO18 MM R1 RoadsAndJunctions

方針

序盤

置く候補を全探索し、置いたときにスコアが大きくなる順に置いて行った。 盤面がでかくて全探索できないときは探索する点を間引いた。

終盤

  1. 焼き鈍しを9400ms実行。遷移は以下の3つで、失敗確率0での解を求めた。

    • ランダムにjunctionを置く
    • 隣へ移動する
    • junctionの削除
  2. 失敗確率も考慮し、期待値が低くなるように1.で求めた点を多重化

反省点

  • yoursの期待値の最小化ではなく、(yours^-2)の期待値を最大化をする発想がなかった
  • 期待値の計算が適当
  • GCEでテストできるようにしていたが、環境構築に失敗していて、最終日までその失敗に気づかなかった(ずっと初期に書いたコードでテストされていた、途中でおかしいなとは思ったんですけどね…)
  • パラメータの調整の時間がもったいなかった(雑で良いので自動調整できるようにしたい)

良かったところ

  • 1週間頑張れた(えらい)
  • EMSTのO(nlogn)解法のような、面白そうだけど効果が薄そうな実装はせず、より効果の高そうな方針の検討に時間を割いた。(初期頂点から構成されるMSTの最長辺の長さで平面を分割するお手軽高速化は行ったけど、よく考えると非常に遅くなるケースあるしやらないほうが良かったな…)

ローカル1000ケースで評価して焼き鈍し解法のほうがよかったのでそっちを投げたけど、standingsでは下がっていた。もしかしてTLEしていたのかな。

別に着るわけじゃないだけどTシャツ獲得を目標にして残りを頑張ろう。

復習

  • 自動調整できるようにする
  • 期待値計算の見直し
  • (yours^-2)の期待値を最大化をしてみる
  • コードの書き直し