競技プログラミング
atcoder.jp 1 〜 D の各難易度の問題を 1 問でも解くかどうかの組み合わせは 2D 通り、と考えられなくもないので、ビット全探索を使ってみた。 using System; namespace ABC104C { class Program { static void Main(string[] args) { var DG = Console.Read…
atcoder.jp 入力文字列 S の長さを N として、文字と文字の間に '+' が入るまたは入らないパターンは全部で 2N-1 通り。2N 通りの全探索で有効なビット全探索を使ってみた。 using System; using System.Collections.Generic; namespace ARC061C { class Pro…
atcoder.jp 単純に全探索すれば良い。座標の格納には System.Numerics.Vector2 を使った。2点間距離の計算が Vector2.Distance 一発で済んで楽。 using System; using System.Numerics; namespace ARC004A { class Program { static void Main(string[] args…
atcoder.jp ABC085C - Otoshidama の類似問題。x と y が決まれば z も決まるので、2重ループで x と y を全探索すればいい。 using System; namespace ABC051B { class Program { static void Main(string[] args) { var input = Console.ReadLine().Split(…
atcoder.jp 2 * 2 * 2 = 8 通りしかないので、総当たりで OK。今回は C# らしく LINQ で。クエリ式ならネスト深くならないし、途中の計算結果を let で保持できて、これはこれで便利。 using System; using System.Linq; namespace ABC079C { class Program …
atcoder.jp 西側から「自分より西にいるのに西を向いている人の数」を数える。 同時に、東側から「自分より東にいるのに東を向いている人の数」も数える。 最後に、「自分より西にいるのに西を向いている人の数」と「自分より東にいるのに東を向いている人の…
atcoder.jp N はたかだか 100 までだし、行数もたった 2 行なので、愚直な 2 重ループによる全探索で問題なく間に合う。一見ループは 1 つだけに見えるけど、LINQ を使っているので、やっていることは 2 重ループと同じ。 using System; using System.Linq; …
atcoder.jp ボタンを押したとき次に光るボタンの組を Dictionary<int, int> に詰めておき、押したボタンを Dictionary<int, int> から除いていく。 Dictionary<int, int> 中に無いボタンを押そうとしたら、それはすでに押されたボタンということになるので、ボタン2を光らせることは不可能</int,></int,></int,>…
atcoder.jp 逆転の発想。(B * i + C) % A == 0 を満たす i が存在するかどうかを調べる。 A で割った余りは記録しておき、同じ余りが出現したら、見つからないと判断して終了。 using System; using System.Collections.Generic; namespace ABC060B { class …
atcoder.jp 0 〜 b の範囲内で x で割り切れる値の個数から、0 〜 a-1 の範囲内中で x で割り切れる値の個数を差し引けばいい。ただ、a が 0 のときだけ特殊で、0 は x で割り切れるため +1 する。 using System; namespace ABC048B { class Program { stati…
atcoder.jp 1 番目のボールを塗る色は K 通り。2番目のボールには 1 番目と同じ色が使えないので K - 1 通り。3 番目のボールには 2 番目と同じ色が使えないので、これまた K - 1 通り。後はその繰り返しで、N 番目のボールを塗る色は K - 1 通り。 using Sy…
atcoder.jp System.Numerics.BigInteger を使えば N が最大値 100000 でも計算できるけど、時間がかかりすぎて、とても2秒以内には終わらない。 最後に剰余を計算せずとも、毎回計算しても大丈夫だった。 using System; namespace ABC055B { class Program {…
atcoder.jp スイッチを離した時間の早い方と、スイッチを押し始めた時間の遅い方の差を求めればいい。差がマイナスなら、同時に押している時間はない。 using System; namespace ABC070B { class Program { static void Main(string[] args) { var input = C…
atcoder.jp 左上から順番に探索していって、# のマスのとき「上下左右に隣接するマスのうちどれか1つでも # があるか」をチェックする。# があれば探索を続け、無ければ目標を達成できないので探索終了。 using System; using System.Collections.Generic; …
AtCoder Beginners Selection は全部解いたので、次は AtCoder Beginner Contest の過去問を解くことにした。 atcoder.jp 左上から順に全探索しつつ、現在のマスが . だったら、接しているマスに # が何個あるかを数えて出力していく。 using System; using …
atcoder.jp 次の目的地に向かって進んでいって、早く着きそうだったら周辺で時間を潰し、最終的に時間ぴったりに着けば OK。 using System; namespace ABC086C { class Program { static void Main(string[] args) { var n = int.Parse(Console.ReadLine());…
atcoder.jp 後ろから比較すれば、dream は確実に dream だし、erase は確実に erase。 比較する範囲を前にスライドしていく際には、ReadOnlySpan<char> を使った。 余計な string のインスタンスが生成されるのを回避し、速度と読みやすさを両立できたのでは。 usi</char>…
atcoder.jp x + y + z = N なので x と y から z は決まる。z でのループは不要。x と y の二重ループで探索すればいい。 using System; namespace ABC085C { class Program { static void Main(string[] args) { var input = Console.ReadLine().Split(' ')…
atcoder.jp 実は並び替える必要はなく、重複している値を取り除いて残ったものを数えればいい。 LINQ 便利。 using System; using System.Linq; namespace ABC085B { class Program { static void Main(string[] args) { var n = int.Parse(Console.ReadLine…
atcoder.jp 降順にソートして、先頭から 1 つずつ Alice と Bob 交互に割り振っていけばいい。 using System; using System.Linq; namespace ABC088B { class Program { static void Main(string[] args) { _ = int.Parse(Console.ReadLine()); var a = Cons…
atcoder.jp 各桁の和を求める部分、とくに各桁の値を取り出すのに悩んだ。 「10 で割った余りを求める→10で割る」を繰り返す泥臭い方法になったけど、 もっとスマートに書けないものかな。 using System; namespace ABC083B { class Program { static void M…
atcoder.jp 0 <= A, B, C <= 50 なので、所持している硬貨の枚数の組み合わせは最大 125000 通り。 組み合わせ全パターン計算して X と一致するものを数えても、2 秒以内で余裕で間に合う。 using System; namespace ABC087B { class Program { static void …
atcoder.jp 配列の中身を全部 2 で割り切れた回数をカウントすればいいな。2 で割り切れなかったら、結果を出力して即終了で。 using System; using System.Linq; namespace ABC081B { class Program { static void Main(string[] args) { var n = int.Parse…
atcoder.jp 要は、入力された文字列の中に '1' が何個出現するかを数えればいいわけだ。 using System; using System.Linq; namespace ABC081A { class Program { static void Main(string[] args) { var answer = Console.ReadLine().Count(x => x == '1');…
昨日から始めた AtCoder。まずは AtCoder Beginners Selection を上から順に解いていく。 お次はこれ。 atcoder.jp 偶数かどうかを判定するには、2 で割った余りが 0 かどうかを見ればいい。今回は特に変わった解き方をせずシンプルに。 using System; names…
ブログに書くネタ&プログラミング面接対策として、AtCoder を始めてみた。 まずは入門である AtCoder Beginners Selection からコツコツやっていく。 atcoder.jp b と c の代入に、あえての Deconstruct。 ただ単に Deconstruct を使ってみたかっただけ。 …