AHC032 の考察記事です。 11,762 M 点で 18 位でした。 #AHC032 おつでした。11,762 で 18 位でした。（解法）1 マス 1 手を基準に上から貪欲に決めていきます。・各行について、左の 4 マスに影響する置き方を全探索 → 右 5 マスを全探索・一番下の 3 行は …

AHC031 やったこと 縦に切った盤面を構築し、日ごとには横線のみを更新する 縦線の切り方は、 日間動かさずに耐えられる範囲でなるべく細く切る 切った後の分け方は、なるべく細いところで入るだけ入れる 列ごとに、翌日と全く同じ位置で切れるなら切る（列…

AHC 030 参加記 AHC 030 おつでした。 プレテスト 7,885 M で暫定 55 位です。 （追記）システスは 528 B で 51 位でした。 最終提出 提出コード が小さい場合は可能なすべての状態（各油田の左上の座標の組）を持って、期待獲得情報量がなるべく大きくなる…

AHC でよく出てくる分布について書きます。 （書きかけ。あとで追記する。） 確率分布と確率変数 あとで書く。 期待値と分散 確率変数 の期待値を 、分散を と書きます *1 。 正規分布 こんな やつ。 確率変数 が平均 、分散 の正規分布に従うとき *2 と書き…

AHC 029 参加記 AHC 029 でやったことと参加記です。 プレテストは 6.4B で暫定26位です。 やったこと 最終提出 の説明です。バグなどもありますがそのまま説明しています。細かいところは一部省略しています。 概要 評価関数による貪欲です。将来ターンのシ…

AHC 027 （HTTF 2024）参加記 問題は こちら この記事に書いてあること 最終提出（プレテスト 189 位）は、汚れやすいマスを TSP で回るのをベースとして、それを倍々に複製しながら、残りのマスを最も良い位置に入れる貪欲 マスをグループ分けしたとき、グ…

AHC レーティング橙になりました！ AtCoder のヒューリスティックレーティングが橙（2400+）になりました。 ヒュ橙になりました！-----Kiri8128さんのトヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）での成績：4位パフォーマ…

AHC 025 AHC025 の参加記です。 プレテスト 94.158B で暫定 27 位でした。 （追記：システス 469.343B で 26 位でした。） 総評 面白い 通常、焼きなまし・山登りはうまい近傍を作ることと、なるべく高速化することで時間内に探索をたくさん回すことを要求さ…

この記事は何？ 某ツイートで紹介されていた、 人の天皇の誕生日が一様独立に決まっている場合に、天皇誕生日の日数の分布と期待値を求める計算を厳密にやります *1 。 ワロタhttps://t.co/kEyQOTwjLI pic.twitter.com/5IwrSro7sx— 鴨川を徘徊する魔女 (@Kam…

AHC 018 に関する考察・日記です。 Pretest 40.4B で暫定 13 位です。 （Seed 0 の結果） 動画は一番下のツイートリンクを参照 *1 問題ページ 戦略概要 ざっくり言うとこんな感じです。最後にもう少し正確に書きます。 10 マス刻みで 20 × 20 のグリッド（格…

この記事は何？ 2048iang というゲームについて、戦略などを書きます。 honoka55.github.io 2048iangってどんなゲーム？ ビャン（）という漢字のパーツが湧いてくるので、うまくくっつけてビャンを作るゲームです。完成タイルはこんな感じです。 パーツの組…

環境構築（ディスプレイなど） ディスプレイ関係の環境構築についてやったことなどを書きます。 仕事用と私用でPCが異なるので、切り替えをスムーズに行うこと デュアル（トリプル）ディスプレイの設定 あたりが主なトピックです。 PC・モニター（マルチディ…

ネストすごろくの解法について書きます。 下記の問題のネタバレを含みます。 [問] 下記のネストすごろくをクリアできる確率はいくらでしょうか？ネストすごろく：ゲームが始まると、下記のように START のマスにいる状態になります。サイコロを振り、出た目…

本稿について AHC016 Graphorean の考察（主に理論面）について書いています。最尤推定（ ※ 追記：あとで調べたら事前分布を仮定するものはベイズ推定と呼ぶのが正しいようです *1）に類する方法で復元をします。正規分布近似によるグラフを構築した際の誤判…

AHC 014 AHC 014 でやったことのメモです。暫定 45.5M です。 忙しい人は最後の「まとめ」だけ読めばおけです。 9/17-19 親戚の結婚式を兼ねて家族旅行 9/18 移動中はできないと思っていたが、マニュアルモードでスマホでもできることに気付いたので遊んでみ…

AHC 013 でやったことを書きます 結論 （時間がない人はここだけ読めば OK です。） 盤面（ケーブル情報も含む） Move の履歴 Connection の履歴 注目しているコンピュータの種類 を持つ山登りで、 1 種類のコンピュータを優先して進める貪欲方式で Pretest …

ゆきこ 352 の Writer をやっていました。 みなさん参加ありがとうございました。 yukicoder.me 各問題（作問・総評）について 一部ネタバレを含みます。ご注意ください。 A問題 簡単枠ですが、 E 問題とセット（布石）になっています。 B問題 よくあるちょ…

AHC 011 でやったこと・考察したことなどをつらつら書きます。最終的なアルゴリズムを見たい人は最終日（9 日目）の項目へ。 1 日目（5/28 土） 【昼】 子供と公園に行ったり人生ゲームをしたりしていたので実装はできなかったけど、問題文は読めた。 【考察…

CodinGame を知っていますか？ 私はよく知りませんでした *1 。 ちょうど TL で少し流行っていた Line Racing というのが初心者向けと聞いてやってみました。 1～2 週間ほどやりましたが、一旦やりたいことはだいたいできたので *2 感想を書いておきます *3 …

競プロでたまに出てくるけど忘れがちな定理・公式などをまとめる予定です。 クリックで開くよ （まだ下書き中） 定理 数え上げ系 行列木定理 問題例 頂点 辺のグラフの（ラベル付き）全域木はいくつありますか。 答え ラプラシアン行列の任意の余因子の行列…

わーい！ 特に書くことはないんですが。 レートグラフ なんかこんな感じです。濃橙から 1 年ちょい。 https://codeforces.com/profile/Kiri8128 緑 → 青 ： 9 日 青 → 紫 ： 3 か月 紫 → 薄橙 ： 4 日 薄橙 → 濃橙 ： 1 年 2 か月 濃橙 → 薄赤 ： 1 年 Pytho…

この記事は 2 変数関数の最大値を嘘解法で求めるときに思いついた方法を書いています。厳密性のない感覚的な議論が多いので、厳密な話をしたい人はお帰り頂くか、読んだうえでいろいろご指摘頂けると嬉しいです。 題材 もとは この問題 を考えていたときに考…

この記事は 競プロ典型 90 問 のコード置き場です。 基本的に PyPy3 で書いています。 コンテスト中は他人の Submission が見れないので何かのお役に立てば。 他の人に見やすいようにとかはあまり考えずに書いてるので、通せないときの参考ぐらいで。 難しめ…

ARC 115-E （LEQ and NEQ） 問題リンク 便宜上、 を 0-indexed にします。 番目まで見たとき、最後のものが である場合の数を として、これを管理することを考えます。同じところはまとめて管理すると、 のようなスタックで表せます。これは の範囲では、 で…

yukicoder contest 275 - yukicoder 良問揃いですごいです。 ABCF の 4 完9位です！（嘘です、 F はテスターをしてました。） DE は後で解きましたが面白かったです。 E 木と駒 問題ページ 解説と似てますが、全方位木 DP の状態の持ち方を工夫すると簡単に…

35歳から Python で競プロを始めて2年が経ちましたが、やっと AtCoder で橙になることができました！ ふぁぼ、コメントもたくさん頂きありがとうございました。 競プロを始めて2年、なんとか橙になることができました。 pic.twitter.com/r0GwrNogHi — きり (…

参加ありがとうございました！（まだの人はやってみてねー！） https://yukicoder.me/contests/275 あなたは ゲームは好きですか？ 私は好きです（楽しいので）。みんなも好きだと思います。 コンテストについて 決まったテーマに沿った問題を出そうと決めて…

わーい！ 初薄橙から1年2か月ぐらいかかりました。ちなみに紫から薄橙は4日だったので100倍です。 Kiri8128's Rating Graph Profile: ■ グラフ見ると、どう見ても上振れなんですが笑 やったこと 調整後紫から Div2 で上げる Div1（単独）は耐える 混合（ぐろ…

この記事は、11年ほど前、世間ではリーマンショックがあった少し後ぐらいに、ある人が就職活動をした記録です。某別の場所に書いていたものを、移植しています。なるべく当時の思いが伝わるように （編集者訳：めんどくさいので） 、タイトル （本稿での「見…

ABC 170 の感想 D - Not Divisible 問題文 AC コード 素因数分解系は、ρ法で殴る癖がついてしまいました。 計算量は \( O(NA^{\frac{1}{4}}) \) です。 ρ法を使った \( O(n^{\frac{1}{4}}) \) の素因数分解 E - Smart Infants 問題文 AC コード heapq （prio…