ラベル フロー の投稿を表示しています。 すべての投稿を表示
ラベル フロー の投稿を表示しています。 すべての投稿を表示

2026年9月4日金曜日

AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）

　Gが解けず。

コンテスト後のツイート

G - Cascading Grid

　「燃やす埋める」だと聞いても解法が分からず、けんちょんさんが最近出した記事を読んでAC。
　が、この記事の解法通りの方法は思いつけず、グリッド中の、#でない最も左端の頂点だけを取り出し、そこから左右だけを見たときのスコアの増減を見て、その頂点同士の木構造を調べて、ようやく燃やす埋める問題に直せてACできた。

　その後、けんちょんさんの解法も理解してACしたけど、その実装にも苦戦。

　「燃やす埋める」の中では簡単な問題と書いている人もいたが、個人的には簡単に思えなかった。もっと慣れたら違うのかなぁ。
時刻: 0 件のコメント:
ラベル: , ,

2025年12月26日金曜日

ユニークビジョンプログラミングコンテスト2025 クリスマス（AtCoder Beginner Contest 437）

　Fまで六完だがEに手こずった。

コンテスト後のツイート

G - Colorful Christmas Tree

　解説放送を見てAC。

　コンテスト中、フローは少し考えたのだが、使い方が分からなかった。

　次数を見れば最終的に何の色になるか分かるとは思ったが、その間の色を全部使うと気付けなかったのが敗因か。それに気付ければ自力でフローに思い至れた可能性はある。



時刻: 0 件のコメント:
ラベル: ,

2025年7月13日日曜日

yukicoder contest 473 第1回 生成AI作問コンテスト

　遅刻参加でEまで。

　AIでこれくらいの問題が作れるのか、という思いもあるけれど、実際に作ったときのプロンプトを見るとかなり苦労しているのが分かるので、現状だと、AIによって時間節約になるか？　にはあまりならないのかなぁ。


No.3200 Sinking Islands

　自力AC。
　後ろから見るのはすぐ分かったけど、何を求めれば良いか（後ろから見たときの答えの求めかた）が分からなくなり間に合わず。

　落ち着いて考えれば難しくないが、残り五分では解けなかった。……とはいうものの、五分で解けて良い問題だと思うので、ここで詰まったのは良くなかった。

No.3201 Corporate Synergy

　色々資料を見ながらAC。

　燃やす埋めるだと分かってからも時間がかかってしまった。
　特に「Aが赤でBが赤だとC円報酬」の形のときどうするかが分からず調べた（参考：ここやここ）。このときは頂点を追加すれば良いのね。

No.3202 Periodic Alternating Subsequence

　解説AC。生成AIが作った問題を解けなかったのは良くないねぇ。典型といえる内容だし。

　制約から行列累乗を使いそうとは分かるが、そこへもっていけなかった。つまり、K=1の場合のDPが構成できなかったということ。

　こういう、スコアが二乗の形で表される問題は、二乗という特性を使って何かすることが結構あるが、上手く使えず解けていないことが多い。とりあえず、l^2が(l+1)^2になったらどうなるか？　というのを式で書き眺めて見なくてはいけない。
時刻: 0 件のコメント:
ラベル: ,

2024年10月30日水曜日

Educational Codeforces Round 171 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Best Subsequence

　「燃やす埋める問題」というキーワードを見てAC。

　コンテスト中、フローは少し考えたはずなのだが、ちゃんと追及しなかった。
　DPなどでは指数時間の解法しかないときにフローを疑うのは大事で、特に、「燃やす埋める問題」を疑ってみなくてはいけない。

　フローを考えた時間はあったはずなのに、「燃やす埋める問題」ではないかと考えなかったのは反省。





時刻: 0 件のコメント:
ラベル: , ,

2024年10月7日月曜日

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）

　Fまで六完。

コンテスト後のツイート

G - Only One Product Name

　解説放送・解説を見て、けんちょんさんの記事も参考にAC。

　SCCして、DAG の最小パス被覆に帰着、という解法はちゃんと勉強していれば思いつけそう。（コンテスト中、自分も一瞬フローでは？　とは思ったので。その後違う方向に行ってしまったけど）

　ただ、実装が難しい。SCCで頂点と頂点とを同一視できても、そこから出ている辺は同一視できない、というあたりが混乱を招く。

　たとえば、AとBには両向きの辺があり、CとDには両向きの辺がある。さらに、AからCへ、BからDへそれぞれ辺があるとき、この二つの辺は区別しないといけない。

　このあたりに注意するのが非常に難しく、たくさんのWAを重ねてしまった。解法を詰めてからやればできるのかもしれないけど、解法の概要が思い浮かび、細かいところは実装しながら詰めよう、とすると非常に難しい気がした。
時刻: 0 件のコメント:
ラベル: , ,

2024年5月7日火曜日

yukicoder contest 291

 　ABの二完。Bで唖然とするようなミスをして、Cも分からぬまま終了……。


No.1478 Simple Sugoroku

　自力AC。

　ワープを使う場合、「後ろx個へワープで辿りつけたらそこからは歩く」という戦略を取るのが良く、このxを全探索すればOK。

No.1479 Matrix Eraser

　フローの練習で解いた。自力でグラフは構築したがTLEが取れず、他の人の提出などを見てAC。

・start→縦でまとめられるもの→(i, j)→横でまとめられるもの→goal

　というグラフを考えたが、これだとMLE・TLEしてしまった。
　（i, j）の部分は省略することが可能。また、A[i][j]の値ごとにflowを流せば良いので、H+Wの大きさのflowをHW回流す感じで解ける。
　こうすればACできた。

　ただ、言語とかDinic法の実装とかで工夫したら最初の方針でもACできたはず。そういうライブラリも持っておきたいね。
時刻: 0 件のコメント:
ラベル: ,

2024年4月28日日曜日

AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテスト後のツイート

D - Swap Permutation


　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。

E - Max Vector

　解説AC。

　問題を読んでフロー（最小カット、燃やす埋める）じゃないかとは思ったが、どうやってグラフを作れば良いのか。

　とりあえず、

・Nが多いことはあまり本質的ではない。N=1の場合に関するグラフを構築すれば、一般のNでのグラフも（今回は）同じように構築できる。
・X_i+Y_iなどというのはフローで扱いにくそうだし、X_j, Y_j, A_ijが500以下という条件があるので、各数字に関する頂点を作りそう。

　というあたりを手がかりにすれば良かったか。

　ただ、劣モジュラ関数についての一般的な知識は得ていた方が良いのは間違いない。theory and meさんのこの記事を理解すべきだよね……。
時刻: 0 件のコメント:
ラベル: ,

2023年10月29日日曜日

パナソニックグループ プログラミングコンテスト2023（AtCoder Beginner Contest 326）

　Dを飛ばしてFまで五完。

コンテスト後のツイート

D - ABC Puzzle

　自力AC。

　Rの条件を満たすボードが20の五乗なので、これを全部作って調べようと思ったのだが、これだけだとTLEしてしまった。Cの一行目を満たすかどうかで枝狩りしたら通った。

　間違った方針ではないだけに、コンテスト中、時間があったとしてもこの方針に拘泥してしまった気がする。結構時間を残していないと通すのは厳しかったかも。

G - Unlock Achievement

　解説放送を見てAC。

　フロー（それも「燃やす埋める」の変形）だと分かった上でまあまあ長いこと（二時間くらい？）考えてもグラフが構築できず解説放送を見た。

　各スキルについて、「ゴール→レベル１→レベル２→……→レベル５→スタートとINFの辺を張る」、というあたりを思い付いていなかった。頂点倍加が必要？　とかもっと複雑なグラフを考えてしまった。
　言われてみればなるほど、という感じではあるのだが……。
時刻: 0 件のコメント:
ラベル: , ,

2023年9月22日金曜日

THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）

　Fまで六完。

コンテスト後のツイート

G - Typical Path Problem

　フローだという情報を得てAC。

　フローだと言われれば、解くのは難しくない（頂点数を倍にするところで引っかかったけど）し、フローにしか見えなくなる。
　けど、こういうグラフの問題をフローで解いた経験がなかったのでちょっとびっくりでした。
時刻: 0 件のコメント:
ラベル: ,

2023年4月8日土曜日

yukicoder contest 383

　Cまで三完でした。


No.2263 Perms

　解説AC。

　大きい方から貪欲に取ったりすればいけるのかな？→ダメ　フローを使う問題でした。
　言われてみればフローっぽい見た目なのに、全く思いつかなかったのは反省。

　この問題が類題だったらしい。解いていなかったので解いておこう。
　→解いた（解説AC）。フローを繰り返し使うというのは同じだが、どういう風にフローを使えば良いか分からず解説を見てしまった。どんなマッチングが欲しいかが分かれば良いので、落ち着いて考えればできそうなものなのだが、結構混乱してしまう。
時刻: 0 件のコメント:
ラベル: ,

2022年10月24日月曜日

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

　Eまで五完。

コンテスト後のツイート

F - Fishing

　一応、自力AC。

　イベントソートという方針は合っていたが、同時に出入りがあったり、0秒ちょうどに出ていくものを忘れていたりしていた。

　また、PyPyで通すのは結構厳しく、FractionをソートしたりしてはTLEが取れない。出入りする時間にある程度大きな整数をかけて誤差を小さくし、tupleを一次元化してからソートしたら通った。

G - Security Camera 3

　解説放送を見てAC。

　コンテスト中、フローだと思ったし、「燃やす埋める」のスライドなどを見に行ったりしたがグラフを構築できなくて、うーん。

　ただ、この問題は、二部グラフの最小点被覆と見るのが分かりやすかったか。けんちょんさんのqiitaの内容はしっかり抑えたい。

　また、グラフ構築の際、

・何を頂点にし、何を辺にするか

　を考え、

・上手くいかなかったら逆（今まで頂点にしていたものを辺に、辺にしていたものを頂点に）も試してみる

　などをすれば解けた気もする。

　類題を解いておこうと思って、これを解いたが（一応、解説は見ないで解けたが）かなり苦戦した。フローのグラフ構築は難しい。
時刻: 0 件のコメント:
ラベル: , ,

2022年8月8日月曜日

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

　Eまで五完。Gを考えていたが、Gは惜しくなかった。

コンテスト後のツイート

F - Tournament

　解説AC。

　DPだとは思ったが、どういうDPにすれば良いか組み立てられなかった。完全二分木なので、各段ごとにDPしていくというのは自然なのだけど、その後どう立式するかが難しい。
　勝者以外のもらえるお金を持つというのは、言われてみれば分かるけど思いつきにくい。

G - Erasing Prime Pairs

　解説AC。

　問題を見たとき、まずフローを疑ったのに、グラフの作り方を思いつかずその方針を追わなかったのはひどい。1がなければ、偶数と奇数で二部グラフになるのね、なるほど。

　実際にACしたのは、頂点を倍加し、i→j+Nに、A_i+B_iが素数のときに無限の流量を流す、という方法でACした。この解法の正当性が話題になっていたが、noshiさんのツイートに証明が書いてあった。

時刻: 0 件のコメント:
ラベル: ,

2022年7月13日水曜日

AtCoder Beginner Contest 259

 　Fまで六完。

コンテスト後のツイート

G - Grid Card Game

　解説AC。（解説放送も見た）

　コンテスト中、いわゆる「燃やす埋める問題」ではないかと疑ったりもしたのだが、違うと思ってしまった。

・start→行のノードたち→列のノードたち→ゴール

　みたいなグラフを考えていたのだけど、

・start→行および列のノードたち→ゴール

　を考えるのが正解。「燃やす埋める問題」を思ったなら、そういうグラフを考えるのは当然なはずなのに、捨ててしまったのはまずい。
　こういうグラフ構築と、「燃やす埋める問題」では「Xを選択してYを選択しない場合のペナルティ」を見ていく、という点は頭に入れておきたい。

　その後の処理もテクニカルだけど、この系統の問題になれていれば突飛な考え方ではない気がする。類題経験を積んだ方が良さそう。

Ex - Yet Another Path Counting

　解説放送を見てAC。

　二通りの四乗の解法がある：

・同じラベルの二点全てについて二項係数を足す
・多点スタートのDPをする

　各ラベルの個数によりこれらを使い分けることで三乗になり、ACできる。
　コンテスト中は一番目の方法しか思いつけなかった。二つ目も見たことあったのに。
時刻: 0 件のコメント:
ラベル: , ,

2022年4月15日金曜日

AtCoder Regular Contest 137

　Dまで四完で、目標だったレート2200（二段）を達成しました！

コンテストへのリンク
コンテスト後のツイート


 E - Bakery

　解説AC。

　コンテスト中もフローだとは思ったが、最大流か最小費用流かも分からず、グラフが構築できなかった。

　今回は最小費用流。
　日にちを0日, 1日, 2日, …と並べてから考えると良かった。そういう数直線上でグラフを構築しようと思えたなら自力でグラフ構築できたかもしれない。

　今回の解説、解説放送で、最小循環費用流から負辺のない最小費用流へ言い換える部分も（まだ完全に理解できたとは言えないが）以前より少し理解できた気がする。



時刻: 0 件のコメント:
ラベル: , , ,

2022年3月10日木曜日

AtCoder Beginner Contest 241（Sponsored by Panasonic）

　Fまで六完。

コンテスト後のツイート

G - Round Robin

　解説AC。
　フローで判定する問題。
　問題文を読んでフローらしさを感じるのは難しいけれど、「iさんがx勝で他の人たちがx勝未満、という状況は可能か？と捉えると、フローを使いたい気持ちにもなるか。

Ex - Card Deck Score

　解説放送を見て、さらに解説も参考にAC。

　形式的ベキ級数には慣れないが、この問題は形式的ベキ級数を用いて立式しようという気持ちになり、立式はできた。
　問題はその後の式変形。部分分数分解を用いた後、さらに
$\frac{1}{1-x}=1+x+x^2+x^3+\dots$
　を用いて変形するところはテクニカルに見えるが、慣れればできるのかなぁ。

　なお、解説放送でBostan–Mori のアルゴリズムの解説もしてくれたのはありがたかった。これで典型90埋まるかも？
時刻: 0 件のコメント:
ラベル: , , ,

2022年3月6日日曜日

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

　Eまで五完。

コンテスト後のツイート

F - Construct Highway

　一応自力AC。落ち着いて考えたら実装できた。

　ツイートした通り、「連結成分から出る辺が残り1個」なものから「2個以上のもの」へ繋ぐことを繰り返せば良い。これをどう実装するかだが、最初に、連結成分ごとにまとめたものを一点と思って実装する。そうすると、実装上ネックになる「最初からある辺」を無視することができる。各連結成分ごとに、どの頂点から何本ずつ辺が出ているかを覚えておけば、そこから復元できる。

　コンテスト中もこの方法は考えたのだけど、一旦まとめてからもう一度復元するのは面倒な気がし、一気にやる方法を考えてしまった。（一気にやる方法もあるかもしれないけど、上手くいかないときは）横着しちゃダメね。

G - Builder Takahashi

　フロー（最小カット）なのは問題を読めば分かり、グラフの構築もそう難しくはない。
　あとは復元。解説動画を見てしまったが、グラフがスタート側とゴール側に分かれるということに思いがいけば難しくなかった。

　が、その後ACするまで苦労したのは、最初に与えられるグラフが有向グラフだと勘違いしたため。何度かWAを出した後問題文を読み直してようやく気付いた。復元部分で間違っているんだろうという先入観があったせいだけど、こういうミスはひどい。

Ex - Dice Product 2

　DPを立式し、どこをまとめて高速化すれば良いかは自力で分かった。
　が、実装が上手くいかず、解説放送を見てAC。
　やることは分かっても、この実装はなかなか難しいですね。
時刻: 0 件のコメント:
ラベル: ,

2022年2月1日火曜日

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)

 　Dまで四完。


E - Swap

　解説放送を見てAC。（解説方法後半の賢い方法で書いた）

　制約を見ると全探索は無理そうなので、DPを疑ってはみたがどのような状態を持てばいいか全く分からなかった。

　言われてみれば当たり前なのだけれど、何も思いつかないなら、「一文字目から決めていこう」と考えるべきでした。そうすれば、Swapがテーマなので転倒数が重要そうなのは分かるし、他に何をキーに持てばいいか、というと各文字の個数でしょう。

　DPを疑い、「一文字目から決めていこう」とさえ思えれば、結構自然な考察で正しい解法にたどりつけたはず。Fを中心に考えていたとはいえ、何も思いつけなかったのは反省。

F - Treasure Hunting

　解説放送を見てAC。（解説放送後半の、簡単かつ計算量の良い方法で書いた）

　コンテスト中は嘘のDPに走ってしまったが、最初考えたときに二分探索（二文法）では？　と思ったときがあった。何を固定すれば良いか、どういう問題にすれば良いか分からず捨ててしまったけど、その着想が重要だった。

　「K番目の数がX」となるときどうなるか？　という方針で上手くいくかどうかが分かりにくいが、この方針をちゃんと考えればDPに辿り着ける。

G - Divisors of Binomial Coefficient

　ツイッターで「区間篩」というキーワードを見てAC。
　EやFは難しかったと思うけど、この問題は解けなくてはいけなかった。反省。

H - Eat Them All

　解説放送を見てAC。

・ハミルトン路（全ての頂点を一度ずつ通る閉路）を構築するより、オイラー路（全ての辺を一度ずつ通る閉路）を構築する方が簡単

　これを使うのはなるほど。その後、

・グリッドが二部グラフであることを用いて、フロー（とその復元）を用いて各辺を通る回数を求める。

　最後に、

・オイラー路の復元は、dfsの帰りがけでOK。

　一つ目が見えても、二つ目三つ目のポイントを超えるのは難しい。ただ、フローがこういう風に使えるということを押さえておくのは頭に入れておきたい。
時刻: 0 件のコメント:
ラベル: ,

2022年1月31日月曜日

AtCoder Beginner Contest 224

　Gまで七完。二桁順位は嬉しい。

コンテスト後のツイート


H - Security Camera 2

　解説放送を見てAC。

　ちゃんと理解はできていないけれど、双対を取ると簡単な問題に帰着される場合があることは分かった。

　今回は、

・フローを使いそう→だけどそのままの問題だと上手くいかない→双対を取ってみよう

　くらいな感じで良いのかな。
　双対問題が何になるかを考えるところは難しい。けれど、コストと容量が、最大と最小が入れ替わるといったあたりを考えて、あとはsampleが合うようにごちゃごちゃやる……くらいの気持ちで良いか。

　ちゃんと立式して、正確に双対問題を記述できる力もあれば良いのだろうけど、コンテスト中にやるのは厳しそう。資料とか見ながら時間をかければ、自力でやることはできそうな気もするし（本当？）。
時刻: 0 件のコメント:
ラベル: , ,

2021年9月1日水曜日

AtCoder Beginner Contest 214

 　Fまで六完でした。GとHは解法にかすりもしていなかった。要復習。


G - Three Permutations

　snukeさんの解説放送を見てAC。
　えー、難し過ぎませんか？　ステップ数が多いし、一つ一つのステップが重い。今は理解できているけど、もう一度まっさらな状態から解けと言われると結構厳しい気がしてしまう……。

　以下、（提出コードにも書いたけおｄ）snukeさんの解説放送を聞いたメモ。
 
　順列→グラフの問題と考える。
　二つの順列から、サイクルの集合と考える。
　各辺について、両端の頂点以外のものを書き込むと考える。
 
　辺を、
・〇（両端以外を書き込むもの）
・×（両端のいずれかを書き込むもの）
・？（上記どちらでも良い）
　の三つに分ける。
 
　〇は扱いにくいので、包除原理を使う。
 
　2^N通りのうち、×の箇所を決め打つと、
　各連結成分について考えることで答えを求めることができる。
 
　×の個数でDPする。
　DP[i][j] = iまで見て×がj個のときの場合の数　とする。
 
　各サイクルごとにDPする。
　辺を順々に見ていき、「直前の頂点を使ったか？」をflagに持つ。
　サイクルなので、最初の辺については二通り試す。

H - Collecting

　解説放送を聞いてAC。
　問題を見ても全くフローに思えなかったのでどうしようもないが、最小費用流と言われればなるほど、と思えた。Kが小さいのも、「フローを流す回数が小さい」と考えれば確かに、と。

　ただ、
・コストが負の辺があるので、それを解消する工夫が必要
・自分のフローライブラリが遅い

　ため、その後も非常に苦労した。
　一点目については、snukeさんの記事も理解しておきたいが、なかなか難しい……。

　二点目については、毎回距離を初期化して一からダイクストラしているのがまずい気がする。使い回せるところは使い回と高速化できそうな気がするが、よく分かっていない。
時刻: 0 件のコメント:
ラベル: ,

2021年3月26日金曜日

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

　Dまで四完でした。EFを見てFに行ったのですが、解けずに終了。Eの制約には気付いていたのに、やり方を思いつかなかったのも、Fの解法が思いつかず迷走してしまったのも大いに反省です……。


E - Oversleeping

　コンテスト中は主にFを考えていたので、こちらはあまり考えなかったのですが、Y,Qの制約が小さいのには気付いていました。しかし、周期性があるのなら、制約が小さくても何の意味があるんだろう？　と思い、全探索を思いつかず。
　Y, Qを固定した場合の式を立式していれば解法に気付けたんでしょうか……。中国剰余定理まわりにもやや苦手意識があるので、ちょっと自信がないです。

・制約が小さいのだから、Y, Qを固定、全探索を考える
・Y, Qが決まっている場合を立式し、中国剰余定理に帰着

　のどちらのステップも自然な考察でたどりつけるものなので、できなかったのはまずいですね。反省。

F - Zebraness

　フロー。
　いわゆる「Project Selection Problem」（燃やす埋める問題）だった。
　フローと疑えば気付けるかもしれないけど、結構難しいですね。

　なお、PyPyだと（自分の）Ford-Fulkersonだと間に合わず、初めてDinic法を実装した。挑戦したことはあったけど理解できなくて今まで避けていたもの。とはいえ、分かってしまえばそこまで複雑ではなかったですね。

　「Dinic法」で検索してでてきたページ多数を参考にしてコードを書きました。ありがとうございます。坐禅Logさん、tkwさん、みさわさんなどを読んでいたらだんだんと理解できました。

時刻: 0 件のコメント:
ラベル: , , ,
登録: 投稿 (Atom)