競技プログラミング 【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のようなものを書ければいい。戻り値どうすんの型どうすんの...
競技プログラミング 【C#】ABC444 C問題のみ備忘録
愚直に有り得る組み合わせを試していったらMLE（メモリ制限超過）した。愚直過ぎた。悔しい。解説制約と問題の性質上、有り得るパターンを分けていけば探索の必要なくACできる。2つより多く分かれることを考えなくてよく、分かれなかったものが存在する...
競技プログラミング 【C#】ABC428 C問題のみ備忘録
問題の要約空文字列であるsにQ個のクエリを施し、その各クエリの直後にそれぞれの()が対応する「良い括弧列」であるかを判定する。クエリは800000あるので、「良い括弧列であるか」の判定をO(1)程度でできないと3秒に間に合わない。解説クエリ...
競技プログラミング 【C#】ABC418 C問題のみ備忘録
途中まで考え方は良かったけど、時間的に無理だったしそも微妙に考慮不足。解説を何度も読み返して、解法は合ってるはずなのに何故かWAが出る、と試行錯誤してたら結局それまで使ってたはずの二分探索のコードにバグがあったことが判明するまで2時間ほどあ...
競技プログラミング 【C#】ABC421 C問題のみ備忘録
AB2完灰コーダー言われてみれば確かにそうだな、みたいなことで考えが凝り固まっていていつもC問題が解けません。皆さんは先に行っててください。私はもう……いえ、後で必ず追い付きますので。公式解説の言い換え要点は3つ。'A'だけに注目し、それを...
競技プログラミング 【C#】ABC417 C問題のみ解説備忘録
筆者が数学苦手勢なので、そういう人向けです。数学得意な人からすれば同じことを言い方だけ変えて言いまくっているようなものです。使用環境 C# 11.0 .NET 7.0.20C問題はj-i=A+Aとなるようなiとjの組み合わせを数える...