最近この手の記事を書いていないので書く。この問題は、多段階の考察が必要。 問題 (0...K) から構成される数列のうち、門松列列を満たすものの個数を求めよ。ついでに含まれている数の総和を求めよ。 考察 めんどくさいので、以降門松列列をと呼ぶ。 0 総和…

色々実装してみたので、ここに置いておく 対象読者 十分な実装時間があれば簡単な機能をもった（例：範囲加算・範囲総和取得など）遅延セグメント木を実装できる ATLのlazy_segtreeを使う前に、自分で抽象化されていない簡単な遅延セグメント木を作ってみる…

writer解説とは少し違うかもしれない yukicoder.me 問題概要 文字列Sが与えられる。 全ての部分文字列の「同一の文字が連続する非空かつ極大な区間（以下「連」と言う）」の個数の総和を1e9+7で割った余りを求めよ。

概要 yukicoder.me 社員全員はスター型のリモート会議サービスに参加している。お互いの声が聞こえる。 遅延があり、社員iは、情報が社員からサーバに届くのにA[i]秒、サーバから社員に届くのにB[i]秒掛かる。 社員jは、j-1の数字が聞こえたら or j-2の数字…

とりあえず。 問題概要 鉱石を集めて回収する。 ただし、鉱脈のある場所は分からない。 レーダを配置することで、距離4以内の鉱脈が分かる 爆弾も設置できる。爆弾を設置した場所を掘ると爆発する。隣接して置くと誘爆する。 相手のロボットが何を持っている…

これ本当に300点ですか？？？ 概要 N 以下の正の整数の組(a, b, c)であって、a+b, b+c, c+a が全てKの倍数であるようなものの個数を求める。 考察 1 %を剰余演算の記号とする。 制約が N <= 2*105なので、aだけを全探索するような実装が予想される。 なので…

しました。 codevsとは codevs.jp ゲームAIを作って強い人が優勝。 tl;dr 結果 17/112位 ずっとシルバー(30位以内)をキープしていたようなしていなかったような*1。 前回参加した、codevs for student(以下codevsFS)は社会人含めて27~30位ぐらいだったので、…

結果 Legendary到達．38/1543．Legendary到達後はコード触ってない（触ると落ちそうだったので）． 問題概要 客が常に3人居て，何か料理を注文している．適切な料理を出すと，スコアを獲得する． なるべく高いスコアを獲得したい． 料理は，皿と複数の食材か…

解けなかった 問題 leetcode.com K種類の整数から構成される連続部分配列をgoodと呼ぶ． 入力から与えられる配列の連続部分配列のうち，goodな配列はいくつ存在するか？

問題文 atcoder.jp 頂点重みX 辺重みY の無向グラフが与えられる． 次の条件を満たすように，なるべく少ない辺を削除したい． 削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。

雑でごめんなさい 問題 cf18-relay-open.contest.atcoder.jp 数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。 次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が…

この程度の愚直DPが間違ってたのダメ 問題文 beta.atcoder.jp スタミナとよばれる概念があり，0で空，Xで満タンである．時刻1単位でスタミナは1回復する 時刻0にてスタミナはXである T_1..T_NからK個のタイミングを選んで，スタミナを0にして，スタミナを減…

ハル研究所プログラミングコンテスト2018とは www.hallab.co.jp 自分にとっては 2度め． 2019年卒なので，今回が最後． 今年の成果 16位．食べられないクッキー獲得！ 例年より参加者数が多いらしい． 問題概要 20x20のオーブンと，2つのレーン(SmallLane,La…

問題概要 0～9で構成されるN文字の文字列のうち、桁が昇順になるものはいくつか？

解説ACしてから理解しようとしたら辛かった https://yukicoder.me/problems/no/75 https://yukicoder.me/submissions/285676 問題概要 さいころを振って，でた目を累積する．これを1手とする． 累積値がKになったら終了．超えたら0にリセットする． 手数の期…

アルゴリズムとはほぼ無関係． スタート地点 遅いコード 2797 ms Submission #3108991 - AtCoder Regular Contest 025 namespace Twoを修正します． 一番早いantaさんを見て絶対届かないと思いました．

解説とは違う方法なので 問題 N個の石があって，i番目の石はi+1..i+H\[i\]にジャンプ出来る． 次のD個のクエリに答えたい：s番目の石からt番目の石へ移動する方法の数を答えよ． キーワード 行列演算表現を用いた動的計画法 行列が乗ったセグメントツリー

タイトルについて 正しくは「データアクセスに制限のある Binary Indexed Tree (と同じクエリに答えるデータ構造) の高速化」です Binary Indexed Tree とは 以下のクエリに時間O(logN)で答えることが出来るデータ構造． 初期化 サイズNの配列の要素を0に初…

解説と若干違っていたので 概要 https://beta.atcoder.jp/contests/arc061/tasks/arc061_c 鉄道会社の乗り換えを最小化せよ かなり雑なブログ記事です

解説を軽く読んだだけでは理解できない脳なので記事書いた． 問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_b 昼：客のsnukeさんがジュースをB個買う 夜：rngさんが在庫を確認し，C個以下なら翌日朝までにジュースをD個仕入れる ある日の朝，…

本番の時は N = A+B or N+1=A+B で考察してWAでした． 問題文 最長増加部分列の長さがA，最長減少部分列の長さがBとなるようなN要素から構成される順列を印刷せよ． 提出 Submission #2751681 - AtCoder Regular Contest 091 解説を殆ど*1見ずにACした． *1:…

参加はしていましたが，改めて解いてみた． 問題概要 30x30のグリッドがあり，各マスに自然数が書き込まれている．次の一連の流れを1手とする．手数を最小化せよ． 1つのマスを選ぶ デクリメントする． ４近傍のうち，デクリメント後のマスの数と一致したマ…

問題概要 KutuluのMinionの攻撃を回避して最後の1人になることが目標． sanity(SAN)の減少 何もしなくても勝手に下がる．近くに味方が居ると下がりにくくなる． Minionの攻撃を受けると-20． 手段 敵を遠ざけるLight*1 周囲の味方を回復するPlan 一度だけ周…

作文に関する余談など．有用な解説についてはyukicoderの解説ページを参照してください．

永続データ構造とは 永続データ構造 - Wikipedia 変更履歴(バージョン)を記録するデータ構造． 本記事について 永続データ構造の性質について取り上げたい．

嘘解法かもしれないので程々に． 2つのコーナーケースを記事に載せたのでぜひ． 問題文 https://beta.atcoder.jp/contests/apc001/tasks/apc001_d 公式想定解法 考察すると次が分かる 各連結成分のうち，必ず使わなければならない頂点は 1 個 全て合わせて2(…

2018/02/24 表現を修正 writerしました 問題 https://yukicoder.me/problems/no/629 ざっくり説明：グラフと頂点に割り当てる数字が与えられる．門松パスは存在するか？ 本記事の目的 グラフに含まれる，門松パスの個数を O(M) で求める． cielさんの提出コ…

勉強になるとTLで見かけたので 問題 agc002.contest.atcoder.jp キーワード 並列二分探索

平面tspの分岐限定法のコードをなんとなく書いてみたけれども，全然早くならなかった． Traveling Salesman Problem (TSP) N個の都市と都市間の距離が与えられる．全ての都市をちょうど一度ずつ巡って始点に戻る順回路の中で移動距離が最小のものを出力する…

2018/02/22 更新 文章を修正 区間スケジューリング問題 http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用． 区間スケジューリングは次の問題である．仕事が n 個与えられる．各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定さ…