ctf.harekaze.com CTFに参加して久しぶりに問題が解けました。 Harekaze mini CTF 2020に一人チームで参加しました。結果は393点でした。 解いたのは、 Welcome (misc) (91pt) NM Game (misc) (179pt) What time is it now (Web) (123pt) でした。 ソースコ…

Eは先にgcd(n,s,k)にしていれば通せていたみたいなので辛いです。 scrapbox.io scrapbox.io scrapbox.io

ABCの早解き勝負回は辛いです。Fはセグ木まんまではと思ったらそうで右端が含まれるか含まれないかが一番難しかったです。 scrapbox.io scrapbox.io scrapbox.io

D問題で小さいケースで試して計算式を見つけてACできたので良かったです。 scrapbox.io scrapbox.io scrapbox.io

Dは小さいパターンで試す方法すら思いつかなかったんですが、単一の座標で形を表せるというのでなるほどとなりました。 scrapbox.io scrapbox.io

Cで乗っている斜線間の距離の計算で無限に時間がかかっていたので、個人的難易度はA

Dで愚直解を書いて小さいNで試したら解けたのが印象的でした。 scrapbox.io scrapbox.io scrapbox.io

Cはすぐ右に置くだけで任意のロボットを壊せるという所に気づけなかったので駄目でした。 scrapbox.io scrapbox.io scrapbox.io

Fは下の方から完結するDPしか考えられず、上から値を0に向けていくとかそうすると取れる値が高々桁毎に2つとかまったく思いつかなかったです。 scrapbox.io scrapbox.io scrapbox.io

久しぶりの全完でレーティングを1800まで戻せました。Dの4WAが無ければ200位パフォが高かったかもなのでWAも気をつけます。 scrapbox.io scrapbox.io scrapbox.io

Dは言われてみるとなるほどという感じだったので数式の変形が可能かどうかについても考えていきたいです。 scrapbox.io scrapbox.io scrapbox.io

Cはおおよそ考察は合っていたのですが、移動先となる点の判定に穴があり無事冷えました。 scrapbox.io scrapbox.io

Fは同じサイズの連結成分が後々重複してカウントしてしまうところがどうにもなりませんでした。 scrapbox.io scrapbox.io

端を含まないと分かっていたはずなのに、距離計算の時に間違えていたので境界値のミスをなくしていきたいです。 scrapbox.io scrapbox.io

EでTLEしたのを直そうとしてWAを稼ぎまくり、最後はメモ化でごまかしました。 累乗の最大値がHWなのにH+Wと勘違いしながらもACできてなんとかなりました。 scrapbox.io scrapbox.io scrapbox.io

Dの累積和は気付いたものの時間内に間に合わなかったです。その後も累積和で1引く場所を間違えており時間がかかりました。 レーティングが大きく飛んでいったので頑張ります。 scrapbox.io scrapbox.io

想定解法ではないですが何とかEが解けたので良かったです。あまりACLは使えませんでした。scrapbox.io scrapbox.io

Bは偶然通った気が scrapbox.io scrapbox.io

Eでループが途中から始まるということに気付かずに時間をかなり使ってしまいました。ただ終了13秒前に何とかACできたので良かったです。 scrapbox.io scrapbox.io scrapbox.io

久しぶりに全完した気がします。Eの添字間違えが無ければペナルティ込みで30分位短縮できたのでかなり辛いです。Cも20分位かかりました。 scrapbox.io scrapbox.io scrapbox.io

何度か解こうとして解けなかったので解説AC。効率的にどこでカウントさせるかが解けなかったんですが、今まで見た中で一番左になるというのはなるほどでした。 scrapbox.io

すべての列を管理してO(HW)より減らせるとは考えもしなかったので勉強になりました。 scrapbox.io scrapbox.io scrapbox.io

Fがあまりに分からなかったのでその内理解したいです。 scrapbox.io scrapbox.io

Dのバグで一生嵌まってました。諦めてEに挑戦できたのは良い判断だったと思います。最終的にDが解けなかったのは駄目です。 scrapbox.io scrapbox.io

Aの考察を間違えていて二問で10WAで辛い順位になりました scrapbox.io scrapbox.io

Fはオンラインで解いて各クエリの計算にかかる時間を減らすと言うことしか考えていなかったので、あんなに解く人が多いとはまったく思いませんでした。 scrapbox.io scrapbox.io scrapbox.io

Eは焼きなまし法で行けるかなと思いながら、マラソンじゃ無いからとやらなかったのがやや後悔です。ただhighest更新できたので良かったです。 scrapbox.io scrapbox.io scrapbox.io

手元のpopcountがintだけ対応版であることに気付かず、数時間溶けました。 scrapbox.io scrapbox.io

Fが非常に難しかったので5完でもhighest更新できました。C,Dあたりも難しめでした。 scrapbox.io scrapbox.io

点と辺の数から連結成分の数が求められるというのはまったく思い浮かばなかったです。 scrapbox.io scrapbox.io scrapbox.io