Processing math: 0%

2025年4月29日火曜日

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）

　Fまで六完。

コンテスト後のツイート

G - Odd Position Sum Query

　解説放送を見てAC。

　この前のこたつがめさんの解説放送で、セグメント木≒Binary Trieだという話を聞いていた。知識はあったので解けなくてはいけない問題だった。

　ただ、そもそも、値が小さければ普通のセグメント木で解ける、ってこと自体思いついてなかったんだよね……。



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

BrainPad プログラミングコンテスト 2025 （AtCoder Heuristic Contest 046）

　384位。終了間際の提出がTLEになってしまい悲しい。

コンテスト後のツイート

　コンテスト中考えていた提出でバグがなかったら81位相当だった。

　惜しかったようで惜しくなかったのでは、考えていた方針はそれほど悪くなかったと慰めたい。






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

2025年4月26日土曜日

yukicoder contest 465

　Eまで。


No.3129 Multiple of Twin Subarray

　自力AC。コンテスト後に自力で解けたけど、大分時間がかかった。

　左右から、累積和の差分が最大・最小になるような値を見つけられれば良い。これは、左右から累積和を取り、さらに今の累積和の値とそれまでの累積和のminの差分を取り、そのmaxを取っていき……のようにやればできる。

　最初、切れ目を全探索を考えて上手くいかず悩んでしまった。
時刻: 0 件のコメント:
ラベル:

2025年4月25日金曜日

CPCTF2025

　81位でした。
　「CTF」初体験だったので、CTF中心にやったつもり。LV1は一応全部解いたけど、LV2から苦戦する問題が多くて大変でした。

　競技プログラミングがパズルっぽいとすれば、CTFは謎解きっぽい印象。
　面白いとは思うけど、自分は謎解きよりはパズルの方が好きかつ得意だと思うので、もしCTFを解くために必要な基本技術を習得したとしてもそんなに上手くはなれないだろうな、と感じました。
　まあ、もう少し勉強してみないとなんとも言えないだろうけど。

コンテスト後のツイート

　以下は、yukicoderの問題について書きます。

No.3117 Reversible Tile

　解説AC。これが解けないのはダメ。

　こういう区間をひっくり返すやつは、0と1の切れ目が二個変わる、と考えるのが定石。制約を見ると、二乗DPということが分かるので……というところで詰まってしまった。

　ここまでの考察は合っているのに、なぜ解法にたどりつけないのか。

　今回は、「切れ目の値が入れ替わっている個数」を持ってDPすれば良い。なぜかそう思いつけなかった。

No.3119 A Little Cheat

　解説AC。
　swapによって増大する分と、通常の値を分けるというのは考えたけど、swapによる増大分が高々1と気付かなかったし、それをDPで求められるというのも分からなかった。

　また、解説を理解した後も、DPの遷移（場合分け）が大変過ぎて実装が大変過ぎるのでは、と感じた。実際に場合分けしてみると遷移に共通する部分が多い（コピペで良い部分が多い）ためそこまで大変ではなかったが、とはいえ、こういうのをさくっと実装するにはどうすれば良いのかなぁ。

No.3120 Lower Nim

　自力AC。

　最初にx=1を選択するとすると、Aの総和が奇数だと先手必勝。
　なら、最初にx=2を選択するとすると、A[i]/2の総和が奇数だと先手必勝。
　なら、最初にx=4を選択するとすると、A[i]/4の総和が奇数だと先手必勝……というようになることを利用した。

No.3121 Prime Dance

　自力AC。

　メモリ制限が大変だけど、難しいという気はあまりしなかった。
　……と思ったら、メモリ制限が大変だったのは、左に操作した回数、下に操作した回数を持ったせいか。
　自分は、DP[left, down, x ,y]で、左にleft回、下にdown回操作して(x, y)に辿り着いたか？　をboolで持ってやったけど、もう少しメモリを減らせたんですね。
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 400

　Eまで。

コンテスト後のツイート

F - Happy Birthday! 3

　解説AC。解説放送やこたつがめさんの放送の振り返りも参考にした。

　区間DPなのは良いが遷移が難しい。四乗にする時点でかなり難しくないか？

　こたつがめさんにやると、計算量削減部分は「区間DPの遷移でDPする必要があるとき」という典型らしい。l降順、r昇順にDPを計算していく。

　しかし、そのパートにたどりつくためには遷移を把握できていなくてはいけないのが厳しい。ただ、こういう典型があると知っていれば、どういう遷移かを掴める確率は上がるはず（と信じたい）。
時刻: 0 件のコメント:
ラベル: ,

2025年4月18日金曜日

Kotlin Heroes: Episode 12

　Eまで。

コンテスト後のツイート

F. Weapon Upgrade

　三乗で良いというツイートを見てAC。難しくない。

　残り時間が少なかったのでACまでもっていくのは厳しかったかもしれないが、方針は立っているべきだった。

　a, bをそのときのそれぞれのパワー値とし、DP[a][b]=そのときのダメージ量の最小値として更新していけば良い。(a, b)が分かれば、そのときまでに倒した敵の数が分かる。なのであとは、(a, b)のときに倒せる敵の個数さえ分かれば良いが、これは、毎回500*500のマップを更新していけば良い。

　敵が出尽くした後も、さらにn回くらいDP更新作業を続ければ答えが得られる。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 1017 (Div. 4)

　全完。
　Hの方針が若干自信なかったけど、通って良かった。

コンテスト後のツイート






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

AtCoder Beginner Contest 401

　全完でした。

　調べてみたら、ABC全完はABC197以来だったらしい。四年ぶり！
　当時のABCは六問時代だった！

　最近も何度か簡単なABCはあったけど、いつも全完を逃していたからね。
　嬉しいけど、自分の実力で全完できるくらいのABCはちゃんと全完できるようになりたいね。

コンテスト後のツイート





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

2025年4月12日土曜日

yukicoder contest 464

　ABの二完。


No.3101 Range Eratosthenes Query

　解説AC。これが見えなかったのは良くない。

　たとえば、[L,R]中にあるx=20を食べるかどうか考えるとき、xの1でない一番小さい約数は2なので、20/2=10が[L,R]中に存在するかどうか、で判定できる。Lが10以下か10以上かで変化する。
　このことに気付いていなかった。

　これが分かれば、クエリを先読みし、Lの順にソートして見ていけば解くことができる。

No.3102 floor sqrt xor

　解説AC。

　x^√xを考えると、上半分の桁はxのままなことを利用できそう。xを動かすとまずいけど、√xを固定すると、ルートして切り捨てた値が√xになるような範囲が分かるので、それで調べられる。

　……というようなことを考えたはずなのに、実装する段階になると分からなくなってTLEの解法を書いてしまい、解説を見て考察していた内容を思い出した。

　ちょっとあやふやなところはあったけど本質的解法は一度自力で考察したはずなので、時間があれば解けていたと信じたい。

No.3103 Butterfly Effect

　自力AC。

　その人がはじめて噂を知った時刻を持って、毎回ダイクストラすれば良いように見えるが、それだとTLE。
　同じ辺は二度通らないように見えるため、なぜTLEするのかしばらく気付けなかった。

　なぜTLEするかというと、ある人から辺（AさんとBさんの噂話）がたくさん出ているとき、（伝播しないのに）それらの辺を何度も見ることがあるため。

　じゃあ、「同じ辺は二度通らない」という性質があるのなら、辺もheapqで持ち、一度通った辺は削除すれば良い、と気付きAC。

　「ダイクストラで解けそう」という方針自体は思いつきやすいけれど、ちゃんとそこから一捻りしてあった。

　

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

2025年4月11日金曜日

AtCoder Grand Contest 071

　A一完。

コンテスト後のツイート

C - Orientable as Desired

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

　全く惜しくはなかったが、サイクルがあってもYesになる条件を考える、という方針自体は良いのかも。そういうグラフを列挙していけば正しい条件にたどりつけるかもしれない。

　ただ、解法を理解した後も、二重頂点連結成分分解を実装したことがなかったため、自力で実装できなかった。LOWLINKを使った関節点や橋は実装したことがあるので、あと一歩なはずなのだが……。

　とりあえず、二重頂点連結成分分解をChat-GPTに実装してもらいAC。原理は理解したつもりだけど、実装がよく分かっていない。ちゃんと自力で実装しなきゃなぁ。



　ついでに、二重頂点連結成分分解を調べる仮定ででてきたこの問題も解説（放送）ACした。ポリアの数え上げ定理（バーンサイドの補題）はこういうときに使うのか。数え上げパートまでいけたとしても解けなかったと思うので、そこまでいけたら解けるようになりたい。



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

2025年4月3日木曜日

April Fools Day Contest 2025

　ADの二完。


B. Plinko

　自力では解けず。
　0～17におくとゲームをプレイしなくてはいけないが、その外側におけば良かった。これは思いつきたかった。

C. Would It Be Unrated?

　解説AC。
　一つACが出るまでできることがなくないか？

D. Where Am I?

　写真を検索するとラスベガスだと分かるので、その緯度と経度を書く問題。それっぽい提出をしても「very close!」などと返ってきて、submitデバッグするしかなかった。
　……が、もっと狭い範囲に絞れたらしい。

E. Pair Count

　解説AC。リンクがあればそこを押す、ということさえしていれば、順を追って解ける問題でした。

　エイプリルフール部分の後にもk=0というコーナーがあるのも面白い。


G. Definitely a Geometry Problem

　解説AC。
　制約に引っ掛けがあるだけで普通の（注意力を要する）問題だった。問題文は丁寧に読まないとね。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)