AtCoder Beginner Contest 325参加記（A～C）
キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）に参加したので記録を残します。
今回は3完、微温まり。
A - Takahashi san
文字列にちょっと付け足して出力するだけなので、A問題にしてもかなり簡単な部類ですね。
fun main() {
val (s, t) = readln().split(" ")
println("$s " + "san")
}
まあ
これに1分かかってるのはよくないですねぇ。
B - World Meeting
結果的には全探索するだけでしたが、ちょっと時間がかかってしまいました。
考え方としては、世界標準時であり得るパターンを全部列挙して、それぞれを各拠点の時刻になおして9:00から18:00に収まるかどうかを調べます。
import kotlin.math.max
fun main() {
val n = readln().toInt()
val wx = List(n) {
val (w, x) = readln().split(" ").map { it.toInt() }
w to x
}
var ans = 0
for(i in 0 until 24) {
var sum = 0
for((w, x) in wx) {
if(((i + x) % 24) in 9..18 && ((i + x + 1) % 24) in 9..18) {
sum += w
}
}
ans = max(ans, sum)
}
println(ans)
}
最初は % 24 を忘れてました。
答えは最大でも ansはIntでも大丈夫。
C - Sensors
グラフとして捉えて連結成分の数を数えるだけなので、Union-Findを使うだけじゃんとすぐに気づきました。ただ、愚直に考えると頂点は単一の数値ではないので、手元にあるUnion-Findの実装はそのまま使うことはできませんでした。結局DFSかBFSで数えることに。
最初に提出したのは以下。まずグラフを作って、各センサーがあるマスから探索を開始、連結している頂点の探索済フラグを設定していきます。全マスからの探索を試行しますが、探索済フラグが設定されていれば既知の連結成分なのでスルー、未知の連結成分が見つかったら答えをカウントアップしてそこから辿れる頂点を探索済みにする、としていきます。
import java.util.ArrayDeque
fun main() {
val (h, w) = readln().split(" ").map { it.toInt() }
val s = List(h) {
readln()
}
val diList = arrayOf(-1, 0, 1, -1, 1, -1, 0, 1)
val djList = arrayOf(-1, -1, -1, 0, 0, 1, 1, 1)
var count = 0
for(i in 0 until h) {
for(j in 0 until w) {
if(s[i][j] == '#') {
count++
}
}
}
val graph = mutableMapOf<Pair<Int, Int>, MutableList<Pair<Int, Int>>>()
for(i in 0 until h) {
for(j in 0 until w) {
if(s[i][j] == '.') {
continue
}
for(k in 0 until 8) {
val di = i + diList[k]
val dj = j + djList[k]
if(di !in 0 until h) {
continue
}
if(dj !in 0 until w) {
continue
}
if(s[di][dj] == '.') {
continue
}
val start = i to j
val end = di to dj
graph.putIfAbsent(start, mutableListOf())
graph[start]?.add(end)
//graph.putIfAbsent(end, mutableListOf())
//graph[end]?.add(start)
}
}
}
val ans = walk(h, w, graph, s)
println(ans)
}
fun walk(h: Int, w: Int, graph: MutableMap<Pair<Int, Int>, MutableList<Pair<Int, Int>>>, s: List<String>): Int {
val seen = mutableSetOf<Pair<Int, Int>>()
var ans = 0
for(i in 0 until h) {
for(j in 0 until w) {
val start = i to j
if(start in seen) {
continue
}
if(s[i][j] == '.') {
continue
}
ans++
seen.add(start)
val queue = ArrayDeque<Pair<Int ,Int>>()
queue.add(start)
while (queue.isNotEmpty()) {
val v = queue.removeFirst()
//System.err.println(v)
if(v !in graph) {
continue
}
for(node in graph[v]!!) {
if(node in seen) {
continue
}
seen.add(node)
queue.add(node)
}
}
}
}
return ans
}
しかしこれはTLEに。
うーん、全部見ると
計算量はどう改善すればいいか思いつかず、まあなんとか頑張ってUnion-Findでやれば問題ないはずなのですが、もうちょっと簡単なことが思いついて試してみようと思いました。
それはC++での書き直し。おそらく計算量としては問題ないし、C++なら通るんじゃないかなって…
自分で書き直すのは大変なので、AIにやらせてみました。C++は以前使っていたので、ベースだけ作ってもらって細部は自分で直すつもりでした。しかし、実際には1つだけコンパイルエラーを取り除いたら、サンプルは全部合いました。もしや…とそのまま提出。
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <set>
using namespace std;
int walk(int h, int w, map<pair<int, int>, vector<pair<int, int>>> graph,
vector<string> s) {
set<pair<int, int>> seen;
int ans = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
pair<int, int> start = make_pair(i, j);
if (seen.count(start)) {
continue;
}
if (s[i][j] == '.') {
continue;
}
ans++;
seen.insert(start);
deque<pair<int, int>> queue;
queue.push_back(start);
while (!queue.empty()) {
pair<int, int> v = queue.front();
queue.pop_front();
if (graph.count(v) == 0) {
continue;
}
for (auto node : graph[v]) {
if (seen.count(node)) {
continue;
}
seen.insert(node);
queue.push_back(node);
}
}
}
}
return ans;
}
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
for (int i = 0; i < h; i++) {
cin >> s[i];
}
int di[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dj[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
map<pair<int, int>, vector<pair<int, int>>> graph;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (s[i][j] == '.') {
continue;
}
for (int k = 0; k < 8; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni < 0 || ni >= h || nj < 0 || nj >= w) {
continue;
}
if (s[ni][nj] == '.') {
continue;
}
graph[make_pair(i, j)].push_back(make_pair(ni, nj));
}
}
}
int ans = walk(h, w, graph, s);
cout << ans << endl;
return 0;
}
通った！こんなことあるんですねぇ…
追記
いくつかのパターンでC問題を解き直しています。
長くなるのでコードは貼らずリンクだけ。
Union-Find解法
頂点を一つの数値にすればUnion-Findが使えました。縦のほうを1000倍にして足せば一意の数値と扱えると… 思いつかなかったなあ。
今回の解き直しだとこれが一番高速ですね。
頂点を数値で扱ってBFS
頂点を数値化すればBFSもできます。TLE解法と計算量は変わりませんが定数倍がだいぶ軽くてACとなりました。
隣接行列としてBFS
公式解説だとそもそもグラフを扱うための隣接リストを作る処理をしていなかったです。まあ、隣接リストを作る解法だと全探索を二回するので無駄が多いです。今回TLEになった理由でもあり…
それで、入力をそのまま隣接行列と捉えれば別にグラフのためのデータを作らずに解けますね。
この解法もかなり高速でした。
隣接行列としてBFS、探索済フラグをSetにする（TLE）
基本的に上と同じ解法ですが、探索済みかどうかをSet<Pair<Int, Int>>にした点だけ異なります。これでも通るかなと思ったのですが1件だけTLEとなって通らず。
Pairをハッシュテーブルで使うとめちゃくちゃ遅いのですね…
その他
Cを解いた時点で1時間くらい経っており、疲れてしまったのでDは着手せず。（問題文は一応見た）
感想
Cの通し方は若干ずるいと言えなくもないですが、そこはあまり気にしていないです。ベースのコード自体は自分で書いたので。自分ができないことをAIにやらせるのはリスクが高いですが、できることをやらせて省力化するのはAIの正しい使い方なのかと。
ただ、通らなかった悔しさはあるので、後日KotlinのままACしようと思います。今回の解法の延長と、Union-Findを使った解法の両方やりたいですね。今思えば、頂点を一つの数値として表現する方法を考えれば普通にUnion-Find使えるんじゃないかという気が…
まあTLEになったのでアレですが、一応WAは出ない（はずの）コードをちゃんと書けたのは嬉しいと少し思いました。ちょっと前の私だと、バグらせまくってサンプルすら通らないってことになっていた気がするんですよね…
グリッドに何度か殺されましたし。特に斜めの扱いが苦手過ぎて。なのでこれでも多少は前進しているのかなと。亀の歩みのようなものですが。
あとは、やっぱり実装が遅いというのを痛感しましたね。Cまで通すのに1時間はちょっとかかりすぎなのかと。Cまで速く解ければレーティングが高くなるというのもありますが、それくらい速く解かないとDに着手するための時間が残らないのですよね。あと、上に書いた通りで、時間がかかるということはその分脳への負荷も高いので疲れてしまい、Dを解くには時間もないけどそれ以前に気力がないということになってしまいますね。
今までDがコンテスト中に解けたことはありますが、いずれもCまでが簡単だったため速く解けたときか、もしくはCが無理すぎてスキップした場合かのいずれかなんですよね。Cまで時間がかかったのちDが解けたことはたぶんなくて…
ということで、しばらくは難しい問題が解けるようになるための練習よりは、Cまでを速く解くための練習のほうが重要なのかなあという気がしました。
反省点は多々あるにせよ今回はなんか楽しかったです。これからの楽しんでいきます。
（執筆時間: 38分2秒）
Discussion