ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

Codeforces

Codeforces 455A : Boredom

概要 問題文はこちら http://codeforces.com/problemset/problem/455/A解法 動的計画法で解くことができる。ある値aを消すとa-1とa+1も消えてしまうため、dpの更新では ・dp[i + 1] = max(dp[i + 1], dp[i]) ・dp[i + 2] = max(dp[i + 2], dp[i] + aを消して…

Codeforces 456 B : Fedya and Maths

概要 問題文はこちら http://codeforces.com/problemset/problem/456/B解法 規則性を探していくと、解はn % 4 == 0 のとき4、それ以外は0になることが分かる。ソースコード #include <bits/stdc++.h> #define REP(i, x, n) for(int i = x; i < (int)(n); i++) #define rep(i</bits/stdc++.h>…

Codeforces 456A : Laptops

概要 問題文はこちら http://codeforces.com/problemset/problem/456/A解法 aとbをペアで持たせて、aを基準にソートする。 そのときbi > bi+1となるものがあれば条件を満たす。下のコードではmaxvとかやってるけど、なくてよい。ソースコード #include <bits/stdc++.h> #de</bits/stdc++.h>…

Codeforces 449B : Jzzhu and Cities

概要 問題文はこちら http://codeforces.com/problemset/problem/449/B首都と複数の町があり、それぞれの移動手段として普通の道と路線がある。首都から各町への最短距離を変えることなく路線の本数をできるだけ減らせという問題。解法 ダイクストラ法で解く…

Codeforces 449A : Jzzhu and Chocolate

概要 問題文はこちら http://codeforces.com/problemset/problem/449/Aチョコレートを割って複数個の欠片を作る。 その欠片の最小値を最大化する問題。解法 (あんまり納得はできてないけど)縦と横の両方から割るよりは片側から割りまくったほうが良いっぽい…

Codeforces 448D : Multiplication Table

概要 問題文はこちら http://codeforces.com/problemset/problem/448/D1 2 3 2 4 6 3 6 9みたいな行列が与えられたときにk番目に小さい値を探す問題。 (問題文にはlargestって書いてあるけど、んーって感じ)解法 二分探索で解くことができる。二分探索である…

Codeforces 448C : Painting Fence

概要 問題文はこちら http://codeforces.com/problemset/problem/448/Cフェンスにペンキで色を塗るときに塗る回数の最小値を求める問題。解法 再帰でうまい感じに解くことができる。ある区間においてフェンスの高さの最小値を求め、 ・フェンスの最小値分ま…

Codeforces 448B : Suffix Structures

概要 問題文はこちら http://codeforces.com/problemset/problem/448/B文字列s, tが与えられ、ある動作を行うことでsからtにできるかを判定する。動作は以下の通り。 ・automaton: 任意の文字列を削除 ・array: 任意の文字2つを入れ替える解法 条件に当ては…

Codeforces 448A Rewards

概要 問題文はこちら http://codeforces.com/problemset/problem/448/A主人公が持っているトロフィーとメダルを棚に入れたいという話。解法 トロフィーとメダルを入れる棚がそれぞれ何個ずつ必要か計算してやればよい。ソースコード #include <bits/stdc++.h> #define REP(i</bits/stdc++.h>…

Codeforces #192 div2

【結果】oooo- +0/-0 82th 1550 -> 1709http://codeforces.com/contest/330/standingsdiv1に上がる事ができましたし、レートのHighestも更新です。去年の12月頃からちょっと前まで競プロから離れていたのでここ最近はレートが落ちてばかりだったのでこの結果…

Codeforces 244B : Undoubtedly Lucky Numbers

概要 問題文はこちら http://codeforces.com/problemset/problem/244/B2つ以下の数字からなる値をundoubtedly luckyと呼びます。 (例) ・11(1のみ使用) ・404(0と4を使用)n(1 9)が与えられます。 n以下の値の中でundoubtedly luckyが何個あるかを求める…

Codeforces 244A Dividing Orange

概要 問題文はこちら http://codeforces.com/problemset/problem/244/A 解法 やるだけ問題です。ほしいミカンを先に配り、その後残ったミカンを配ればよいです。問題理解に時間がかかってしまいタイムロス。 ソースコード #include <iostream> #include <string> #include <algorithm> #in</algorithm></string></iostream>…

Codeforces #150 div2

oo--- +0/-0 193th 1622 -> 1655 (Highest)今回はCodeforces2度目の参加でした。 前回に引き続きレートが上がってとても嬉しいです。 この調子がいつまでもつだろうか…

Codeforces 233B : Non-square Equation

概要 問題文はこちら http://codeforces.com/contest/233/problem/Bx2 + s(x) * x - n = 0s(x)は各桁の数の和です。 1 18 解法 解く流れとしては、 ・s(x)の値を定める(1 ・そのときのxの値を求める。(2次方程式の解の公式を用いる) ・先ほど定めたs(x)…

Codeforces 236B Easy Number Challenge

概要 問題文はこちら http://codeforces.com/problemset/problem/236/B 解法 素数判定・約数の個数判定がきちんとできていれば解ける問題です。・素数判定について 私はエラトステネスの篩を用いて求めました。蟻本にも載っているので参考にしてみてはいかが…

Codeforces 236A Boy or Girl

概要 問題文はこちら http://codeforces.com/problemset/problem/236/A 解法 setなどを使ってアルファベットの数を数えるだけです。 ソースコード #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <numeric> #include <complex> #i</complex></numeric></set></map></stack></queue></vector></algorithm></string></iostream>…

Codeforces・初参戦

今日Codeforces初参戦でした。 いつも開催時間が遅いので敬遠してましたが、今日は16時開催でしたのでついに!結果は、ooo-- +0/-0, 239thでした。 そしてレートは1622、とてもよいスタートだと思います。 レートが下がらないように今後も頑張ります。

Codeforces 235A : LCM Challenge

概要 問題文はこちら http://codeforces.com/problemset/problem/235/An(1 6)が与えられます。 n以下の値を3つ選んだときのそれらの最大の最小公倍数を求める問題です。 解法 小さい値でいろいろ規則性を探しているうちにだんだん分かってきました。まず…