競プロ
AtCoder Heuristic Contest 001に参加した！技育祭でchokudaiさんが「ヒューリスティックスコンは自分の書いたプログラムを育てるのが楽しい」のようなことを言っていたけれど、かなり実感した。 atcoder.jp 一週間のうち、最初の3日と最終日にがっつり取り…
WriterがE869120さんとsquare1001さんの双子なので別解がたくさん紹介されている．公式解法3に近いが，途中でheapqに追加していくというよりは，次の候補を先に全部追加して解いた． D - Cake 123 解法 制約からAとBの和は全列挙できるので，まずそれを行う…
コンテスト後，公式解説に「multisetなどを用いることで高速に処理することができます」ってあったからPythonじゃ解けないのか？？と放置していた問題．2時間くらいかかっちゃったけど，なんとかC++で解けた． E - Smart Infants 解法 シミュレーションをす…
反省．ABC3完．レート-51． D - Wandering 解法 問題文の，箇条書きの一行で表されるまとまった動作を，ここではステップと呼ぶ． 2回累積和を取った配列から，各ステップの開始時（終了時）の座標がわかる．あとは，各ステップ内で移動できる最大値を計算し…
昨日のABCはEまでの5完！やったぜ！ コンテスト本番中はわからなかったFを復習したのでまとめる． F - Silver Woods 問題概要 下の図のように， からの直線に挟まれた通路にいくつか釘（赤い点で表す）が打たれている． 円をからまで動かすとき，円の内部に…
色変記事のいつもの画像からです． 水色を目指している人が読んでくれることを考えて，オススメの精進方法などを多く書いています． 一番読んでくれるのはTwitterのフォロワーの方々だと思っていて，自分のこれまでの苦労や今後の目標についても書いています…
D. Concatenated Multiples 問題概要 正整数，と，個の正整数が与えられる．とを連結させた数のうち，で割り切れるペアの個数を答えよ．ただし．連結させた数の例としては，となら．とならとする． 解法パートで，とを連結させた数をという風に書く． 解法 …
コンテストへのリンク ABCD4完．Eは解けなかった． 以下問題ごとの感想とACコード． A問題 問題概要 正整数とが与えられる．にからの数を足したり引いたりして，にしたい．必要な最小の操作回数はいくつか求めよ． 解法 できるだけを足したり引いたりする方…
E - Coprime 問題概要 個の整数からなる集合{}が，pairwise coprime，setwise coprime，もしくはnot coprimeであるか判定せよ． pairwise coprimeとは，についてが成り立つときのこととする．setwise coprimeとは，pairwise coprimeでない，かつが成り立つと…
C2. Good Numbers (hard version) バチャをした．4か月くらい前にも解いたのだけれど，3ペナ出した．うーん． 整理のために言語化しておく． 問題概要 以上の整数のうちで，最も小さな「良い数」を出力せよ，というクエリがいくつか与えられる．整数はクエリ…
D - Wizard in Maze 久しぶりにコンテスト中にDまで解けた！嬉しい～～！ 問題概要 グリッドグラフが与えられる．スタートのマスからゴールのマスまで移動したい．移動する操作は2種類ある．移動Aは現在のマスから上下左右に1マス移動できて，移動Bは現在の…
コンテストへのリンク バチャをした．ABCD4完（３ペナ）．AとDは正解の考察に行くまでに時間がかかった．問題を上手に整理しつつ，もっと早く正確に解法にたどり着きたい． 以下ACした問題ごとの感想とそのコード． A問題 数列が与えられて，値の差の絶対値…
C - 決勝進出者 何人かのコードを見た感じ，これ人によって解法違いそう． 解法 (順位，予選時期，ID)をタプルとし，heapqに入れていく． 予選ごとにheapqを見て，（取り出した値から将来負けうる人数）+ （既に通過した人数）がK未満だったらその予選時にメ…
初めてのTopCoder．運がよかったのか青になった．やったね． TopCoderのSRMは，AtCoderやCodeForcesよりもコンテストサイトがわかりにくかったり，入出力の形式が違ったりで少し参加しにくかったです．事前に過去問を解いたり，最初の一回目は慣れのために手…
コンテストへのリンク バチャをした！べるさんとしふとさんとはてぃーぽったーさんとnok0さんとmedoさんとkumakumaaaaaさんとサマリ6さんと並走！ ABC3完．Aでめちゃくちゃ苦戦した．悔しい！！！！！！！！ 以下問題ごとの感想とACコード． A問題 解説見た…
コンテストへのリンク ABCD4完．Eはコンテスト後にnok0さんに教えてもらって通した！ 以下問題ごとの感想とACコード． A問題 サンプルが親切なので，じっと見ると大きい方から2個が一致していればよさそうなことに気づく． 解は，小さい数を2個と大きい数が1…
C - ロト2 思考過程 与えられた整数のそれぞれについて，他の整数のそれぞれと積を取り，の倍数であるか確認する解法がまず思いつきます． が，計算量がO()になり，今回の入力サイズはとなるのでTLEしてしまいます． ここでサンプル1を見てみましょう． 4 6 …
F - Intervals on Tree 解法 コンテスト中にここまで気づけるようになりたい（この回はEで苦戦してFを見ていませんが…）． 与えられるのは木であり，閉路が存在しない． よって，辺がない状態から辺を1つ増やすと，連結成分が必ず1つ減ることがわかる． まっ…
頭がバグる．人に説明できるくらい理解したい． D - へんてこ辞書 解法 dfsして閉路検出．ダブリングでやるにはKが大きすぎると思ったけれど，上手くできたりするんでしょうか？ 類題として解いたのに１時間くらい実装にかかってしまった．反省． 以下、ぐち…
AtCoder Problems （2020/9/8 追記）この記事を作成したのは2020/04なので，見た目が違ったりバーチャルコンテストの情報が古かったりします． （2020/11/2 追記）少し内容を整理しました． AtCoder Problemsとは, @kenkooooさんが作成したサイトです. AtCod…
D - RGB Triplets 解法 文字列から3つ選んだとき, 3つとも異なる文字かつ, (1番目と2番目の添え字の差)と(2番目と3番目の添え字の差)が等しくない組を数え上げたい. なので, 二重ループくらいの処理は許される. 入力例1を紙に書いてみて, 1つ目の'R'は選んで…
コンテスト中に解けなかった！悔しい！ E - Sum of gcd of Tuples (Hard) 自分の解法や思考過程などを書いています. 解法 競プロフレンズさんのツイートにもあるように問題を読み変え, gcdがになるような数列を数え上げる. の で合計を取ったものが答えであ…
A - Biscuits 思考過程も含めて、自分の解法を書きます。 あまり証明などはしません。きちんとした解説が読みたい方は、公式や他の記事を読んでください。 解法 まず途中で使うことを書きます。 これは二項係数の和です。二項係数のwikiにもDEGwerさんの数え…
D - Disjoint Set of Common Divisors 思考過程も含めて、自分の解法を書きます。 あまり証明などはしません。きちんとした解説が読みたい方は、公式や他の記事を読んでください。 解法 やりたいことは、公約数の中から条件を満たすように整数をできるだけ多…
初めまして、ntk（@ntk_ta01）です。 先日のキーエンスプログラミングコンテスト2020にて、やっと緑色になれました。緑になるまでに何をしたか、などを書いていこうと思います。 自己紹介 情報系の学科に所属するB3 プログラミングの経験は、大学に入ってか…
