くるの競プロ記録

競技プログラミングの感想とか解説とか。

むしょくstreak9

競プロ

  • 黄diff考えつつ実装できていない。

開発

  • データ指向アプリケーションデザイン 5章
  • テスト駆動開発 21-24章
  • Effective Java 項目11,12
  • マスタリングTCP/IP 入門編 1.9 - 1.10
  • 安全なWebアプリケーションの作り方 3-3 CORS

セキュリティの方はまだ知ってることだけだなあって感じで読んでる一方で、ネットワークの方は知らない言葉だらけなのでなかなか読むのがしんどい。
既知の情報と未知の情報が半々ぐらいだと技術書読みやすいな。その点でデータ、テスト、javaはまあかなり読みやすい。

漫画

ゲーム

  • モンハン

 1日ずっとやってた。やっとHR7まで来た。上位の防具揃えたい。
 
その他

プログラミング全然しない日を作ってしまった。さすがにちょっとまずい。

むしょくstreak8

競プロ

  • 橙diff 1問
  • library checker 2問

 等差数列の多項式補間、fps多項式補間、多点評価を書いた。めっちゃ時間掛かった。
 黄diff埋めたらライブラリに時間割いてもいいなあってなった。盆栽は楽しい。


開発

 データ指向アプリケーションデザインが面白いね、まだ途中だけどそうなんだよな〜って思うところが多い、バックエンドやるならチームの皆に読んでほしいなって感じる。
 Effective Javaとspringの親和性を感じる。lombokって偉大なんだなってのが言語化されているね。

  • Code Deployのセッティング

 appspec.ymlが見つからないってお前な〜〜。
 趣味開発のEC2 to ECS移行を早くしないと......、先月のAWS代が結構掛かっててびびった。


漫画


ゲーム

  • モンハン

 やっと上位にいった。後は他人に頼りたい。twitterでやってる人に声かけて手伝ってもらわねば。他力本願......。


その他

  • 自炊をしなかった。

 今日は昼は肉じゃがの残りを食べて、夜は自炊をせずに出前を頼んだ。休みが続いても全部自炊はきついね。家事は何をやっても疲れる。
 主婦業?主夫業?の人とか毎日家事してる人本当にすごく感じる。

むしょくstreak7

競プロ

  • 多項式補間を書こうと思ったら多項式除算を持っていなくて、なんかfpsライブラリをチューニングしたくなってしまい泥沼に、、、なんとか明日ぐらいには終わらせたい。


開発

競プロに時間吸われて本も読めていない、スケジュール管理がダメ。



漫画

 やっと最新まで追いついた。最終巻楽しみ。


ゲーム


その他

  • 自炊をした。

 エビチリ作ろうと思ったけどエビとか処理したこと無いので鶏チリにした。こっちのほうが美味しいまであるね。

  • インターネットが開通した。

 モンハンやっていきたいね。

f:id:ningenMe:20210408000735j:plain

むしょくstreak6

競プロ

  • 黄diff 2問

開発

  • データ指向アプリケーションデザイン 2章
  • 安全なWebアプリケーションの作り方 3-2 受動的攻撃と同一オリジンポリシー
  • Effective Java 項目7,8
  • マスタリングTCP/IP 入門編 1.7 - 1.8
  • テスト駆動開発 9-13章

漫画

 マーレ編めっちゃ面白いな、カタルシスがありすぎる。みんな思想がちゃんと行動原理になってるの最高だな。



ゲーム



その他

  • 自炊をした。

 昼ナポリタン。夜は肉じゃがと卵焼き。
 ほんだしを使うことで卵焼きのかなり味がよくなったが、焼き目が目立つ。トレードオフなのか技術の低さなのか......。

f:id:ningenMe:20210407005343j:plain


丁寧に暮らしていきたいね。

AGC050. B - Three Coins

問題リンク。
atcoder.jp
サボってtex使ってないので表記が読みにくいかも。



flipする操作を愚直に管理すると、2^N個の状態があるのでかなり筋が悪そう。
とりあえずNが小さいときをシミュレーションする。

  • N = 1のとき

A[i]は3個そろってはじめて取得できるので、ans = 0

  • N = 2のとき

A[i]は3個そろってはじめて取得できるので、ans = 0

  • N = 3のとき

flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2])

  • N = 4のとき

端っこを無視して、flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2],A[1]+A[2]+A[3])

  • N = 5のとき

端っこを無視して、flipするかしないかなので、ans = max(0,A[0]+A[1]+A[2],A[1]+A[2]+A[3], A[2]+A[3]+A[4])

ここでN=4,5のときを踏まえると、3の倍数じゃないときは端っこ削って良さそうな感じがなんとなくする。
端を削ってN=3のときに帰着できそう。→区間dpっぽい。


半開区間[l,r)に関して、dp[l][r] := [l,r)がまだflipされていない(コインが置かれていない)ときの価値の最大値。と定義してみよう。
もう少しNを試すと

  • N = 6のとき

端っこを無視して、flipすると、
ans = max(0,dp[0][3],dp[1][4],dp[2][5],dp[4][6])

でもまだこれだけでは足りてなくて、全flipや、全flipした後一部戻すことも出来るので、
ans = max(0,dp[0][3],dp[1][4],dp[2][5],dp[4][6],A[0]+A[1]+A[2]+A[3]+A[4]+A[5], A[0]+A[4]+A[5], A[0]+A[1]+A[5])
となる。

ここで、dpの定義を再度考えると、N=5のときに帰着できるところがあるので
ans = max(0, dp[0][3]+dp[3][6], dp[0][5], dp[1][6], A[0] + dp[1][4] + A[4]+A[5], A[0]+A[1] + dp[2][5] + A[5])

一般化して書けそうな感じがしてくる。
とりあえず列を2個に分割するところは全探索で良さそう。そうすることでNが小さいときに帰着できる。

  • N = 7のとき

ans = max(0, dp[0][i]+dp[i][7])
7は3の倍数ではないので、N=6のときのように端だけ残すことは出来ず上記の遷移のみ。

  • N = 8のとき

N=7のときと同様。

  • N = 9のとき

N=6のときの遷移同様に、
A[0]+A[1]+dp[2][8]+A[8], A[0]+dp[1][7]+A[7]+A[8]が考えられる。
端を残して、サイズが3の倍数に中を切った後遷移させるのが何となく見える。

加えて、下記のようなものも可能性としてあり得る。
A[0] + dp[1][4] + A[4] + dp[5][8] + A[8]

サンプルで言うと下記のようなケース。

9
10
-1
-1
-1
10
-1
-1
-1
10

上記ももれなく拾える遷移を考えると、

ans = max(A[0] + dp[1][i] + A[i] + A[i+1][8] + A[8])
と書けそう。ここでiは[1,i)と[i+1,8)のサイズが3の倍数になるような整数。


よって、基本的には2分割。
さらに、3の倍数のときだけ中1マスを決めて、2分割。
のような遷移が考えられる。

これで全状態を満たしているかどうかは、未証明のままだが、とりあえずsubmitするとACが得られる(最悪)

#include <bits/stdc++.h>
using namespace std;
template <class T> void chmax(T& a, const T b){a=max(a,b);}
int N,A[500],dp[500][501];
int inf = 100*500+1;

//メモ化再帰
int rec(int l,int r) {
    //既に計算済ならreturn
    if(dp[l][r]>-inf) return dp[l][r];
    int n = r-l;
    //nが小さいなら愚直
    if(n< 3) return dp[l][r]=0;
    if(n==3) return dp[l][r] = max(0,A[l]+A[l+1]+A[l+2]);

    int res = 0;
    //区間を2分割
    for(int i=l+1;i<r;++i) {
        chmax(res,rec(l,i)+rec(i,r));
    }
    //3の倍数のとき、真ん中1点使って区間を2分割
    if(n%3==0) for(int i=l+1;i<r;i+=3) {
        chmax(res, A[l] + rec(l+1,i) + A[i] + rec(i+1,r-1) + A[r-1]);
    }
    return dp[l][r]=res;
}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N;++i) cin >> A[i];
    //-infで初期化
    for(int i=0;i<N;++i) for(int j=0;j<=N;++j) dp[i][j]=-inf;
    cout << rec(0,N) << endl;
    return 0;
}

atcoder.jp


800にしては実装かなり軽いけど、上記以外の遷移がないことを証明しろと言われるとあんまり分からないので、やっぱり難しい。

むしょくstreak5

競プロ

  • 青diff 1問

青diffでしょと思っていたAtCoder Jumperが全然わからず......。
atcoder.jp



開発

  • データ指向アプリケーションデザイン 1章
  • 安全なWebアプリケーションの作り方 3-1 HTTPとセッション管理
  • Effective Java 項目5,6
  • マスタリングTCP/IP 入門編 1.1 - 1.6
  • テスト駆動開発 1-8章

1年目のときにセキュリティもネットワークも勉強しなかったために今基礎からやる羽目に......。
データ指向アプリケーションデザインが面白いね、分散処理とか大学で勉強してみたかったな。どうして物理を......(n回目)



漫画

  • VRおじさんの初恋

よかった。感想はまた別記。



ゲーム

モンハンをやる時間を作らねば。



その他

  • 遊んでいた。

 清水寺などにいった。 


毎日遊んでいるね。遊んでくれる人がたくさんいることに感謝。
遊ぶ頻度減らして勉強しないとなと思いつつ、思うだけ!