arc079.contest.atcoder.jp 解き方 1回の操作で、数列の総和は-1される 操作回数は最低でも 回操作をすると、総和が0になるのでこれが操作回数の上限になる（多分） K回の操作後、条件を満たすかどうかは全体を+Kしたあと、K回どれかの要素を-N-1する操作と…

arc079.contest.atcoder.jp 解き方 Nは50に固定しておき、とりあえずN-1+K/NをN個並べる K%Nとかを使って数字を調整すれば構成できる ハマったところ 素直に構成できたが、自信を持てず時間を無駄にしたみたいなところがある github.com

arc079.contest.atcoder.jp 解き方 1から1回で行けるところ、Nに1回で行けるところを列挙し、重複があるかどうか調査 ハマったところ 順調に解けた気がする github.com

競技プログラミング ARC 079 結果 137th, 1305->1480 (パフォーマンス 2255) 望外の3完。Fも手も足も出ない感じではなかった。ただし、運が良かったんだろうなぁという感じはする。 実装 DeepCoder データセットを増やしながら学習 → 現在N=800万で回してい…

前回まで mhiroaki.hatenablog.com mhiroaki.hatenablog.com 学習 前回20万件で駄目だったので、データセットのサイズを増やしていく N=60万 N=100万 N=200万 N=200万で、学習時間は10時間強 (p2.xlargeインスタンス)だった。 今後 データセットのサイズを増…

agc018.contest.atcoder.jp 解き方 全競技を実施すると仮定して、そこから参加人数が多いものを消していく貪欲 ハマったところ 実施競技0から増やしていく貪欲がWAになったあと諦めた 逆からの貪欲くらいは試してみるべきだった github.com

agc018.contest.atcoder.jp 解き方 すべての数の最大公約数を求めて、その倍数かどうかで判定 ハマったところ gcdの実装再確認に時間をかけた gcdを求めれば良いことに確信を持つまでに時間がかかった。 github.com

競技プログラミング AGC018 結果 525th, 1269->1305 (パフォーマンス 1526) Aしか解けなかったし、Aも不完全な考察で出したが、レートは1300超えた。Bは解けてもおかしくはなかったなぁ、といった感じ。 実装 DeepCoder g2インスタンスでの学習の結果、デー…

前回: mhiroaki.hatenablog.com データセット生成の高速化 方法 入力の型(e.g., [Int], [List], [Int, List, List])ごとに別スレッドでdfsすることで高速化 入力の型が異なるプログラム同士はequivalenceの判定を省いているので、データ競合なく並列化が可能…

arc078.contest.atcoder.jp 解き方 1から｀N`へのパス上をまず塗り、その後残りを塗るのが最適解 1とNからの距離でそのマスが黒か白か決まる 1とNの2箇所から幅優先探索して、黒白それぞれの塗られる数を探索 ハマったところ Nヶ所から幅優先探索する方法を…

arc078.contest.atcoder.jp 解き方 カードに書かれている数字の和を求めるのはO(n) 上から1枚取る場合、2枚取る場合、と順々にxとyを求めるのは、それぞれO(1)でできる 全部計算してminを求める ハマったところ xをi32で宣言していてオーバーフロー 定数項を…

競技プログラミング ARC 078 結果: 624th, 1280 -> 1269 (パフォーマンス: 1224) 初のレートマイナス．C問題を1回ミス（オーバーフロー見逃し）が直接的な要因．ただ，より根本的にはDを思いつかなかった事の方が問題． アルゴリズムはやはり要勉強． 実装 …

agc017.contest.atcoder.jp 解き方 一つ前のマスより小さくなるマスの数を固定して，その条件のもと達成できるか判定，これをN回繰り返す ハマった所 どれかの値を固定することで高速に判定し，それをn回繰り返す，って発想が出づらい

競技プログラミング ARC 077 (D) コンテスト中に解けなかったので復習． 10^9+7でmodをとる系統の問題への知識不足がある程度あったし，組み合わせを高速に計算できなかったのも知識不足が主因かなぁ． n!をメモ化する方法は確かに思い付けなくもなさそうだ…

arc077.contest.atcoder.jp 解き方 重複を考えずに組み合わせを計算し，重複分を引く 条件より重複は必ず1個存在する 組み合わせの計算は，n!を事前に計算しておく事でO(1)で行う n!^{-1}もmodを取る場合は前計算できる ハマった所 組み合わせ計算の高速化方…

arc077.contest.atcoder.jp 解き方 自分の解法 偶奇で場合分けし，前半分と後ろ半分をそれぞれ表示 想定解 dequeあたりを使って，前後から要素を挿入→最後に表示 ハマった所 特に無かったと思う

DeepCoder概略 [(Input, Output)] => Map[関数, 出現確率]の関数をディープラーニングで学習し，それを利用してプログラム空間を探索・プログラム合成をする． 詳しくは論文． 追実装について レポジトリ: ここ データセットの生成 深さ優先探索でプログラム…

チュートリアルを一通りやった上で，追加でハマったことのメモ Datasetの作成方法 以下のように，DatasetMixinを使って作る．データの生成（ファイル読み込みなど）をget_exampleまで遅延させるのもOK class Dataset(chainer.dataset.DatasetMixin): def __i…

競技プログラミング AOJ 0588 蟻本で練習問題に上げられていたので取り組んだ． 幅優先探索の実装練習． ARC 077 結果: 425th, 1198->1268 (パフォーマンス: 1614) Cは順調に解けた． Dは組み合わせを高速に計算する方法を思いつけなかった．あと10^9+7のmod…