ABC184参戦記 再々入緑しました

はじめに

2020年1月22日21:00-22:40に開催されたABC184に参戦しました。

結果は102分53分3ペナABCD４完で1761位／7822人、パフォーマンス1202でレートは+55となり800に。３度目の入緑となりました。

2020年10月17日に茶に転落してから１月余り、前回までの7回の出場中6回で冷えるなどなかなかレートが伸びずにいましたが、着実に力がついている実感はあり、めげずに続けていたところで初めての水パフォとなり嬉しいです。

A問題

制約の軽い行列式の計算。コーナーもなく単純な四則演算です。
１分ちょうど。

B問題

クイズの結果が〇×の文字列になっており，最終的な得点を求める問題です。
得点が０より低くならないことに気を付けて実装。
丁寧にサンプルを試して提出。
３分３９秒、通算４分３９秒。
まずまずです。

C問題

C - Super Ryuma

無限の盤面を動き回るスーパー竜馬の問題。
一見して面倒そうですが，いろいろ試すと最大３回で到達できそうなことがわかります。

引き算してa,bを原点にして単純化。もっとも引き算したのを忘れていてバグってたりもしました。
第一象限に移すと更に簡単だったか。

見かけのみならず実際にも相当面倒で，なかなかエラーがとれずに途中であきらめてD問題へ。

D問題が奇跡的に解けてコードを修正しトライしたところAC.

もっとも嘘解法だったみたいでafter contestに引っかかってました（自白）。

D問題

D - increment of coins

この問題が解けたのが今回のハイライトでした。

DPを再帰で解く練習をしており初期値の立て方や遷移式の組み方がだいぶ身についてきています。
もっともこの問題は最終的にDPで解いています。

DP[99][99][99]が１であること、DP[99][99][98]からDP[99][99][99]に１回かかることから遷移式を考えました。
期待値の線形性（平たくいうと単純に足せばいい）みたいなところも感覚は理解。

提出コード

#include <bits/stdc++.h>
using namespace std;

double dp[110][110][110];
 
int main(){
  int a,b,c;   
  cin>>a>>b>>c;
  dp[99][99][99]=1;
  dp[100][99][99]=1;
  dp[99][100][99]=1;
  dp[99][99][100]=1;
  
  for(int i=99;i>=0;i--){
    for(int j=99;j>=0;j--){
      for(int k=99;k>=0;k--){
        if(i==99 && j==99 && k==99) continue;
        double ans=0;
        if(i+1==100){
          ans+=(double)i/(i+j+k);
        }
        else{
          ans+=(double)i/(i+j+k)*(dp[i+1][j][k]+1);
        }    
        if(j+1==100){
          ans+=(double)j/(i+j+k);
        } 
        else{
          ans+=(double)j/(i+j+k)*(dp[i][j+1][k]+1);
        }          
        if(k+1==100){
          ans+=(double)k/(i+j+k);
        }
        else{
          ans+=(double)k/(i+j+k)*(dp[i][j][k+1]+1);
        }
        dp[i][j][k]=ans;
      }
    }
  }
  cout<<setprecision(15)<<dp[a][b][c]<<endl;
  return 0;
}
 

E問題

E - Third Avenue

残り時間で検討しましたがワープの処理をどうしていいのかわからず詰まりました。

終わりに

真面目に精進を重ねていれば、着実に力はつき、いつかはコンテストの成績に、そしてレーティングに反映するのだということを改めて実感しました。

今回は嘘がとおったり、たまたま直前に精進していたDPがでたり、みたいなラッキーが重なりましたが、水パフォを続けて出せるようになれば理論的には水色になれることが証明されているそうです。

楽しみながら続けていきます。