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 <= 10⁹
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予選模擬にもかかわらずガチ参加できるほど良問ぞろいでした。
部外者が勝手に参加してすみませんでした。
運営陣は素晴らしい。はっきりわかんだね。

問題文

[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

startcpp’s blog

JOI模擬予選2015-2016参加記