RUPC2019参加記 Day1

Posted on 2 mins read

※この記事は問題のネタバレを含みます

はじめに

立命館大学競技プログラミング合宿2019(RUPC2019)に参加してきました。

こういった競プロの合宿に参加するのは初めてだったのですが、いろいろな人と交流したり、初対面の人と一緒に問題を考察したりするのは楽しかったです。
コンテストも教育的な問題が多く、勉強になりました。
運営の方々、交流してくださった方々ありがとうございました。

コンテスト

@Kutimoti_Tさん、@hogemochiさんと組みました。
初日で緊張していたのですが、声をかけていただいてありがたかったです。

問題は、立命館大学の3時間のセットでした。
コンテストでは、解ける問題を手分けして早めに通せたと思います。

C、Dはチームメイトがいつの間にか通してくれていました。
Fが思いつかなかったのが悔しかったですが、勉強になる問題でした。

内容

B: たぬきつね

順番にシミュレーションするだけ

char f(char a, char b) {
  if (a == 'T' && b == 'F') return 'F';
  return 'T';
}
signed main() {
  int n; cin >> n;
  vector<char> a(n); REP (i, n) cin >> a[i];
  char ans = f(a[0], a[1]);
  REPI (i, 2, n) {
    ans = f(ans, a[i]);
  }
  cout << ans << endl;
}

E: LISum

LISをlower_boundを使ったdpで求めると、sumが最も小さいものになります。
よって、sumが最も大きいLISものを求めるには、全要素を-1倍したもののLISを逆から求めればよいです。

signed main() {
  int n; cin >> n;
  vector<int> a(n); REP (i, n) cin >> a[i], a[i] = -a[i];
  reverse(ALL(a));
  vector<int> dp(n, 1e17), sum(n + 1, -1);
  REP (i, n) {
    int idx = lower_bound(ALL(dp), a[i]) - dp.begin();
    dp[idx] = a[i];
    chmax(sum[idx], (idx == 0 ? 0 : sum[idx - 1]) - a[i]);
  }
  REP (i, n + 1) {
    if (sum[i] == -1) {
      cout << sum[i - 1] << endl; return 0;
    }
  }
}

上で書いたのが想定解だったようですが、セグツリー(BIT)を更新していくだけでも解けるという知見を得ました。
LISをセグツリーで解く方法は応用の幅が広そうです。

F: Absum

コンテスト終わってから@tempura_cppさんから解説を聞いて天才だなあと思いました。

G: イルミネーション

後で通して追記することをここに宣言しておきます。

その他

  • 新幹線に乗るときは学割を取りましょう。
  • 会場に向かう途中でほげもちさんに会ってお話しました。
  • この日の深夜のこどふぉに出てレートを溶かしました。

day2に続きます。