Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

トップ > プログラミング

【AtCoder】ABC 351 A - The bottom of the ninth | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 Easy プログラミング

atcoder.jp

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

問題概要

チーム高橋とチーム青木が、チーム高橋を先攻として野球を行なっており、現在9回表までが終了し、9回裏が始まろうとしている。試合において、チーム高橋は i (1 \leq i \leq 9) 回表に A_i 点を取り、チーム青木は j (1 \leq j \leq 8)回裏に B_j 点を取った。ここで、9回表の終了時点でチーム高橋の得点はチーム青木の得点以上である。チーム青木は9回裏に最低何点取れば勝利する (引き分けではない) ことができるかを求めよ。

制約

  • 入力はすべて整数。
  • 0 \leq A_i, B_j \leq 99

考察

ループを用いて \displaystyle \sum_{i=1}^{9} A_i - \displaystyle \sum_{i=1}^{8} B_i + 1 を計算し、それを出力すればよい。

コード

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

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

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

int main()
{
    int a_sum = 0, b_sum = 0;
    rep(i, 0, 9)
    {
        int a;
        cin >> a;
        a_sum += a;
    }
    rep(i, 0, 8)
    {
        int b;
        cin >> b;
        b_sum += b;
    }

    cout << a_sum - b_sum + 1 << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】AtCoder Beginner Contest 351 - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

atcoder.jp

コンテスト時間: 2024-04-27(土) 21:00 ~ 2024-04-27(土) 22:40 (100分)

A - The bottom of the ninth

Difficulty: ???
解答時間: 3:08

  • 2チーム A, B が野球の試合をしたときの各回の得点が9回表まで与えられるので、 B が9回裏に何点を取れば A に勝てるかを求める問題。
  • 2チームの現在の得点を計算し、その差 + 1 を出力すればよい。

B - Spot the Difference

Difficulty: ???
解答時間: 3:06

  • 各マスに英小文字が書かれた2つのグリッド A, B が与えられる。両者を比較したときに1か所だけ書かれている文字が異なるマスがあるので、そのインデックスを出力する問題。
  • グリッドのマスは最大で 100 \times 100 = 10000 なので、愚直に2重ループを回して1個ずつ比較していけばよい。

C - Merge the balls

Difficulty: ???
解答時間: 19:13

  • i 個目の大きさが 2^{A_i} である N 個のボールと空の列がある。以下の操作を N 回繰り返した後の、列に残っているボールの数を出力する問題。
  • i 回目の操作 :
  1. i 個目のボールを列の一番右に付け加える。
  2. 列にあるボールが1つ以下ならばこの操作を終了する。
  3. 列にあるボールのうち右から1番目と2番目の大きさが異なるならば操作を終了する。
  4. 列にあるボールのうち右から1番目と2番目の大きさが等しいならば、2つのボールを取り除き、「取り除かれた2つのボールの大きさの和」の大きさのボール1つを列の一番右に付け加える。その後、手順2に戻り以降の手順を繰り返す。
  • まず、 2^A + 2^A = 2^{A+1} であることから、ボールの大きさを底を2とする対数で管理してよい。
  • 列をstackで管理し、手順3, 4について、加えるボールの大きさをnextとして以下のような再帰関数f()で対応する (大きさを結合する操作を再帰して、最後にstackに反映する感じ。うまく言語化できませんでした。) 。
void f(stack<int> &st, int next)
{
    if (!st.empty() && st.top() == next)
    {
        int temp = st.top();
        st.pop();
        f(st, temp + 1);
    }
    else
    {
        st.push(next);
    }
}

結果

Performance: 743
Rating: 572 → 590 (+18)

atcoder.jp

良い感じで3完できて嬉しい。

【AtCoder】ABC 338 A - Capitalized? | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 Easy プログラミング

atcoder.jp

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

問題概要

英字からなる文字列 S が与えられる。「 S の先頭が大文字であり、それ以外の文字は全て小文字である」かを判定せよ。

制約

  • S の長さは1以上100以下。

考察

AtCoderでたまに問われる、英字が大文字または小文字であるかを判定する問題。

C++ においては、英字が大文字かを判定するためにはisupper()関数が、小文字かを判定するにはislower()関数を使えばよい。

あとはループを回して各文字ごとに判定していけばOK。

コード

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

using ll = long long;

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

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

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

    rep(i, 0, S.size())
    {
        if (!isupper(S[0]))
        {
            cout << "No" << endl;
            return 0;
        }
        else if (i >= 1 && !islower(S[i]))
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

atcoder.jp

実装時間: 5分以内

【C++】数値と文字列の相互変換まとめ

C++ プログラミング キャスト AtCoder

AtCoder でしばしば問われる「数値と文字列の変換」。出題のたびにググるのがそろそろ面倒くさくなってきたので、頻出の変換をメモ程度にここにまとめておく。なお、 C++ のバージョンは C++20 である。

数値から文字列に変換する

std::to_string()ですべて対応可能。ただし、小数の変換に関しては、精度を指定することはできない。

リファレンス :

cpprefjp.github.io

例 : 

#include <iostream>
#include <string>

int main() {
  int a = 12345;
  double b = 1.23;
  double c = 1.23456789;
  
  std::string s = std::to_string(a);
  std::string t = std::to_string(b);
  std::string u = std::to_string(c);
  
  std::cout << s << std::endl;
  std::cout << t << std::endl;
  std::cout << u << std::endl;
}

出力 : 

12345
1.230000
1.234568

数値 (int型) から 文字 (char型) に変換する

特別な関数を用いる必要はない。 C++ では内部的にchar型が連番の整数値で扱われていることを利用して、文字コードでの加算を行って明示的にchar型にキャストするのが良いだろう。1桁の数値に対してのみ有効なことに注意。

例 : 

#include <iostream>

int main() {
  int x = 7;
  char c = char(x + '0');
  std::cout << c << std::endl;
}

出力 : 

7

文字列から数値に変換する

文字列からint型への変換はstd::stoi()を使用する。同様に、long long型への変換はstd::stoll()が、double型への変換はstd::stod()を使用する。このとき、0埋めは無視される (例参照) 。

また、変換元の数値を表す文字列が変換先の数値型の形式に対応していない場合、例外std::out_of_rangeを返す。

リファレンス (他数値型への変換に対応する関数も掲載) :

cpprefjp.github.io

例 : 

#include <iostream>
#include <string>

int main() {
  std::string a = "123";
  std::string b = "0012";
  std::string c = "-12";
  std::string d = "123.456";
  std::string e = "-1234.56000";
  
  int u = std::stoi(a);
  int v = std::stoi(b);
  int x = std::stoi(c);
  double y = std::stod(d);
  double z = std::stod(e);
  
  std::cout << u << std::endl;
  std::cout << v << std::endl;
  std::cout << x << std::endl;
  std::cout << y << std::endl;
  std::cout << z << std::endl;
}

出力 : 

123
12
-12
123.456
-1234.56

文字 (char型) から数値 (int型) に変換する

inttocharのときと同じ要領で、文字コードでの減算を行ってから明示的にint型にキャストするのが良いだろう。

例 : 

#include <iostream>
#include <string>

int main() {
  char c = '7';
  int x = int(c - '0');
  std::cout << x << std::endl;
  
  std::string s = "12345";
  for(int i = 0; i < s.size(); i++) {
    std::cout << int(s[i] - '0') << " ";
  }
  std::cout << std::endl;
}

出力 : 

7
1 2 3 4 5

【AtCoder】ABC 350 C - Sort | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 300~399 sort プログラミング

atcoder.jp

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

問題概要

数列 {1, 2, ..., N} を並び替えてできる数列 A が与えられる。次の操作を0回以上 N - 1 回以下行うことで、 A を昇順にソートしたい。操作回数を K として、1行目には K を、続く K 行には各操作で選ぶ整数 i, j を空白区切りで出力せよ。

  • 操作 : 1 \leq i < \leq j \leq N を満たす整数の組 (i, j) を選び、 A_i と A_j を入れ替える。

制約

  • 入力はすべて整数。
  • 2 \leq N \leq 2 \times 10^5

考察

一見するとバブルソートもしくは選択ソートの手順に見えるが、それらの計算量は O(N^2) であり今回の制約では TLE する。典型のソートアルゴリズムはいったん忘れて、純粋に考えてみよう。

最大操作回数が N - 1 回であることに注目すると、もっとも思いつきやすいのは次のアルゴリズムだろう。

  1. A の先頭から A_i が正しい位置にあるか (先頭から A_i 番目にあるか、つまり A_i = i であるか) どうかを判定していく。
  2. もし正しい位置にない場合、 A_j = i となるような j (i < j \leq N) を求める。
  3. A_i と A_j の位置を入れ替える。

しかし、2の過程で最悪 N - 1 回の探索が必要となり、 TLE となってしまう (例えば、 A_N = 1 のとき) 。


これを改善するために、あらかじめ A_k = k (1 \leq k \leq N) となるような k を格納する配列 (ここではposとした) を作成しておき、2, 3の過程をそれぞれ次のように書き換えてみよう。

2'. もし正しい位置にない場合、 j = pos_i とする。
3'. A_i と A_j の位置、 pos_{A_i} と pos_{A_j} の位置をそれぞれ入れ替える。

こうすることでこの部分の処理は定数時間で行うことができるようになり、全体として計算量を O(N) に落とすことができる。


あとはこれを実装していく。各操作で選んだ i, j の組を出力する必要があるので、処理のしやすさからpair型のvector配列にその組を格納している。

コード

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

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

using Pair_int = pair<int, int>;

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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N + 1), pos(N + 1);
    rep(i, 1, N + 1)
    {
        int a;
        cin >> a;
        A[i] = a;
        pos[a] = i;
    }

    vector<Pair_int> ans;
    rep(i, 1, N + 1)
    {
       if (A[i] != i)
        {
            int j = pos[i];
            swap(A[i], A[j]);
            swap(pos[A[i]], pos[A[j]]);
            ans.push_back(make_pair(i, j));
        }
    }

    cout << ans.size() << endl;
    for (auto p : ans)
    {
        cout << p.first << " " << p.second << endl;
    }
}

atcoder.jp

実装時間: 25分

これが灰Diffの時代になってしまったのか...