CodeFestival2015本選の問題（解法メモ）
備忘録に解法に至るアプローチを貼っておきます。
A: 575判定。cin >> s >> t >> u; cout << (s.length()==5&&t.length()==5&&u.length()==5) ? "YES":"NO" << endl;
B: N≧2における合計値の確率分布では平均が一番盛り上がっている。N=1では均一なので1が答え。
C: 前から文字列を見ていき、"01"か"10"が見つかったら即座にペアにしていって良い。（010…とあったとき、0「10」…としても「01」0としても前3文字までの分解数は同じ＆0「10」とすると残った0とペアになる1が絶対なくなるが「01」0とすれば残った0とペアになる1があるかもしれない -> そのときは得！）などと考えたが、詳しい証明は分からない。
同じ文字を複数のペアに割り振らないように注意する。
D:
①いつだれがどのスイッチを押すかと考えると闇 -> 人数だけ求めればよい！
②N点取る場合…区間が最大M個かぶっていたらM人以上必要、また、M人で十分。
③N-1点取る is 全区間 - {ある一つの区間}
④(ある区間にXを足す, 区間のMaxを求める)というクエリが沢山来る -> StarrySky木
もしくは、N点取る場合に区間が最大M個かぶっているとき、答えがMかM-1であることを利用すればO(N)。(M個区間が被っている時間の(左端, 右端)を覆えるかどうかで判定できる）
E:
答えはそんなに長くならない -> 反復深化で全探索しよう！判定は色んな入力を元のコード, 生成したコードの2つに与えて、出力の一致を確かめるなど…。
F:
①サイクルにする（グラフ問題にする）
②頂点と辺の通る回数に注目する
③辺を通る回数を考える
④連結判定
G:
・列の問題に落とせるらしい？？
H:
・3枚重ねるのはタブー
・重なって損した量（ペナルティー）で辺を貼ると、最短経路問題になるらしい
競プロ始めたときに埋めた問題
について少しメモしておきます。
競プロを本格的に始めたのはARC(AtCoder Regulars Contest)18からです。
(当時は、B問題のバグに苦しめられていた。）
-1.5年～-0.5年
・JOI予選1～3問目を新しい年のものから埋めていました
（実力、JOI予選200点レベル）
・20行のコードのデバッグに20分以上かけてしまうこともしばしばありました。
-0.5年～0年
JOI予選4～6問目埋め
・このとき、AOJでは30問程度解いていました
・6問目は、2006, 2007年度の予選のものしか解けていませんでした
・一番印象を受けた問題は、「1年生」です。
・この問題をきっかけに、競技プログラミングが好きになりました
JOI本選1～3問目埋め
・楽しい問題、良質な解説…これに手を付けない手はありませんでした
・100枚1冊のレポート用紙に考察を書きこんでいたこと、今でも覚えています
（・2次元累積和に自力で気づいたり、JOI2008本選5番が解けたときは感動した）
（実力、AtCoderRegularsContestB問題が解けるかどうか）
0年～
・AtCoderの定期コンテストに参加
・PCK, JOI, ICPC, JAGあたりを中心的に埋めた(AOJ200問解きました)
・TopCoder, Codeforces…（深夜コンテストへの参加は不可能でした）
・YukiCoder☆2(1/4くらい面白そうな問題をやりました）
最近
・留年の危機()が迫ってきたので、TopCoder-Div1Easyに絞って練習しています。
（実力、CodeFestival本選5完、ARC2完、TopCoder-緑(1100付近))
最後に
文章がひどいですね…
【備忘録】SRMDiv1Easyを20問埋めてみたら
はじめに
最近、SRMDiv1Easyを20問解いたので、そろそろ何か書き残しておこうと思います。
殆ど自分用なので、かなりひどい文章です。ご容赦ください。
1.SRMを選んだ理由
・読みやすい問題文が多い
・実装が軽い
・良問が多い
・難易度が安定している
・↑のこともあり、TopCoderのレートを上げたくなった
・時間で得点が変わる＆英語だから緊張感を得られる
2.Div1Easyを選んだ理由
・最初の方針が合っていれば解ける／嵌ると解けない
→方針を合わせる練習になる
・1～2時間で解ける問題が半分くらいある
→ギリギリ解けるのが面白い
・想定解は自分でも分かるくらい簡単
→解説で分かると悔しい
・実装が軽い
→お手軽
3.解くときの方針
手順
①1～2時間解いてみる
②解けなければブログ解説の解法だけを見る
③理解できなければ実装もチラ見する
④理解した（クリアだ！簡単だ！と思えた）ら実装して通す（必ず通す）
心得
・証明不能な貪欲は大体嘘貪欲
・簡単な考察＆軽実装で解ける（そうでないものは捨てる）
・必ず解けると思う、ただしあきらめも肝心（無理に通そうとしない）
・本番の環境に近づけるため、新しい問題からやる
4.埋める前に思ったこと
・闇雲に埋めてもダメ
・意識して埋めてれば実力は上がりそう
・どのくらい？？
・というより長続きするの？（AOJ埋めは3日坊主で終わった）
5.埋めてみて思ったこと
・実力は微妙に上がった気がする
→考察の個数が「1つ」から「3つ」くらいになった
→埋める前に嵌った問題は、やはり嵌ったので微妙
・ギリ解ける問題解いてる時は勝手に集中してた
・細々とだが続いている
→SRM(するめ)には中毒性がある
6.最後に
とりあえず、SRM600台は埋める予定。
これで解ける問題が増えたらラッキーなんだけど世の中そんなに甘くなさそうだ。
SRM 658 div1 easy: OddEvenTree
問題概要
N頂点(頂点0～N-1)の木の距離行列xが与えられる。
0 <= i, j <= N-1を満たす全ての(i, j)組について
x[i][j] = 'O'ならば頂点(i, j)間が奇数長
x[i][j] = 'E'ならば頂点(i, j)間が偶数長
が成り立つような、木は存在するだろうか。
存在しなければ{-1}を返し、存在すれば、そのような木を一つ出力せよ。
解法
木が存在するためには、以下の条件を全て満たす必要がある。
・xが対称行列
・全てのiについて、x[i][i] == 'E'
・任意の3頂点A, B, Cについて、AB間の距離 + BC間の距離 + CA間の距離が偶数
・一つ以上'O'が存在
なお、これは十分条件ではない（テストケース88は、これらすべてを満たすが、{-1}を返すべきケース）
上の条件をすべて満たしたとき、木の構築をする。
木の構築は、以下の貪欲アルゴリズムで行い、全部つなげなければ{-1}を返すようにしたら通った。
・頂点0を接続済み頂点にする。他の頂点は「接続済み頂点」ではない。
・全ての頂点を「接続済み頂点」にするか、つなげなくなるまで以下を繰り返す。
・「接続済み頂点A」と「接続済みでない頂点B」を見つけたら、頂点AとBを結ぶ。
・見つからなければ、{-1}を返す。
・このアルゴリズムを使って木を構築したとき、条件を満たさない木が出来たり、条件を満たす木が存在するのに{-1}を返したり しなかった。理由は良くわからない。
//必要条件だけで枝刈り＆条件を満たしたらすぐにつなぐ、という嘘っぽいあれ。
//木の構築中に矛盾が生じたらfalseでも良かったけど、見落としがあると不味いので。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class OddEvenTree{
public:
vector<int> False(){
vector<int> ret;
ret.push_back(-1);
return ret;
}
vector<int> getTree(vector<string> x)
{
int i, j, k;
int n = x.size();
int Ecnt = 0;
for( i = 0; i < n; i++ ){
for( j = 0; j < n; j++ ){
if( x[i][j] != x[j][i] )
return False();
if( i == j && x[i][i] == 'O' )
return False();
Ecnt += (x[i][j] == 'E');
}
}
if( Ecnt == 0 ){
return False();
}
for( i = 0; i < n; i++ ){
for( j = 0; j < n; j++ ){
for( k = 0; k < n; k++ ){
int d = (x[i][j] == 'O') + (x[j][k] == 'O') + (x[k][i] == 'O');
if( d % 2 == 1 )
return False();
}
}
}
//木の構築(エラーは検出済みなので、これで構築できなかったら最適な構築ではない)
//ばばーん
//(貪欲に構築しているため、条件を満たさない木が出来るかもしれない…)
bool used[50] = {false};
int sz = 1;
vector<int> ans;
used[0] = true;
while( sz < n ){
bool okflag = false;
for( i = 0; i < n; i++ ){
for( j = 0; j < n; j++ ){
if( used[i] && !used[j] && x[i][j] == 'O' ){
used[j] = true;
ans.push_back(i); ans.push_back(j);
okflag = true;
sz++;
}
}
}
if( !okflag ){
return False();
}
}
return ans;
}
};
提出コードのコメントがひどい
JOI模擬予選2015-2016参加記
JOI模擬予選に参加しました。
難易度はおおむね例年の予選と同じだが、問1が若干難しく、問3が簡単な印象。
備忘録ということで、コードを貼りつけておきます。
1 けんだま
問題
玉がA個、本体がB個ある。玉を1個増やすのにC[円]かかり、本体を1個増やすのにD[円]かかる。
予算X[円]で最大いくつのけん玉を作れるか。
解法
y個のけん玉を作るとする。
このときかかる金額は、C * max(0, y - A) + D * max(0, y - B)[円]である。
したがって、これがX以下となるようなyの最大値を出力すればよい。
コード
#include <iostream>
#include <algorithm>
using namespace std;
signed main()
{
int a, b, c, d, x;
int y;
cin >> a >> b >> c >> d >> x;
for( y = 0; y < 20000; y++ ){
int cost = c * max(0, y - a) + d * max(0, y - b);
if( cost > x )
break;
}
cout << y - 1 << endl;
return 0;
}
signedはintみたいなもの。
2 回文
問題
N文字の文字列S = s[1]s[2]…s[N]が与えられる。
3つの文字列
{s[i]s[i+1]…s[i+X-1]}
{s[i+X]s[i+X+1]…s[i+X+Y-1]}
{s[i+X+Y]s[i+X+Y+1]…s[i+2*X+Y]}
が全て回文となるようなiの個数を計算せよ。
解法
愚直にシミュレーションします。
文字列{s[l]s[l+1]…s[r-1]}が回文かどうかを判定する関数を作ると実装が楽でした。
コード
#include <iostream>
#include <string>
using namespace std;
int n, x, y;
string s;
bool ok( int l, int r ){
string t, u;
for( int i = l; i < r; i++ )
t += s[i];
for( int i = r - 1; i >= l; i-- )
u += s[i];
if( t == u )
return true;
return false;
}
signed main()
{
int i;
cin >> n >> x >> y;
cin >> s;
int ans = 0;
for( i = 0; i < s.length() - 2 * x - y + 1; i++ ){
if( ok(i, i + x) && ok(i + x, i + x + y) && ok(i + x + y, i + 2*x + y) )
ans++;
}
cout << ans << endl;
return 0;
}
3 渦巻きに歩く問題
問題
H行W列のグリッドがある。各マスには(1, 1), (H, W)などの座標が付けられている。
私は左上のマス(1, 1)から右渦巻きに移動していき、通ったマスに色を塗ることを繰り返す。
最初は青を塗り、次は赤、その次は青、というように青と赤を交互に塗っていく。
このとき、N個の座標(r1, c1), (r2, c2), …, (rN, cN)にあるマスはそれぞれ何色で塗られていたでしょうか。
青で塗られていたマスの数, 赤で塗られていたマスの数を空白区切りで出力せよ。
(制約)
1 <= H, W <= 109
1 <= N <= 1000
解法
ラフな考え
手で試すと、市松模様になることが分かる。
したがって、マスの座標を(a, b)とするとそのマスはa + bが偶数なら青、a + bが奇数なら赤で塗られている。
厳密な考え
移動先のマスの座標を(a, b)すると、移動するごとにa + bの偶奇が入れ替わる。
塗る色も入れ替わる。最初はa + bは偶数で塗る色は青である。
したがって、マスの座標を(a, b)とするとそのマスはa + bが偶数なら青、a + bが奇数なら赤で塗られている。
というわけで、(ri + ci) % 2 == 0となるiの個数、(ri + ci) % 2 == 1となるiの個数を計算すればよい。
コード
#include <iostream>
using namespace std;
int h, w, n;
int r, c;
signed main()
{
int i;
cin >> h >> w >> n;
int bcnt = 0;
int rcnt = 0;
for( i = 0; i < n; i++ ){
cin >> r >> c;
if( (r + c) % 2 == 0 )
bcnt++;
else
rcnt++;
}
cout << bcnt << " " << rcnt << endl;
return 0;
}
4 鉄道に乗る問題
問題
駅1, 2, 3, …, Nがこの順で並んでいる。
私は時刻0に駅Sにいる。いくら時間がかかってもよいので駅Tにつきたい。そのような電車の乗り方が何通りあるかを計算せよ。
ただし、乗り換え時間は無視できるものとする。電車の情報は以下の通り。
電車はM本ある。
i本目の電車は時刻A[i]に駅B[i]を発車し、駅B[i] + C[i], B[i] + 2C[i], …の順で止まる。なお、到着時刻(=発車時刻)はそれぞれA[i] + C[i], A[i] + 2C[i], …となる。
(制約)
1 <= N <= 100
1 <= M <= 100
1 <= A[i] <= 100
1 <= B[i] <= N
1 <= B[i] + C[i] <= N
(C[i]が負になる場合もある)
解法
次に乗れる電車は、現時点での（時刻, 駅, さきほど降りた電車）から分かる。
また、この3つを持っておけば、電車Xに乗って駅Yで降りた直後の(時刻, 駅, さきほど降りた電車)も分かる。
今いる駅 = Tになれば駅に行けたことが分かる。
したがって、(時刻, 駅, さきほど降りた電車の番号)を引数にした再帰関数を組むことができる。
ただし、再帰関数を愚直に組むと時間超過するので、一工夫する。
同じ(時刻, 駅, さきほど降りた電車の番号)場合の再計算が無駄なので、最初に計算した結果を配列にメモしておき、
再び同じ(時刻, 駅, さきほど降りた電車の番号)に遷移したときは、その結果を返すようにする。
つまり、(時刻, 駅, さきほど降りた電車の番号)を状態としてDPする。
遷移(X, Yを決めるところ)は複雑なので注意。
コード
#include <iostream>
#include <cmath>
using namespace std;
int n, m, s, t;
int a[100], b[100], c[100];
int dep; //デバッグ用(探索の深さ)
int dp[201][101][100]; //dfs(jikoku, eki, ressya)の返した値
//「時刻jikokuに駅ekiにいて列車ressyaから降りた」状態から「駅tへ行く方法の数」を返す
int dfs( int jikoku, int eki, int ressya ){
int i, j;
int ret = 0;
/*for( i = 0; i < dep; i++ ) cout << "・";
cout << " 時刻" << jikoku << " 駅" << eki;
cout << endl;*/
if( ressya >= 0 && dp[jikoku][eki][ressya] != -1 )
return dp[jikoku][eki][ressya];
if( eki == t )
ret++; //駅tについたから1通り加算する
for( i = 0; i < m; i++ ){
//降りた直後に同じ電車には乗れない
if( i == ressya )
continue;
//駅ekiに停車しない電車には乗れない
if( (eki - b[i]) / c[i] < 0 || abs(eki - b[i]) % abs(c[i]) != 0 )
continue;
//駅ekiを通過してしまった電車には乗れない
if( jikoku > a[i] + abs(b[i] - eki) )
continue;
//電車iに乗って駅jで降りる
for( j = eki + c[i]; 1 <= j && j <= n; j += c[i] ){
dep++;
ret += dfs(a[i] + abs(b[i] - j), j, i);//次の駅からの行き方を足す
ret %= 100000; //逐次余りを取る
dep--;
}
}
dp[jikoku][eki][ressya] = ret;
return ret;
}
signed main()
{
int i;
cin >> n >> m >> s >> t;
for( i = 0; i < m; i++ ){
cin >> a[i] >> b[i] >> c[i];
}
for( i = 0; i < 201; i++ ){
for( int j = 0; j < n + 1; j++ ){
for( int k = 0; k < m; k++ ){
dp[i][j][k] = -1;
}
}
}
cout << dfs(0, s, -1) << endl;
return 0;
}
もっときれいなコードを書きたかった。
想定解とは少し違うらしい。
5 楽しい楽しい花の水やり
問題
花1, 2, …, Nがある。0日目の花iのみずみずしさはA[i]である。花のみずみずしさは日付が変わる瞬間にB[i]減少する。
みずみずしさが0以下になった花は枯れてしまう。
私は好きな時刻に何度でも「みずやり」をすることができる。「みずやり」は次の2ステップで行われる。
１.整数iを決める
２.花i - K, i - K + 1, …, i + KのみずみずしさをC増やす。
T日目にどの花も枯れていないようにしたい。しかし「みずやり」も重労働なので「みずやり」の回数もなるべく少なくしたい。
「みずやり」の回数の最小値を計算せよ。
(制約)
1 <= N <= 5 * 10 ^ 6
1 <= T <= 10 ^ 7
1 <= K <= N / 2
1 <= A[i], B[i] <= 10 ^ 7
1 <= C <= 10 ^ 7
なお、a ^ bはaをb回かけたものである。
(補足)
A[i], B[i]は乱数で生成する。生成の仕方はコードを見て察してください。
解法
まず、全ての入力はlong long型変数で管理したほうが良い。
考察1
水やりを全く行わなかったら、花iのみずみずしさは、A[i] - B[i] * Tとなる。
花iにX[i]水がかかったら、花iのみずみずしさは、水やりをしたタイミングによらず
A[i] - B[i] * T + C * X[i]
となる。
少なくともこれが0を超えている必要がある。逆に、これが0になるような最小のX[i]をMx[i]としたとき、
花iにはMx[i]回以上水がかかれば良い。
水やりは0日目にまとめて行おう。なお、水やりの中心位置は
花1 + K, 2 + K, …のようにずらしていくのが最善である。
具体的には、
花1～1 + 2Kに「みずやり」をする。
花1にMx[1]回以上水をやったら（花1が枯れなくなったら)花2～2 + 2Kに「みずやり」をする。
花2にMx[2]回以上水をやったら（花2が枯れなくなったら)花3～3 + 2Kに「みずやり」をする。
～
を繰り返せばよい。
これを愚直にやるとO(NK)で答えを計算できる。
考察2
上記の「みずやり」シミュレーションを高速化したい。具体的には
・X[i]の値を求める
・X[i+1]～X[i+2K]の値をX[i]減らす
というクエリを高速に処理したい。
これは区間加算1点クエリのセグメントツリーでできる。
もしくは累積和を行えばよい。私はセグメントツリーで解いたが、累積和（いもす法）を使えば
実行が速く実装も楽である。
コード
#include <iostream>
#include <algorithm>
#define int long long //intがlonglongに置換される
using namespace std;
int N, K, C, T;
int Sa, Xa, Ya, Za;
int Sb, Xb, Yb, Zb;
void input(){
cin >> N >> K >> C >> T;
cin >> Sa >> Xa >> Ya >> Za;
cin >> Sb >> Xb >> Yb >> Zb;
}
void generate(int A[], int B[]){
for( int i = 1; i <= N; i++ ){
A[i] = Sa + 1;
B[i] = Sb + 1;
Sa = (Xa * Sa + Ya) % Za;
Sb = (Xb * Sb + Yb) % Zb;
}
}
int A[5000001], B[5000001];
int X[5000001]; //X[i] = 花iに水をかける回数の最小値
const int depth = 23;
class Segtree{
public:
int data[20000000];
void init(){
for( int i = 0; i < 20000000; i++ ) data[i] = 0;
}
void add( int l, int r, int v, int a = 0, int b = (1 << depth) - 1, int ind = 0, int dep = 0 ){
if( dep > depth ) return;
if( b < l || a > r ) return;
if( l <= a && b <= r ){
data[ind] += v;
}
else{
add( l, r, v, a, a + (b - a + 1) / 2 - 1, ind * 2 + 1, dep + 1 );
add( l, r, v, a + (b - a + 1) / 2, b, ind * 2 + 2, dep + 1 );
}
}
int getNum( int x ){
int ret = 0;
x += (1 << depth) - 1;
ret += data[x];
while( x > 0 ){
x = (x - 1) / 2;
ret += data[x];
}
return ret;
}
}seg;
void generateX(){
for( int i = 1; i <= N; i++ ){
//A[i] - B[i] * T + C * X[i] > 0となるX[i]の最小値を求める
X[i] = max((int)0, (B[i] * T - A[i]) / C + 1);
}
}
void segInit(){
seg.init();
for( int i = 1; i <= N; i++ ){
seg.add(i, i, X[i]);
}
}
//花1 + Kを中心に水をかける→花2 + Kを中心に水をかける→…
//水やり回数を返す
int solve(){
int center;
int ans = 0;
for( center = 1 + K; center <= N + K; center++ ){
int left = center - K;
int right = min(N, center + K);
//max(0, X[left])回水やりをする
//①max(0, X[left])を求める
int kaisu = max((int)0, seg.getNum(left));
//②答えを更新
ans += kaisu;
//③X[left]～X[right]に-max(0, X[left])足す
seg.add(left, right, -max((int)0, kaisu));
}
return ans;
}
signed main()
{
input();
generate(A, B);
generateX();
segInit();
cout << solve() << endl;
return 0;
}
高級な道具を使ってしまった。
6 完全に忘れました
ごめんなさい
感想
JOI予選模擬にもかかわらずガチ参加できるほど良問ぞろいでした。
部外者が勝手に参加してすみませんでした。
運営陣は素晴らしい。はっきりわかんだね。
Markdown記述のテスト
問題文
[input.txt]には行数h、列数w、文字列S1,…,Shが書かれてます。
S1～Shは、#と (空白)から成るw文字の文字列です。
形式は以下の通りです。
[input.txt]
h w
S1
S2
…
Sh
ぬぬぬ君は[input.txt]を加工することで、0と1から成るテキストを作りたいです。
加工は以下の手順で行います。
①1行目(h wが書かれている行)を削除する
② (空白1文字)を0に、#を1に置き換える
③テキストを左90度回転する
④テキストを上下反転する
ぬぬぬ君はこの加工を手で行っていたのですが、疲れからか黒塗りの車に衝突してしまい、
手が使えなくなってしまいました。
そんなぬぬぬ君を見たあなたは、彼のテキスト加工を手伝うことにしました。
それでは、[input.txt]を加工し、加工後のテキストを[output.txt]に書き込む
プログラムを作成してください。ただし、リダイレクトを用いてはいけません。
すなわち実行形式は、
./a.out
または
～.exe
のようにします。
入力[input.txt]の制約
1 <= h, w <= 100
入出力例
例1
//input.txt 4 5 ## # # # ## # # ## //output.txt 1100 1011 0010 0101 1011
//手順1を終えたとき ## # # # ## # # ## //手順2を終えたとき 11001 10010 01101 01011 //手順3を終えたとき 1011 0101 0010 1011 1100 //手順4を終えたとき 1100 1011 0010 0101 1011
例2
//input.txt 3 26 # ### # # # # ### # # # # # # # # # ## # # # ### ### # # ### # # //output.txt 111 000 111 101 111 000 111 001 001 000 111 000 100 010 001 010 100 000 111 111 101 000 111 000 000 111
■
JOI2012予選4「Hot Days」
解けたので、備忘録のため、コードを適当に貼ります（ひどい）。
コードの貼り方が分からないので、この記事は何回か更新されます。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int d, n;
int t[200];
int a[200], b[200], c[200];
int dp[201][200]; //dp[day][fuku] = sumの最大値
int ans = -1145141919;
void makeAns(){
int day, fuku, i;
//初期化
for( day = 0; day < d + 1; day++ ){
for( fuku = 0; fuku < n; fuku++ )
dp[day][fuku] = -114514;
}
for( fuku = 0; fuku < n; fuku++ ){
if( a[fuku] <= t[0] && t[0] <= b[fuku] )
dp[1][fuku] = 0; //0日目に服fukuを着た場合
}
//dp配列の更新
for( day = 1; day < d; day++ ){
for( fuku = 0; fuku < n; fuku++ ){
//day日目の服を決める(遷移)
for( i = 0; i < n; i++ ){
if( a[i] <= t[day] && t[day] <= b[i] ){
//day日目に服iを着る
dp[day + 1][i] = max(dp[day + 1][i], dp[day][fuku] + abs(c[fuku] - c[i]));
}
}
}
}
//答えを計算する
for( i = 0; i < n; i++ ){
ans = max(ans, dp[d][i]);
}
}
int main()
{
int i, j;
cin >> d >> n;
for( i = 0; i < d; i++ ) cin >> t[i];
for( i = 0; i < n; i++ ) cin >> a[i] >> b[i] >> c[i];
makeAns();
cout << ans << endl;
return 0;
}
