ABC 170 D - Not Divisible
エッジケースを通すコードを書く技術がまだまだ足りない． ネストが深くなったり変数定義が増えるときは大体考察が足りていなくて，そういうときはアクセプトしない．
ネストを浅くしたり変数定義を減らせばアクセプトするのは事実だと思うが，それができるのは考察が正しいからという前提があるのを忘れてはいけないと思う．
回答時の方針
本番ではエラトステネスの篩は頭に浮かんだがエラトステネスの篩の高速化について理解していなかったのでTLEしてしまった．コンテスト終了後は高速化した上で提出を繰り返したが全てのテストケースを通すのにかなり苦労した．
正答
Submission #14397726 - AtCoder Beginner Contest 170
結果だけ見るとそんな難しいことはしていないがいくつか詰まった点をまとめる．
- 高速化
入力例1で考える．ナイーブに考えると各 Ai について Aj を試すことになるので計算量は O(n^2) になる．
5 24 11 8 3 16
要素Aiで割り切れる要素を取り除きたいとき別途リストDPを利用すると高速化できる．リストAを昇順ソートした上で要素Aiの倍数要素についてDP[Aj]=trueとすれば改めて要素Ajを試行するまでもなく倍数判定が可能となる．
for(ll j = 2*ar[i]; j <= max; j+=ar[i]) { s[j] = true; }
- リストのサイズに余裕を持たせる．
これは書いてあるとおりで例えば入力例1の場合要素の最大値は24なのでDP.size=24あれば十分なのだが，このあたりを厳密にやるよりは与えられた制約の最大値で初期化したほうが問題が起きないことが多いように思う．DP(200000, false)
ABC 129 C - Typical Stairs
リハビリっていうほど元々すごいわけでもないけど レポート提出が落ち着いたのでリハビリがてら解きました
diff 795
Total Accepted 122
回答時の方針
最近関数型言語に触れていたこともあり再帰脳で全探索しにいってしまった,当然間に合わず.
Submission #14092942 - AtCoder Beginner Contest 129
i番目の階段に辿り着く移動方法を以下のように定義した.
v[i]= v[i-1] + v[i-2] (2 <= i) v[0] = 0 v[1] = 1 v[2] = 2
途中でv[1]とv[2]について自身と前の階段が壊れていることを考慮していないことに気づき以下のように修正した.
if(b[1]) v[1] = 0; else v[1] = 1; if(b[2]) v[2] = 0; else if(b[1]) v[2] = 1; else v[2] = 2;
Submission #14095479 - AtCoder Beginner Contest 129
正答
dpで計算するのが正答で上の解答も同じ方針なので特に問題はなかったが洗練されてない. 条件分岐が増えるとそれだけバグが混入する可能性が上がるのでなるべく条件分岐を考えずに済むコーディングを意識したい. 今回の場合だと
- v[0]=1とおくこと - v[i+1] = v[i+1] + v[i]としてループを回す - v[i+2] = v[i+2] + v[i]としてループを回す
これにより不要なif文は回避できた,結局はシンプルさに行き着くんだと改めて感じたのだった.
5月の振り返りと6月の目標
Android
とりあえず1記事/月は守った. 年末のアドベントカレンダーネタもなんとなく決まりつつあって流れとしては悪くないと思う.
ここでDIツールのパフォーマンスが比較されてるんだが仕組みはわかっているつもりだけど,実装的に何故ここまで差がでるか説明できないので6月はこれについて記事を書こうかなと思う.
大学院
周り賢い人多すぎてわろてる,1を聞いて100知る人が多すぎる. 地頭+CSバックグラウンドじゃない人の中でも業務経験の長さとかで理解力に差がでるのかなと思いつつ比較的早い段階でこういう経験できてよかったかなと思っている. 真似できるとこは真似しつつ,少なくとも自分の中では納得できるまでCS系の授業の内容を理解したい.
競技プログラミング
大学院生活が軌道にのるまではお預けかなという感じ悲しいかな. 勘が鈍らない程度に茶diffくらいは解くようにはしてます.
koinのインスタンス管理について
Android開発していて体験的に特に不満はないんだが,単体テストの書き味だけはrspecに劣るなと思っている.特にfactory_botによるテスト用のオブジェクト生成はtraitによる拡張とか含めシンプルで好きだった.サーバーサイドだとDBという状態の塊をテストする必要があるから状態を保持するためにオブジェクトを作る必要があるのだが,Androidでもオブジェクトを生成する機構があるといいなと思ったりする(mockを使うとかイミュータブルにして変更を配列で保持するというのが正攻法だと思うがとはいえ欲しくなる).
前置きが長くなったがkoinのfactoryと同じような仕組み(=インスタンスに名前をつけて生成/取得する）で,factory_botと同等とまではいかないがそれらしい振る舞いをするものは作れるのではと思い少し調べてみた次第である.
TL;DL
- インスタンスはBeanRegistryのdefinitionsに保持される.
- 生成した各インスタンスはBeanDefinitionにより抽象化される.
- factoryやsingleDSLによりそれぞれDefinitionInstanceを継承したFactoryDefinitionInstance,SingleDefinitionInstanceが生成される.
- DefinitionInstanceはBeanDefinitionをメンバに持ちそれを管理する責務を持つ.
環境
Koin Core 2.0.1
登場クラス
インスタンスの保持や破棄を行うクラス.このクラスのメンバ変数のdefinitions: HashSet<BeanDefinition<*>>に実際のデータが格納される.
class BeanRegistry { private val definitions: HashSet<BeanDefinition<*>> = hashSetOf() private val definitionsNames: MutableMap<String, BeanDefinition<*>> = ConcurrentHashMap() private val definitionsPrimaryTypes: MutableMap<KClass<*>, BeanDefinition<*>> = ConcurrentHashMap() private val definitionsSecondaryTypes: MutableMap<KClass<*>, ArrayList<BeanDefinition<*>>> = ConcurrentHashMap() private val definitionsToCreate: HashSet<BeanDefinition<*>> = hashSetOf() ... }
dslで生成したインスタンスをkoinのクラス群で取り扱えるように抽象化したクラス.インスタンスのクラス情報やインスタンスの名前(qualifier)に関する情報などを持つ.
class BeanDefinition<T>( val qualifier: Qualifier? = null, val scopeName: Qualifier? = null, val primaryType: KClass<*> ) { ... /** * Create the associated Instance Holder */ fun createInstanceHolder() { this.instance = when (kind) { Kind.Single -> SingleDefinitionInstance(this) Kind.Factory -> FactoryDefinitionInstance(this) Kind.Scoped -> ScopeDefinitionInstance(this) } } ... }
BeanDefinitionのメンバ変数で共にDefinitionInstanceを継承する. KoinComponentから呼び出すとき,最終的にこのクラスがoverrideしたgetが呼ばれることになる.
SingleDefinitionInstance.kt
override fun <T> get(context: InstanceContext): T { if (value == null) { value = create(context) } return value as? T ?: error("Single instance created couldn't return value") }
FactoryDefinitionInstance.kt
override fun <T> get(context: InstanceContext): T { return create(context) }
所感
ARC 042 A - 掲示板
ギョームでも取り扱いそうな問題.
diff 855
回答時の方針
Submission #12993816 - AtCoder Regular Contest 042
まずは全探索.
愚直にやると書き込みがあったスレッドのインデックスを0にしてそれ以外のインデックスを+1する,これをm回繰り返せば期待する結果にはなるが計算量はで最大
で間に合わない.
構造的にpriority_queueとか使えそうだなと思ってスレッド番号と書き込まれた順をpairにしてpushしようとしたが同じスレッドに複数回書き込んだ場合に対応できないと思い断念.書き込んだ順にソートする実装がうまくできずに別の方法を取ることにした.
同じスレッドに複数回書き込みがあったとしても常に最新のもののみ採用すれば良いと気付き同じスレッドでも別物としてvector<ll>にpushして探索済みフラグで対応することにしてAC.
正答
ほぼほぼ上記の通りだがデータ構造的にはvector<pair<ll, ll>>をソートすればよかった.keyにスレッド番号valueに書き込まれた順番を持ってきてソートすればok.
REP(i, n) {
v[i] = PAIR(10000000 + i, i);
}
REP(i, m) {
v[a[i] - 1].first = m-i;
}
三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN
diff 836
回答時の方針
Submission #12909261 - Sumitomo Mitsui Trust Bank Programming Contest 2019
N個の数字の中から3個選んで3桁の数字を作ろうかと思ったがとなり筋が悪そうだと思い別の方法を検討した.暫くして3桁
としたときにN個の数字の中から
を決定する場合に同じ数字を選ぶことを考えると左のものから優先で選ぶことが最適だと気づいた.入力例2
123123からの値として1を選ぶ場合index=3は考える必要がなくindex=0が最適となる.
s: 123123 // 文字列s c: 333210 // 2桁目としてとり得る値の種類
この場合xとして1を選ぶと,
x=1 -> y=[1 i=3,2 i=2, 3 i=3] -> 2+3+3 = 8
同様にx=2,3について
x=2 -> y=[1,2,3] -> 2+1+3 = 6 z=3 -> y=[1,2,3] -> 2+1+0 = 3 t=8+6+3=17
ということで文字列を左から精査して各桁について先にマッチしたindexで決めてしまうのが最適だとわかる.
計算量は1桁目の選び方[1-9]2桁目の選び方[1-9]文字長Nでかな？
各文字ごとにi番目以降の数字のバリュエーションを保持しているぶん,解法の貪欲法より若干早い気がする.
正答
いくつか解法が提示されていたが計算量を見積もるのが重要だなと改めて思った.全探索で間に合うならそれで解けばよい.
貪欲法
表現が難しいんだがとり得る値ベースで全探索する方法が便利そうだなと思った, ABC 057 C - Digits in Multiplication でも同様の方法で解答されていたので競技プログラミングではよくやる書き方なのかなと思った.業務プログラミングだと全然やらない書き方だから意識して慣れないとあまり思いつかない.今回でいうととり得る値が[0,1000]なので for(ll i =0; i < 1000; i++) で回すみたいや感じのやつ,圧倒的に解答がシンプルになって良いので書けるようにしたい.
動的計画法
入力例1
4 0224
dp[i][j][k]としてiを現在の文字列の位置,jを選択した文字長,kを構築した値として初期値dp[0][0][0]=trueとする. 例えばi=2,j=1,k=2のとき次の番号を選択するときdp[2][2][2*10+2]=true,選択しない時dp[2][1][2]=trueと分岐する. 桁数[0,3],暗証番号候補[0,999]について網羅的にこれを繰り返し暗証番号が作れるかどうかを記録する.
最終的に求めたいのは暗証番号3桁で文字列を最後尾まで探索したときの要素なのでdp[N][3][k]について判定を行う.
所感
DP汎用性高いから積極的に使っていきたいが今回のような解法は思いつかない...
緑問題を難なく解けるようになるには計算量の見積もりを正確にして解法はそこから逆算する感じが良い気がする,あとは全探索でもシンプルに書けるならそっちのほうが良くてコードがシンプルであればエッジケースにも気づきやすいと思った.思考の順番としてまずは全探索を考えてそれが無理になら計算量を減らす方法を考えるのようにする.
