gotutiyan’s blog

プログラミング関連の話題を中心に

AtCoder

ABC136 D Gathering Children

問題 atcoder.jp 解説 最終的にどのような状態になるのか 軽くシミュレートをすると、子供たちは、最終的に"RL"または"LR"であるような境界を行き来するだけになります。文字列の長さに対して回も移動するので、これは確実です。 そこで、このような境界にお…

ABC117 D XXOR 解説

問題 atcoder.jp 数列Aの全ての要素とのxorを最大化するようなK以下の整数を求めよ。 解説 公式解説の序盤について、Xの候補となりうる整数とは Xがなんでも良ければ難易度が下がりますが、K以下というところが難点です。 まずK以下の整数とはどのようなもの…

Atcoder ABC99-D GoodGrid

問題 D - Good Grid色iを色jに塗り替える時に感じる違和感と、色が塗られたマス目の情報が与えられる。この時、(i+j)%3=(x+y)%3となるような(i,j),(x,y)のマス目は全て同じ色に塗らなければならない。感じる違和感の最小値を求める。 解説 全探索をします。 …

ABC 108(9/1) A,B,C問題の思考過程

なんか3完で58位を取れたので思考過程を書きます。珍しくA→C→Bで解きました。 A問題 簡単な掛け算で解けそうでしたが、その式を考える時間で愚直ループ解を実装できそうだったのでそっちにしました。偶数の個数と奇数の個数を数えて掛け算します。 int ma…

AGC006 A Prefix and Suffix 解説

・問題 A - Prefix and Suffix内容は問題文の通り。・解説 s,tの文字列の長さは共にNで共通である。題意を満たすには、文字列sの後ろの部分文字列と、文字列tの前の部分文字列がどの程度被るかを調べればいい。1つ目のテストケースで例えれば、1回目 s: ○○…

競技プログラミング入門(仮

はじめに 言語は基本的にC++を使っています。プログラムの簡単な説明もある程度行いながら進めていきます。C言語などの予備知識があると読みやすいかもしれません。競技プログラミングとは 競技プログラミング(以下競プロ)とは、プログラミングを用いて…

ABC 088 の解説を書いてみる

初めて全完できたので Tasks - AtCoder Beginner Contest 088A問題 500円玉を無限に使えて、1円玉の数Aが与えられるとき、金額Nを払えるかどうかを出力。 解法 500円玉はいくらでも使えることから、500円玉で払えるだけ払った後の金額は、500で割った余りに…

ABC 085 D Katana Thrower

問題 D - Katana Thrower N本の刀があり、それぞれの刀はAとBの攻撃力を持つ。無限回できる振る攻撃はAのダメージを与えて、1回しかできない投げつける攻撃はBのダメージを与える。投げてしまうと、その刀は使えなくなってしまう。Hの体力を削りきるための最…

ABC 032 C 列

問題 C - 列 要素数Nの数列の中で、全ての要素の積がKを超えないような、連続した最長の範囲の要素数を求める。解法 連続した範囲という言葉を聞いたら尺取り法を使うことを考えよう。尺取り法は、範囲の右端と左端の変数を用意して、範囲における特定の値が…

ARC 011 A 鉛筆リサイクルの新技術

問題 鉛筆の初期値Nがあり、m本あればn本新たに作ることができる。最終的に何本の鉛筆を売れるか。解法 まず、答えは「N+新たに生成された鉛筆」となる。以下のコードでは、resという現在手元にある鉛筆を格納する変数を作り(初期値はN)、答えとなる変数…