Codeforces - Lyft Level 5 Challenge 2018 - Final Round (Open Div. 2)

バーチャルコンテストをやって自分が解けたところまで解説します。 後で自分で書いて思ったのですが問題概要読むよりは問題をGoogle翻訳したほうが良いかも


A. The King's Race

http://codeforces.com/contest/1075/problem/A

問題概要

白と黒の2人の王がいる。 最初の王の座標は白が(1,1)で黒が(n,n)。
メダルが(x,y)にある。 それぞれの王は8近傍のいずれかに移動可能。 白の王から最適に行動した時、先にメダルを取るのは誰か?

解説

白の王がメダルにたどり着くターン数はW = max(x-1,y-1)である。 また、黒の王が目ダリにたどり着くターン数はB = max(n - x, n - y)である。 W <= Bのとき 白の王が勝ち、そうでないときは黒の王が勝つ

ソースコード

http://codeforces.com/contest/1075/submission/45375546


B. Taxi drivers and Lyft

http://codeforces.com/contest/1075/problem/B

問題概要

数直線上にタクシードライバーと住民がいる。 住民がタクシードライバーを呼ぶ時一番近いタクシードライバーが選ばれる(ただし、同じ距離のものがあるときはindexが小さい方が選ばれる) タクシードライバーそれぞれの住民に選ばれる人数を出力せよ

解説

それぞれの住民の左にいる一番近いタクシードライバーと右にいる一番近いタクシードライバーを比較すると実装が楽。 {右, 左}にいる一番近いタクシードライバーのindexは累積{max,min}を使えばいい。

ソースコード

http://codeforces.com/contest/1075/submission/45376803


C. The Tower is Going Home

http://codeforces.com/contest/1075/problem/C

問題概要

(この問題ではxの値が大きいほど上、yの値が大きければ右にいます) (10 ^ 9) * (10 ^ 9)サイズのチェスボード上にルークが(1,1)においてある。 また、以下のような線が何本か引かれている。

  1. y軸に平行でx[i]とx[i] + 1に引いてある直線(これがn本)
  2. x軸に平行でy[i]とy[i] + 1の間に始点がx1[i]で終点がx2[i]の線分(これがm本)

ルークは線の上を渡ることができない。 任意の回数ルークを移動させて(1,1)からy = 109を満たすいずれかの場所に到達可能になるためには最小で何本の線を取り除けばいいか

解説

x軸に並行な線は始点のx座標が1でなくてはいけない(そうじゃなければルークの進行に影響はない) y軸に並行な線を左からi(0 <= i <= n)個取り除いた場合、x軸に並行な取り除くべき線は何個あるかをカウントすればいい。 取り除くべきx軸に平行な線はx軸に並行な線分のうち始点のx座標が1であり、終点がx[i]のものである。 二分探索(lower_bound)を使えばこれはO(log m)で求められる。 これをy軸に平行な線を左から一つづつ消した場合のそれぞれの値を求めることになるで計算量はO(n log m)となる。

ソースコード

http://codeforces.com/contest/1075/submission/45377479


D. Intersecting Subtrees

http://codeforces.com/contest/1075/problem/D

問題概要

インタラクティブ問題。 あなたとLi君に木が与えられる。 与えられる木の形は同じだが頂点のラベルは異なる。 あなたの木とLi君の木の部分木に色が塗られている。 あなたは以下の5回以内の質問であなたとLi君の木の同じ位置(ラベルが同じとは限らない)で色が塗られている場所を答える(存在しない場合もある)。 質問 - 質問A あなたの木の頂点xと同じ位置のLi君の木の頂点の番号を答える - 質問B Li君の木の頂点xと同じ位置のあなたの木の頂点の番号を答える

解法

最初質問Bを行う。この時指定する頂点はLi君が持っている木の色が塗られている頂点を選ぶ。この時返ってきた答えをsとする。 あなたの木でsから任意の頂点の距離を求める。 次に色が塗られていて一番sから近い頂点をtとする。 木の特性上これは一つに定まる。 次に質問Bを行う。この時指定する頂点はtとする。 この時返ってきた答えをuとする。 uがLiくんの色が塗られている頂点ならそれが答えとなる。 そうでなければそのような頂点は存在しない。

ソースコード

http://codeforces.com/contest/1075/submission/45379785

ABC113

A


解法

A + B / 2を出力する

ソースコード

beta.atcoder.jp

 

B


解法

abs(A - (T - 0.006 * H[i]))が一番小さいiを出力する

ソースコード

beta.atcoder.jp

 

C


解法

県ごとに市が誕生した年順にソートして番号を割り振る
実装方針としては以下の通り。

  1. 1.vector<vector<pair<int,int>>>型の変数vvを用意する。
  2. vv[i]にpair<int,int>の要素を追加していく。追加される要素の変数名をeとした時、e.firstは年代を表しe.secondはid(何行目に登場したか)を表す。
  3. vv[i](i = 1 ~ M)をそれぞれソートする。
  4. 最初の6桁をi, 次の6桁をvv[i][j].firstとしたものをans[vv[i][j].second]に代入する。

(言葉で説明すると難しかったのでソースコードを見てください><)

ソースコード

beta.atcoder.jp


D


解法

動的計画法を用いて考える。
以下に深さという単語を用いるがここでいう深さとはスタート地点の深さを0として横線を設置可能な場所を超えるたびに深さは1増えるものとする。
dpを以下のように定義する。

  • dp[i][h] := スタート地点(縦棒1の一番上)から初めた場合、深さがhのとき縦棒iに達する組み合わせの数。
  • dp[1][0] = 1とする。

こう定義した場合dp[i][h]の遷移先は以下の通りになる。

  • dp[i - 1][h + 1]
  • dp[i][h + 1]
  • dp[i + 1][h + 1]

それぞれの遷移が意味することを考えてみる

  • dp[i][h]からdp[i-1][h + 1]に遷移するということは深さhとh+1の間の縦棒i-1とiの間に線を引くということである。

すなわち

  • dp[i - 1][h + 1] = (1 ~ i-2の間に線を引く組み合わせ数) * (i+1 ~ Wの間に線を引く組み合わせ数) * dp[i][h]

となる。

(xからyまでの間に線を引く組み合わせ数)を求めることを考える。
xからyまでの間に線を引く候補はy - x 個ある。
これはy - x個のボールを隣り合う2つが同時に選ばれないように選ぶ組み合わせと同じである。
func(n)を以下のように定義すると(xからyまでの間に線を引く組み合わせ数)はfunc(y - x)となる。

  • n <= 0のとき、 func(n) = 1
  • それ以外のとき、 func(n) = func(n-1) + func(n - 2)

すなわち

  • dp[i - 1][h + 1] = func(i - 3) * func(W - i - 1) * dp[i][h]

となる。
同様に考えると

  • dp[i + 1][h + 1] = func(i - 2) * func(N - i - 2) * dp[i][h]
  • dp[i][h + 1] = func(i - 2) * func(W - i - 1) * dp[i][h]

となる。

 

こうやってdpを求めると答えはdp[K][H]となる。

ソースコード

beta.atcoder.jp

 

AGC023-C Painting Machines

問題概要

・N個のますとN-1個のペイントマシーンがある。

・最初、ますはすべて白

・ペイントマシーンiはiとi+1のますを黒にする。

・ペイントマシーンを順列Pの順番で稼働させる

・すべてのますが初めて黒になったとき、ペイントマシンがK回稼働していたらその順列のスコアはKとなる。

・すべての順列でのスコアの総和を求める。

解法の概要

マシンをK回動かしたときにすべてのますが黒になっている順列の数をf(K)とする。

スコアがちょうどKとなる順列はf(K) - f(K-1)個ある。したがってΣ[K = 1...N-1]K*(f(K)-f(K-1))が答えとなる。

解法

f(K)を求める。最初のK回に動かすマシンをA型、そうでないものをB型とする。(B型のマシンは必ずすべてのますが黒に塗られた後に稼働する)それぞれのマシンをA型かB型かを決める通り数をg(K)とする。

ここで、B型のマシンの両隣は必ずA型のマシンになることに注意する。したがってA型のマシンとA型のマシンの間にあるB型のマシンは最大で1つである。

g(K)は(K-1)個あるA型のマシンとA型のマシンの中から(N-1-K)個選んでB型のマシンを配置する組み合わせなのでg(K) = C(K-1,N-1-K)がなりたつ。(Cは二項係数)

A型のマシンの順列はK!、B型のマシンの順列は(N-1-K)!なのでf(K) = C(K-1,N-1-K) * K! * (N-1-K)!となる。

あとはf(1),f(2),...f(N-1)を求め、それを利用してΣ[K = 1...N-1]K*(f(K)-f(K-1))を求めれば答えが求まる。

 

 

 

 

Competitive Programming Advent Calendar 2017

Competitive Programming Advent Calendar 2017の5日目の記事です。 アドベントカレンダーを書くのはこれが初めてのため当日0時に公開することを知りませんでした。すみません。 普段自分が競プロするときに使っているエディタCLionについて書きます。 設定ファイルを弄るようなすごいことはしていないため過度な期待はしないでください><

CLion is 何?

CLionはJetBrain社のC/C++IDEです。 JetBrain社はIntelliJ IDEAなども出してる会社です。有料のIDEAですが学生は無料で使えます!!!

CLionを使う理由

1. デバッグができる

  • これが主な理由です。

2. コード補完機能がある。

  • 元からある関数だけでなく、自分で書いた変数や関数まで予測してくれる。

3. VisualStudioはMacではC++が使えない。

4. VisualStudioCodeも設定が面倒

5. 他によいIDEを知らない><

  • 知ってる方いたら教えてください

基本的な使い方

1. プロジェクトを作成

  • CLionを起動した直後に「New Project」を押します。
    f:id:homesentinel2147483648:20171205163522p:plain
    起動後
  • その後プロジェクトを作成する場所をLocation:に入力して「create」を押します。
    f:id:homesentinel2147483648:20171205163533p:plain
    プロジェクトを作成
  • 2回目以降は作成したプロジェクトを左側から選びます。
    f:id:homesentinel2147483648:20171205163526p:plain
    プロジェクトを開く

2. main.cppにコードを書く

f:id:homesentinel2147483648:20171205163518p:plain

3. 実行

  • 右上の緑色の矢印を押すとコードが実行されます!実行結果は↓に表示されます。 f:id:homesentinel2147483648:20171205163540p:plain

デバッグ方法

続いてはデバッグ方法を紹介します。

1. ブレークポイントをつける

2. デバッグボタンを押す

  • 右上の緑色のむしさんをクリックしてデバッグします。

3. デバッグ中の操作

  • ↓の図のようなものがでてきます。これがデバッグウィンドウです。 f:id:homesentinel2147483648:20171205163537p:plain

  • 主に知っておけば良い機能は3つあります

    1. f:id:homesentinel2147483648:20171205163502p:plainStep Over : 次の行に進む,関数があってもその関数の中には行かない
    2. f:id:homesentinel2147483648:20171205163505p:plainStep Into : 次の行に進む。関数があればその中に行く。
    3. f:id:homesentinel2147483648:20171205163508p:plainRun to Curcor : マウスポインタのところまで進む。
    4. f:id:homesentinel2147483648:20171205163459p:plainResume Program : 次のブレークポイントまで進む。
    5. f:id:homesentinel2147483648:20171205163511p:plainEvaluate_Expression : グローバル変数の値をみる

ターミナル

  • 下のバーからTerminalを選択すればターミナルが使えます。

デメリット

学生以外だと有料

起動に時間がかかる

  • IDEなので仕方ないかなと

入力中に固まることがある

  • これは私の環境で起こっているだけかもしれませんが,vector<vector > v(num,vector(num)) の「,」を入力したときに重くなるときがあります。今後改善されると良いのですが...

さいごに

MacerやUbuntuerはCLion使ってみてください。

(競プロだけを考えた場合)CLionより優れているIDEがあったら教えてください。

ABC061 Dを解きました

ABC061 D - Score Attackを解きました

解法

  1. グラフを構築する。このとき辺のコストは正負を反転する。(今回の問題が最大コストを求める問題のため)
  2. ベルマンフォード法を使いスタートから各頂点までの最短経路を求める。(ただし最短距離の更新回数Vを頂点数とするとはV回までとする)
  3. もう一回ベルマンフォード法を用いる。このとき更新された頂点は無限に更新される。
  4. 頂点Nが3.で更新されてなければ最短経路を出力し、更新されていればinfを出力する。

自分の提出結果(http://abc061.contest.atcoder.jp/submissions/1673591)

感想とか

少しわかりづらい説明ですみません>< 今回気をつけるべきポイントは「負の閉路があるなら答えはinf」ではないということです。 例えば下図の場合出力すべき答えは132です。このとき4->5->6は負の閉路ですが7に至るまでの経路に関係ありません。 これに引っかかるって残り3つのWAが取れずに苦労しました><

f:id:homesentinel2147483648:20171010112320j:plain
図1

AGC016Aを解きました

AGC016 A - Shrinkingを解きました

解法

sに文字列を入力 変数ansに適当な大きい数を代入(今回は114514にした) C(Cは'a'から'z'の文字)について以下の操作を繰り返す
1. S に C + s + Cを代入する。
2. Sに含まれるCが出現する場所を配列Aに記録
3. A[i]-A[i-1] (1<= i < A.size)で最も大きいものをcntに記録
4. ansにansとcntのうち小さい方を代入
ansを出力

自分の提出結果(http://agc016.contest.atcoder.jp/submissions/1652193)

AGC013Aを解いた

A: Sorted Arrays - AtCoder Grand Contest 013 | AtCoder

AGC013Aを解きました

最初に思いついたWAな解法

  1. 配列BにB[i] に A[i] - A[i-1] (2 <= i < N) を代入する。 このときB[i] = 0ならB[i]にB[i-1]を代入する。
  2. 以降は以下の擬似コードのとおりにやる
  int ans = 1;
  for(int i = 2; i < N;){
    if(B[i]とB[i+1]の符号が異なる){
      iを2増やす;
      ansを1増やす;
    }
    //B[i]とB[i+1]の符号が同じ場合
    else{
      iを1増やす;
    }
  }
  ansを出力

この方法だと何故か2/14がWAになってしまい2~3時間くらい考えても原因はわかりませんでしたorz 解説を見てもなにがおかしいのかはわかりませんでした><

そこで以下のようにやり方を変えました

ACした解法

以下の擬似コードの通りにしました。

int flag = 0;
int ans = 0;
for(int i = 1; i < N; i++){
  if(flagが0){
    A[i+1] - A[i]が正ならflagに1を負ならflagに-1を0なら0を代入;
  }else{
    if(A[i+1] - A[i]とflagの正負が異なる場合){
      ansを1増やす;
      flagを0にする;
    }
  }
  
}
ansを出力

なぜかこの方法だとACしました。 ですが最初の方法でなぜWAになってしまったのか今でもわかりません><

今回は途中で大幅に方針を変更した結果うまくいきました。 WAの数が少なくても一からやりなおしたほうがいい場合もあるということですかね。