ferinの競プロ帳

競プロについてのメモ

chokudai contest 001

競技プログラミング マラソン AtCoder

問題ページ
Tasks - Chokudai Contest 001 | AtCoder

唐突にマラソンがやりたくなったのでジャッジが公開されているマラソンのchokudai contest 001を試しにやってみることにした。

6:46 問題を読む グリッドゲーで操作にかかる手数をできるだけ小さくしたいらしい。

8:40 プロ各位のマラソン入門ブログを読み漁る。時間で殴る、問題の性質をちゃんと理解する、探索空間をうまくとるあたりが大事らしいことを学ぶ。とりあえず正の点数を取れるプログラムを出すことにする。1以上のマスがあったらそのマスから右下左上の順でいけるところまで行くコードを出す。0indexで出力して1回WAをもらうがとりあえずAC。541378点で202位/224相当。80万点で本番の上位50%みたいなのでとりあえずそこを目標にいろいろ試すことにする。

9:20 手元で試せるようにテストケースをつくる。本番10個らしいしそこまで偏らなさそうと思ったのでとりあえず15個用意した。いちいち実行するのはアホらしいのでpythonでまとめて実行したりそれぞれのテストケースで実行時間を測れるようにしたのをつくる。
盤面と開始するマスを決めればそのマスから一手番で取れる最長の取り方は決まる。右下左上の順で適当に探索するのからその最長の取り方に変える。サンプルを実行してみると長さ1の取り方ばかりしている。よくよく考えると1から100の均等配置で偶然並ぶ確率はだいぶ低そう。とりあえず出すだけ出す。544856点で予想通り低い。

10:30 何をしていいかよくわからなかったので有名アルゴリズムのビームサーチをとりあえず実装することにする。ビームサーチの1世代を1手番にしたりすればいいのかなあとか考える。queにvector<pair<int, int>>をつっこめばできないことはなさそう。計算量について考える。世代数×ビーム幅×遷移数とかになりそう。遷移数はO(HW)、世代数はこれまでの結果を見るに50000くらいになりそうで、1手番を選ぶのにO(HW)掛けているので大体k510^8くらいになりそう。ビーム幅kかなり小さい気がするけど大丈夫なのか…？

13:30 大きい値のマスから開始するものを先に選ぶようにすれば連続で並ぶ列ができやすいのでは?!と考えてとりあえず出す。510000点で最低記録を更新した。あとから考えると連続で並んだ列の数のどこかと同じ数があれば連続で消せるのに別の方に飛ぶのでこれが論外なのはそれはそう。

14:20 ビームサーチをしても幅が小さいと1手番で1マスしか操作できず、評価が難しい最初のほうでいいのが消えて結局いいのが残らないのではと思ったりする。焼きなましの方が向いているのか？と思ったりしたが焼きなましとビームサーチの違いもよくわからないのでうーん。
とりあえず1手番で何マスも操作できるようなのをどうやってつくるかが鍵っぽい？一回連続で並んだマスをつくればそこを何回も取れそうで連続列をつくっていくのが大事そう。(20 19 18 17 16と並んだマスをつくれば16回1手番で5マス操作ができる) 適当にやってたところで連続列はあんまりできなさそうだし連続列をうまく作ってやるのが大切そうに思える。

15:00 LISみたいなものを求めてその列に対して手番を行うを繰り返すとかを思いつく。

2日後の5:00 LISのを実装することにする。バグらせまくる。途中経過を見ると1手番で多くても6,7マスしか取っておらずそんないい影響はなさそう。

7:00 ようやく実装ができたのでとりあえず出すが572649点とそこまで上がらない。連続列をつくる方針は良いと思うのでもっと長い連続列をつくれるような貪欲を書いてみることにする。途中で小さい数が来ると短い列になってしまいそうなのでできるだけ大きい数の方向に進んでいくような列をつくってその列に対して操作を行うとした。

8:35 バグらせつつようやく実装を終える。737247点で161位/224相当でようやくマシな点数を出せた。

9:00 全てのマスを始点として試して、最も長い列であったものに対して手番を行うと変えてみる。むしろスコアが下がった。

10:40 大きい数を入れると連続にするために使う手数が増え、小さい数を入れると列の長さが減る。長さNの連続列があったとき、もっとも悪い取り方をするとN*(N+1)/2手番なところをN手番で取れるのでO(N2)からO(N)への改善となることを考えると列が長い方が大事そう。

10:55 考えてても何もわからなかったので途中でつくっている列の長さだったりを表示してみる。大きい数の方に進んでいく貪欲のコードを2番、長い列を貪欲に選ぶコードを3番と呼ぶことにする。列の長さの平均は6から7くらいで予想より短かった。(10くらいはあると思っていた。)想定どおり3番が2番よりも長い列を選ぶことはできていたが全体のスコアは低い。

11:30 最初の連続列30個で手数を見てみると、3番の方が7000手近く多い。そこからの手数消費は2番よりも小さいくらいなので最初が問題そう。連続列の長さに対する手数の比率を表示してみると2番は30から40くらいなのに3番は50近くいっているものもある。つまり連続列の中に大きく外れた数が存在する…？

12:00 連続列の決定方法として差が小さい方に貪欲に進んでいくとする。（これを4番と呼ぶ） 提出すると742553点で156位/224相当。一応上がった。あとは時間を全然使ってないのでこの時間をつかって探索して連続列をもっとうまく選べないか考える。連続列の選び方でビームサーチすることにする。

12:30 ビームサーチの実装を何となく考える。BFSからちょっと変えればいいだけに思えるので実装する。

queue<state> que
while(que.size()) {
  priority_queue<state> pq
  // このループでビームサーチ1段分の探索をする
  while(que.size()) {
    top = que.top
    // top の状態から遷移したのを pqに突っ込む
  }
  // pqの上位k個をqueに突っ込む
}

13:00 評価関数の部分をどうするか悩む。とりあえず連続列から手番の操作を生成するコードをコピーしてきて 手数/連続列の長さ を評価関数の値として返すことにする。

15:00 バグらせ続ける。pop忘れて無限ループとか評価関数で例外処理が抜けてる部分があったり色々とひどかった。

翌日の4:00 手数の操作を順番に求める必要はないので評価関数をちょっと軽くしたりして改善する。とりあえず動くようになった。スコアがむしろ落ちている。TLを無視してビーム幅を長くしてみると大してスコアが上昇しない。評価関数をただの手数に変えてみる。大してスコアは上がらない。atcoderとローカルの実行時間の比較のためにとりあえず出してみる。ローカルで7秒くらいのを出したら4.3秒しかかかっていない、atcoder優秀。ローカルの2/3くらいになるかなーといった感じ。

4:30 評価関数を手数/連続列の値の和としてみる。連続列の長さの比よりもこっちのほうがよさそう。提出すると787405点で136位/224相当でいい感じ。

6:00 評価関数をいじったり、貪欲と合わせたりいろいろしたがスコアはむしろ下がる。

7:00 ビーム幅調整とか色々するがスコアが上げられる方針が一向にみつからない。

8:00 連続列を選ぶところをビームサーチの遷移にするようなのを考える。連続列の候補を何個か貪欲で選んでそれを遷移にするようなのを考える。

10:00 実装途中にとんでもない事実に気がつく。priority_queueの中身の順序がまずいので評価値順に並んでいないのとか評価値が低い方からk個選ぶようなとんでもないコードになっている。まともに直したらビームサーチ部分がやたら時間がかかるようになってビーム幅が2になった…
提出したら805260点で121位/224相当になる。目標の80万にとりあえず届いてよかった。

感想

とりあえず80万点は届いてよかった。ただ時間かけすぎだったり連続列をつくるべきなのに気づくのが遅すぎたり色々反省。ビームサーチとか手元にジャッジ環境つくるのとか何となくマラソンの雰囲気がわかったので色々やっていきたい。コードの管理がひどかったのでこれからはちゃんとgitで管理したい。

解説記事を読んで復習しようとしたがtopcoderのMMが始まってしまったのでそっちが一区切りついたら復習して追記するつもり。

ABC074 D Restoring Road Network

競技プログラミング AtCoder

問題ページ
D - Restoring Road Network

考えたこと

問題を読むとワーシャルフロイドの逆をやるらしい。それぞれの頂点間にA[i][j]の長さの辺があるのを初期状態として、どの辺を減らせるかといった方針で考える。i->k->jと移動した時、A[i][j]と同じコストで移動できるならi->jへの辺はなくても問題ないはず。また、A[i][j]より小さいコストであれば前提がおかしいのでそのようなグラフは存在しない。 したがってO(N^3)で中間となる頂点kと2頂点i, jについて消せる辺を求めて残っている辺の長さが答えになると思って出したら通った。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[305][305], dp[305][305];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) REP(j, n) cin >> a[i][j], dp[i][j] = a[i][j];

  REP(k, n) REP(i, n) REP(j, n) {
    if(k == i || k == j || i == j || dp[i][k] == INF || dp[k][j] == INF) continue;
    if(dp[i][k] + dp[k][j] == a[i][j]) {
      dp[i][j] = INF;
    } else if(dp[i][k] + dp[k][j] < a[i][j]) {
      cout << -1 << endl;
      return 0;
    }
  }

  ll sum = 0;
  REP(i, n) REP(j, n) if(dp[i][j] != INF) sum += dp[i][j];
  cout << sum/2 << endl;

  return 0;
}

SRM616 div1 easy WakingUp

競技プログラミング SRM

考えたこと

とりあえず周期性がありそう。全てのアラームが鳴るタイミングまで進めばあとは周期lcmで繰り返されそう。10以下の整数のlcmは5*7*8*9=2520で計算量的には問題なさそう。周期の部分が負なら必ず起きそうなので-1を返すことにする。サンプル3で全てのアラームが鳴るタイミングが求められない。よくよく考えるとそもそも鳴るタイミングの偶奇が一致しないパターンも存在するし全てのアラームが鳴るタイミングがないパターンがある。このあたりを例外処理したつもりの怪しいコードを書いて出してみる。案の定落ちる。
解説記事を読むとそもそも全てのアラームが鳴るタイミングまで進まなくても周期lcmの周期性があるらしい。言われてみれば自明。imosを使ってシミュレーションを書くと通った。

学び

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b) {
  return a/gcd(a, b)*b;
}

int imos[3010];
class WakingUp {
   public:
   int maxSleepiness(vector<int> p, vector<int> s, vector<int> v, int D)
  {
    int n = p.size();
    memset(imos, 0, sizeof(imos));
    REP(i, n) {
      int j=s[i];
      while(j<2521) imos[j]-=v[i], j+=p[i];
    }
    FOR(i, 1, 2521) imos[i] += D;
    FOR(i, 1, 2521) imos[i] += imos[i-1];
    if(imos[2520] < 0) return -1;
    int ret = INF;
    FOR(i, 1, 2521) chmin(ret, imos[i]);
    if(ret >= 0) return 0;
    else return abs(ret);
  }
};

SRM615 div1 easy AmebaDiv1

SRM 競技プログラミング

考えたこと

Xに含まれないサイズはそのサイズを初期サイズとすれば最終サイズも等しくなるので必ずSに含まれる。Xに含まれるサイズを全て試せばいい。
実装したら通った。ものすごい簡単で逆に驚いた。

// BEGIN CUT HERE
// END CUT HERE
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

map<int, bool> mp;
class AmebaDiv1 {
   public:
   int count(vector <int> X)
  {
    int n = X.size();
    REP(i, n) mp[X[i]] = false;
    for(auto i: mp) {
      int now = i.first;
      REP(j, n) {
        if(now == X[j]) now *= 2;
      }
      if(mp.find(now) != mp.end()) mp[now] = true;
    }
    int ret = 0;
    for(auto i: mp) if(!i.second) ret++;
    return ret;
  }
};

SRM614 div1 easy MinimumSquare

SRM 競技プログラミング

概要

xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。

考えたこと

x座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせたりした結果1時間くらい実装にかかる。サンプルを試すと落ちる。よくよく考えてみると貪欲が嘘。二分探索を思い浮かべ幅Xの正方形をつくることができるかの判定について考えてみる。各頂点が正方形の4隅になるパターンを試して判定するコードを実装するとサンプルが通った。提出するとシステスで落ちる。よくよく考えると二分探索の判定が嘘（4隅以外にすべきパターンが自明に存在する）。
解説記事を読むと2辺固定すればk点を貪欲に取れるのでO(n^3logn)で解けるとある。実装するとk=1のときの処理がバグっていてシステスで一回落とす。k=1で4を返すようにしたら通った。
色々難しく考えすぎて方針迷走&&実装バグらせまくりと色々ひどかった。n <= 10^5に慣れすぎてn <= 100が解けない。

学び

オーダーが大きめの解法もちゃんと思考に入れる。誤読しない。変な実装ミスをしない。

// BEGIN CUT HERE
// END CUT HERE
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a <= x && x < b)
#define MP make_pair
#define PB push_back
const int INF = (1LL << 30);
const ll LLINF = (1LL << 60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
// #define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class MinimumSquare {
public:
  long long minArea(vector<int> X, vector<int> Y, int K) {
    int n = X.size();
    if(K == 1) return 4;
    ll ret = LLONG_MAX;
    REP(i, n) FOR(j, i+1, n) {
      ll sx = min(X[i], X[j]), gx = max(X[i], X[j]);
      VL v;
      REP(k, n) if(sx<=X[k] && X[k]<=gx) v.PB(Y[k]);
      if((int)v.size() < K) continue;
      sort(ALL(v));
      ll l = LLONG_MAX;
      FOR(k, K-1, v.size()) {
        chmin(l, v[k]-v[k-K+1]);
      }
      l+=2;
      chmax(l, gx-sx+2);
      chmin(ret, l*l);
    }
    return ret;
  }
};

AOJ0633 ぬいぐるみ

AOJ 競技プログラミング

問題ページ
Plush Toys | Aizu Online Judge

解法

bitDPをする。dp[S] = (集合Sの要素に含まれる種類を左から並べたときの最小の並べ替え回数) とする。dp[S|1<<i] = dp[S] + (並び替えに必要な回数) と遷移できる。並べ替えに必要な回数は並べる区間に含まれていない種類iの個数なので、種類別に累積和を取っておけばO(1)で求めることができる。したがってO(M2^M)で解ける。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], b[25][100010], cnt[25];
PII dp[1LL<<20];
signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, n) {
    cin >> a[i];
    cnt[a[i]-1]++;
    b[a[i]-1][i] = 1;
  }

  REP(i, m) FOR(j, 1, n) b[i][j] += b[i][j-1];

  REP(i, 1LL<<20) dp[i] = {INF, INF};
  dp[0] = {0, 0};

  REP(i, (1LL<<m)-1) REP(j, m) if(!(i>>j&1)) {
    int tmp = dp[i].second == 0 ? 0 : b[j][dp[i].second-1],
        kind = b[j][dp[i].second+cnt[j]-1] - tmp;
    chmin(dp[i|1LL<<j], MP(dp[i].first+cnt[j]-kind, dp[i].second+cnt[j]));
  }

  cout << dp[(1LL<<m)-1].first << endl;

  return 0;
}

JOI2008 春合宿 Cheating

AOJ 競技プログラミング

問題ページ
http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf

考えたこと

最大の最小化と言われたので二分探索をする。幅Xで実現することができるかの判定について考える。x方向、y方向についてそれぞれ貪欲に決めていくと幅Xで必要なカメラの台数をO(M)で判定できる。したがってO(Mlog(max(X,Y)))で解くことができ間に合う。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int n, m;
VI x, y;

bool check(ll mid) {
  int tmp = 0;
  // x方向
  int i = 0;
  while(i < (int)x.size()) {
    int st = i;
    while(i < (int)x.size() && x[i] - x[st] <= mid) ++i;
    ++tmp;
  }
  // y方向
  i = 0;
  while(i < (int)y.size()) {
    int st = i;
    while(i < (int)y.size() && y[i] - y[st] <= mid) ++i;
    ++tmp;
  }
  if(tmp <= n) return true;
  return false;
}

signed main(void)
{
  cin >> n >> m;
  REP(i, m) {
    int xx, yy;
    cin >> xx >> yy;
    x.PB(xx); y.PB(yy);
  }

  sort(ALL(x));
  x.erase(unique(ALL(x)), x.end());
  sort(ALL(y));
  y.erase(unique(ALL(y)), y.end());

  // (low, high]
  ll low = -1, high = 1000000000;
  while(high-low>1) {
    ll mid = (low+high)/2;
    if(check(mid)) {
      high = mid;
    } else {
      low = mid;
    }
  }

  cout << high << endl;

  return 0;
}