問題 atcoder.jp 解法 数列 7, 77, 777, 7777, ....は 漸化式 10+7 で表現できる。 これはmod（余り）をとった値でも同様。 7%K の次の77%K も 10+7の関係にある。 それを利用して、K回この処理を繰り返せば、とりうる余りは１ループする。 この余りのループ…

問題 atcoder.jp 赤と白の石がランダムにある。 ・石を2個えらんで入れ替える ・石を1個えらんで、色を塗り替える この操作を行なって、赤い石の左隣に白い石がない状態を作る。 最小で何回の操作が必要でしょうか？ 解法 まず最終形を想定してみる。 石を1…

問題 三角形を作ることのできるような長さの異なる3本の棒を選ぶ方法は何通りあるでしょうか。 atcoder.jp 解法 三角形には、2つの辺の長さを足し合わせると残りの1つの辺の長さより長くなる。 という成立条件があるので、これで三角形が成立するかを判断す…

問題 atcoder.jp 解法 カコモンジムに行くと強さがA倍、経験値+1 AtCoderジムに行くと強さが+B、経験値+1 強さXとして、A * XとX + Bを比較して小さい方を行えば良いが、制約条件から愚直にシミュレーションすると計算量がO(108)を超えてしまう。 まず、カコ…

問題 atcoder.jp 解法 defaultdictを使って、頭文字ごとの単語数を数える。 itertools.combinationsで、M, A, R, C, Hの中から3つを選んだ組み合わせを生成。 頭文字ごとの単語数の積を求めて、足し合わせる。 実装 参考 qiita.com note.nkmk.me

問題 atcoder.jp 解法 数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。 f[i]はIの約数の数が入る。 これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。 f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAi…

問題 atcoder.jp 解法 1 〜 Nまでの約数を配列に保存する方針。 1の倍数、2の倍数、3の倍数……と各配列に1づつ足していく。 この約数を求める計算量は Nを外にだして Σ部分は調和級数になるので、だいたいlogNになる。 ゆえに計算量はO(NlogN)とのこと。 約数…

問題 atcoder.jp 解法 とにかく入力例とか問題の内容読むと「これ約数の問題っぽくない！？」と悟れという問題のよう。 最大公約数がモンスターのHPの最小値になるので、これを求めればよい。 3つ以上のパラメータの最大公約数の求め方が実装例(Python3.8系)…

問題 atcoder.jp 解法 フロイドワーシャルとかライブラリ叩けば良いんじゃね？と思ってたんだが、この問題で求められてる処理自体がフロイドワーシャルのアルゴリズムそのものですよ。 というアルゴリズム教養問題だった。 なるほど、こういう処理なのね。 …

問題 正整数Nが与えられます。A x B + C = Nを満たす正整数の組 (A,B,C)はいくつありますか？ atcoder.jp 制約 2 ≤ N ≤ 106 入力はすべて整数 解法 A, B, C はすべて1以上。 A x B + C = N この式を展開していく。 C = N - A x B Cは1以上なので 1 ≤ N - A x…

Atcoder公式放送みたら、snukeさんが言ってたのでメモ。 TLEにならないのは、だいたいO(108)くらいまで。 簡単な処理ならO(109)までいけたりもする。 あ、そうなのね。 youtu.be

問題 atcoder.jp 解法 約数列挙問題。 たとえば20の約数を調べるときに、20%2は余り0。 よって約数とわかるが、20/2 = 10もついでにわかる。 こうしておくと、ループは20の平方根までで済み、だいぶ計算量をおさえることができる。 ループ最後あたりで、答え…

問題 atcoder.jp 解法 文字を処理するクエリの * 先頭に追加 * 末尾に追加 という特性をみて、dequeでデータ管理すれば良いという点に気がつくかがポイント。 文字の反転も、馬鹿正直にクエリでるたびに行うと計算量がかなり増えるので反転をフラグ管理して…

問題 atcoder.jp 解法 Pythonのdictionaryで、Aiのインデックス番号を管理する変数noを作成。 Aをソートして、Aの中身をループさせてnoから元のインデックス番号を引っ張ってきて表示。 実装

問題 相違なる整数 があります。 となるような整数 を出力してください。 そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。 atcoder.jp 解法 atcoder ABCのA問題って、基本的には問題に書いてある文言通りにコード書けばACできる…

atcoder.jp 解法 再帰関数を使ったDFS (深さ優先探索)でアッサリ解けた。

atcoder.jp 解法 各条件について考えてみる。 これを満たす数列の個数(ア) = 10N なるが存在する(イ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 なるが存在する(ウ)。 これを満たす数列の個数 = 10N - 9N 9Nはを満たす個数 abc178_c 問題の答え…

atcoder.jp 解法 問題文より 行を何行か選び (0行でもよい)、列を何列か選ぶ (0列でもよい)なので、選ぶ行は何行でも自由に選択できる。 1 <= H, W <= 6 なので、最大でも212 = 4096通り。 bit全探索で総当たりをかけて、答えを求める。 実装 参考 blog.hama…

問題概要 atcoder.jp 解法 公式解説には、３の倍数に関する色々な考察が書いてある。 数十行にわたって難しそうなことが延々かいてあるのだが、最後の１行で驚きのどんでん返し。 Nが18桁しかないので消す桁を2進数を使って全探索でも解けます えー！それな…

AtCoder ProblemsにRecommendationって機能あって、ユーザことにオススメの難易度の問題を勧めてくれるんですよね(Atcoder Problems -> User -> Recommendation)。 茶diffやるべきだろうなと思ってたら、見事に茶の問題ばかり勧められるので、素直にやってき…

AtCoder Problemsが茶diffと判定した問題から重点的にやっておこう。 という方針を立てました。 このレベル帯の問題が出来ないことが多いと感じるんですよ。 問題に書いてある通りに実装するとTLEで、実は数学的に計算量減らせますよ。 系の問題が多い、この…