Python3で解いた AtCoderの勉強になった問題 2020
- サマリー
- AtCoder Beginner Contest
- 169 C-Multiplication 3 (2020-05-31)
- 169 D - Div Game (2020-05-31)
- 170 D - Not Divisible (2020-06-14)
- 172 C - Tsundoku (2020-06-27)
- 172 D - Sum of Divisors (2020-06-27)
- 173 C - H and V (2020-07-05)
- 174 C - Repsept (2020-08-02)
- 176 D - Wizard in Maze (2020-08-22)
- 178 C - Ubiquity (2020-09-13)
- 180 C - Cream puff (2020-11-01)
- 181 D - Hachi (2020-10-17)
- 182 D - Wandering (2020-11-08)
- 183 D - Water Heater (2020-11-15)
- 184 D - increment of coins (2020-11-22)
- 186 D - Sum of difference (2020-12-19)
- AtCoder Regular Contest
- 最後に
- 参考書籍
サマリー
- 6月くらいから、AtCoderやってみようと、ふと思い立って初めて約半年。
- 年末時間ができたから復習していてそこで面白かった問題を上げていく。
- 基本過去記事の再掲しつつ、もう一度振り返る。
AtCoder Beginner Contest
169 C-Multiplication 3 (2020-05-31)
問題は以下 atcoder.jp 初めての参戦で、いきなりこの問題でWAを超絶だした記憶。オーバーフローや計算精度に関する問題も出るのかと痛感した。
どういう時に問題が起きるのかをそもそも理解できずに、試行錯誤しつつ、以下のうように、浮動小数は実際には正しい値を保持していないことを改めて知って勉強になった。
0.07 * 100 # 7.000000000000001 0.29 * 100 # 28.999999999999996
でもDecimalモジュール使えばいいやと思って通した。
a, b = map(str, input().split()) res = int(a) * Decimal(b) print(int(res))
けど本来は、数値をそのまま掛け合わせて後で割って整数部分だけ取得するとやってほしかったんだろうなぁ
a, b = map(str, input().split()) c,d = b.split('.') # int(c+d)とするとbを文字通り100倍された結果になる。 res = a * int(c+d) print(res//100)
169 D - Div Game (2020-05-31)
問題は以下 atcoder.jp この当時は、素因数分解をする方法もコードに落としてなくて1から実装しなきゃで大変だったが、それさえできればあと一工夫でできる。
170 D - Not Divisible (2020-06-14)
問題は以下
この当時は、エラトステネスの篩的な考えもコードに落としてないし、発想としても持っていなかった。
- リストに含まれるある値の定数倍の値をふるい落とすという考えを学んだ
- また、
in
で探すときは対象をlist
ではなくset
にしておくことが速度として重要というのも学んだ
n = int(input()) a = list(map(int, input().split())) a_s = sorted(a) a_set = set(a_s) maxv = max(a) res = [0] * (maxv+1) rep = 0 for i in a_s: # iを評価してない時はiを含むの定数倍のところは+1 if res[i] == 0: for j in range(i, maxv+1, i): res[j] += 1 # iを評価してあればiを+1 # すでに定数倍として評価されていたら2以上にしたい else: res[i] += 1 cnt = 0 # 最終的に検索対象が定数倍リスト内で1になっているものだけをカウントする for i in range(n): if res[a[i]] == 1: cnt += res[a[i]] print(cnt)
172 C - Tsundoku (2020-06-27)
問題は以下 atcoder.jp
ここらへんから記事書き始めた。
- しゃくとり
- 累積和と二分探索
この時、これらのイメージを掴んだ感じ
172 D - Sum of Divisors (2020-06-27)
問題は以下 atcoder.jp
Pythonだとでもだと通らないということを感じた回だった。
工夫すれば、
約数 等差数列の和で計算できる。
173 C - H and V (2020-07-05)
問題は以下 atcoder.jp
はじめてbitをコードで起こした。bit演算子である、'&'や '>'の意味を学んだ。
- bit全探索
- itertoolsのproduct の両者を学んだ。bitは未だに苦手でbitで全パターン検索するような場合は先にproductで作ってしまうほうが考えやすい。
174 C - Repsept (2020-08-02)
問題は以下 atcoder.jp
愚直に'7'をいくつも並べたものを順に割っていくっていうのはだめ。基本的にという様にたくさん文字列を羅列する形は遅い。
純粋に'7', '77', '777' ... なので初項7, 公比10の等比数列と考える。
- 等比数列の和
- 余りで考えれば良いのでモジュラの性質をうまく使って10倍されていく時にあまりを10倍して考えればオーバーフローなどを木にする必要がなくなる。
176 D - Wizard in Maze (2020-08-22)
問題は以下 atcoder.jp
結構重くて、なかなか通らなかった。 対策としては、外側へのはみ出しを防止。結構むずくて、今解き直しても素直に実装できなそう。
- 上下左右を'##'で埋める。
- あとは歩いていけなくなるまで普通の迷路探索 。
- ワープのパターン出いけるところに歩いていける範囲としてキューに加える。
178 C - Ubiquity (2020-09-13)
問題は以下 atcoder.jp
愚直に条件に当てはまるものを求めるのではなく、包括原理より、全パターンから条件に合わないものを引くとしたほうがいいパターン。
ポイントとして、という形は愚直に計算すると遅いので計算過程ではくり返し二乗法を使う
180 C - Cream puff (2020-11-01)
問題は以下 atcoder.jp
単純な約数列挙だが、いちからコード書くと結構大変だった。考え方としては素因数分解と同じようなイメージでいけた。からまで試し割りして、 割り切れたものと、割り切れたときの商を別々に保持して後でリストを連結
181 D - Hachi (2020-10-17)
問題は以下 atcoder.jp
単純な倍数判定だが、入れ替えを考慮するため侮れない。 結果から言うと、Counterで8の倍数の下3桁の文字列のパターンと一致するかどうかで判断。Counterの結果は引き算できることがポイント
182 D - Wandering (2020-11-08)
問題は以下 atcoder.jp
その時までの値の累積和とその時までの値の最大値の和を考える。 図示しながら考えるとわかり良い。
183 D - Water Heater (2020-11-15)
問題は以下 atcoder.jp
持ち方がポイントで、使うスケジュールの最初の時刻でプラス、終わりでマイナスしたリストを頭から順に足し合わせていくようにして、スケジュールの累積和として考える
184 D - increment of coins (2020-11-22)
問題は以下 atcoder.jp
メモ化を自動的にやってくれるlru_cacheというデコレータを知った。 メモ化と比較するとスッキリすることがわかる。
186 D - Sum of difference (2020-12-19)
問題は以下 atcoder.jp
久しぶりにコンテストの最中にDまで解けた。
引き算の絶対値がポイントで、事例を書き出して、ソートして考えても良いと考えられれば単純な数え上げとなる。
AtCoder Regular Contest
106 B - Value (2020-10-24)
問題は以下
Union-Find問題。連結しているグループの値の和が一致するかを検討するだけ。このとき注意しなくてはいけないのは、find()でrootを求めていく。
109 B - log (2020-11-28)
問題は以下
これまで、リストが存在する二分探索はやったことがあったが、この問題ではリストを作ってから行うと、TLEとなってしまうため、midの値を適切に変形し 探索したい値と比較する。
110 B - many (2020-12-05)
問題は以下
最初'0'にアサインできたら、最後、左から数えて何番目の'0'にアサインできるかを考える問題
最後に
結局だいたい実際にコンテストで解いた問題全部あげただけみたいになってしまったがまとめながら、半日かけて、ここに書き出した問題をもう一度解き直しして良い復習ができた。
ブログにまとめながらやっていたおかげで数ヶ月前に書いたコードを少し見直しただけで思い出せたし、復習が比較的楽にできてよかった。
2020年06月以前の問題も実際には精進として解いていて、その中でも良さげな問題はあったが、とりあえず今回は取り扱わないでおいた。
参考書籍
けんちょんさんの本。非常に参考になる。行き詰まった時にもう一度読み直したりしてる。
こちらで、書籍を7章まで進めている。
【Fast.ai Vision】Single-Label Classificationの基礎
サマリー
Fast.aiのversion2で関数が結構変わっていたので、Single-Label Classificationを行うために最低限の知識をメモとしてまとめる。 基本的にはこちらの書籍に書かれている。
Deep Learning for Coders With Fastai and Pytorch: AI Applications Without a Phd
- 作者:Howard, Jeremy,Gugger, Sylvain
- 発売日: 2020/08/11
- メディア: ペーパーバック
本格的に使う場合は、csvからのデータ取得やaugumentationも既存ツールでないものを使ったほうがいい、学習の仕方の工夫などがあるが、今回は取り扱わず、別記事とする。
環境準備
condaでInstallすることが推奨されている。まっさらな環境のときはcondaをオススメする。colabの場合はPytorchも使える状況なので、pip install
で問題ない。
# Colabの場合(すでにPytorch環境が整っている場合)
!pip install -Uqq fastai
# まっさらな環境の場合(Pytorch環境もなく、1から環境作る場合)
conda install -c fastai -c pytorch fastai
Colabではない環境でどうしてもpipで環境を作りたい場合は、以下で適切にPytorchのinstallの設定を調べてから行う。 pytorch.org
モジュールの読み込み
賛否両論あるが、Fastaiはこの様に一行ですべて読込させる方針。
from fastai.vision.all import *
どのような形で必要なモジュールを読み込んでいるのかを把握したい場合は、いかから追ってみるといい。必要なモジュールだけを、すべて個別で読み込もうと試みたが、ただ使うだけなら度々import errorが起きるため諦めて、Fastaiの方針にのることにした。
Data Blockについて
DataLoadersの準備
以前はDataBunchというクラスでDataSetsやDataLoadersを作成したがversion2以降では変更となったようだ
DataBlockは、以下の引数を与えるとのDatasetsまたはDataLoadersを作成できる。
今回は比較的簡単にpathを取得できる例で説明する。Multi-Label ClassificationやデータセットのPATHがcsvで提供されている場合のDataBlockの作り方は別記事にする。
blocks
はsinglelabelならblocks = (ImageBlock, CategoryBlock)
で- ImageBlockはTransformBlockのはPILで画像を読み込むための派生クラス
get_items
は画像ファイルのパスを取得する方法、例えばget_image_filesを使う。splitter
は、データを分割する方法、以下のsplitterから状況に応じて使い分ける。get_x
は、入力に何かを適用する必要があるなら記述。get_y
は、ターゲットに何かを適用する必要があるなら記述。多くは予測ラベルの取得方法の関数。例えば、画像ファイル名から0, 1にする関数や画像ファイル名から名前やカテゴリ名を取得する方法を記述。 例えば、RegexLabellerとusing_attrを使うなどする。item_tfms
は、batchが形成される前にアイテムに適用される変換を記述。GPUにコピーされる前に個々の画像に適用される。例えばresize。batch_tfms
は、batchが形成された後に適用される変換を記述。GPU上で一括して適用される。例えばaug_transformsなどを使う。
item_tfmsとbatch_tfmsの両者に使う関数は以下が参考になる。 Data augmentation in computer vision | fastai
# 例えば、path/"images"以下に画像データそれぞれのPathが入ってるとすると data = DataBlock(blocks = (ImageBlock, CategoryBlock), get_items=get_image_files, splitter=RandomSplitter(seed=42), get_y=using_attr(RegexLabeller(r'(.+)_\d+.jpg$'), 'name'), item_tfms=Resize(460), batch_tfms=aug_transforms(size=224, min_scale=0.75)) dls = data.dataloaders(path/"images") # 実際のカテゴリ、カテゴリ数を表示 print(dls.vocab) len(dls.vocab)
DataLoadersの確認
DataLoadersの中身をバッチ分確認したい場合は以下。 デフォルトでは、バッチサイズは64。
x, y = dls.one_batch() # y # TensorCategory([18, 36, 35, 22, 17, 26, 0, 21, 32, 34, 1, 7, 1, 20, 31, 15, 31, 34, 5, 1, 22, 33, 21, 26, 0, 9, 15, 7, 13, 16, 28, 23, 18, 5, 1, 5, 15, 6, 5, 12, 1, 24, 2, 16, 6, 5, 8, 11, 30, 5, 22, 34, 11, 18, 0, 19, 25, 28, 32, 9, 21, 6, 17, 13], device='cuda:0')
画像自体を確認するときは[show_batch] (https://docs.fast.ai/data.core.html#TfmdDL.show_batch)で表示できる。以下は、The Oxford-IIIT Pet Datasetを読み込んだときの例。
dls.show_batch(nrows=4, ncols=4, max_n=16)
学習(Fine turning)
learnerの設定
基本的に最低3つ設定する。
- DataLoaders
- モデル
- Metrics
モデルは自分で構築したものも使えるし、以下のpretrainedされたモデルアーキテクチャも使える。 pytorch.org
Metricsは自分で構築したものも使えるし、以下の用意されたMetricsを使える。
learn = cnn_learner(dls, resnet34, metrics=error_rate)
モデル構造のチェック
cnn_learnerで作っている場合は、選択したモデルの最後の層だけcutして、DataLoaderに合わせた数にセットされる。以下で確認できる。
learn.model
転移学習とFine turning
転移学習は、
事前に学習した重みや他のレイヤーの重みを変更せずに(freezing)、目的のタスクを正しく達成するように最終層の完全結合層(fully conect layer)はランダム重みを持つ新しいものに置き換えてこの重みを置き換えた最終層のみの重みだけを更新するように学習すること。
Fine turningは、
転移学習後の微調整で、転移学習後に他のレイヤーの重みの変更を許して(unfreezing)、目的のタスクを正しく達成する重みに置き換えて学習すること。
多くの場合で、以下のやり方で転移学習・Fine turningすることでよりLossが下がることが知られている。
- 最終層以外をfreezingして学習する。
- unfreezeする。
- 更に学習する。
Fastai version1のときは
learn.fit_one_cycle(1) unfreeze() learn.fit_one_cycle(1)
のようにやっていたが、version2から新たにfine_tuneというmethodが追加された。unfreezingで何epoch学習するかが引数。freezingで何epoch学習するかは別途設定できる(デフォルトでは1)
なので、上記と同義なのが以下
learn.fine_tune(1)
ただ、基本的には、fit_one_cycleとlr_findを組み合わせて、freezing時でも最適な学習率を設定し、unfreezingでも最適な学習率を設定し(最初は大きな値、徐々に小さく)学習することが望ましい。
以下に、適切な学習率を探索する方法について書いた。
適切な学習率の探索
Leslie Smithによって、learning rate finderというアイディアが考案された。 arxiv.org 内容の詳細は省くがその論文は以下なので、参考にするといい。学習率の良い値は、
- ダイバージェンス前の最小値の10分の1
- 勾配が一番急な時
learnerを設定したら、以下のようにすれば、上記の2つの値が返ってくる。
learn = cnn_learner(dls, resnet34, metrics=error_rate)
learn.lr_find()
# SuggestedLRs(lr_min=0.012022644281387329, lr_steep=0.0063095735386013985)
まず、freezingしている状態で実際にその値を見た上で適切な学習率を考える。上記の例だと、以下のようにするのが例となる。
learn = cnn_learner(dls, resnet34, metrics=error_rate) learn.fine_tune(2, base_lr=3e-3)
fit_one_cycleを使った改善
fit_one_cycleはfine_tuneを使わずにモデルを学習する方法として用意されていて、より自由度高く学習の設計ができる。低い学習率で学習を開始し、最初の部分では徐々に学習率を上げ、最後の部分では再び学習率を徐々に下げていくことが可能。
- 学習率を探索する。
- freezingして、最終層の重みだけを更新するように学習する。
- unfreezingする。再度学習率を探索する。
- すべての層の重みを更新するように学習する。
# 1. 学習率を探索する。 learn = cnn_learner(dls, resnet34, metrics=error_rate) learn.lr_find() SuggestedLRs(lr_min=0.012022644281387329, lr_steep=0.0063095735386013985)
# 2. 最終層の重みだけを更新するように学習する。 learn = cnn_learner(dls, resnet34, metrics=error_rate) learn.fit_one_cycle(3, 3e-3)
# 3. unfreezingする。再度学習率を探索する。
learn.unfreeze()
learn.lr_find()
上記の例だと、freezing前の探索時のLossの落ち込みに比べて、unfreezing後の探索時の急激なlossの落ち込みがないのは、学習がある程度進んでいるからと考えられる。この場合だと、以下のように学習をすすめるなど、考えられる。
# 4. すべての層の重みを更新するように学習する。 learn.fit_one_cycle(6, lr_max=1e-5)
Discriminative Learning Rates
Jason Yosinskiらによって、支持されているものとして、ネットワークの初期層には低い学習率を使い、最終層には高い学習率を使うのが良いとされている。論文は以下。 arxiv.org
例えば、これまでの内容をふまえると、以下のような流れで行うことができる。
learn = cnn_learner(dls, resnet34, metrics=error_rate) learn.fit_one_cycle(3, 3e-3) learn.unfreeze() learn.fit_one_cycle(12, lr_max=slice(1e-6,1e-4)) # lossのプロット learn.recorder.plot_loss()
Mixed Precision
より、深いネットワークを使ったときの問題点としては、
- メモリ不足
- 時間がかかる
解決策として、以下が考えられる。
- メモリ不足に関してはバッチサイズを減らして学習させる。
- 時間がかかることに関しては、Mixed Precisionとして、半精度浮動小数点(fp16)を使うことで数倍早くなる。
Fastai version2では半精度浮動小数点はfrom fastai.callback.fp16 import *
を読み込むことで使うことができる。
(fastaiのバージョンにもよる。callbackのうちfp16についてはfrom fastai.vision.all import *
で自動的に読み込まれることもある)
from fastai.callback.fp16 import * learn = cnn_learner(dls, resnet50, metrics=error_rate).to_fp16() learn.fine_tune(6, freeze_epochs=3)
精度解釈
学習時にvalidation lossで自分で決めたmetricで精度は理解できているものの、実際にどのクラスとどのクラスが間違えやすいか、その程度はどの程度かを把握するために、confusion matrixで予測があっているかを直感的に理解する。
confusion matrix
interp = ClassificationInterpretation.from_learner(learn) interp.plot_confusion_matrix(figsize=(12,12), dpi=60)
クラスを間違っているかのチェック
間違っているクラス同士をチェックするにはmost_confused
というメソッドが用意されている
interp.most_confused(min_val=5)
参考になる書籍
FastaiとPytorchを使って画像認識や協調フィルタリング・NLP関連のタスクを例として、かなり詳細まで書かれている。Fastaiを使っていくなら一読することをおすすめする。
Deep Learning for Coders With Fastai and Pytorch: AI Applications Without a Phd
- 作者:Howard, Jeremy,Gugger, Sylvain
- 発売日: 2020/08/11
- メディア: ペーパーバック
Python3で解く AtCoder Beginner Contest 186 D - Sum of difference
結構単純な、数え上げ。 ソートして考えることにきづければ簡単。
目次
概要
問題概要は省略。
解くときに考えた内容
- すべてのパターンは でも制約的に、線形で考えなくてはいけないので二重のforではだめ。
- 差の絶対値をとったものの和なので順番をソートしても問題ない。
- 大きい順にする。
- あとはindexと対応する値を適切に足し合わせたり、引いたりする。
- 簡易的な例を考えると、だとした時に、順番に引き算すると となる。図を見ると、大きい順にソートしてから考えた時と、計算結果は変わらないことがわかる。(左右が入れ替わったパターンが出てくるだけでそれは絶対値によって和にするならば一致するため)
- ここまで理解できれば、あとは規則性。
- 全体でどれがどれだけ+なのか-なのかを考える。
- が回加算される(図では+)回減算される(図では-)。
- が回加算される(図では+)回減算される(図では-)。
- 一般にが回加算される(図では+)回減算される(図では-)。
最近は実際のコンテストの最中にイメージ図を書くようにしている。その方が、indexとの関係などをが明白になってミスが減っている気がしている。上の図も実際の場面で書いたもの。
コード
n = int(input()) A = sorted([int(x) for x in input().split()], reverse=True) ans = 0 for i in range(n): ans += A[i] * ((n-i-1) - i) print(ans)
参考になる書籍
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。
とうとう発売され自分の手元にも来た(2020-10-03)。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う(答え合わせできるのはありがたい)。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本
7章までは別記事に残してある。 blacktanktop.hatenablog.com
AtCoder Beginner Contest 186 参加ログ・感想
内容
- Python3でやっている。
- 参加ログ。
- 所感。
- コンテスト中に何を考えたか。
- コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
- 問題の詳細で細かく書こうと思うものは別記事とする。
結果
久しぶりにABCD完。Eも方針が立つくらいにまでは時間があった。 少しは成長している感触だった。Cはn進数をリストで持つようにして対応。制約的にDは線形で考えなくてはいけないと考え、絶対値がポイントになると踏んで対応した。
どう考えたか + α
A - Brick
問題タイプ:商
文意から商が答え
n, w = map(int, input().split()) ans = n // w print(ans)
B - Blocks on Grid
問題タイプ:最小値・ループ処理
- を多重リストで持つと面倒なので、flattenして、1次元のリストにする。
- の最小値を求める。
- をループで回しながら最小値をとの差を加算していく。
import itertools def flatten(l): return list(itertools.chain.from_iterable(l)) h, w = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(h)] a = flatten(A) min_a = min(a) cnt = 0 for i in a: cnt += i - min_a print(cnt)
C - Unlucky 7
問題タイプ:n進数
もしかしたら、組み込み関数でいい感じにできるかもしれなかったが、知らんかったのと、入力値とn進数を入れたら、各桁のリストで管理したかったので、その様にやった。あとは10進数と8進数どちらも出てきたの中にがないものだけカウントするだけ。
def shinsu(N, shinsu=8): keta=0 for i in range(10**5+1): if N<shinsu**i: keta+=i break ans=[0]*keta check=0 for i in range(1,keta+1): j=N//(shinsu**(keta-i)) ans[check]=j check+=1 N-=(j)*(shinsu**(keta-i)) return ans n = int(input()) cnt = 0 for i in range(1, n+1): ans10 = ch(i, 10) ans8 = shinsu(i) if 7 not in ans10 and 7 not in ans8: cnt += 1 print(cnt)
ちなみに、調べたらoct()
とすれば8進数にできるらしい。
10進数はstrにすればいいので、そうすると以下のように可能。
oct()
のために超絶めんどいことしてしてしまった。
n = int(input()) ans = 0 for i in range(1, n+1): if ('7' not in str(i)) and ('7' not in oct(i)): ans += 1 print(ans)
D - Sum of difference
問題タイプ:ソート・累積和
すべてのパターンは でも制約的に、線形で考えなくてはいけないので二重のforではだめ。 ポイントは、順番をソートする。その後順番に数ごとに加える量や引く量を線形に計算していく。別記事にする。
おわりに
今回は、比較的できた。今までやってきたことが、問題に多く出てきたという感じ。やはり慣れが重要だし、ぱっと思いつける様に精進が重要。 が沼はまだ深い・・・。
参考になる書籍
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本
7章までPythonで章末問題をこなしていっている。
Python3で解く AtCoder Beginner Contest 114 D - 756
階乗の約数のカウント、七五数のカウント。愚直に約数を列挙して数え上げるとだめで数え上げに組み合わせのを考えながら工夫が必要な、いい問題
目次
概要
- が与えられる。
- の約数の中に七五数は何個ある?
- 七五数とは約数をちょうど75個持つ正の整数とする。
解くときに考えた内容
約数のカウントは以下のように考える。
- が素数とすると
- の形でなにかの数字が表せるとすると、
- がその約数の数
の約数の中に七五数は何個あるで、約数を列挙して、それぞれの約数の数をカウントすると、TLEになってしまう。列挙せずに組み合わせのパターンで考える必要がある。
の素数の数の数え上げを行う。
- 七五数はでいうと、
-
- となるようなの数
-
- となるようなの数 x ( となるようなの数 )(以上になるなので、片側に含まれたらもう片側に含めたくないので)
-
- となるようなの数 x ( となるようなの数 )
-
- となるようなの数 x ( となるようなの数 ) x (となるようなの数 ) を で割る
- で,するのは、ある数以上あるものとしているので、該当の素数たちのなかから一度選んだものを排除したい。
- の時2で割るのは、累乗が4以上になる素数が10個ある時に二つ選ぶ選び方なので
コード
# 階乗の素数のカウント用 def factorization_list(n): tmp = n i = 2 while i*i <= n: if tmp%i == 0: cnt = 0 # 割れる場合は割れなくなるまで同じ数でわる while tmp%i == 0: cnt += 1 tmp //= i e[i] += cnt i += 1 # 最後1になるか素数が余るので素数ならリストに追加 if tmp != 1: e[tmp] += 1 # nが1以外の素数だったら if e == [0] * (n+1): if n != 1: e[n] += 1 return e # m以上の個数(たとえばeの中に4以上のものがいくつあるかを調べる) def e_count(m): l = [i for i in e if i >= m] return (len(l)) n = int(input()) e = [0] * (n+1) for i in range(2, n+1): factorization_list(i) # print(e) # nが与えられた時に、1-indexでn!の素数の累乗の合計を示す。 # n=6 # 2! [0, 0, 1, 0, 0, 0, 0] # 3! [0, 0, 1, 1, 0, 0, 0] # 4! [0, 0, 3, 1, 0, 0, 0] # 5! [0, 0, 3, 1, 0, 1, 0] # 6! [0, 0, 4, 2, 0, 1, 0] # 重複しないようにうまくカウント、e_countはm以上だから一度選んだものを選ばないようにする # 同じ値のものを選ぶときは選び方的に割り算する(mが4以上をを2つ選ぶ選び方のこと) print(e_count(74) + \ e_count(24) * (e_count(2)-1) + \ e_count(14) * (e_count(4)-1) + \ e_count(4) * (e_count(4)-1) // 2 * (e_count(2)-2))def factorization_list(n): tmp = n i = 2 while i*i <= n: if tmp%i == 0: cnt = 0 # 割れる場合は割れなくなるまで同じ数でわる while tmp%i == 0: cnt += 1 tmp //= i e[i] += cnt i += 1 # 最後1になるか素数が余るので素数ならリストに追加 if tmp != 1: e[tmp] += 1 # nが1以外の素数だったら if e == [0] * (n+1): if n != 1: e[n] += 1 return e # m以上の個数(たとえばeの中に4以上のものがいくつあるかを調べる) def e_count(m): l = [i for i in e if i >= m] return (len(l)) n = int(input()) e = [0] * (n+1) # nが与えられた時に、1-indexでn!の素数の累乗の合計を示す。 # n=6 # 2! [0, 0, 1, 0, 0, 0, 0] # 3! [0, 0, 1, 1, 0, 0, 0] # 4! [0, 0, 3, 1, 0, 0, 0] # 5! [0, 0, 3, 1, 0, 1, 0] # 6! [0, 0, 4, 2, 0, 1, 0] for i in range(2, n+1): factorization_list(i) print(e) # 重複しないようにうまくカウント、e_countはm以上だから一度選んだものを選ばないようにする # 同じ値のものを選ぶときは選び方的に割り算する(mが4以上をを2つ選ぶ選び方のこと) print(e_count(74) + \ e_count(24) * (e_count(2)-1) + \ e_count(14) * (e_count(4)-1) + \ e_count(4) * (e_count(4)-1) // 2 * (e_count(2)-2))
参考になる書籍
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。
とうとう発売され自分の手元にも来た(2020-10-03)。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う(答え合わせできるのはありがたい)。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本
7章までは別記事に残してある。 blacktanktop.hatenablog.com
Python3で解く AtCoder Beginner Contest 185 D - Stamp
結構単純な、数え上げするだけ。 問題を把握するのに、少しだけ苦戦したがよく読んだらDにしては結構単純だった。
目次
概要
問題概要は省略。
解くときに考えた内容
- 最初と最後を同等に考えられる様にとをリストに加える。
(元のリストのうち、最初と最後の値を同等に扱える必要にするため結構キモ) - 更にソートする。
- 具体的に言うと入力例1だと →
- 0以上の差分のリストを作成する(間にいくつ数値があるかという意味で)
- →
- この時点で、0以上の差分のリストに値がなければ、白がないということ。
- は0以上の差分のリストの最小値になる。
- そうでないと、どう取ってもかならず白を含んでしまうため
- 差分のリストに含まれる値をで割って、切り上げた値を足し上げていく。
- 切り上げのイメージはX:白、O:青、△:赤として、XOOOOOXを例えばでで△で埋めていくことを考えると割り切れる範囲はX△△△△OXのようなイメージで割り切れない部分は1度重なるようにしてX△△△△△Xとする必要があるから、切り上げするイメージ。
コード
n, m = map(int, input().split()) a = [int(x) for x in input().split()] # 最初と最後を同等に考えられる様に # 0とn+1をリストに加える a.append(0) a.append(n+1) # print(a) num = len(a) a_s = sorted(a) l = list() for i in range(num-1): c = (a_s[i+1] - a_s[i] - 1) # print(c) if c > 0: l.append(c) # print(l) if len(l) == 0: print(0) else: k = min(l) cnt = 0 for i in l: # 切り上げ if i % k == 0: cnt += i // k else: cnt += i // k + 1 print(cnt)
参考になる書籍
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。
とうとう発売され自分の手元にも来た(2020-10-03)。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う(答え合わせできるのはありがたい)。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本
7章までは別記事に残してある。 blacktanktop.hatenablog.com
AtCoder Beginner Contest 185 参加ログ・感想
意味不明なやり方して頭大混乱で、絶対に落としちゃいけないCを落としてしまった・・・
内容
- Python3でやっている。
- 参加ログ。
- 所感。
- コンテスト中に何を考えたか。
- コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
- 問題の詳細で細かく書こうと思うものは別記事とする。
結果
AB完。Cはただのコンビネーションでとにかく11箇所を選ぶだけの計算だったのにわけわからんこと考えて終了なぜパニクるのかもよくわからんし、さらにPythonならオーバーフロー気にせずできる。Dは、マスのリストをソートして、差分を取って、一番小さい値で差分を割って切り上げを足すだけ。あとから考えると結構ラッキー回だったのにできなかったのは実力不足Orz
どう考えたか + α
A - ABC Preparation
問題タイプ:最小値
文意から問題数が最も小さい値が答え。
a = [int(x) for x in input().split()] ans = min(a) print(ans)
B - Smartphone Addiction
問題タイプ:クエリ処理・条件分岐 初期に持っているバッテリー値に対して、
- 以降の変化するバッテリー値 とする。
- - 前回のの値()を引く。(状況:歩いている時間)
- 初回はを引く。
- この時に になったら'No'
- を足す。(状況:カフェで充電)
- この時に になったらとする。(状況:満充電)
- 次のクエリのと引き算するためにを保持しておく。(状況:カフェ出た時間の保持)
なんか、結構条件をきちんと書き上げるだけなんだけど、条件分岐も多くて結構ハマった。
n, m, t = map(int, input().split()) ab = [list(map(int, input().split())) for _ in range(m)] _b = 0 bat = n for a, b in ab: _a = a - _b _b = b - a bat -= _a if bat <= 0: print('No') exit() bat += _b if bat > n: bat = n _b = b if t - _b < bat: print('Yes') else: print('No')
C - Duodecim Ferra
問題タイプ:組み合わせの数え上げ
文意から、とにかく箇所切るところを選ぶ選び方。つまり Pythonの場合はオーバーフローは気にせず。分子と分母を別々に計算して割り算するだけ。
l = int(input()) # l-1から11を選ぶ選び方 a, b = 1, 1 for i in range(1, 12): # 分子 a *= l-i # 分母 b *= i print(a//b)
おわりに
今回は、絶対わからんっていう感じでもなかったのに、解ききれないといった感じ。またRatingは少し下がってしまった。沼はまだ深い・・・。
参考になる書籍
- 問題解決力を鍛える!アルゴリズムとデータ構造
けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!(実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい)どのようなステータスの人にもおすすめの一冊になっている。
問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)
- 作者:大槻 兼資
- 発売日: 2020/10/02
- メディア: 単行本
7章までPythonで章末問題をこなしていっている。