online-judge-tools と atcoder-cli, verification-helper を導入した 導入方法 npmとpipにあるので普通にインストールする online-judge-toolsとatcoder-cliはこれで普通に使える verification-helperは, githubAPIキーを取得して, リポジトリでSECRETの変…

数え上げは言い換えの質 問題リンク 解法 0の前の1の数を並べて数列に変換する。 みたいな感じ この数列と文字列は一対一対応をもち、この数列を , もとの文字列の0の数を とすると、操作は なる を選び、] に 加え、] から 減じる、と言い換えられる。 この…

問題リンク 解説 要素が複数あるクエリ問はとりあえず1要素ソートするのが基本。 たぶんどっちをソートしても解けるが、今回は直径を降順ソートした。 クエリとマトリョーシカの追加を合わせてソートすれば、直径についての条件を考える必要はなくなる。 次…

だるかったので高速化したら通った 問題リンク 解法 とりあえず交点を求めてダイクストラしたいおきもちになるが、めんどくさいので愚直なダイクストラを書いてみる。 路線と場所ごとに距離を持たなければいけないが、これは unordered_map を使うのが最適（…

この問題好き。面白かった。 問題リンク 問題概要 文字列 と整数 がある。 の好きな位置に好きな英小文字を 回挿入してできる文字列の通り数を で求めよ。 解説 とおく。 結果の文字列を前から決めていくことを考えると、 を、「 文字目までで、 回小文字の…

問題リンク 解説 問題の要旨を見ればわかると思いますが、すべての注文について、「どの店が一番注文先に近いか」を求めることができればよいです。 円環なので少し実装が煩雑になりますが、これは店の位置をソートして二分探索してやればよいです。 ここか…

問題リンク 解説 動的計画法の問題です。 たとえば、 を 日目に、前日店 で買い物をし、そこでは 日連続で買い物をしている、という場合の最小の合計金額とすると、 で解くことができます。 このように、最終的な最適解が、条件を絞れば途中まででも必ず最適…

問題リンク 解説 蟻本にもほぼ同じ問題が載っていることで有名です。 解法の説明はおそらくそちらの方が詳しいので、そちらを参照していただければ良いと思います。 2本の矢を投げて作れる点数を で列挙しソートしたあとに、それらを探索しながら「和が を超…

問題リンク 解説 問題文中にもあるように、 が小さいことを利用します。 まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多…

問題リンク 解説 難易度5の中では考察寄りな問題です。 結論から言うと、「座標と熟すまでの時間の和の最大値」と、「座標の最大値の2倍」のうち大きいほうが答えになります。 以下に証明を示します。このような問題の証明を考えるのは、より難しい問題を解…

問題リンク 解説 累積和の典型的な問題です。 まず、宝石の位置を固定すると解きやすくなる、というのは感覚的に明らかでしょう。オーブと金塊のあるべき位置の条件が定まるからです。 結局、宝石を決めたとき、その右側にオーブが何個あるか、下に金塊が何…

問題リンク 解説 まず、B が残すカードは、山の中の連続する部分列だということがわかる。このようなものは 個ある。 これらすべてについて、A からカードを取ることで作れるか判定すればよいが、これは となってしまい、間に合わない。 B の残すカードの列…

問題リンク 解説 まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。 そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものを…

問題リンク 解説 調べなければいけない長方形が多いので、それぞれの長方形について高速にクエリを処理する必要があります。 これは、二次元累積和を使って、それぞれの種類のブロックが、1頂点を左上の端などに固定した長方形 通りの中にいくつかあるかを高…

問題リンク 解説 愚直にシミュレーションすることを考えると、時間計算量は になって、間に合いません。 毎日の移動で、区間の和をひとつずつ足して計算するのは無駄なので、累積和を使って高速化すると、計算量を にすることができます。 また、毎日の移動…

AtCoder でも colun 法が使えたというだけの話。 colun 法とは およそ6年前のこと。 TopCoder SRM 620 Div1 Easy で、再帰の引数を増やしすぎるとスタックオーバーフローする問題が出たらしい。 これを、「自分で確保したヒープ領域に rsp ポインタを移動さ…

Segtree Beats を書いた。 仕組みや計算量について話そうと思う。 仕組み 普通の Segment Tree を使うと、chmin クエリなどでは、総和の効率的な更新が不可能である。（それはそう） ここで、特殊な場合だけ更新が可能になるのでその場合になるまで下に辿っ…

雑なライブラリを切り貼りする生活だったので書いといた。 非再帰・std::function排除なので定数倍は軽め…なはず？ あと、std::functionを排除すると、外でラップしないと使えない。（ので、典型的なクエリはすでにクラスにしてある。） 区間変更が必要なけ…

問題リンク 問題概要 長さ の文字列に対して、 文字選んで 0 にする、 文字選んで 1 にするという操作を好きなだけ行って生成できる文字列の個数を求めよ。 考察 10秒くらい考えると、 文字選ぶ、というのは 文字以上選ぶ、というふうに言い換えられる。 で…

Project Eulerの解説をひたすら書き綴ります。 すべてに共通することがら プログラムしたいときはPythonを使うと楽です。 オーバーフローの心配がないのが大きなメリットでしょうか。 最初の方もはや解答と感想になってるんですけどごめんなさい。 1 Multipl…

問題リンク 細部が詰められなかったので解説の方法でACしてしまったが、あとで落ち着いて詰め直したらできた。 自分の解法は解説の方法より（実装は面倒だが）直感的だと思うので、紹介しておく。 問題概要 長さ の数列があって、異なる2要素を選んでそれぞ…

30秒眺めただけで解けた。全力でイキっていきたい。 問題リンク 問題概要 長さ の円環上に蟻が 匹いて、ある向きを向いている。蟻は向いている向きに一定の速度で進んでいき、他の蟻とぶつかるとそれぞれ向きを変えて進み始める。 秒後にそれぞれの蟻がいる…

書いた class BIT { unsigned int n; std::vector<lint> bit; public: BIT(unsigned int n) :n(n) { bit.resize(n + 1, 0); } void add(int a, lint x) { while (a <= n) { bit[a] += x; a += a & -a; } } lint query(int a) { lint cnt = 0; while (a > 0) { cnt </lint>…

問題リンク 問題概要 木があって、頂点には値が割り振られている。 葉を2つ選んでその間のパスの頂点の値をインクリメントする、という操作を、最初全部値が0の状態から始めてこの状態を構成できるか。 解説 頂点ベースではなく、辺ベースで考えると、ある葉…

マジで何やっても解けねえ 問題リンク 問題概要 略 考察 とりあえず式変形をして添字ごとでまとめると、結局 を計算して、かけて だったらダメ、という条件になる。 が のときには定義できないが、これは別にして計算できるのでまあどうにかなる。 さて、こ…

ネタを思いついたので、書きます。 「うちのオカンがね、好きなWriterがいるらしいんやけど、その名前をちょっと忘れたらしくてね」 「Writerの名前忘れてもうて、どうなってんねんそれ」 「でもね、オカンの好きなWriterなんて、touristか、双子ぐらいやろ…

問題リンク 結構面白かったので、解説を。 解説 まず、 のときは、経過時間が指数関数的に増加していくことに気がつく必要がある。 これで、であるような店は高々 個以内に収まることがわかる。 であるような店は、明らかに最後にまとめて訪れるのが良いので…

マラソン問題なので、したアプローチなどを記してみる。 問題概要 以上 以下の整数を100個、それらの約数の和集合の大きさが最大になるように出力せよ。 考察 約数の個数が多いといえば、高度合成数が思い浮かぶ。 ちょうどいい高度合成数に、大きめの素数を…

AtCoder社のアルゴリズム実技検定 第二回の問題を全部解いてみた。 感想をはさみながら解説をする。 今回はバチャ形式で一気に解いたので、時間も記しておく。 A問題 2:42 やるだけ、条件分岐して和か差。 B問題 4:54 std::countを使うと楽。やるだけ。 C問…

AtCoder社のアルゴリズム実技検定 第一回の問題を全部解いてみた。 感想をはさみながら解説をする。 A問題 PASTだけに普段よりは実務的な問題って感じがする。やるだけ。 入力例もどことなく実務を意識している感じがある。（アルファベットの入った文字列を…