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 …

インベスターZ(1)〜(21)

だいぶ前に Kindle で凄く安くなっていて、まとめ買いしたはいいものの、積読してしまっていたのをようやくを消化。「ぜんぜんわからない。俺たちは雰囲気で株をやっている」のセリフが有名になってしまった本作だけど、実際はそんなセリフ登場しない。投資…

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…

WEB+DB PRESS Vol.118

読んだ感想。 特集1 実践リモートワーク リモートワークになったら、今まで通りの成果を上げるのが難しそうだし、評価したりされたりするのも難しそうだ。まぁ、自分は緊急事態宣言中も出勤した社畜ですが。GMO ペパボのような、既にリモートワークの土壌が…

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…

ABC088B - Card Game for Two

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…

ABC083B - Some Sums

atcoder.jp 各桁の和を求める部分、とくに各桁の値を取り出すのに悩んだ。 「10 で割った余りを求める→10で割る」を繰り返す泥臭い方法になったけど、 もっとスマートに書けないものかな。 using System; namespace ABC083B { class Program { static void M…

ABC087B - Coins

atcoder.jp 0 <= A, B, C <= 50 なので、所持している硬貨の枚数の組み合わせは最大 125000 通り。 組み合わせ全パターン計算して X と一致するものを数えても、2 秒以内で余裕で間に合う。 using System; namespace ABC087B { class Program { static void …

ABC081B - Shift only

atcoder.jp 配列の中身を全部 2 で割り切れた回数をカウントすればいいな。2 で割り切れなかったら、結果を出力して即終了で。 using System; using System.Linq; namespace ABC081B { class Program { static void Main(string[] args) { var n = int.Parse…

ABC081A - Placing Marbles

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

からかい上手の(元)高木さん(9)(10)

「からかい上手の(元)高木さん」の 9 巻と 10 巻が同時発売したので両方購入。 (元)高木さんが西片くんとちーをからかうのは当然(?)として、 ちーまでが西片くんをからかおうとするのは微笑ましいけど「父親の威厳が…」と複雑な気分。 それでも3人仲睦まじい…