最近解いた問題の解説をしてみる(AtCoder)
タイトル通りです。editorial読んだほうがええやろという感想は尤もなのですが、自分の理解のために書いておこうかと思います。(解説と違う解答だったりしたので)
ABC057 C - Digits in Multiplication(300点)
問題文の要約をするまででもないですね。
方針としては、普通に積が となるような2つの整数の組を全探索していけばいいです。注意として、 から順に の約数となっているかチェックするわけですが、チェックする最大の整数は とすれば十分です。割る数を とすれば、 より大きい約数は として既に出てきているので、ここで計算量を落とせます。全体の計算量は となり、今回の制約では十分余裕を持って間に合います。
桁数の計算は普通に各言語に実装されているであろう常用対数を使えばいいと思います。常用対数の値に1を加えたものが整数の桁数になるので、これで計算できます。
Submission #9320273 - AtCoder Beginner Contest 057
(自分の提出)
ABC142 D - Disjoint Set of Common Divisors(400点)
解答では最大公約数を使った簡潔なもの等がありましたが、普通にこの問題も上の問題と同じ発想(ほぼ実装も同じ)で解けます。
まず方針ですが、少し考えれば選ぶことのできる正の公約数というのは、1か素数であるものしかありえないことが分かります。
これが分かれば、さっきと似たようなことで公約数を全て配列にでも突っ込んで全て素数判定してしまえばいいです。
公約数の計算は なので、これも余裕をもって間に合います。
実装上の注意としては、C++のstd::vector等を使うと入力が平方数のとき折返し地点で同じ約数を2回カウントしてしまうので気をつけましょう。std::set等を使えば問題ないです。
Submission #9320526 - AtCoder Beginner Contest 142
ARC033 B - メタ構文変数(?点)
配点が40と70に分かれてるらしいですが自分の提出についてる点数は100点なの謎です
要約:
与えられた数の集合 の共通部分と和集合の要素数の比を求めよ。
方針ですが、和集合については普通にsetにでも値をinsertしていって最後にsize()で出力すればいいです。共通部分は、どちらかの集合の要素全てについて、もう一方の集合にも含まれているかどうか調べればよいです(std::setを使うならfind()を使えば簡単です)。特に難しいことは無い。
Submission #9332944 - AtCoder Regular Contest 033
第二回全国統一プログラミング王決定戦予選 B - Counting of Trees
頂点 をrootとする木を考えます。
まず前提として であってかつそれ以外は0でない必要があります。そうでなければ答えは0です。
距離0の頂点には距離1の頂点から辺が伸びていて、距離1の頂点には距離2の頂点から辺が伸びていて……という風になっているので、まずはそれぞれ距離0、1、2、…となっているような頂点の数を数えましょう。このときに、距離1と距離3の頂点は存在するけど距離2の頂点は無い、のような状態になるとこれも木を構成できないので、答えは0です。
実装していく際には、数列 をソートしておくといいです。
あとは先頭からしゃくとり法しましょう。
ここまで来たら、あとは頂点から辺の伸ばし方が何通りあるか数えればいいです。
例えば、距離1の頂点が2つあり、距離2の頂点が3つ存在するとき、その繋げ方は 通りになります。距離 の頂点それぞれについて、距離 の頂点のどれを選ぶか、という話なのでこのような計算になります。
ここは解説動画見たほうがいいです。
頭の悪い数え方をしたりするとTLEになるので気をつけましょう(実話)。