おかゆの競プロ日記(その他もあるよ)

主に自分の解いた問題を載せていきます。

Google Code Jam 2018 - Qualification Round

Saving The Universe Again 問題をざっと説明します. まず, 敵の攻撃力の初期値は 1 です. また, 敵は 2 種類の行動が可能で 'S' と 'C' で表されます. 入力では, この 'S' と 'C' からなる文字列 s が与えられます. 'S' : 攻撃(Shoot). 現在の攻撃力で攻撃…

ARC044-B : 最短路問題

ARC044-B : 最短路問題 なんとなく解いた問題で, 難しくはないんですがちゃんと考察したのでまとめておきます. 問題の概要は省いて考察をここに書きます. 与えられる入力を満たすようなグラフの種類はいくつあるかを答えるのですが, 入力で与えられるのは, …

AtCoder Beginner Contest 051

この記事は以前あったものをいろいろあって修正したものです 久しぶりの投稿です。 AtCoder Beginner Contest 051のB,C,Dを書きたいと思います。 B問題(B - Sum of Three Integers) 入力K,S(2 <= K <= 2500, 0 <= S <= 3K)が与えられ、3つの変数x,y,z(0 <= x…

POJ3000 - Frogger

この記事は以前あったものを色々あって修正したものです 今日から解いた問題をぼちぼち日記に残しておこうと思います(メモみたいなものなので解説ではありません)。 難易度的にはeasyからnormalと言ったところでしょうか… もしご覧になった方で「こうした方…

CSAcademy Round#53 C

CSAのソースコードのリンクが貼れない(わからない)ので久しぶりにブログに...(この記事は以前あったものを色々あって修正し直したものです) CSAcademy #Round53 - C(Histogram Partition) N個の色んな数字からなるAという配列とN個の要素すべてが0の配列Bが…

ABC082-D : FT Robot

ABC082-D : FT Robot 問題の概要はこちら 最初は O(N3) の dp(dp[i][x][y] := i 番目の命令の後に位置 (x, y) にいるかどうか)だと思ったんですが, これでは MLE かつ TLE してしまいます(工夫すれば MLE は避けられますが計算量はそのまま). しかし, 'F' は…