Heno World! チーム練習 2020年2月12日

• コンテストページ

https://codeforces.com/gym/102428

• コンテスト中のムーブ

てんぷら不在でスタート。

[0:06]テンプレートを書き、MをAC.

やむなくがEを解けたらしいので任せる。

この間にLを考察終了し、Iを読み始める.

[0:16]やむなくに完全に任せたEがAC.

[0:21]LをAC.

解かれてる問題どころか読まれてる問題がほとんど無い。2人と3人の違いを痛感___

[0:40]英語力不足でIの読解に100年かかるが、AC.

ここでGをパスされる。Gの解法がSAを利用すること以外思いつかないのにめちゃくちゃ通されてて泣く。

[0:50ぐらい]てんぷら起床、参戦

このあたりで、GとKを交互に実装するような感じになる。

[1:07]KがACされる.

[1:08]結局SAを使ってGをAC.

Dの解法をやむなくから共有される。

偏角sortしてmaxとminがπ以内であればいいのはわかるが、円環上になっているので判定が少し厄介。そこで、[0,pi/2),[pi/2,pi),[pi,3pi/2),[3pi/2,2pi)のそれぞれの区間で一番小さいやつを取ってきて、そこから反時計回りにpi以内に全点が載っているかを調べた。

ということがあって、

[1:32]DをAC.

[1:46]数え上げキラーがFをAC.

[2:04]CをAC.

ここから椅子温めコンが開幕する。

Aが全然わからず、貪欲を投げては落ちるを繰り返す...

[3:48]Aに諦めが付く。

[4:00ぐらい]Hの考察が終わる。同時期にJの考察が終わっているらしい。Aの新しいエスパー解を生み出す。

今まですっからかんだった実装キューに突然3つの刺客が。どうしてこうなった...

遷移を詰め切れていなかったので、先にJを書いてもらう。

[4:28]Jが通る。

[5:00]コンテスト終了

[5:11]Hが通る。惜しい...

• 反省点

正当性も無いのにAに執着してはいけない

てんぷらの家に凸して起こすべきだった

• おまけ(Hの解法)

dp[x][y][c]を、過去の自分の点がx点、相手の点がy点、このターンで自分がc点稼いでいる時の勝率、と定義します。こうすると、dpの遷移は、

dp[x][y][c]=max(val1,val2).

-----------------------------------------------------------

ただし、

//holdするとき

val1=1-dp[y][x+c][0]

//continueするとき

val2=0;

//1の目

val2+=(1-dp[y][x][0])/6.0

//それ以外の目(adと置く)

for(int ad=2;ad<=6;ad++){

  if(x+ad+c>75)val2+=(1-dp[y][x][0])/6.0

  else val2+=dp[x][y][c+ad]/6.0

}

----------------------------------------------------------

さて、この遷移をdfs等でやろうとすると、自分に帰ってきて循環してしまいます。

まず、dp[x][y][c]の遷移先にはdp[y][x][0]とdp[x][y][c+なんか]の形だけが登場し、dp[y][x][c]の遷移先にはdp[x][y][0]とdp[y][x][c+なんか]の形だけが登場することをふまえると、dp[x][y][~]とdp[y][x][~]を同時に考えたくなります。

ここで、次のような工夫をします。

1.x+yの大きい順に見る

これをすると、遷移部分のdp[x][y+c][0]やdp[y][x+c][0]は既に計算されていることになり、定数と考えてよくなります。

x==yとx!=yで場合分けします。

2.x==yのとき。dp[x][x][0]の値を二分探索する。

dp[x][x][0]の値を決めつけた時、先ほどの遷移を用いると、dp[x][x][0]の値が再計算できます。しかもこの再計算した値は、dp[x][x][0]の正しい値に近づくはずなので、例えば決めつけた値よりも再計算した値の方が大きい場合、正しい値は決めつけた値よりも大きくなります。

3.x!=yのとき。dp[y][x][0]の値を二分探索する。

上の場合とほとんど同じです。dp[y][x][0]の値を決め付けると、先ほどの遷移から、まずdp[x][y][0]の値が計算できます.このdp[x][y][0]の値を用いるとdp[y][x][0]の値が再計算できるので、あとは上と同じ理屈です。

以上により、全状態の確率が列挙できるので、クエリへの回答はholdの場合とcontinueの場合の確率をそれぞれ計算すればよいです。

(本番の実装では、c+x==74,c+x==75の場合だけ分けました。)