AtCoder

AGC033A - Darker and Darker

atcoder.jp 開始地点となる # の位置を記録しておいて、まとめて幅優先探索を行う。一つずつ幅優先探索を完了していったらタイムオーバーになるので、まとめてやるのが重要だった。 using System; using System.Collections.Generic; using System.Linq; nam…

第10回日本情報オリンピック予選(オンライン)E - チーズ (Cheese)

atcoder.jp 1→2→…→N と順番に辿っていけばいい。答えは「(S から 1 までの距離) + (1 から 2 までの距離) + … + (N - 1 から N までの距離)」になるので、幅優先探索による全探索を、開始地点を変えながら繰り返す。 using System; using System.Collections…

ABC007B - 辞書式順序

atcoder.jp 'a' を出力すれば、入力 A のほとんどのケースで正解になってしまう。例外は入力 A が 'a' のとき。そのときは -1 を出力するしかない。プログラミングコンテストは時間との勝負でもあるので、簡単な方法で解けそうなら、その方法を選んで時間を…

ABC091B - Two Colors Card Game

atcoder.jp カードの文字列を読み込みながら、その文字列が言われたとき何円もらえるかを計算しておく。 using System; using System.Collections.Generic; using System.Linq; namespace ABC091B { class Program { static void Main(string[] args) { var …

ABC088D - Grid Repainting

atcoder.jp 幅優先探索でスタート地点からの距離を測ってみた。ゴール地点の距離が判明していたら到達可能と判断できる。 ゴール地点の距離 + 1 が必須の白いマスで、それ以外の白いマスは黒に塗りつぶせる。あらかじめ白いマスの数を数えておき、ゴール地点…

ABC007C - 幅優先探索

atcoder.jp キューを使って幅優先探索を実装した。探索でスタート地点からの距離を記録していき、探索し終わったらゴール地点までの距離を出力。 using System; using System.Collections.Generic; using System.Linq; namespace ABC007C { class Program { …

ARC037B - バウムテスト

atcoder.jp 頂点の数 N は 100 以下なので、深さ優先探索を行った場合の深さは最大でもたかだか 100。今回は趣向を変えて、再帰で深さ優先探索を実装してみた。スタック使うよりすんなり書けたので、今後も使えそうな問題があれば使っていきたい。 using Sys…

ARC031B - 埋め立て

atcoder.jp 埋め立て候補の海をスタート地点にした、スタックを使った深さ優先探索。探索終了してスタート地点に戻ったとき、全ての陸地を訪れていれば1つの島にできる。 using System; using System.Collections.Generic; namespace ARC031B { class Progra…

ATC001A - 深さ優先探索

atcoder.jp スタックを使って深さ優先探索を実装。深い=sから遠い。次に調べる区画をスタックにプッシュしていき、調べ終わったらポップして前の区画に戻る、の繰り返し。 using System; using System.Collections.Generic; namespace ATC001A { class Prog…

ABC002D - 派閥

atcoder.jp N 人の議員がそれぞれ派閥に参加するかどうかのパターンは 2N なので、ビット全探索を使ってみた。仮の派閥を作っておいて、全員がお互いに知り合いかどうかを調べる。 using System; using System.Collections.Generic; using System.Linq; usin…

ARC029A - 高橋君とお肉

atcoder.jp 焼く時間が長い順にソートしてから、2台の肉焼き機に振り分けた。 using System; using System.Linq; namespace ARC029A { class Program { static void Main(string[] args) { var N = int.Parse(Console.ReadLine()); var t = new int[N]; for …

ABC104C - All Green

atcoder.jp 1 〜 D の各難易度の問題を 1 問でも解くかどうかの組み合わせは 2D 通り、と考えられなくもないので、ビット全探索を使ってみた。 using System; namespace ABC104C { class Program { static void Main(string[] args) { var DG = Console.Read…

ARC061C - たくさんの数式

atcoder.jp 入力文字列 S の長さを N として、文字と文字の間に '+' が入るまたは入らないパターンは全部で 2N-1 通り。2N 通りの全探索で有効なビット全探索を使ってみた。 using System; using System.Collections.Generic; namespace ARC061C { class Pro…

ARC004A - 2点間距離の最大値

atcoder.jp 単純に全探索すれば良い。座標の格納には System.Numerics.Vector2 を使った。2点間距離の計算が Vector2.Distance 一発で済んで楽。 using System; using System.Numerics; namespace ARC004A { class Program { static void Main(string[] args…

ABC051B - Sum of Three Integers

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(…

ABC079C - Train Ticket

atcoder.jp 2 * 2 * 2 = 8 通りしかないので、総当たりで OK。今回は C# らしく LINQ で。クエリ式ならネスト深くならないし、途中の計算結果を let で保持できて、これはこれで便利。 using System; using System.Linq; namespace ABC079C { class Program …

ABC098C - Attention

atcoder.jp 西側から「自分より西にいるのに西を向いている人の数」を数える。 同時に、東側から「自分より東にいるのに東を向いている人の数」も数える。 最後に、「自分より西にいるのに西を向いている人の数」と「自分より東にいるのに東を向いている人の…

ABC087C - Candies

atcoder.jp N はたかだか 100 までだし、行数もたった 2 行なので、愚直な 2 重ループによる全探索で問題なく間に合う。一見ループは 1 つだけに見えるけど、LINQ を使っているので、やっていることは 2 重ループと同じ。 using System; using System.Linq; …

ABC065B - Trained?

atcoder.jp ボタンを押したとき次に光るボタンの組を Dictionary<int, int> に詰めておき、押したボタンを Dictionary<int, int> から除いていく。 Dictionary<int, int> 中に無いボタンを押そうとしたら、それはすでに押されたボタンということになるので、ボタン2を光らせることは不可能</int,></int,></int,>…

ABC060B - Choose Integers

atcoder.jp 逆転の発想。(B * i + C) % A == 0 を満たす i が存在するかどうかを調べる。 A で割った余りは記録しておき、同じ余りが出現したら、見つからないと判断して終了。 using System; using System.Collections.Generic; namespace ABC060B { class …

ABC048B - Between a and b ...

atcoder.jp 0 〜 b の範囲内で x で割り切れる値の個数から、0 〜 a-1 の範囲内中で x で割り切れる値の個数を差し引けばいい。ただ、a が 0 のときだけ特殊で、0 は x で割り切れるため +1 する。 using System; namespace ABC048B { class Program { stati…

ABC046B - AtCoDeerくんとボール色塗り

atcoder.jp 1 番目のボールを塗る色は K 通り。2番目のボールには 1 番目と同じ色が使えないので K - 1 通り。3 番目のボールには 2 番目と同じ色が使えないので、これまた K - 1 通り。後はその繰り返しで、N 番目のボールを塗る色は K - 1 通り。 using Sy…

ABC055B - Training Camp

atcoder.jp System.Numerics.BigInteger を使えば N が最大値 100000 でも計算できるけど、時間がかかりすぎて、とても2秒以内には終わらない。 最後に剰余を計算せずとも、毎回計算しても大丈夫だった。 using System; namespace ABC055B { class Program {…

ABC070B - Two Switches

atcoder.jp スイッチを離した時間の早い方と、スイッチを押し始めた時間の遅い方の差を求めればいい。差がマイナスなら、同時に押している時間はない。 using System; namespace ABC070B { class Program { static void Main(string[] args) { var input = C…

ABC096C - Grid Repainting 2

atcoder.jp 左上から順番に探索していって、# のマスのとき「上下左右に隣接するマスのうちどれか1つでも # があるか」をチェックする。# があれば探索を続け、無ければ目標を達成できないので探索終了。 using System; using System.Collections.Generic; …

ABC075B - Minesweeper

AtCoder Beginners Selection は全部解いたので、次は AtCoder Beginner Contest の過去問を解くことにした。 atcoder.jp 左上から順に全探索しつつ、現在のマスが . だったら、接しているマスに # が何個あるかを数えて出力していく。 using System; using …

ABC086C - Traveling

atcoder.jp 次の目的地に向かって進んでいって、早く着きそうだったら周辺で時間を潰し、最終的に時間ぴったりに着けば OK。 using System; namespace ABC086C { class Program { static void Main(string[] args) { var n = int.Parse(Console.ReadLine());…

ABC049C - 白昼夢

atcoder.jp 後ろから比較すれば、dream は確実に dream だし、erase は確実に erase。 比較する範囲を前にスライドしていく際には、ReadOnlySpan<char> を使った。 余計な string のインスタンスが生成されるのを回避し、速度と読みやすさを両立できたのでは。 usi</char>…

ABC085C - Otoshidama

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(' ')…

ABC085B - Kagami Mochi

atcoder.jp 実は並び替える必要はなく、重複している値を取り除いて残ったものを数えればいい。 LINQ 便利。 using System; using System.Linq; namespace ABC085B { class Program { static void Main(string[] args) { var n = int.Parse(Console.ReadLine…