今日この問題を解いていて、定数倍改善で TLE が取れたのでメモ…。 atcoder.jp 問題ですが、しばらく考えて幅優先探索しかないかなぁ、と思い、状態をどのように持たせるか考察しました。 はビットと見なして整数値で持たせられますが、現在のインデックスも…

簡単な全探索を考える 唐突ですが、次のような問題を考えてみます。【問題 A】3 種類の硬貨 A, B, C が 1 枚ずつ存在します。A, B, C の価値はそれぞれ 2, 3, 5 です。これらの硬貨を組み合わせて、ぴったり支払える金額は何種類ありますか。ただし、1 枚も…

数列 の増加部分列（Increasing Subsequence）は、「全ての で を満たす部分列」と定義されます。この部分列は、元の数列から非連続で取ることができ、順番を変えてはいけません。 たとえば、「」という数列 の増加部分列の1つは、「」＝「」です。 増加部分…

昨日のABC F問題のように、既約分数（有理数）を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。 atcoder.jp この記事では 分数をなぜ整数として表現できるのか どうやってその値を算出するのか という辺りを丁寧にま…

ここ最近、以下の最長増加部分列（LIS）問題にやたらと手こずっていました。atcoder.jp LIS自体はアルゴリズムも理解して、この問題も解法が分かったのでササッと書いたのですが、何故かサンプルは通るものの他のテストケースの大半が落ちてしまいます。二分…

2次元座標系における点 と点 間のマンハッタン距離 は、 と定義されます。簡単に言うと「斜め移動はできず、縦横方向にしか動けない場合の距離」です。 マンハッタン距離上図では、中央の緑マスからのマンハッタン距離を各マスに記しています。また、中央か…

「エラトステネスの篩」は素数列挙に使われる効率的なアルゴリズムです。 「2」から「対象とする最大値」までを「素数候補」とする 残っている数のうち最小値を「素数」と判定して「素数候補」から除外する 2. で素数と判定した倍数を、全て「素数候補」から…

計算量で対数時間 というものをよく見かけると思いますが、これが具体的にどの程度のものか、感覚で理解してみます。 まず大前提として、 の底は（計算機科学においては一般に）2 です。何故 2 なのかというと、分割統治法の考え方で問題サイズを半分にする…

最近は競技プログラミング用のライブラリをチマチマと作っているのですが、競技プログラミングは「問題に対して適用するアルゴリズムを決めて、ライブラリから引っ張れば良いだけ」…というわけでもありません。 その代表例が動的計画法（DP）の問題だと思っ…

久々に「純粋なブログ」というものを始めてみました。 最近は無為に時間を過ごすことも多く、仕事でもプログラムを書くことが中心なので、言語野が劣化してきた感覚があります。その対策や、日々何か成長していきたいという思いから「ただのブログ」を立ち上…