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

2026年9月15日火曜日

AtCoder Heuristic Contest 071

　187位。
　最初は焼きなましを考えていたが上手くかず。方針転換しこの解法を思い付いたときは割と筋の良い貪欲を思い付いたと思ったが、実際はイマイチでした。

コンテスト後のツイート

　上から置き方を確定させて良い、とは気付いていたのに、実際の解法に生かせなかったのがまずかったか。
　分割してDPとか、上からビームサーチなどという解法が流れてきて、確かに……という気持ちになった。



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

AtCoder Beginner Contest 475

　F分からず、G間に合わずで五完。

コンテスト後のツイート

G - Has Many Divisors

　コンテスト中の方針でAC。
　最初の素数いくつかのベキを決め打ち、それ以降の素数を高々一個できるだけ使う感じでやった。
　コンテスト中は、実装ミスで、決め打った素数と一個ずつ順に使う素数の間に使わないものがでていたりしたのがひどかった。そういうミスがなかったとしてもTLEとの勝負があったから通せてたかは分からないけど、惜しかったねぇ。
　F飛ばした判断自体は間違ってなかったと思う。
　



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

2026年9月8日火曜日

AtCoder Beginner Contest 474

　F解けず六完。早めにGに行ったおかげだけど、レートが上がって嬉しい。

コンテスト後のツイート

F - Increment All Divisors

　自力AC。

　コンテスト中の方針で、判定方法を変え、三分探索にしたらACできた。
　判定方法は、「揃えたい数字との差の絶対値、の和」これが最小になるものを探した。

　凸性は示してないけれど……。
　公式解説を見ると、一次式の和であることを利用して解いている。これなら凸になりそう？（分かっていません）





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

2026年9月7日月曜日

AtCoder Regular Contest-- 229

　ACDEの四完。

コンテスト後のツイート

B - Halving Subtraction

　解説AC。

　全く考えていない方針だったのでびっくりした。
　Nが小さいからシミュレーションみたいなことをするのでは？　という方向性でしか考えられなくなった時点で負けている。
　全ての要素を0にすることは可能か？　と考えて必要条件で絞っていかなくてはいけなかったが、一旦まずい方針にハマると難しかった。

F - Angst for All Pairs 2 

　自力AC。

　実験すると、（コストが最大の）一枚を除いて他の全てのカードについて、複数毎あるか、複数枚あるものとペアか、どちらかであれば良いと分かる。
　複数毎使うカードを全探索すると、コスト計算は累積和を利用すれば計算できる。

　自分にとってはBより簡単だったけど、実験したりしてそこそこ時間かかっているから、こっちに取り掛かれば解けたという気はあまりしないねぇ。


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

2026年9月4日金曜日

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

　Gが解けず。

コンテスト後のツイート

G - Cascading Grid

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

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

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

2026年8月31日月曜日

AtCoder Regular Contest++ 228

　一問も解けずおしまい。しかし、Bは解けなくてはいけない問題だった。

コンテスト後のツイート


B - Minimize Topological Order

　コンテスト中の方針でAC。
　値を変更したらセグ木の更新を二ヶ所しなくてはいけないのに、一ヶ所しかしていなかったせいでした。

　最初にとりあえず一列に並べて置いて、後ろの一段を先祖のどこかへ付け替える……と考えていたのがまずかった模様。これだと正当性がよく分からないし、葉から考えるのが自然（？）にも思える。

　根から順番に木を構成すると考えれば貪欲の正当性も分かりやすかった。
　
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 473

　久しぶりの全完だが、良い順位とは言えず。

　Dは「最後の一要素を場合分け」が正当であったらしい。確かに、これをすれば無駄な探索を省けるが、こういう枝狩りみたいなのを要求されるると思っていなかったため、思いついた後も正しい解法とは思えなかった。

コンテスト後のツイート





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

2026年8月21日金曜日

JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）

　既出に気付けたおかげで、久しぶりに2400パフォを獲得。全完チャンスだったねぇ。

コンテスト後のツイート



E - Concentration

　自力AC。
　DP[x毎既知][y毎取得][z消費ライフ]とする方針で合っていた。

　コンテスト中は、y枚取得しているとき残っているカードの枚数をN-yにするのを忘れて、yのまま計算していたため答えが合わなかった。
　これくらい気付いて欲しいものなのだが、今（コンテスト後）にコードを見直したときも気付けず、デバッグ出力を行って気付けたので、コンテスト中に気付けないのは仕方ないのかなぁ。
時刻: 0 件のコメント:
ラベル:

2026年8月18日火曜日

AtCoder Regular Contest 227

　AB二完。

コンテスト後のツイート

D - Median of Binary Strings

　解説放送を見てAC。

　全く思いつかなかったのでどうしようもない。なかなか天才的な発想が必要だった。
　これはコンテスト中に解けた気がしないので、他の問題にいくべきでした。







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

2026年8月14日金曜日

ユニークビジョンプログラミングコンテスト2026 夏（AtCoder Regular Contest 226）

　Bまで二完。

コンテスト後のツイート

C - Square Corner Packing

　自力AC。
　ツイートに書いた解法であっていた。HかWが偶数の場合は愚直で良く、(4n+1)*(4n+1)の最大の正方形を入れて、あとは愚直でOK。

　が、実装は大変だった。10分ではとても実装終わらず。早く実装できている人は凄いなぁ。
時刻: 0 件のコメント:
ラベル:

2026年8月3日月曜日

AtCoder Beginner Contest 469

　E解けずABCDFの五完。

コンテスト後のツイート

E - Pro Exam Eligibility

　キーワードを見てAC。解けなくてはいけない問題だった。

　二分探索だと思ったものの判定問題が解けなかった。
　これは「oとxに上手く値を振り分ければ」連続部分列の和が0以上になるか？　という問題になり解ける。

　「oとxに上手く値を振り分ければ」の部分、最近だとこの問題で同じようなことをやっていて、このときは解けている。しかし、実数値を振り分ける問題は見たことがなく、頭が働かなかったのだと思う。
　


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

2026年7月20日月曜日

AtCoder Regular Contest 225

　Dまで四完。Cでバグらせたのが敗因。

コンテスト後のツイート

E - Gap Swap (hard)

　解説AC。

　実験しなきゃ思いつかなかったと思うけど、実験する時間もなかったし仕方なかったか。
　近くの場所へ移動させる貪欲は思いついていたけどねぇ。

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

2026年7月17日金曜日

AtCoder Regular Contest 223

　Cまで三完。三完の速解きにはまあまあ成功したが、DやEで迷走した。

コンテスト後のツイート


D - Xpectation of Cards in Hand with Laboratory

　解説放送を見てAC。
　経路数とか鏡像法とかいうキーワードを見てもピンと来ずACできなかったので、コンテスト中のACは遠かった。

　やることは、
・ドローカードをx軸、普通のカードをy軸としてプロットし、どの経路を計算するかを調べる。
・鏡像法で計算

　というだけ。

　ただ、そもそも、問題文では全てカードを区別しているのに、カードを区別しなくても良いの？　というところから詰まった。
　これは、
・A_1 A_2 B_1 B_2 A_3
　という区別した順列に対して、
・A A B B A
　という区別しない順列を考えると、どんな区別しない順列に対しても、区別する順列はA、Bの並び替えA!B!通りを掛けただけ存在することから分かる。


　また、経路数を求めた後、使っていないA、Bの並び替えを掛けなくてはいけないことにもなかなか気付かなかった。
時刻: 0 件のコメント:
ラベル: ,

2026年7月3日金曜日

CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)

　Fまで。

コンテスト後のツイート

G - Completely Wrong

　解説放送を見てAC。包除原理で解ける。

　Cを並び替えたもののうちk箇所が一致（C_i=G_iとなる箇所がk箇所）しているものを求めたい。
　これを、各色ごとに求めて、それを合わせることにより求められる、と考えるのがポイント。具体的には、FFT（畳み込み）を使って計算できる。

　最後に、包除原理を用いて、kが奇数のとき-1の係数をかけて足し合わせれば良い。（解説放送では-1を掛けるのをFFTする前にやっていたけど、最後にやってOKですね。その方が分かりやすいと思う）




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

2026年6月15日月曜日

第七回日本最強プログラマー学生選手権-予選-（AtCoder Regular Contest 222）

　Aしか解けず。

コンテスト後のツイート

B - Circular RPS

　解法ツイートを見てAC。

　コンテスト中は、正当性の怪しい三分探索にいってしまいダメだったし、a=0,b=cのようなケースも思いついていなかったため、全然ダメだった。

　冷静に、勝者が一人の場合、二人の場合、三人の場合について立式していったら解けた。配列から「二つの要素を選んで1ずつ減らす」という操作が何回できるか？（最大値が他の要素の和以上かによって場合分け）　という頻出問題を意識したら分かりやすい。

　ただ、a=0,b=cのようなケースは全く頭から抜けていたので、コンテスト中にACできた可能性はなさそう。

C - 2 Directions vs 4 Directions

　解法ツイートを見てAC。

　分かってしまえばなんてことはない。
　三列ずつ動く感じになるというのはコンテスト中も考えていたが、端にいかないとそこからはみ出てしまうと勘違いしてしまった。実際は、横三マスをキープしたまま、一つずつずれて上下に動ける感じになる。

　手痛い考察ミスで、そういう変な思い込みをしてしまっては修正は難しかったと思うが、もっと落ち着いて考えられていたなら正しい考察ができていたようにも思う。

　AとBをすんなり通せていたら違ったのでは？　とも思うけど、Bがすんなり通せた可能性はなさそうなので厳しい。

D - Shift and Add

　解説AC。

　下八桁くらいの数字と、その上の桁に9が何個続いているか？　を持ってDPすれば良いと思って実装を始めたが、TLEやWAが出てダメ。
　まず、下八桁ではなく九桁が必要。そして、9が何個続いているか？　ではその個数が複数あったときに計算量を減らせない。なので、「1を足したときに桁和がいくつになるか？」を持たなくてはいけなかった。

　また、桁和を求めるときは、int(str(x))を足していくのではなく、x%10を足してx//=10する、という風にした方が速い。その辺に気を配らないとTLEは取れなかった。（し、codonにしないとTLEは取れなかった）

　おおまかな解法はあっていたが、そこから実際にACするまでは遠い問題だった。

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

2026年6月7日日曜日

AtCoder Beginner Contest 461

　Dまで四完で破滅。Eは一分後に通ったが。

コンテスト後のツイート

F - Total Product is N

　解法ツイートなどを参考に、Aを降順に列挙するDFSを書いたら（codonなら）通った。コンテスト中の提出（はmodの余りを取るの忘れたけど）とあまり本質的には違わないのだが。


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

2026年6月5日金曜日

AtCoder Beginner Contest 460

　Eまで五完。このFは思いつけない。

コンテスト後のツイート

F - Farthest Pair Query

　解説放送を見てAC。

　セグ木と言われても、何を乗せるか分からず、解説放送を二回見て（解説も読んで）ようやく理解。
　分かってしまえば当たり前に思えるが、全く発想になかった。
　「その頂点集合のみを見たときの、直径の端点」を乗せれば良い。


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

2026年5月26日火曜日

東京海上日動プログラミングコンテスト2026（AtCoder Beginner Contest 459）

　Eまで。

コンテスト後のツイート

F - -1, +1

　解説放送を見てAC。

　操作を、「ブロックを右にずらす」というイメージで捉えられると考察が進みやすい問題だった模様。コンテスト中は差分をとって考えている時間が長かったけど、それほど筋が良さそうではなかったのだから、元の問題に戻って絵を描くべきだった。



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

2026年5月20日水曜日

AtCoder Regular Contest++ 220

　A一完でさらにレートを落とす。

コンテスト後のツイート

B - Incomplete Shuffle

　解説放送を見てAC。

　グラフの問題だろうとは思ったが、問題特有の考察は全くできていなかった。あまり考察せず解説を見てしまったけど、まずは、操作をした結果どのようなものが現れるか？　を実験してから考えていく感じですね。

C - Range Increment

　解説放送を参考にAC。

　解説放送を見ても（他の解説を読んでも）なかなか理解できず、一時間くらいじっと考えたらようやく分かった。

　解説放送に出てくるmod=3で1 0 1のケースより、（実質的には同じだけど）mod=6で1 5 1のケースを考えた方が自分には理解しやすかった。

　解法自体は、左から決めていくしかなくて、単純な貪欲で上手くいかないのなら、heapqか何かを使うかも……と想像することはできるかもしれない。しかし、こういう風な推察から正しい解法に至るのは結構厳しそうなので、じっくり問題の性質を見極めるしかなさそう。

D - Long Trail

　解説AC。解法ツイートを見て大体解法は把握していたけど、解説放送も見た。

　解法を思い付くのも難しいけれど、実装も大変だった。コンテスト中にACするのはなかなか大変な問題。
時刻: 0 件のコメント:
ラベル:

2026年5月18日月曜日

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

　Eまで。またレート1800を割る。

コンテスト後のツイート

F - Critical Misread

　コンテスト中の方針で大まかなものはあっていたが、どこでWAになるか分からず、ランダムテストでACしている提出と比較した。

　ミスは次のようなものだった。
　たとえば、"bcb"と"c"がある場合に、"bcb"が出たらそもそもいけないのだが、"bc"や"bcb"もノードとして数えてしまっていた。
　そのようなものを削る前処理を行ったらAC。

　Aho-Corasick法を使う場合に、必要になることが多い前処理という気がするが、知らなかった。

　そして、AIに聞いたところ、Failure_pathを利用して"c"に印がついているなら、"bc"にも印がつくようにする、という構築を行うのが一般的らしい。勉強になった。

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