ARC079 E: Decrease (Judge ver.)

arc079.contest.atcoder.jp

解き方

• 1回の操作で、数列の総和は-1される
  • 操作回数は最低でも
  • 回操作をすると、総和が0になるのでこれが操作回数の上限になる（多分）
• K回の操作後、条件を満たすかどうかは全体を+Kしたあと、K回どれかの要素を-N-1する操作と考えればO(N)で判断可能
  • ARC075 Dと同じような考え方
• 最初に上げた値の範囲全部を調べていけばO(N^3)で判定できる

ハマったところ

• ARC075 Dと類似であることを認識するまでにまず時間がかかった気がする
• 二分探索を構築できないか迷った時間は結果的には無駄だった

github.com

ARC079 D: Decrease (Contestant ver.)

arc079.contest.atcoder.jp

解き方

• Nは50に固定しておき、とりあえずN-1+K/NをN個並べる
• K%Nとかを使って数字を調整すれば構成できる

ハマったところ

• 素直に構成できたが、自信を持てず時間を無駄にしたみたいなところがある

github.com

ARC079 C: Cat Snuke and a Voyage

arc079.contest.atcoder.jp

解き方

• 1から1回で行けるところ、Nに1回で行けるところを列挙し、重複があるかどうか調査

ハマったところ

• 順調に解けた気がする

github.com

活動記録(2017/7/24-2017/7/30)

競技プログラミング

ARC 079

結果 137th, 1305->1480 (パフォーマンス 2255)

望外の3完。Fも手も足も出ない感じではなかった。ただし、運が良かったんだろうなぁという感じはする。

実装

DeepCoder

• データセットを増やしながら学習 → 現在N=800万で回している
• 評価をどうするか決めた
  • 評価用のデータセットは作ったので、データセットでき次第投げる
  • 今のモデルでやって見る限り、微妙

その他

• デスクトップのメモリを64GBに換装

DeepCoder追実装記録 (3)

前回まで

mhiroaki.hatenablog.com mhiroaki.hatenablog.com

学習

前回20万件で駄目だったので、データセットのサイズを増やしていく

N=60万

N=100万

N=200万

N=200万で、学習時間は10時間強 (p2.xlargeインスタンス)だった。

今後

• データセットのサイズを増やす必要がまだありそうな気もする（400万~くらい）が、評価に移る
  • 趣味の追実装であることを考えるとこのくらいで良いかなという気分

AGC018 B: Sports Festival

agc018.contest.atcoder.jp

解き方

• 全競技を実施すると仮定して、そこから参加人数が多いものを消していく貪欲

ハマったところ

• 実施競技0から増やしていく貪欲がWAになったあと諦めた
  • 逆からの貪欲くらいは試してみるべきだった

github.com

AGC018 A: Getting Difference

agc018.contest.atcoder.jp

解き方

• すべての数の最大公約数を求めて、その倍数かどうかで判定

ハマったところ

• gcdの実装再確認に時間をかけた
• gcdを求めれば良いことに確信を持つまでに時間がかかった。

github.com