灰コーダーのABC348振り返り（3完パフォ396）

本日は4/7(日)のAtCoder ABC348を振り返る。

結果

ABCまでの3完で、パフォーマンスは396。

45分程度でCまでACできたが、D問題を解くための知識を持っておらず3完で終了した。


これを受けて思うのは、前回(ABC347)ではAB2完だったのだがパフォ385で、今回とは「C問題を解けなかった」という大きな差があるにも関わらずパフォーマンスに10程度しか差がない。
自分の直感では解いた問題数によってパフォーマンスが階段式に変わるのかと思っていたが、こちらの記事を読むに「参加者全員に対する順位」が参照されている模様？
なるほど、であれば前回と今回で順位に大きな差がないため、パフォーマンスがさほど変わっていないというのも頷けるではある。
「茶コーダーになるにはパフォ400を安定して取れるようになる」というのをどこかで見たことがある気がするので、であれば「6000位」より高い順位を安定して取れるようになれば良さそうなのかな。


閑話休題。
以下、各問題を個別に振り返る。

A(5:45)

atcoder.jp

事前目標は5分以内だったのだが、45秒オーバーしてしまった。
ロスした原因は「算術演算子」の記述ミス。「iが3の倍数ではなかったら」の部分を、

if (i+1 % 3 != 0)

と書いてしまったせいで、出力が全て"xxxxxx"となってしまった。
正しくは

if ((i+1) % 3 != 0)

非常に初歩的だが、実戦は気付かなくてとても焦った。
「A問題で時間を使っているようではこの先思いやられる…」的な思考がよぎってしまったが、今振り返ってみるとこのような思考は視野を狭くする原因になるためあまり良くないと思う。
モチベーションが高いことの裏返しではあるものの、純粋に問題を解くことのみに思考リソースを使うべきだろう。メンタル面での精進が必要だ。

最終的に提出したコードは以下。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <bitset>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N;
    cin >> N;
    rep(i, N) {
        if ((i+1) % 3 != 0) {
            cout << "o";
        } else {
            cout << "x";
        }
    }
    cout << "" << endl;
    return 0;
}

B(5:45-17:38)

B - Farthest Point
シンプルな全探索。
この問題で分からなかったのは「2乗する」の記述方式。普通に調べてcmathヘッダのstd::powを使用した。
今回は使用しなかったが「平方根」も、pow(X, 0.5)の形で計算できるようだ。

B問題も5分を目標にしていたのだが、実際にかかった時間は12分程度…。powを調べたロスがあったとはいえ、個人的にはそれなりの速度で書けたと思っていたものの、5分というのはやはり高い目標のようだ。

公式の模範回答コードとの差分もほとんどなかったし、この辺りは純粋な「速度勝負」という感じなのかもしれない。C++の知識もそれなりについてきて、問題文通りに実装できるようになってはいるものの「慣れ」の部分で上位勢と差がついている感じはある。
こればかりはB問題を無限に解きまくって「慣れ」を高めるしかなさそう。少なくとも今回のように「2乗ってどう書くんだっけ？」と調べているようでは難しいだろう。まずは「本番で調べる必要がなくなる」程度の知識水準にしておきたいか。
先週は結構C問題の過去問を解くことに時間を割いてしまっていたが、今週はB問題を解くことにも時間を使うことにしよう。

次回はとりあえず目標を10分とする。

実際に提出したコードは以下。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    rep(i, N) {
        cin >> X[i] >> Y[i];
    }
    vector<int> G(N);
    rep(i, N) {
        int max_length = 0;
        int max_length_i = 1;
        if (i == 0) max_length_i = 2;
        rep(k, N) {
            if (i==k) continue;
            int length = pow(X[i]-X[k], 2) + pow(Y[i]-Y[k], 2);
            if (max_length < length) {
                max_length = length;
                max_length_i = k;
            }
        }
        cout << max_length_i+1 << endl;
    }
    return 0;
}

C(17:38-43:31)

atcoder.jp
関門のC問題。先週はC問題に80分掛けても解けず、半分トラウマになっていたが、今回は25分程度ですんなりと解けて（実際難易度も低かったようだ？）「あ、自分でもC問題は普通に解けるんだな」という心持ちを作ることができて良かった。

とはいえ、ここから更に解く速度を高めないとレートは増えていかない。
参考として、冒頭で設定した「6000位」の解答時間を見てみると、2:39-24:12-36:13の3完となっていた。周辺順位の一通り目を通したが、今回においては3完を36分程度で完了することがボーダーだったようだ。

ちなみに、前回のABC347の6000位ボーダーを見てみると「AB2完を10分で終えた上で、C問題にミスを数回出している」層。
毎回C問題の難易度に差があるので、6000位ボーダーが2完になるのか3完になるのかは問題次第というところか。

今回においてはC問題ACまでの時間を後8分短縮できていれば、という感じではある。これは、B問題で5分程度の短縮を見込めることを考えると、C問題で後数分短縮すれば良かっただけということになり、わりかし現実的なラインに思える。

改めて、来週は6000位を目標に、今週の過去問解きに取り組んでいこう。

話が逸れたが、C問題において詰まった箇所を振り返る。

まず、単純な全探索ではTLEすることがすぐにわかる。最も単純な全探索は2×10^5を2周することだと思うが、それはO(10^10)となる。計算の工夫が必要だ。

この問題のポイントはmap変数の使い方。色Ciをキーとして、値に「Ciに対応するAiのうち最大のもの」を格納する。この操作はO(10^5)で実施され、各色の中でのおいしさの最大値を格納することができる。

自分は当時の時点でmap変数を知らず、最初ベクトルで同じことをしようと考えた。しかしCの最大値が10^9ということで、長さ10^9のベクトルを定義して探索するという方式は明らかにおかしいということになり、Pythonにおける辞書的なものをcppで書く方法をChatGPTに聞いたところmapを教えてもらった。

mapさえ分かればあとは実直に実装するのみ。最終的なコードは以下。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <bitset>
#include <map>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), C(N);
    rep(i, N) {
        cin >> A[i] >> C[i];
    }
    map<int, int> minAForC;
    rep(i, N) {
        if (minAForC.find(C[i]) != minAForC.end()) {
            minAForC[C[i]] = min(minAForC[C[i]], A[i]);
        } else {
            minAForC[C[i]] = A[i];
        }
    }
    int maxA = 0;
    for (const auto& pair : minAForC) {
        if (pair.second > maxA) {
            maxA = pair.second;
        }
    }
    cout << maxA << endl;
    return 0;
}

D(43:31-2:00:00)

atcoder.jp
BFS（幅優先探索）の知識があることが前提の問題。自分はBFSの勉強をしていなかったため、解けずに終了。

さて、BFSとは何だろうか？　いい機会なのでここで勉強することに。
すごくわかりやすそうな記事があったため、知識をここから収集する。対応するものとしてDFS（深さ優先探索）もあり、こちらも勉強が必要そうだ。

まず、この問題を見て「これはBFSをしようすべきだ」と判断するためにはどのような知識が必要だっただろうか。BFSに関する基本的な知識は勿論必要。その上で「どのような問題にBFSを導入しがちか」という知識が必要だっただろう。すなわち「BFSは「最短経路問題」を解くのに適している」ということを知っていれば良かったことになる。今回のD問題はまさに最短経路問題（獲得可能なエネルギーの総量が、経路長より大きいかを判断するために最短経路を知る必要がる）であった。

次にBFSの実装について。通常は「グラフ上」のBFSがベースなようで、グラフ構造を定義する必要が別途ある。今回は「グリッド上」のBFSになるため、グリッドの定義を単に2次元ベクトルで行えば良い。グラフの定義は不要だ。と、思ったが「薬」の制約があるため単に2次元ベクトルを作るだけではダメらしい。
「薬iを使った後他の薬を使用せずに薬jに到達できる」ことを「頂点iからjに辺がある」と定義した有効グラフを作成するのが今回のベースであるようだ。
つまり全ての薬iについて、BFSを行い、薬jに対する最短経路を求める。ゴール地点に薬があれば、スタート地点の薬からゴール地点の薬まで辺が繋がっているかどうかを調べて"Yes"か"No"を出力すれば良い。ゴール地点に薬がない場合は？　解説では「ゴール地点に仮想の薬」を追加してしまうのが実装上楽であると紹介している。確かに、ゴール地点の薬に関してはエネルギーがいくつであっても影響しないので、勝手に追加してしまっても問題ないということだ。

解説を読み、内容を理解しても、ここまでを本番の1時間程度で解けるようになるためには中々ハードルがありそうだと感じる。単純に問題を読み解き、条件を整理した上で、必要となる知識を引っ張ってきて、それを実装という形に落とし込み、更に細かい制約条件を踏まえた上で、正しい答えを出力する必要がある。

一朝一夕でできるようになることではないなと思う。茶コーダーを目指す上でD問題への必要性はさほど高くなく、優先度については後回しでいいと思っているが、いずれ向き合う必要がある。

E問題以降

D問題の理解で頭一杯になってしまったので、今回E以降はスキップとする。

今日の記事は以上。来週は3完の速度を高め、6000位・パフォ400以上を目指す！

CD問題過去問解き記録（三井住友PC2019_D、ABC128_C）

今日も今日とてAtCoderの過去問解き。本日はC問題1問、D問題1問。
問題のチョイスはこちらの1-6-4より。

三井住友信託銀行プログラミングコンテスト2019 D問題

自分はD問題を解いたことがなく、ほぼ問題を見ようとしたこともないため、「茶色になるためには」の記事内でこの問題が紹介されてて少しビビってしまったが、とはいえ機械的に取り組むことに。
D問題はC問題に比べて必要となる知識量が多そうというイメージではあるが、中でには全探索で解ける問題もあるんだね。

問題はこちら。
atcoder.jp

ラッキーナンバーNから任意の3文字を取り出し、3桁の数字を作るという問題。
初動でまず思いついたのは「可能な組み合わせを全探索する」方法。しかしそれではO((3×10^4)^3) = O(10^13) の計算量になり、余裕のTLEであることが分かる。
どのように工夫して計算量を減らすか。問題紹介の文脈から全探索で解けることは分かっているのは何かズルい気もしつつ考える。

次に思いついたのは「重複する数字が見つかったら、以降の探索を打ち切る」という方式だ。
例えば、作成される3桁の数字の1文字目としてあり得るのは、0-9の10通りのみ。
従って1文字目として探索されたことがある数字を記録しておけば、計算量はO(10×(3×10^4)^2)に減らすことができる。
さらに、2文字目についても同様の操作を行えば、更にO(10×10×3×10^4) = O(10^6)まで減らすことができ、これはTLEを防ぐことができるラインだ。

後は、この方針通りに実装するのみ。
道中、set周りのメソッド（挿入や検索）が曖昧だったので調べたり、charとstringの扱いの違いを理解していなかったりで時間を喰われ、最終的にACを出すまでに掛かった時間は約49分。
最終的なコードはこちら。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N;
    string S;

    cin >> N;
    cin >> S;
    set<string> keys;
    set<char> c1s;
    rep(i, N-2) {
        char c1 = S[i];
        if (c1s.find(c1) != c1s.end()) continue;
        c1s.insert(c1);
        string S2 = S.substr(i + 1);
        set<char> c2s;
        rep(k, N-2-i) {
            char c2 = S2[k];
            if (c2s.find(c2) != c2s.end()) continue;
            c2s.insert(c2);
            string S3 = S2.substr(k+1);
            set<char> c3s;
            rep(l, N-2-i-k) {
                char c3 = S3[l];
                if (c3s.find(c3) != c3s.end()) continue;
                string key = string(1, c1)+string(1, c2)+string(1, c3);
                keys.insert(key);
            }
        }
    }
    cout << keys.size() << endl;
    return 0;
}

まあ、現状の自分のレートからすると「C問題をACすること」が第一目標なので、1時間以内に解き切れればセーフである。

続いて2問目。

ABC128 C問題

atcoder.jp

問題が複雑で条件の理解に結構苦労した。
ただ、要は取りうる全てのスイッチのon/offの組み合わせに対し、愚直に全探索して「電球が全て点灯するパターン」をカウントしていけばいいだけではある。

計算量としてはO(2^10)より少し多いくらいの計算量であるから、TLEを気にする必要は無し。
実装的な部分で「スイッチのon/offの全パターンをどう表現すればいいのか」に悩んだ。まさかrep(i, 2)をN回繰り返すような愚直なプログラムは書きたくない…。

ChatGPTに聞いてみると、「bitシフト演算」というものを使うと良いらしい。例えば、2^Nまでのループを回したい場合は、

for (int bit = 0; bit < (1<<N); ++bit) {
}

のように、bitシフト演算を使って表現することができる。これは2^Nと同じ計算をしているらしい。
また、これを各スイッチのon/offの組み合わせに変換する際は、

vector<bool> switches(N);
rep(i, N) {
    switches[i] = bit & (1 << i);
}

のようにする。
これは、まず1にiビットシフト演算を適用することで「iビット目のみが1で他が全て0」であるような整数を作っている。
次に、その整数とbit（これはforで回しているローカル変数）をAND演算し、「bitのiビット目が1である場合true、0である場合false」を返すような操作を実現することができる。
調べながらやってたけど、こんな風にできるんだね。

最終的に作成したコードは以下。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <bitset>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> K(M), P(M);
    vector<vector<int>> S(M);
    int all_swit_light = 0;
    rep(i, M) {
        cin >> K[i];
        S[i] = vector<int>(K[i], 0);
        rep(j, K[i]) cin >> S[i][j];
    }
    rep(i, M) cin >> P[i];
    vector<bool> switches(N);
    for (int bit = 0; bit < (1<<N); ++bit) {
        rep(i, N) {
            switches[i] = bit & (1 << i);
        }
        int flag = 1;
        rep(i, M) {
            int sum_swit = 0;
            rep(j, K[i]) {
                if (switches[S[i][j]-1]) sum_swit += 1;
            }
            int on_swit_per2 = sum_swit % 2;
            if (on_swit_per2 != P[i]) {
                flag = 0;
            } else {
            }
        }
        if (flag==1) {
            all_swit_light += 1;
        }
    }
    cout << all_swit_light << endl;
    return 0;
}

掛かった時間は1:04:48:34。
問題の条件が複雑で、入力形式も2次元ベクトルの取り扱いとかに少し苦戦し、実装面でも細かいミスを逐一修正しながらやって1時間を超えてしまった。
しかし、逆に言えば1時間を掛けて一つの作品を作り上げたと言うこともでき、ACの文字を見たときは少し感動というか達成感があった。
難しいと感じる問題ほど解けた時は達成感を感じるものだ。

本日は以上。
いよいよ明後日が復帰後2回目のABCなので、それに向けて万全の準備をしていきたいところではある。

読書記録『その仕事、AIエージェントがやっておきました。』二章まで

今日は読書記録の一環として、西見公宏氏著の『その仕事、AIエージェントがやっておきました。』を読みつつその要約や感想などを書いていく。

今日は第二章まで。

買った経緯・読む前の印象

X(旧Twitter)を見ていたら広告か何かで流れてきたのが目に入った。生成AI系の文脈だった気がするが、「AIエージェント」という単語にはキャッチーさがある。
自分が「AIエージェント」という単語に持つイメージとしては、個別タスクに特化されている近年の生成AIサービスに対して一段階上のレベルであり、例えば①複数のタスクに対する汎化性能がある②ユーザーによる指示を待たずにエージェント自ら自発的行動を行う　等の機能を持っていることが想起される。

実際にはどのような内容であるのかは読んでみないと分からないが、初版2023/12/29出版ということで、自律AIに関する最新の情報が手に入ることを期待して購入。

第一章 あなたの仕事がAIエージェントで変わる

本書ではAIエージェントのざっくりとした定義として「人がいちいち指示をしなくとも、自分でやることを考えて、様々なツールを活用して目標に向かってタスクをこなしていくAIの仕組み」と述べている。

ChatGPTとの対比もされており、ChatGPTはあくまで「指示待ちAI」の域を出ていないという主張だ。以前のプログラミング言語ベースの指令に比べ、ChatGPTは自然言語ベースでの指令が可能になった点において革新的だったが、根本的な「指示待ち」である部分に変化はない。
それを改革するのが自ら行動を行うことができるAIエージェントである、ということだ。

現在あるAIエージェントの例として"GPT Researcher"というオープンソースアプリケーションが紹介されている。
Githubリンクは以下。
github.com

自分としてはAIエージェントがどれほど価値ある存在なのかは実際に自分で体感してみるのが早いと思っているので、本を読むのを中断してこのGPT Researcherを触ってみた方が早いかな…。

データベースとAIエージェントの接続

「自社データベースを管理しているもののそれを活用できている企業は少なく、AIエージェントとデータベースを連携させることで活用コストを軽減できる」という記述があった。確かにAIエージェントが自発的にデータベースから有用な知見を抽出してくれるのであればそれは有意義なことだと思う。
具体的なサービス名としてはAirtableやkintoneというものが挙げられていた。
Airtableとは「便利なクラウドデータベースサービス」のようであり、これそのものはAIエージェントと関係ないが、「Airtable AIエージェント」で検索してみると活用事例のような記事がいくつか出てくる。具体的な活用手法については本には書いていなかったので、踏み込んで理解したい場合は別途自習が必要そうだ。
kintoneの方は、「アプリ開発プラットフォーム」の一種であり、自然言語でアプリ開発をできることを謳っているようだ。こちらは月額780/1500円で利用できる比較的わかりやすそうなサービスだったので、一回自分で触ってみるのが早そうだ。

こういう本を読んでいて思ったが、やはり概括的な情報をインプットするよりも、具体的なソースやサービスを自分で触ってみて体感するプロセスを踏まないと実態を理解するのは難しいなと感じる。

第二章 AIエージェントとはなにか

第一章でAIエージェントの便利さについて言及し、読者の興味を引いた所で具体的な構造の説明に入っている。

まず最初に述べられているのは「ChatGPT」を始めとするチャット型AIの能力限界について。ChatGPTはいわゆるプロンプトエンジニアリングにより、複雑で高度なプロンプトを与えることでかなり専門的な質問にも回答を生成できるようになっている。
しかしプロンプトエンジニアリングというハードルが障壁となり、結局利便性に限界が生じてしまう、ということだ。高品質な回答を要求すればするほど、ユーザーが要求されるプロンプト技術が高まり、学習コストも生じていく。これがチャット型AIの活用における課題。

これに対しAIエージェントは、あくまで大規模言語モデルの持つ「汎用的な知的能力」をベースにしながらも、それを自律的なエージェントとして構築するという仕組みになっている。
例として挙げられているのがAutoGPT。
github.com
これもPythonで実装されたオープンソースプロジェクトであり、自分で触ってみることができそうだ。

また、本書の中ではAutoGPTはあくまでブームの火付け役であり、これをベースとして試作された様々なAIエージェント開発の流れそのものが重要だと述べられている。いくつかの事例の紹介。
・インターン：指定されたデータベース内のすべてのテーブルの役割を理解し、タスクに応じて自動的にSQLを作成、タスクの完了時にSlackチャンネルで報告。


・Webサイトの自動構築
・BabyAGI：タスク駆動型、というらしい。140行という短いコードで実装されたことが反響を呼んだ。
github.com
最新のBabyAGIであるところのBabyFoxAGIには、自己改善機能が追加されており、完了したタスクについての振り返りをデータベースに保存することで、次のタスクリストを作成する際により良いものを生み出すことができるという仕組みだそうだ。実際どの程度性能向上に寄与しているのか想像するしかないが、ワクワクする。
・Generative Agents：この論文は話題になったのもあり自分も見たことがあったが、本書でも紹介されていた。
arxiv.org
複数のAIエージェント同士の組み合わせによる創発的協働に関する報告。エージェントには初期の記憶が与えられ、それをもとに役割を振る舞う。エージェントが自己の役割（例えば、子を持つ父親であるとか）に従った社会的行動を行なった、という報告だ。
・ChatDev：AIエージェント同士の協働によって架空のソフトウェア開発会社を作ってしまおうという試み。
github.com
これは自分は知らなかったが結構すごいなと衝撃を受けた。Generative Agentsとは違いこちらは具体的な「ゴール」がある上で、最終的には成果物（ソフトウェア）が完成されているようだ。しかも「テスト」というプロセスが含まれているおかげでバグの発見もきっちり行われている。全ての工程が終了し成果物が完成するまでの時間は7分程度だったということだ。これによって作成される成果物がどの程度使えるものなのかは本書を読んでいる上では不明だが、もしそれなりのクオリティのものが生み出せるのであればまさに革命的と思わざるを得ない。

第二章の内容はこれにて終了。AIエージェントという仕組みについては「どうせまともなクオリティのアウトプットができる段階になってなさそうだよな〜」という漠然とした感想を持っていたが、ChatDevを見ると自分の認識が少し甘かったような気がしている。
あと、まだ二章までしか読んでない段階で既に触ってみたいリポジトリがいくつか出てきている。
論文を読んでる時にも思うことなのだが、ある論文を読むために参照されている別の論文を読む必要が出てきたりして、芋づる式にその範囲が無限に広がっていってしまい収拾がつかなくなることがある。これどうにかしないとダメだよな。個人的工夫が必要な領域。

眠くなったので今日はここまで。次回は三章から読んでいく。

C問題過去問解き記録（ABC57_C、ABC95_C）

今日は気付いたら22時になっていた。
1日1個は何か技術的な学びを発信するつもりでいるのだが、この時間からは重いタスクをするのが難しそうなので、軽くAtCoderのC問題の過去問に取り組むことにした。

問題の参考としてはこの記事の"1-6-4.全探索に慣れる！"よりピックアップ。
茶色コーダーになるためのガイドラインとして参考にさせていただいている。
今日は時間的に2問解いていこう。

1問目はこちら。
atcoder.jp

N=A×Bを満たす整数N, A, Bに対して、AとBの桁数が小さくなるように探索する問題。

Nの上限値が10^10とあるので、Nを全探索するとTLEになる。（昨日学んだ計算量の知識である）
直感的には、A, BがNの平方根に近い時にF(A, B)は最小になるだろう。A, BのいずれかがルートNより大きい時、もう一方はルートNより小さくなるため、対称性を考える時探索範囲をルートN、すなわち10^5まで絞ることができる。

この範囲の全探索であれば、TLEを回避できそうだ。

適当にコードを書き、サンプルを通してみたところサンプル3にて以下のようなエラーが。


8547 Floating point exception: 8

よくわからないのでChatGPTに聞いてみたところ、「このサンプルの入力として与えられている9876543210がint型の定義可能域を超えている」と言われた。

なるほど、そういえばはるか昔にAtCoder参加した時もそんなことあったような…

intは32bitサイズであり、格納できる整数の絶対値は2^31-1まで。約2×10^9であり、今回のNの定義域はこれを超えているので、Nはint型ではなくlong long型で定義する必要がある。

修正し無事AC。最終的なコードは以下。

#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int digitCount(ll n) {
    if (n == 0) return 1;
    n = abs(n);
    int count = 0;
    while (n > 0) {
        count++;
        n /= 10;
    }
    return count;
}

int main() {
    ll N;
    cin >> N;

    int rank = 10;
    for (ll i = 1; i*i <= N; i++) {
        if (N % i == 0) {
            ll b = N / i;
            if (rank > max(digitCount(i), digitCount(b))) {
                rank = max(digitCount(i), digitCount(b));
            }
        }
    }
    cout << rank << endl;
    return 0;
}

提出までの時間は25:42:97。
83分掛けて解けなかった3/30のC問題とはえらい難易度の差だなと思った。



2問目はこちら。
atcoder.jp

組み替え可能なピザを購入して目的の個数を揃える問題。

A+B <= 2C　の時、ABピザを買うインセンティブが存在しないので答えはAX+BYとなるだろう。
問題はA+B > 2C　の時。この場合はAピザ1枚とBピザ1枚をABピザ2枚に置き換えることで得になる。

そして最後にはABピザ沢山と、AピザもしくはBピザのどちらか単体が残る。こうなった場合現実的には単体ピザを買う方が安いと思うが、一応制約として「ABピザ2枚がA or Bピザ1枚分より安い」という非現実な価格設定もあり得なくはない。即ちA > 2C やB > 2C ということだ。この場合は全てをABピザに置き換えることで金額最小となる。

ここまで考えて後は適当に実装。3つのサンプルが通ったので、後は一応32bitオーバーフローが起きないかどうかだけ確認。

今回はピザの価格が5×10^3 で、ピザの枚数が10^5の範囲。これらの掛け算が合計価格になり、かつABピザは2枚ずつ買うという性質があるので、価格の持つ範囲は2×5×10^8 = 10^9。
これは場合によっては32bitの定義域を超えそうなので、価格だけはlong longで定義しておく。
無事にAC。試しに価格をlong long からintに変更して提出してみたところ、こちらもACしたので、別に関係なかったのかもしれない。

というか、こういう「32bitオーバーフローしそうかどうか微妙」な範囲の変数はとりあえずlong longで定義しておくという雑な方針で行く方が、少なくともAtCoderにおける提出時間を早めるということにおいては正解のような気がしてしまう。いちいち定義域の範囲を計算する時間が勿体無いため。
これには別の制約（メモリ？）が引っかかってくるのだろうか。メモリに関する知識が浅いため、今後調べる必要がありそう。

実際に提出したコードは以下。

#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    ll sum = 0;
    if ((A+B) <= 2 * C) {
        sum = A * X + B * Y;
    } else {
        if (X < Y) {
            if (B <= 2 * C) {
                sum = 2 * C * X + B * (Y-X);
            } else {
                sum = 2 * C * Y;
            }
        } else {
            if (A <= 2 * C) {
                sum = 2 * C * Y + A * (X-Y);
            } else {
                sum = 2 * C * X;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

この問題を解いた後に公式解説を見て思ったのだが、これは全探索で解くべき問題なのだろうか？　自分のコードは完全に条件分岐に従って数学的に解いており、探索を行なっていない。
この辺りはコーダーの性格で済ませていい問題なのか、例えば解の安全性的に探索的に解いた方が良いとかあるのだろうか。今の段階では解ければどっちでもいいか〜としか思えない。

提出までの時間は29:06:34。
3/30ではC問題で突っかかってしまったため「3完って思ったよりムズイか」となっていたが、過去問との難易度差を見るとあれが特別に難化していただけなのかもしれない。
もしくは、年々問題の難易度が上がっているのか。この辺りは回数をこなさないとわからなさそう。

今日の記事は以上。

灰コーダーのABC347振り返り

先日、3/30のABCに約1年と3ヶ月ぶりに参加した。

atcoder.jp

結果はABの2完。

本記事ではC問題までについて、思考や解法を振り返る。


ただ、初回記事なので先に筆者のプロフィールについて軽く触れておく。

参加の動機・AtCoder歴

参加した動機としては「プログラミング力を向上させたい」「第三者から見て客観的に分かるプログラミング力の評価指標を得たい」の2点。

今後も継続的に参加する所存。


筆者の現状の参加回数は4コンテストでRatingは69。

Rated登録だけして不参加が5回あるので、記録上は9回参加している。

パフォーマンスが100を超えていない時期（23/1/15~23/6/10）が「Rated登録だけして不参加」に該当する。

1問も提出していないのにパフォーマンスが0ではないのは不思議だ。パフォーマンスはどのように算出されてるのだろうか？

なぜ参加しなかったのかは覚えていない。「AtCoderに取り組みたい」という意思はあったものの「何か予定があって参加しなかったか」「当日になってやる気が湧かずに参加しなかった」のだと思う。

今後はこのようなことがないよう「土曜の21時-23時には予定を空ける」「当日になってやる気が湧かなくならない工夫を考える」等をしていこう。


当面の目標はRating400、茶色への到達。

レベル感については正直分かっていないが、高橋氏の過去のポストを拝見するに、短くても「2ヶ月」は掛かると書いてある。

これを見るに「ある程度の熱意と技術がある人が毎週参加すれば2ヶ月で茶色になれる」のかなという気がする。

現状の自分は「熱意=ある（自認）」「技術=勉強中、初学者」という感じなので、2ヶ月で茶色になるのは85%くらい無理な気はするが、分かりやすさとチャレンジ精神重視で「2ヶ月後までに茶色になる」ことを目標に掲げようと思う。

即ち、3/30のABCを含めて合計8回の参加で茶色になることであり、毎週参加するという前提で「5/18のコンテスト終了時のレートが400を超える」となる。

乞うご期待。

3/30 ABC347振り返り

結果：AB2完、パフォーマンス385。

17分でAB解いた後、C問題に苦戦し、解けずに終了。

AB問題についてはより早く解くために何が必要だったか、C問題については解くためにどのような知識が不足していたのかを振り返っていく。

A問題(0:00~10:53)

atcoder.jp

提出したコードは以下。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    for (int i = 0; i < N; ++i) {
        if (A[i] % K == 0) {
            cout << A[i] / K << " ";
        }
    }
    cout << endl;

    return 0;
}

この問題に10分も掛かった理由としては、シンプルにC++を書くのが久しぶりだったため初歩的な書式からいちいち調べてしまっていたことである。

・vectorの定義方法がわからなくて調べた。
・forの条件文内の書式方法が曖昧だったので一応調べた。

なお、上の方でrepを定義しているにも関わらず、処理部でforをそのまま使っているのに気付いたのは終了後だった。見返すと面白すぎる。

repについては過去に使っていたC++のテンプレをコピペして使っていたのでコードには残っていたものの、当日はそれに気付かなかったのである。

以上を踏まえて、次回のA問題の目標を「5分以内に解く」とし、そのためには

・A問題で要求される範囲の基本的な書式における曖昧さを無くしておく
・for書式を使わずrepを使う

が必要そうなため、来週までに過去のA問題を10問解いて、5分以内に提出できるように書式慣れしておく。

B問題(10:53~17:15)

atcoder.jp

提出したコードは以下。

#include <iostream>
#include <set>
#include <string>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    string S;
    cin >> S;
    set<string> substrings;

    for (size_t i = 0; i < S.length(); ++i) {
        for (size_t len = 1; len <= S.length() - i; ++len) {
            substrings.insert(S.substr(i, len));
        }
    }
    cout << substrings.size() << endl;

    return 0;
}

当日、この問題を解く際に自分の中で曖昧だった部分は以下。

・C++におけるstd::setの取り扱い方。setは複数の要素を持つデータ構造で、重複した要素を持たないという特徴がある（既に含まれている要素をinsertしてもその操作は無視される）ため、今回のような「重複を除いて個数を数える」タスクで有用。
・C++におけるsubstrメソッドの取り扱い方。string.substr(x, y)によりstringのインデックスx番目から始めて長さyの部分文字列を抽出できる。

これらもA問題と同様、C++における基本的な作法に慣れていないのが原因。

来週までにB問題を10問解き、5分以内に提出できるよう訓練しておく。

C問題(17:15~)

atcoder.jp

非常に難しかった。最終的に提出したコードは以下だが、42/52AC-10/52TLEで通らず。

#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<int> D(N);
    for (int i = 0; i < N; ++i) {
        cin >> D[i];
    }
    bool flag1 = true;
    bool flag2 = false;
    for (int i = 0; i < A+B; ++i) {
        flag1 = true;
        if (i == 0) {
            for (int j = 0; j < N; ++j) {
                if (D[j] % (A+B) > A-1) {
                    flag1 = false;
                    break;
                }
            }
            if (flag1) {
                flag2 = true;
                break;
            }
        } else if (i >= 1 && i <= A-1) {
            for (int j = 0; j < N; ++j) {
                if (D[j] % (A+B) > A-i+1 && D[j] % (A+B)  < A+B-i) {
                    flag1 = false;
                    break;
                }
            }
            if (flag1) {
                flag2 = true;
                break;
            }
        } else {
            for (int j = 0; j < N; ++j) {
                if (D[j] % (A+B) < A+B-i || D[j] % (A+B) > 2*A+B-i-1) {
                    flag1 = false;
                    break;
                }
            }
            if (flag1) {
                flag2 = true;
                break;
            }
        }

    }
    if (flag2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

計算量については非常に理解が浅い。

当日は「適当に書いたらTLEになりそうだな」と思いつつ、「とりあえず叩き台としてTLEになるコードを書きそれを修正していこう」と考えて取り組んでいた。

しかし、思いの外アルゴリズムに悩まされ、ちゃんと動くコードが出来上がったのが終了7分前。提出するも案の定TLE…。残り7分で改善できる訳もなく諦めモードに入り終了。

この問題を解く際に必要だった知識を列挙してみよう。

・計算量に関する理解：制限時間2secと指定有り。実行時間が2secを上回る条件は？
・アルゴリズムに関する理解：「全ての予定が休日である可能性がある」をどう読み解くべきだったか？

計算量に関する理解

どれくらいの計算をすると2secを上回ってしまうのか？　軽く調べてみたところ1秒当たり10^7の計算量が目安である、という記事を見つけた。

とすると、基本的にはO(10^7)以下の計算に収める必要がある。

今回自分が書いたコードでは、A+B<=2*10^9とN<=2*10^5の2重ループを回していたため、計算量はO(10^14)となる。余裕のオーバーだ…。

であれば、そもそもA+Bをループで回すこと自体が推奨されてないことが問題文に書いてあったということになる。他の多くの参加者はそれに最初から気づいて、アルゴリズムを考える指針にしていた筈。後述するが自分は「今日が1週間のi日目であると仮定し、iを1→A+Bでループ」する方針を取ったが、それが根本的に間違いだったことになる。計算量に関する知識がなかったせいで初動の方針決めの段階で大損してしまったのか。

今回で計算量に関する理解は深まったので、次回は問題を見た時点で気づけるようになっていると思う。

アルゴリズムに関する理解

前提として、DiはA+Bの単位で周期するので、事前に全てのDiをmod (A+B)で置き換えておく。

まず、自分が最初に発想した方針は以下のようなものだった。
・「「N個の予定が全て休日である」可能性を判定する」のだから、「今日」を「1日目」から「A+B日目」までで全て走査し、その内一つでも「N個の予定が全て休日である」ような「今日」があれば即座に"yes"を出力すれば良い。

→しかしこれは前項で挙げたようにO(A+B) = 10^9であるためTLEに引っかかるので方針として不適切である。

であればどうするか？　次に思いついたのは「存在し得る「今日」の領域」を「予定」によって塗りつぶしていく方針。

例えば、A=2, B=5を考え、D1=3である状況を考える。この時、「今日」としてあり得るのは「5日目」もしくは「6日目」のみとなる。なぜなら他の日付では「3日後が休日」の条件を満たさなくなるため。

つまり、予定Diそれぞれに対し、自然数領域[1, A+B]から「今日」としてあり得る長さAの部分領域[x, x+A-1]が与えられることになる。
全ての予定Diに対して、この部分領域の共通集合を求め、長さが0でなければ題意は満たされる、というわけだ。計算量としてもO(N)で済みそう。

しかし、これを実装するに当たって面倒なのが「部分領域が2分割されることがある」ということだ。
例えばA=2, B=5, D1=1の時、部分領域は[1, 1]と[7, 7]の2つに分割される。これはDiがAより小さい場合に発生し得る。

あとは、C++で「領域の共通集合を求める」という実装をしたことがなく、、、という感じで当日は時間切れもあり断念した記憶。

この辺で一旦、解説を見てみることにする。
atcoder.jp

これを見て、なるほどなーが1つ、よく分からんが2つ。

予定について、重複を削除しソートしてもよいのには気付かなかった。これは、予定の順番が解答に影響ないため。なるほど。

ただ、証明部分がうまく飲み込めない。

ぱっと見るに「ある予定と、それより少し遅い予定について、その差がBより大きいこと」が全ての予定の内1つでもあれば題意を満たす、と主張しているように読めてしまう。これって「あるi」じゃなくて「全てのi」じゃなくて大丈夫なの？　「全ての予定が休日である」必要があるのに、あるiについてだけ条件を満たせば良いと主張しているのが直感的に納得できなかった。

と、思ったのだが、公式解説放送の方を見に行ったら多少理解できた。
www.youtube.com

この円環を参考に自分で図を描いてみた。

上記の図は「どうしても平日に予定が入ってしまう場合」を描いている。
確かに、これを参考にすると「ある予定の次の予定との差がBより大きい組み合わせが存在しない」のが分かる。

つまり平日に予定が入ってしまうと「平日の予定」と「休日の予定の内、最初のもの」との差がBより小さくなるのだ。

で、逆に全ての予定が休日に収まる場合、差がB以上になる隣接する予定の組み合わせが必ず存在すると。

なるほどー。

理解はできたものの、ではどのような知識が必要だったのかと考えると、正直分からない。

この辺は今後C問題を解く経験を積んで、感覚を磨いていく方針でいくことにする。

実装としては、所定の処理をした後に隣接する予定の組み合わせを取り出していき、差がBより大きいものがあるかを判定していくだけ。簡単だね。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    int W = A+B;
    vector<int> D(N);
    rep(i, N) {
        cin >> D[i];
        D[i] %= W;
    }
    sort(D.begin(), D.end());
    rep(i, N) D.push_back(D[i]+W);
    rep(i, N) {
        int l = D[i], r = D[i+1];
        if (r-l > B) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

AC出たので満足。

D問題以降

今回はC問題で手一杯だったので、D問題以降は一旦スキップ。
調べる感じ茶色になるにはCまでの3完ができれば十分、みたいな記事がちらほらあったので、とりあえずこれから2ヶ月の間はCまでをキッチリ解けるようになることを目指していく。

今日の記事は以上。