BuildingCitiesダイクストラ法。任意の街iから街jについて、iとjを結ぶ線分上にmaxDirectごとに街を建設すれば、iとjの直線距離で移動できる。街iとiに到達するまでに建設した街の数jをペアにしたをノードとする。街iと街jの直線距離がdでb個の街を建設する…

Archery #include <vector> using namespace std; class Archery { public: double expectedPoints( int N, vector <int> ringPoints ); }; double Archery::expectedPoints( int N, vector <int> ringPoints ) { double p = 0; for ( int i=0; i<=N; i++ ) p += (double)ringP</int></int></vector>…

CandyBox箱の個数をnとすると、i回目の交換で箱jと箱kの飴が選ばれる確率はx=2(C/nC)(C/(nC-1))。交換前のそれぞれの箱の期待値をp, qとすると、箱jの期待値は(p-q)x/C増える。jもkも同じ箱が選ばれる確率はxではないけど交換に意味は無いので、まあいいか。…

AgeEncoding基数が大きくなるほど表す年齢も大きくなるので、二分探索。例外処理が面倒。蝋燭が0000ならば、-1。蝋燭が0001のとき年齢が1ならば-2、年齢が1以上ならば-1。蝋燭が0101のように最後の１本と他に１本以上立っていて、年齢が1ならば-1。 #include <string></string>…

Easy (250) 0 (Challenge Succeeded)age=1, candle="11"の場合だろうか。-1を返さなければならない。0でいいんじゃないかと思ったけど、0と答えの-1の誤差は1>=1e-9。age=1, candle="000000"の場合に気付いて勝ったと思っていたけど、同室だったid:wata_orz…

SteeplechaseTrack動的計画法。i個目のフェンスとしてフェンスjを跳んだ後の複雑さの最大値をci,jとする。ci,j = max{ ci-1,k | ci-1,kが有効で、k→jに道がある }である。全ての有効なci,jに終点までの複雑さを足したものの最大値を求める。 #include <string> #incl</string>…

TrappingRabbit意訳：トラップまでのマンハッタン距離の最小値を求めよ。 #include <vector> using namespace std; class TrappingRabbit { public: int findMinimumTime( vector <int> trapX, vector <int> trapY ); }; int TrappingRabbit::findMinimumTime( vector <int> trapX, </int></int></int></vector>…

ColoringRectangle大きい順で赤青交互に並べていく。赤から始める場合と青から始める場合の両方試す。 #include <vector> #include <algorithm> #include <cmath> using namespace std; class ColoringRectangle { int choose( int width, int height, vector<int> d1, vector<int> d2 ); public:</int></int></cmath></algorithm></vector>…

Easy (300) 161.04いまいち正当性に自信が無かったけど、あっていたようだ。Medium (500) 0街と増設した街の数をペアにしたダイクストラ法かなと思いつつも実装しきれず。Hard (1000) 0見てない。結果 1448 → 1520黄色になれた。

TheFansAndMeetingsDivOneまず、JohnとBrusのそれぞれがl人のファンに会う確率を動的計画法で求める。Johnがi番目までの街の中からj個の街を訪れてl人のファンに会う確率をpJi,j,lとすると、 pJi,0,0 = 1 pJi,0,l = 0 (l>0) pJi,j,l = Σ[m=minJ[i-1],maxJ[i-…

TheCitiesAndRoadsDivTwo試合中の正解者無し。与えられた辺を含む全域木は何通りあるかという問題。全域道（こんな用語あるのだろうか？）は何通りかと勘違いしていた。連結している街に同じ数字を割り振って、数字の異なる街に辺を追加していく。 #include <string></string>…

TheFansAndMeetingsDivTwoJohnがi人のファンに会う確率pJ[i]と、Brusがi人のファンに会う確率pB[j]を求める。答えはその内積。 #include <string> #include <vector> #include <numeric> using namespace std; class TheFansAndMeetingsDivTwo { public: double find( vector <int> minJ, v</int></numeric></vector></string>…

TheQuestionsAndAnswersDivOne問題の把握に手間取った。例えば、questions=2, answers={"Yes","No","Yes"}として、質問をQ1, Q2とすると、可能な質問の順番は (Q1,Q2,Q1) (Q2,Q1,Q2) の２つ。(Q1,Q2,Q2)のような順番はQ2がYesにもNoにもなっているので不可。…

TheQuestionsAndAnswersDivTwo #include <string> #include <vector> #include <set> using namespace std; class TheQuestionsAndAnswersDivTwo { public: int find( vector <string> questions ) { return 1 << set<string>( questions.begin(), questions.end() ).size(); } };</string></string></set></vector></string>

Easy (250) 113.07題意の把握に時間が掛かった。Medium (500) 0わかんね。Hard (1000) 0見てない。結果 1416 → 1448ちょっと増えた