競技プログラミング 【C#】ABC450 BC問題備忘録
今回のB問題はちょっと癖のある問題だったのでそちらも含みます。B問題一直線の電車の路線で一方向のみ、直に行くよりも途中下車で安く済ませられる区間はあるかどうか。N<=100と制約がそこまで大きくないので特に凝った解法は必要なく全探索できるが...
プログラミング
競技プログラミング プログラミング 【C#】よく使うのに忘れがちな書き方備忘録
競技プログラミングで忘れがちなので個人用に。VisualStudioに「こっちの書き方でいんじゃね？」と教えられることが多いものを特に重点的に置いておく。競プロ用のため、記事内のC#コードのバージョンは13.0が前提です。一部は13.0でな...
競技プログラミング 【C#】ABC456 BC問題備忘録
B問題も少し難しかったのでそちらも備忘録。色々あって（コンテストは数ヶ月前）ところどころ何があったか忘れてるかも。B問題6面サイコロ3つを振り、「4」「5」「6」の目が一つずつ出る確率を誤差10-6以下で出力。しかも6面に書かれる目は指定さ...
競技プログラミング 【C#】ABC449 C問題のみ備忘録
N文字のSがあり、そのインデックスを表す整数の組i,jがあるとして、i,jは同じ文字、かつi,jの距離はL以上R以下、そんなやつをSの中から探索する。Nは5×105、普通に探索すると間に合わない。解説ほぼ問題文の通りに求める素朴な解法では、...
競技プログラミング 【C#】ABC448 C問題のみ備忘録
ここで重要なのは3つ。この問題のクエリ処理では配列Aの要素に対する変更がない。Kの制約が5までと少ない。Aから効率良く最小値を取り出すには並び替えの必要がある。Aの配列は制約上109程度まで大きくなるが、実際に評価するのはAを昇順に並び替え...
競技プログラミング 【C#】ABC367 C問題のみ備忘録
探索の必要があるものの制約はさほど大きくなく計算してみても最大58=390625程度、であれば全列挙した上で条件に合わないものを弾けばいい。全列挙するには再帰か、QueueやStackをWhileでぶん回す、全部ループを書くなどがあるが、ど...
プログラミング 【C#】BFS・DFSを実装する
BFS（幅優先探索）とDFS（深さ優先探索）を実装する力を身につけるための記事です。「概念は分かってんだよ」という人のためにそこの説明は軽くやっておしまいです。枝切り（枝刈り）探索についてはここでは扱いません。記事内のコードのバージョンはC...
プログラミング 【C#】再帰ってどうやって書けばいいんだ？となった時に読む記事
再帰の書き方に苦手意識を持つ全ての初心者プログラマを救済すべく書き上げました。嘘です。苦手意識を持ってたのは私です。使用環境はC#13.0、.NET 10.0。もしVisual Studioに「このバージョンでそんな書き方できネーヨ」と怒ら...
競技プログラミング 【C#】ABC363 C問題のみ備忘録
Sを並び替えて有り得る組み合わせの中で、Kの長さの回文を含まない組み合わせの数を答える問題。で、その列挙のためのC++やPythonにあるnext_permutationはどこ？ というのがC#で解くにあたって最も困難な部分。これが使用する...
プログラミング 【C#】順列全探索を実装する備忘録
順列全探索がどういうことなのか、やっっっっっと分かったぁー……。分からなすぎて放置してたら1年以上経ってた恐怖。というわけで備忘録。つまり、C++にあるnext_permutationのようなものを書ければいい。戻り値どうすんの型どうすんの...