活動記録(2017/7/10-7/16)

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

AGC017 B: Moderate Differences

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

活動記録(2017/7/3-7/9)

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

ARC 077 D: 11

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

ARC 077C: pushpush

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

DeepCoder追実装記録 (1)

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

chainer 2.0勉強記録

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

活動記録(2017/6/27-2017/7/2)

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

AOJ 0588: Cheese

チーズ | Aizu Online Judge 蟻本の練習問題に挙げられていたので練習 解き方 幅優先探索 N=9なので,Nそれぞれに対して幅優先探索しても,9*10^6程度のループ回数で済む ハマった所 最初,N=9を見逃して効率良い幅優先を考えていた コンテストだったらただ…

CHI2017勉強会 論文メモ

Camera-Based Tracking study.hci.one EagleSense: Tracking People and Devices in Interactive Spaces using Real-Time Top-View Depth-Sensing Chatbot Interfaces study.hci.one “Could You Define That in Bot Terms”?: Requesting, Creating and Using…

ARC 076 D: Built?

http://arc076.contest.atcoder.jp/tasks/arc076_b 解き方 コストの定義を使って,辺の数をO(N)に削減 最小全域木をクラスカルなりプリムなりで求める プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない ハマった所 プリム,クラスカルの…

ARC 076 C: Reconciled?

arc076.contest.atcoder.jp 解き方 abs(M-N)が2以上,1,0で場合分け. ハマった所 隣接してはいけないので,組み合わせ(nCr)はいらない テストケース通して気づいた M+1

活動記録(2017/6/20-6/26)

活動記録(6/20-6/26) 競技プログラミング ARC 076 結果: 405th, 1123->1198 (パフォーマンス: 1548) Cで場合分けのミス1回,Dはクラスカルのループ内を条件を使ってO(logN)に収めようとして苦戦. せめてCの実装ミスはなくしたい. 実装 DeepCoder実装 DeepC…