ABC453-D「Go Straight」を解きました✅

状態管理や経路復元で頭が混乱してバグが取れず、2日がかりでようやくAC😅 諦めずに向き合い続けたことで達成感がひとしおでした🚶

gist.github.com/maehrm/63ab988ee06677166...

#AtCoder #競技プログラミング

ABC368-F「Dividing Game」を解きました✅

素因数の個数がそのままGrundy数になり、全要素のXORで勝敗が決まるNim理論の問題。初めてGrundy数を使った問題に取り組みましたが、発想の美しさに感動しました🎮

gist.github.com/maehrm/98dce8760427bb7c6...

#AtCoder #競技プログラミング

ABC332-D「Swapping Puzzle」を解きました✅

行・列の並べ替えを全順列で探索してAをBに一致させる組み合わせを探し、転倒数の合計が最小操作回数になるという解法でした🧩

gist.github.com/maehrm/ce0fb53b1f98d9523...

#AtCoder #競技プログラミング

YMM734 @hyuki.net AIのハルシネーションという言葉にはだいぶ慣れましたが、シコファンシーという言葉は初めて聞いたような気がします。今から30年以上前、コンピュータの世界に触れるようになった頃にはこのような言葉の中で生きるとは想像もしなかったですね。まさに『AIと生きる』という感じです。

ABC246-D「2-variable Function」を解きました✅

最初は二分探索(127ms)で解きましたが、尺取法でも解けることに気づいたら60msと約2倍速くなりました。同じ問題でも解法次第でこんなに変わるんですね🔢

gist.github.com/maehrm/f70ab20e25332c310...

#AtCoder #競技プログラミング

ABC273-D「LRUD Instructions」を解きました✅

アイデアはすぐ思いついたのにインデックス周りのバグが取れず苦戦😅 端点を番兵として初期値に入れることでスッキリ解決できました🗺️

gist.github.com/maehrm/9992a7791a75783f9...

#AtCoder #競技プログラミング

ABC377-D「Many Segments 2」を解きました✅

ABC444-Eで尺取法に触れたので、考え方をより定着させるために取り組みました。右端rを動かしながら有効な左端maxLを更新するだけのシンプルな実装でした🔍

gist.github.com/maehrm/1498493cf8427ef1a...

#AtCoder #競技プログラミング

YMM733 @hyuki.net 「絵文字+アルファベット+番号」の箇条書き、早速真似してみました。#インクリメンタルな環境改善 ですね。『AIと生きる』第6章の副題、改めて見てみるとAuthorshipになってますね。折を見て読み返したいと思います。

ABC444-E「Sparse Range」を解きました✅

スライディングウィンドウ＋SortedListで管理。D未満の隣接要素があれば左端を縮めるだけのシンプルな実装でした📏

gist.github.com/maehrm/54a11733f639d9400...

#AtCoder #競技プログラミング

ABC322-E「Product Development」を解きました✅

K個のパラメータをタプルで状態管理する多次元DP。dictで状態を管理することでメモリを節約しました。タプルをキーにしたDPの発想が面白かったです🏭

gist.github.com/maehrm/b12678a7278488401...

#AtCoder #競技プログラミング

ABC192-E「Train」を解きました✅

ダイクストラ法で解きつつ、次の電車の出発時間を`((t+k-1)//k)*k`で切り上げ計算するのがポイントでした。スッキリ書けて気持ちよかったです🚆

gist.github.com/maehrm/41bafbb26b8456f22...

#AtCoder #競技プログラミング

ABC319-C「False Hope」を解きました✅

9マスの並び方を全順列で試して、リーチになる並び方を数える全探索解法。9!=362880通りなので間に合いました🎰

gist.github.com/maehrm/4ba25c0479c96135b...

#AtCoder #競技プログラミング

ABC391-E「Hierarchical Majority Vote」を解きました✅

再帰で多数決を計算しながら最小コストも管理。「コストが低い2つを選べば多数決を変えられる」という考え方がポイントでした🗳️

gist.github.com/maehrm/574442e7a2524bdb5...

#AtCoder #競技プログラミング

ABC303-E「A Gift From the Stars」を解きました✅

葉からBFSで内側へ向かい、葉の親を星の中心として確定していく処理を繰り返す解法。葉から順番に剥がしていく発想が面白かったです⭐

gist.github.com/maehrm/413c3c4d278559b9a...

#AtCoder #競技プログラミング

ABC198-E「Unique Color」を解きました✅

DFSで色のカウントを+1/-1するバックトラッキング解法。カウントが1のときだけ答えに追加するシンプルな実装で、再帰の美しさを感じた一問でした🎨

gist.github.com/maehrm/46851421931fe9ea9...

#AtCoder #競技プログラミング

ABC254-D「Together Square」を解きました✅

i×jが平方数 ⟺ iとjの平方フリー部分が等しいという性質を利用。篩で平方フリー部分を求めて同じ値の個数の二乗を合計するO(NlogN)解法でした🔢

gist.github.com/maehrm/ca05aa243299a8793...

#AtCoder #競技プログラミング

ABC340-E「Mancala 2」を解きました✅

K個の石をNで割った商・余りに分けて処理し、BITの差分配列で区間加算を高速化しました。BITの使い方の幅が広がった一問でした🪨

gist.github.com/maehrm/5669801dac18e4712...

#AtCoder #競技プログラミング

平成24年度秋季基本情報午後問8 - Mae向きなブログ 平成24年度秋季 基本情報技術者試験(FE)の午後問題8は、 Warshall-Floyd法(ワーシャルフロイド法)を用いて鉄道駅間の最短距離を求める 問題でした。 鉄道の路線から最短距離を求めるという身近な題材であり、これが発展したものがYahoo!などが提供している「乗換案内」アプリにつながっているのかもしれないと思うと、中々楽しい題材だなと思います。 問題を解くだけではもったいないので、問題...

Warshall-Floyd法というと、平成24年度秋期 #基本情報 の午後問8で鉄道駅間の最短距離を求める問題として出題されてますね。鉄道というとても身近な話題でしたので特に印象に残っています。面白い問題でした。

平成24年度秋季基本情報午後問8 - Mae向きなブログ maehrm.hatenablog.com/entry/2019/0...

YMM732 @hyuki.net 《愛の原則》と自分で書くと恥ずかしさがあるので、相手のことを思いやると言い換えて実践したいなと思います。こんなに人間的なことをAIに教えるという発想が面白いですね。具体的な指示と抽象的な原則、双方が必要というのも人間的だなと感じます。

ABC286-E「Souvenir」を解きました✅

Warshall-Floyd法で[最短距離, 最大価値]を同時管理。同距離なら価値が大きい方を選ぶ条件分岐がポイントでした🎁

gist.github.com/maehrm/7ecee96b8c3a814d6...

#AtCoder #競技プログラミング

ABC417-E「A Path in A Dictionary」を解きました✅

DFSで辞書順に次の頂点を試しながら、BFSでYへの到達可能性を確認してから進むアプローチで解けました。無駄な探索を避けるのがポイントでした📖

gist.github.com/maehrm/a1641b8e57aae6a5a...

#AtCoder #競技プログラミング

ABC031-C「数列ゲーム」を解きました✅

高橋君がiを選んだとき青木君が最善手jを選ぶという流れをO(N²)で全探索。Nが小さいのでシンプルな実装で解けました🎮

gist.github.com/maehrm/67df03eca20455c82...

#AtCoder #競技プログラミング

ABC323-D「Merge Slimes」を解きました✅

ヒープで小さいサイズから順に処理し、2体以上いれば半分を合体させて次のサイズに繰り越すシンプルなシミュレーションで解けました🟢

gist.github.com/maehrm/f2d6fc7b8aaad1de8...

#AtCoder #競技プログラミング

ABC445-D「Reconstruct Chocolate」を解きました✅

現在のH・Wと一致するピースからBFSで順次確定していく構築解法。確定のたびにH・Wが更新されて新たなピースが確定できる連鎖がポイントでした🍫

gist.github.com/maehrm/a60d12f06b5d7db36...

#AtCoder #競技プログラミング

ABC179-E「Sequence Sum」を解きました✅

ループ検出でループ前・ループ周回分・端数に分けて計算する解法。ABC241-Eと同じ発想で解けてパターン認識の大切さを感じました🔁

gist.github.com/maehrm/78976137ab180808d...

#AtCoder #競技プログラミング

ABC324-E「Joint Two Strings」を解きました✅

前半マッチ長A[i]と逆順後半マッチ長B[i]を事前計算し、BをソートしてA[i]+B[j]>=len(T)となる組み合わせを二分探索で数えるO(NlogN)解法でした🔗

gist.github.com/maehrm/7706cb3a059f490a0...

#AtCoder #競技プログラミング

ABC165-C「Many Requirements」を解きました✅

NとMが小さいので再帰で単調非減少な数列を全列挙してスコアを計算する全探索で解けました。シンプルな実装でスッキリ解けて気持ちよかったです📊

gist.github.com/maehrm/78742c102777a4798...

#AtCoder #競技プログラミング

ABC428-E「Farthest Vertex」を解きました✅

木の直径の両端点u,vを求め、各頂点からの距離で最遠頂点を判定する典型アルゴリズムで解けました🌳

そしてこの問題でAtCoderの解答数が1000問に達しました🎉 これからも学んでいきたいですね。

gist.github.com/maehrm/826b4d56d4c2ac09f...

#AtCoder #競技プログラミング

YMM731 @hyuki.net メタファーで考えると分かりやすいのは、AIがどんどん人間に近づいているからなのかなと思いました。明日から新社会人が誕生するんでしょうけど、研修中の新社会人のようにも思えます。AIを育てる、世話するって子育てになってるようにも思えますね。もう単なるツールではありませんね。🌸

ABC334-E「Christmas Color Grid 1」を解きました✅

BFSで島数を管理し、各赤マスを緑にしたときの増減を「1-(隣接する異なる島数-1)」で計算。全赤マスの合計を個数で割って期待値を求めました🎄

gist.github.com/maehrm/0e7911f85a84ff01d...

#AtCoder #競技プログラミング