問題
既存投稿一覧ページへのリンク
独り言
この問題が、diff:974(緑コーダーの中の下レベル)って嘘でしょ？
それとも気がついたら一瞬で解ける系なのかな。
有向グラフのBFSで全座標から辿れるマスの数を高速にカウントするとか。（私はそのアプローチ捨てたけど）
すっごい苦労してACした後にdiffを確認したら、下みたいな表情になってしまいましたよ。
問題が難化傾向にあるのは良いとして、解いている人のレベルも上がっているのかね。
それにしても、この問題が緑コーダーの中の下レベルであれば解けるのか…。
競技プログラミング勢は凄いな。
正直、上を見たらキリがないし、解ける問題を解いていこうって気持ちでやってるエンジョイ勢だし、
自信喪失するだけだからAtCoderの受験は止めておこっ。
パズル感覚で問題を解いてる方が私の性にあってますわ。
問題自体はBFS,DFS,UnionFindのいずれかだろうなって思い付き、
無向グラフの問題でなく、有向グラフとして全座標BFSして一番移動距離の大きいものを
答えにすれば楽勝じゃんって思っていたんだけど、TLEしてしまいました。(´・ω・`)
最終的にはUnionFindで両方向のエッジがあるノードを一塊にした後、各塊ごとのノードと結合できるノードをカウント(タプルで重複削除)するアプローチを採用。
個人的にグラフ系の問題は動的計画法や幾何学系の問題より得意なつもりでいたけど、本気で難しかった・・・
まぁ難易度は別として、解けた後は爽快感があるからAtCoderをキメるのは止められないんだけどさ。
全然関係ない話だけど「ドカ食いダイスキ！ もちづきさん」を読んで依頼、食事記録をつける習慣が出来、食前にメカブや納豆を食べて血糖値が上がらない生活を送ってます。
アプローチ
UnionFindで両方向のエッジがあるノードを一塊にした後、各塊ごとのノードと結合できるノードをカウント(タプルで重複削除)する。
【例題をトレースすると下記のような流れ】
解法手順
- 入力の受け取り
- h, wを入力
- sを入力
- UnionFind インスタンス U を作成（サイズ h * w）
- 関数 f(i, j) を定義
- 各マス(i, j)の周囲4マスを調べ、連結可能なマスの集合を返す
- HW 配列の初期化
- 各マスに対して f(i, j) を適用し、結果を格納
- 連結処理
- 各マスについて、周囲4マスとの連結関係を UnionFind に登録
- 最大連結サイズの計算
-. グループ内のマスを集合 x に追加
-. 各マスの HW[j // w][j % w] を x に追加
-. x の要素数の最大値を ans に保存
ACコード(PyPyで提出)
from collections import defaultdict
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def members(self):
group = defaultdict(list)
for member in range(self.n):
group[self.find(member)].append(member)
return group
# 3. 関数 f(i, j) を定義
# - 各マス(i, j)の周囲4マスを調べ、連結可能なマスの集合を返す
def f(i, j):
temp_map = set([])
if s[i][j] == ".":
for x, y in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
if 0 <= i + x < h and 0 <= j + y < w:
if s[i + x][j + y] == "#":
temp_map = set([])
break
else:
temp_map.add((i + x) * w + (j + y))
return temp_map
def solve(h, w, s):
# 2. UnionFind インスタンス U を作成（サイズ h * w）
U = UnionFind(h * w)
# 4. HW 配列の初期化
# - 各マスに対して f(i, j) を適用し、結果を格納
ans = 1
HW = [[0] * w for _ in range(h)]
for i in range(h):
for j in range(w):
HW[i][j] = f(i, j)
# 5. 連結処理
# - 各マスについて、周囲4マスとの連結関係を UnionFind に登録
for i in range(h):
for j in range(w):
if len(HW[i][j]):
for x, y in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
if 0 <= i + x < h and 0 <= j + y < w:
if len(HW[i + x][j + y]):
U.union(i * w + j, (i + x) * w + (j + y))
# 6. 最大連結サイズの計算
for i in U.members().values():
# -. グループ内のマスを集合 x に追加
x = set(i)
# -. 各マスの HW[j // w][j % w] を x に追加
for j in i:
x |= HW[j // w][j % w]
# -. x の要素数の最大値を ans に保存
ans = max(ans, len(x))
print(ans)
if __name__=="__main__":
# 1. 入力の受け取り
# - h, wを入力
# - sを入力
h, w = map(int, input().split())
s = [input() for _ in range(h)]
solve(h, w, s)
その他
AtCoderの特定の問題だけにフォーカスを当てた、アルゴリズムの可視化本を出版したいと考えております。
特に、動的計画法や、グラフ問題については、毎回図示するのも大変だと思いますし。
極力図解説明に力を入れておりまして、2024年11月現在下記の本を出版しております。
情報処理関連
拙著に情報処理試験を解いてみたシリーズをKindle出版しております。
蛇足
3年くらい前までは、IPAの過去問は、AtCoder同様に趣味で解いていたけれど、今年の問題を見てみたら、ほぼ解けなくなってた。(-ω-`)⌒)_
この数年、職務内容が変わって、ネットワークやセキュリティに縁遠かったからなぁ。
TOEICもそうなんだけど、身に付いた知識って、常にアップデートかけてないと本当に置いてかれてますね。
特に、「合格経験」があったりなんかすると、無駄にプライドが芽生えてしまって「有識者顔」してしまいますし。
まだ、技術に置いていかれたくないので、また勉強し直し、Qiita記事の執筆やKindle本の出版等で知識の共有を図りたいと思っています。
pythonのmatplotlib練習
matplotlibの実験で、2020年前半に試しに出版したものですが、今はもっと簡単にコーディング出来ると思いたい・・・
1991年1月1日～2020年3月31日日経平均株価の変動情報（日本の出来事編）
四季報に記載されている「比較会社」をDFSやBFSの解説と紐づけてAtCoderで得た知見を実務に活かしたいと思っています。
Kindle Unlimitedで読むことが可能なので、もしご興味のある方がいらっしゃいましたらお手に取ってください。
（購入いただけると、嬉しいです。）