Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-06-24

[][] TopCoder TCO Round 2C Level2 (500) ThreePoints 20:09 はてなブックマーク -  TopCoder TCO Round 2C Level2 (500) ThreePoints - 練習帳

問題文

 問題文

概要

  • 2次元平面上にn点が与えられている。
    • どの2点をとってもx座標は等しくない。また、どの2点をとってもy座標は等しくない。
  • 次の条件を満たす3点の組(A, B, C)の個数を答えよ:条件「A[x] < B[x] < C[x]かつA[y] < C[y] < B[y]、ここでP[x], P[y]はそれぞれ点Pのx, y座標を表す」
  • 制限:n ≦ 300000, 点のx, y座標は0以上10**9未満の整数値

コード

 Practiceでの提出コード(gist):https://gist.github.com/2863529

 (SRM終了直後の感想戦とPracticeで解答例を見た後に作成しています)

考えた過程

方針

点vについて,vより右上にある点をR[v],左下にある点をL[v]とすると,答えはΣ_{v} R[v]*(R[v]-1)/2 - R[v]*L[v]となります.具体的には,x座標について点をソートし,(x座標が小さい点はy座標が何番目に小さいか)を計算します(上の提出コードではperm[i]で書いています).これの数え上げにはBITを用いています,

どうやって思いつこう

それぞれの点を上の条件の点Aに対応させ,各点Aに対してB, Cの組が何個あるかを考えます・・・(*).B, Cは両方とも必ず右上になければなりません.ただ,B, Cがすべての右上に全部が条件を満たす訳ではありません.なので(1)の問題の前に,B, Cの配置でどのようなものが条件を満たすかを考えてみます.そのために,まず2つの点の配置関係を考えてみます.すると,x, y座標が一致する点がないという条件があるので,/(一方が右上にある)という関係と\(右下にある)の関係しかない事が分かります.

うまく問題の条件を使って問題を簡単に出来たので,この方針は悪くなさそうです.

ナイーブな方法では数え上げられない

では,(*)の問題,すなわち,各Aに対して,B, Cが/の関係になっている組の数は何個あるかを計算します.これにはAより右上にあるそれぞれの点Bに対して,Bより右上にある点が何個あるかを求め,それをすべて足さなければなりません.すなわたい2重ループです.点が300000個あるので,n**2の計算はできません.これをどう解消するかがこの問題のポイントなのだと思います.それぞれの点について「自分より右上にある点の数」を保存しておく事は出来ます,これは後で使うかもしれないので念頭に置いておきます.

真ん中の点を用いて数え上げる

/の関係になっている3つ組全体の個数を数え上げるときにΣを2回計算しなければならないのは,左下の点について分類している為です。これを真ん中の点を用いて分類すると,前述のように(左上の点)*(右下の点)で数え上げられてしまいます.これは1重ループで計算できてしまいます.多分この部分に発想の飛躍がある所なのだと思います.後はそれぞれの点について右上にある点の個数だけではなく,左下にある点の個数も予めBITなどで計算しておけば、答えが得られます.

2011-06-19

[][] TopCoder Open 2011 Round1 19:39 はてなブックマーク -  TopCoder Open 2011 Round1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:12:15.506Passed System Test213.11
5001:02:27.079Opened0.00
10000:43:25.259Opened0.00
Challenge..0.00

部屋(Room 1) 16位,全体 1000位

Rating : 1548 → 1505 (-43)

上位800人がRound2に進出.easyを半分の時間で解くか,1回チャレンジを成功させると進出できたようです.

250 TripleStrings

 問題文

要約

 3つのString型の変数A, B, Cがあり,初めAに○と×からなる文字列(init)が格納され,B, Cは空文字である.次の操作のみを行って,Aの文字列を与えられた文字列(goal)に代えたい.その為に必要な最小手数を答えよ.行える操作は

  • Aの先頭の文字を除き,Bの最後尾に加える
  • Aの先頭の文字を除き,Cの最後尾に加える
  • Bの先頭の文字を除き,Aの最後尾に加える
  • Cの先頭の文字を除き,Aの最後尾に加える

初め,Aに格納される文字列の長さは1以上50以下で,初めの文字列と最後の文字列の○,×の個数は一致する.

方針

 initの後ろ部分とgoalの前部分で共通する文字列があれば,その部分をAに残しつつ

1. すべての○をAからBに,すべての×をAからCに移動させる

2. goalと同じ文字列になるようにB, CからAに○,×を戻す

の手順でgoalを作る事が出来る.従って,共通部分の最大長(maxLen)がわかれば,少なくとも(n - maxLen)*2回で操作は行える(nは文字列長).*2しているのは「A -> BorC」と「BorC -> A」の往復をしているため.

 逆にもしA -> BorCに文字を移動する回数がL (< maxLen)回で十分ならば,Aの[L+1, n]番目の文字はAに残ったままなので,これはgoalの先頭になければならない,しかしこれは共通部分の最大長を取ってmaxLenを決めた事に反する.従って,maxLenが最小回数.

コード例

 下のコードの

        if(goal[j] != init[n - i + j]){

の部分で,goalとinitを逆にした為に半分以上の時間を費やしてしまいました.

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
 
using namespace std;
 
class TripleStrings {
public:
  int getMinimumOperations(string init, string goal) {
    int n = init.size();
    bool flag = true;
    int mn = 0;
    for(int i = 0; i <= n; i++){
      flag = true;
      for(int j = 0; j < i; j++){
        if(goal[j] != init[n - i + j]){
          flag = false;
        }
      }
      if(flag){
        mn = i;
      }
    }
    return (n - mn) * 2;
  }
};

500 MuddyRoad

問題文

 問題文

要約

 Nマスのすごろく([0, N-1]で番号づけられている)があり,i番目のマスはroad[i]% の確率でぬかるんでいる.スタートからぬかるんでいるマスをできるだけ避けつつゴールを目指す.1回の行動で1マスor 2マス進め,全てのマスがぬかるんでいるかいなかったかが分かった状態で最適に行動できる.ぬかるんだマスを踏む回数の期待値を答えよ.

 マスの数Nは2以上50以下.road[i]は0以上100以下で,配列の最初と最後は0である(つまりスタート,ゴール地点はぬかるまない)事が保証されている.

方針

 以下の方針は同じ部屋だったlightning_31さんのコードをもとにしています.

TopCoder | Login

 dp[i][j]でi番目のマスにいて,しかもそれまでにj個のぬかるんだマスを踏んだ確率を現しています.マスを飛び越す事もあるので,dp[i][j]をjについて足しあげても合計が1にはなるとは限りません.

 i番目にいる時と考えます.最大2マス進めるので,i+1番目とi+2番目を考慮します.i+1番目とi+2番目がぬかるんでいるかで場合分けをします(下の(1)から(4)は排他的でかつ全体をつくしています)

  • case 1 : i+1 番目:ぬかるみ,i+2番目:ぬかるみ
    • この場合,i+3番目以降の状態に関わらず,2マス進み,i+2番目のぬかるみを踏むのが最適です
  • case 2 : i+1 番目:ぬかるみ,i+2番目:乾き
    • 前の場合と同様で2マス進みますが,i+2番目は乾いているので,踏んだぬかるみの数は変わりません
  • case 3 : i+1 番目:乾き,i+2番目:ぬかるみ
    • 1マス進むのはよいですが,問題はi+2番目を踏むかどうかです.じつは少し考えるとi+2番目は飛び越えると最適戦略(の一つ)とわかります.例えばi+1番目以降が
(○はぬかるみ,×は乾き)
×○○×・・・

となっていればi+2, i+4番目と進んでも,i+1, i+3と進んでも,この区間でぬかるみを踏む回数は1回のみです.しかし,後者ではi+5番目以降の状態を見てから,i+3 -> i+4と移動する事で,前者の進み方に合流することも出来ます.

 つまり,i -> i+1 -> i+3 (-> i+4(必要ならば))と進む方法はi -> i+2 -> i+4と進む方法に比べて少なくとも悪くなる事はありません.今はi+3番目以降が○×の場合のみを考えましたが,残りも同様(のはず)です.

  • case 4 : i+1 番目:乾き,i+2番目:乾き
    • 1マス進んでも2マス進んでも良いのですが.先ほどと同様に,1マス進んでそれ以降のマスを様子見するのが最適です.

 以上の場合分けは2マス先まである事を仮定しているので,もちろん最後から1マス前は別にしなければなりません.

 これをコードに落とすと次のようになります.

コード例
#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

class MuddyRoad {
public:
  double getExpectedValue(vector <int> road) {
    int n = road.size();
    double dp[55][55] = {};
    dp[0][0] = 1;
    for(int i = 0; i < n-1; i++){
      for(int j = 0; j < n; j++){
	if(i+2 < n){
	  dp[i+2][j+1] += dp[i][j] * road[i+1] * road[i+2] / 10000;     // case 1
	  dp[i+2][j] += dp[i][j] * road[i+1] * (100 - road[i+2]) / 10000; // case 2
	  dp[i+1][j] += dp[i][j] * (100 - road[i+1]) * road[i+2] / 10000; // case 3
	  dp[i+1][j] += dp[i][j] * (100 - road[i+1]) * (100 - road[i+2]) / 10000; // case 4 
	}else{
	  dp[i+1][j] += dp[i][j]; // case *
	}
      }
    }
    double ret = 0;
    for(int i = 0;i < n;i++){
      ret += dp[n-1][i] * i;
    }
    return ret;
  }
};

 上のコードの下のcase3とcase4は統合する事が出来,この2つを統合すると,前述のlightning_31さんと同じアルゴリズムに至りました.

分析

 自分で解いていた際は,e[i]で「i番目のまで進んだ時のぬかるんだマスを踏む回数の期待値」としてDPを行おうとしましたが,e[i]の更新の仕方が分からなかったです.「e[i]の計算を行うにはe[i-1]とe[i-2]の値が必要で,でも,一マスずつ進んだときの場合でe[i-1]の計算を行う時にe[i-2]が考慮されているだろうから,単純に足し合わせたらダブルカウントになるのでは」とか「2マス進む場合と1マスずつ進んだ場合は分けられるけれど,でも1マス進んだあとで実は次は2マス進んだ方が最適とわかったら,期待を計算するべきマスを飛び越える事なって計算に参入できない」...と深みにはまっていっきまいた.確率は受験生時代から苦手です.途中でモレダブりなく数え上げられているのかが分からなくなってきます.