---
title: 'AtCoder Beginner Contest 266'
disqus: hackmd
---

AtCoder Beginner Contest 266
===

[TOC]
## string [A - Middle Letter](https://atcoder.jp/contests/abc266/tasks/abc266_a)
:::info
輸出中間那個數。
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 1e9
 
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  string s;
  cin>>s;
  cout<<s[s.size()/2]<<'\n';
  return 0;
}

## mod [B - Modulo Number](https://atcoder.jp/contests/abc266/tasks/abc266_b)
:::info
x=n+k倍的MOD(998244353)，所以加到變成正數，再模MOD。
k慢慢跑會TLE(次數至多=$10^{18}/MOD+1$)，所以設定k每跑一次，k會變成前一次的k*2。
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define MOD 998244353
 
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n;
  cin>>n;
  for(ll i=1;i<1000000000;i*=2){
    if(n>MOD) break;
    n+=i*MOD;
  }
  cout<<(n-MOD)%MOD;
  return 0;
}

## dp [D - Snuke Panic (1D)](https://atcoder.jp/contests/abc266/tasks/abc266_d)
:::info
開兩個陣列x[t]、a[t]，記錄在t時刻的蟲座標及果實大小。
這題看起來就很dp[i][j] (前後位置有關)，那就來嘗試用dp解吧!
先思考dp[i][j]如何定義
* 定義dp[i][j]是在位置為i、時刻為j時，所能吃到最大size的蟲。

i介於0~4、j 介於0~$10^5$，所以設定陣列大小為dp[5][n]，
再來思考dp[i][j]可能由何者遞迴得到
1. dp[i][j-1]而得(站在原地一秒鐘)
2. dp[i-1][t-1]而得(往右走一步)
3. dp[i+1][t-1]而得(往左走一步)

最後把上面三個取max=dp[i][j]。
記得在dp[i][j]的時刻及位置可以吃到a[t]大小的蟲，要加上去。
最後所求=時刻為$10^5$，在每個位置所能吃到的最大size。
:::
:::danger
注意下面的code:t跟i不能顛倒，不然會產生吃了又吃的問題。
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define n 100010
ll t,x[n],a[n],dp[n];
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll maxi=0;
  ll dp[5][n]; 
  for(ll i=1;i<5;i++) dp[i][0]=-1e18;
  ll N;
  cin>>N;
  for(ll i=0;i<N;i++){
    cin>>t;//t->唯一的x[t]、a[t]
    cin>>x[t]>>a[t];
  }
  for(ll t=1;t<=100000;t++){
	for(ll i=0;i<5;i++){
	    dp[i][t]=dp[i][t-1];
		if(i!=0)dp[i][t]=max(dp[i][t],dp[i-1][t-1]);
		if(i!=4)dp[i][t]=max(dp[i][t],dp[i+1][t-1]);
	}
	dp[x[t]][t]+=a[t];
}
  for(ll i=0;i<5;i++) maxi=max(maxi,dp[i][100000]);
  cout<<maxi<<'\n';
  return 0;
}

## 遞迴 [E - Throwing the Die](https://atcoder.jp/contests/abc266/tasks/abc266_e)
:::info
這題的關鍵在於構造遞迴關係式，我們來思考
1. 第1回合的期望值=f(1)=1*$\frac{1}{6}$+2*$\frac{1}{6}$+3*$\frac{1}{6}$+4*$\frac{1}{6}$+5*$\frac{1}{6}$+6*$\frac{1}{6}$+=3.5
2. 第2回合的期望值=f(2)=max(1,f(1))$\frac{1}{6}$+max(2,f(1))$\frac{1}{6}$+max(3,f(1)) $\frac{1}{6}$+max(4,f(1))*$\frac{1}{6}$+max(5,f(1))$\frac{1}{6}$+max(6,f(1))$\frac{1}{6}$+=4.25
(覺得骰子點數太少就再投一次，
期望拿到max(本次可能投擲的點數,投擲前一次的期望值)$\frac{1}{6}$點
3. 由2.可觀察出遞迴關係式:f(n)=max(i,f(n-1)),i=1~6

如果直接用f(n)下去遞迴到f(1)=3.5會發生一件事情:f(n)無法被確定，無法直接return f(n-1)(因為還要比大小)=>所以要先建表f(n)。
那不如反過來做，從x=1遞迴到x=n。
而從轉移式可知:我們只需要兩個變數紀錄f(n)、f(n-1)即可，所以開x,y分別記錄兩者，完整程式碼如下。
:::
:::danger
如何cout浮點數到小數點下第n位置:
利用cout<<fixed<<setprecision(10)<<數字/變數<<'\n';
:::

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define max(p,q)((p)>(q)?(p):(q))
#define N 1e9
int main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  ll n;
  double x=3.5,y;//x=f(x),y=f(x-1)
  cin>>n;
  for(ll i=2;i<=n;i++){
    y=0;
    for(ll j=1;j<=6;j++){
      y+=max(j,x)/6;
    }
    x=y;//交換
  }
  cout<<fixed<<setprecision(10)<<x<<'\n';
  return 0;
}