こんにちは！じゅぴろ (udon1206) です！ adventar.org でぶ Advent Calendar 2023 の 22 日目です (遅れまくってすいません.) でぶカレンダーなのでダイエットの話を書きます。 きっかけ かっつくんが卒業式の日にうちに来ていたが、かっつくんの瘦せている…

問題 https://atcoder.jp/contests/ahc023/tasks/asprocon10_a やったこと 一般グリッドグラフで考えると大変なので、全域木を取り、葉から根に向けて値が小さくなるようにしていく。 こうすることで、取り出せることは保証される。 全域木の取り方 最初の全…

の場合でも解けるかつ、高度なデータ構造などを用いない解法 (オフラインです)

おそらく想定解と違うので

2021 年を振り返る

コンテストリンク OEIS にかけるということが本質なんてことがマラソンであるなんて思いもしなかった

昨日かっつくんと通話してる時に話題になったので調べた。 -Wl,-stack_size -Wl,20000000 みたいなオプションをつけるといいぽい。なんか僕の環境だと 512MB より大きくはできないんだけど、Mac でも環境によってはそうでもないぽい 例 g++ -Wl,-stack_size …

対象 AHC Rating System (β) が具体的にどういうレーティングシステムなのか知らない人 公式pdf を読んだけど、理解できなかった人 その他 AHC に参加しようとしてる人

コンテストリンク 問題の分析 やったこと ビーム幅を段階的に増やす 目的地を決めてまとめて移動する 多様性？ うまくいかなかった工夫 評価関数 擬似的なお金 高速化 リポジトリ

これはなに？ 注意 テストケース B 問題との違い large で正の点を取る解法 改善のヒント おまけ1 - 無限に文字列長くできそうにみえるけど、ジャッジは大丈夫なの？ おまけ2 - リポジトリ おまけ3 - マラソンの基本？である複数のテストケースで確かめる。 …

問題リンク 解説 LCS の DP と似ています。 LCS を知らないよって方は Educational DP Contest の F ～ J 問題の解説と類題集 - Qiita を読んでからやると理解が早いかもしれません。

コンテストリンク 問題pdf まとめ pretest 100 ケース 98,027,620 (順位 : 27 位) systemtest 1000 ケース 982,098,992 (順位：29 位) 99 M に乗る方法が全くわからね〜

Sublime Text 3 を使っている競プロ er そんないなさそう

問題リンク 観察 得点 入力の生成 観察まとめ クエリ序盤 クエリ後半 並列処理のシェルスクリプトとかリポジトリとか 自分がやった解法の簡単な方針と観察を書きます．

問題リンク オンラインとオフラインどっちが好みの人が多いんでしょうか？

みなさんこんにちは．お久しぶりです． 競プロ er の中では，よくインドという風な呼ばれ方をすることで有名な？CodeChef について説明していこうと思います． CodeChef は AtCoder と同様有志コンテストと公式の rated コンテストが分かれています． 主に，…

問題リンク 解説 補グラフにおいて， 1 つは XOR の値を，それ以外は全て 0 として損をしません． 補グラフにおける辺をいったん全てコスト 0 としてすべてつなげます．そして，元のグラフの分をクラスカル法の要領でくっつけていきます． 補グラフにサイク…

方針は公式解説と大まか同じ． 座圧がめんどくさい -> 速い2部マッチングをパクる -> そのまま愚直でもわりと余裕を持って通る． さすが懸賞金をかけられていた人のコードです． 提出コード yukicoder.me

解説 問題文を 2 段階言い換えます．まず， と が 2 つあるのが大変なので 1 つにまとめます． """ が ? のときは， ? で，そうでない時は， となるグリッド を考えます． このとき， の同じ行または同じ列の 2 つのセルを選んで，反転させる．( ? は ? のま…

AtCoder マイプロフィール -> 設定 -> 退会 Codeforces 現状ではありません． Mike は個人情報などを全て削除してから，放置をしておくことを推奨しています． これは，ブログなどの情報はコメントを含めて消えるべきではないという考えかららしいです． Top…

実はskebで絵を依頼してたんですが、なんと今日完成して届きました！ ちょ～かわいいい～ か。つくんのお友達という理由だけで頼んでたんだけど、かわいすぎてうれしい～ これを見ながら頑張って卒業をします

線形解法がおもったより単純だった 解法 (swap数の総和) (完全順列の数) を求める問題である 個の要素の完全順列の数 とすると，これは有名らしく， で線形で求まる． swap数は に辺を貼った時の サイクル長 だけかかる サイクル長 となる，要素の選び方が …

問題リンク 解説 問題文をまず言い換えます。 をするということはその辺のコストをにすることで、 をすることはその辺を2倍することと言い換えることができます。 そして、じゃない辺でやると得をしないので、任意の辺でどこのコストを0にしてどこのコストを…

MP法を用いて、goalの前 文字に文字 を加えた文字列のsuffixがgoalのprefixと何文字一致するかを前計算します。 後のDPは簡単で、計算量は です 追記(DPパート) 簡単でで説明を省略しない！ということで簡単に スタートから に行くまでの期待値 とします。 …

問題リンク 解説 中学1年生になりましょう です。 欲しいのは としたときの でこれは↑の式を適宜modを取っていきながら繰り返し二乗法で展開すれば、計算量は です 提出コード atcoder.jp

問題リンク 解説 年齢が若い順に見ていきます。 すると、それぞれの辺を加えるか削除するかがわかり、各頂点の左端と右端がわかります。 この更新は遅延セグ木や双対セグ木を用いて、 でできるので解けました。 提出コード atcoder.jp

問題リンク 解説 前計算である集合が条件をみたすかを前計算します。 これは愚直にでできます あとは をすでに分ける最小の数 とすると、これは部分集合を列挙するテクを用いてでできます。 以上で求めることができました。 提出コード Submission #19137551…

問題リンク 解説 o と x の個数は o の個数 xの個数 oの個数 x の個数 のどちらかです。そうでないときはNOを出力します。 oもxもないときはまだ何もしていないのでYESです。 上記の場合以外は一手前の状態が存在します。 一手前の盤面が5目並んでるような盤…

問題リンク 解説 から始めた時に勝てるかどうか とすると、 それ以外 であるので となる をqueueなどで管理することで、 で解けました 提出コード yukicoder.me

問題リンク 解説 公式解説のほうが賢いのでそちらを参考にしてください。 にいて にビーコンを置いてるときの最短距離 としましょう。 愚直にやると、ですが、ビーコンを置くのは通るpath上のどこかでいいのでHLDと双対セグ木を用いて、 でもとまります 提出…