summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

↓問題のページ↓ E - 1D Bucket Tool UnionFindを使うことで鮮やかに解くことができる一問。本番中の自分には欠片たりとも降って来ない発想だったが、それはおそらく「同じ連結成分に属する頂点たちについては、その連結成分の根に対する情報のみを更新するだ…

↓問題のページ↓ F - Exchange Game 本番中にほとんど正解と同じ方針を立てることはできたのだが、細部の詰めが甘く無念のAC失敗に終わった。今後類題が出てきた場合は確実にしばき倒せる体制を整えるため何がダメだったのかも含めて本記事で整理していく。 …

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

summary { padding: 2px 6px; width: 15em; background-color: #ddd; border: none; box-shadow: 3px 3px 4px black; cursor: pointer; } details > p { border-radius: 0 0 10px 10px; background-color: #ddd; padding: 2px 6px; margin: 0; box-shadow: 3…

↓問題のページ↓ F - Add One Edge 2 500点が与えられているF問題ではあるが、自分でもある程度の方針が立つくらいには見た目ほどの難しさは持ち合わせていない一問。だからこそ直前の記事の通り、A問題でWAを被弾して動揺しまくったせいで十分な精度で考察で…

とんでもなく悔いが残る。まず何よりも 大した実力も持てていないうちからイキり散らかすな の一言に尽きる。何も難しいことを考えず問題文通りに実装するだけでA問題はAC獲得できるのに余計なことをして1WAを被弾したせいで無駄に動揺し、なんとか4完したも…

苦しい回だった。十数分で3完までこぎ着けたものの、ぱっと見でD問題の方針が立たなかったためすぐにE問題を何とかダブリングで通せないか考える作戦に出た。しかし、添字の変換則自体が操作の度に変わるためダブリングでは通せないと理解するまでに30分くら…

43分で4完と調子は悪くなかったものの、変にイキった実装をしたり考察がやや甘かったりでA問題・C問題で1WAずつ食らったため反省点が多かった。E問題もあと5歩くらいで本番中のAC獲得にこぎ着けられそうなところまで考えが及んだこと、本番終了後には緑diff…

本番でのACには至らなかったが、どうやらグラフに対して「特定の辺を削除する」または「指定した2頂点間を移動する際の最短距離を答える」クエリがたくさん飛んでくる系統の問題は典型らしいのでこの一問でしっかりと固めたいと思う。 ↓問題のページ↓ F - Ro…

100-150-400-400-450-550-575 という配点を見た瞬間に途轍もなく嫌な予感がしたのだが、このような配点の回であろうとも最低4完するくらいでなければ実力をつけた証にはならないと覚悟を決めて参加したものの無念のABD3完に終わりひたすらに力不足を実感。さ…

40分以内と、比較的調子良く4完には成功。しかしE問題で「解を二分探索する」というところまでは自力で素早く見出せたのだが、その先をどうすればいいのかが正確に分からず無念の撃沈。早く公式解説にあったような鮮やかな視点に立てるようになり、本番中に5…

↓問題のページ↓ E - Xor Sigma Problem 本質的には 公式解説 をなぞっているだけだが、自分の実力が不足しすぎていてなかなか理解できなかったため結論までの詳細を書き残す。この手の問題は典型らしいので素早く処理できるようになりたい・・・。 まず、「b…

↓問題のページ↓ E - I Hate Sigma Problems 例として、数列\(A\)が以下のような6項から構成されているとする。\begin{align} (A_0, A_1, A_2, A_3, A_4, A_5) = (5, 4, 2, 2, 4, 3) \end{align}一旦連続部分列の話は忘れ、とりあえず数列の全範囲に注目する…

またしてもトチ狂ったとしか思えない難易度で出題されたA問題に苦しめられ16分を失うもなんとか4完に成功したので耐え。いい加減5完を獲得したい・・・。 ＜A問題＞ ↓問題のページ↓ A - Jiro 賢い実装方針を何も思いつけず、A問題にして順列全探索を行うとい…

↓問題のページ↓ E - Product Development 結論を先に述べると、動的計画法で解くことができる。制約を確認すると、\(N, K, P\)いずれの値もかなり小さいので、まずは考えるべき状態数がどれくらいあるのかを見積もってみる（なお、本問の制約において最も厳…

4完には成功したものの、C++のnext_permutationによる全探索の構造を書き間違えたせいで時間内の5完には至らず・・・。できれば今回はE問題も解き切りたかった （個人的復習用：以下の記事で既にまとめているのでnext_permutationによる全探索の書き方を確認…

D問題が425点の回における個人的通例を脱し見事4完に成功 ※本記事は0-indexedを前提として記載。 ＜A問題＞ ↓問題のページ↓ A - Cut 何だか最近A問題の難易度が上がってきてない・・・？ それはそうとして問題文に書かれた通りの実装をしよう。一番下のカー…

動的計画法の勉強を積んできた甲斐があって4完に成功して嬉しい限り。E問題の解説をあまりにも理解できないのが頗る歯がゆい。 ＜2024/09/21追記＞ E問題の解説に書かれていた内容をようやく理解することができたので この記事 にまとめた。 ＜2024/09/21追…

発想の根幹にあるのは幅優先探索で、上手く応用できるかを問われている一問といった感触。 ↓問題のページ↓ D - Go Stone Puzzle 問題の状況設定からして、実質的には\((N + 2)\)箇所ある枠を石が動くということなので、以下では入力された\(N\)に対して\(2\)…

ひたすらに変形の同値性を意識し続けたためげっしりと数学をやった気分になる一問。 ↓問題のページ↓ C - Sqrt Inequality だいたいの言語に標準搭載であろうsqrt関数を使って\begin{align} \sqrt{a} + \sqrt{b} \lt \sqrt{c} \tag{1} \end{align}を判定して…

D問題が425点の回における個人的通例から逃れられず3完。DとEについては解説を読んでも全く理解できないとは思わなかったため、今後同様の問題と出くわした場合に撃沈しないよう今回でしっかりと固めておきたい。 ＜A問題＞ ↓問題のページ↓ A - Glutton Taka…

↓問題のページ↓ D - All Assign Point Add 問題文通り愚直にシミュレーションすると、全てのクエリが1である場合に\(\mathcal{O}(N Q)\)の処理となってTLEするのでちょっとした工夫が必要。クエリ1が2度以上連続で入力された場合、最後に入力されたものしか…

↓問題のページ↓ D - I hate Factorization （懺悔： 公式解説 の論理展開を理解できませんでした） \begin{equation} A^5 - B^5 = X \tag{1} \end{equation}という数式において、\(1 \le X \le 10^9\)より\(X \gt 0\)すなわち\(A^5 - B^5 \gt 0\)となるので…