【AtCoder】ABC 360 B - Vertical Reading | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 78

問題概要

英小文字からなる文字列 が与えられる。次の条件を満たす となる整数の組 が存在するかを判定せよ。ここで、 は の長さを表す。

• 条件 : を先頭から 文字ごとに区切ったとき、長さが 以上の文字列の 番目の文字を順番に連結した文字列が と一致する。

制約

• 

考察

ともに 以下なので、2重ループを用いて条件の通りに全探索してしまおう。

実装のポイントとして、「 文字ごとに区切る」という操作と「区切った文字列の 番目を連結する」という操作の2つを同時に行うため、 について 「 文字目から始めて 文字目を順に取り出していく」という方針を取っている。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    string S, T;
    cin >> S >> T;

    rep(w, 0, S.size()) rep(c, 0, w)
    {
        string temp = "";
        for (int i = c; i < S.size(); i += w)
        {
            temp += S[i];
        }

        if (temp == T)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

atcoder.jp

実装時間: 5分

【AtCoder】ABC 360 A - A Healthy Breakfast | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 19

問題概要

各文字がR, M, Sのいずれかである文字列 が与えられる。RがMよりも左にあるかを判定せよ。

制約

• の長さは であり、R, M, Sが1文字ずつ含まれる。

考察

for文で 内にRとMが現れるインデックス( それぞれr, mとした )を記録しておき、 であるかを判定すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

int main()
{
    string S;
    cin >> S;

    int r = -1, m = -1;
    rep(i, 0, 3)
    {
        if (S[i] == 'R')
            r = i;
        if (S[i] == 'M')
            m = i;
    }

    if (r < m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】ABC 361 A - Insert | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 15

問題概要

長さ の整数列 と整数 が与えられる。 の 番目の要素の直後に を挿入した整数列を出力せよ。

制約

• 入力はすべて整数。
• 
• 

考察

色々実装の方針がありそうだが、一番簡単なのはタイトルの通りvector::insertを使う方法だろう。

insertは第一引数に要素を挿入したい位置のイテレータ、第二引数に挿入したい要素を指定する。

cpprefjp.github.io

挿入の処理には線形時間かかるせいで使いどころがあまりないので存在を忘れがち。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, K, X;
    cin >> N >> K >> X;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    A.insert(A.begin() + K, X);

    for (auto &&a : A)
    {
        cout << a << " ";
    }
    cout << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】ABC 361 B - Intersection of Cuboids | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 299

問題概要

空間内において2点 を結ぶ線分を対角線とし、全ての面が 平面上のいずれかに平行な直方体を と書く。2つの直方体 が与えられるので、これらの共通部分の体積が正であるかを判定せよ。

制約

• 入力はすべて整数。
• 
• 
• 
• 
• 
• 

考察

サンプルケース1のところに図が掲載されているので多少考えやすいが、やはり空間上で物事を考えると混乱しやすい。ここは次元を落として1次元の問題として次を考えてみよう。

• 軸上に2点 を結ぶ線分を と書く。2つの線分 が共通部分を持つか判定せよ () 。

これは絵を描いて を固定したうえで を左右に動かしてみればすぐに解決する。2つの線分の左側と右側の点それぞれに注目し、 としたとき、

• 共通部分を持つ
• 共通部分を持たない

と定式化できる。

同じことを 軸に対しても行えばよい。実装に関してはコードを参照のこと。

コード

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

int main()
{
    int a, b, c, d, e, f, g, h, i, j, k, l;
    cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j >> k >> l;

    int x1 = max(a, g);
    int y1 = max(b, h);
    int z1 = max(c, i);
    int x2 = min(d, j);
    int y2 = min(e, k);
    int z2 = min(f, l);

    if (x1 < x2 && y1 < y2 && z1 < z2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

atcoder.jp

実装時間: 5分

幾何に関する問題、特に3次元のものはバグらせがちなのでめっちゃヒヤヒヤする。今回はすんなり解けてよかった...

【AtCoder】ABC 361 C - Make Them Narrow | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 342

問題概要

長さ の数列が与えられる。 の要素のうち任意の 個の要素を削除し、残りの要素をそのまま並べたものを数列 とする。 としてあり得る最小値を求めよ。

制約

• 入力はすべて整数。
• 
• 

考察

問題文に「順序を保って」とあるが、結局最小化をしなければいけないのでソートしても問題はない。

方針としては、次のようになる。

1. を昇順ソートする。
2. ある要素 を固定する。これが の最小値となる。
3. から数えて 個目の要素を見る。これが の最大値となる。 ( の中で から の部分配列を取り出して とするイメージ)
4. を で考えたときの最小値を出力する。

あとはこれを実装するだけ。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];

    sort(all(A));

    ll ans = INFL;

    rep(i, 0, K + 1)
    {
        ll temp = A[i + (N - K) - 1] - A[i];
        chmin(ans, temp);
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 20分