AOJ0525: おせんべい

おせんべい | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 どの行をひっくり返すかは、全部で2^R通りなので、これについてはすべて試すことができる。 ひっくり返す行を決めて、ひっくり返した後は、各列で裏と表のうち、多い方の数の…

AOJ0121: 7パズル

7 パズル | Aizu Online Judge 蟻本初級の練習問題にあったので解いた。 解き方 終了時点(綺麗に整列した状態)から幅優先探索を行い、各状態から終了状態までの最小回数を求める 状態の個数はたかだか8!個程度なので、この前計算は十分間に合う 各クエリに…

ABC070 D: Transit Tree Path

D - Transit Tree Path 解き方 aからKへの距離とKからbへの距離の和を出力する Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。 ハマったところ 0-indexと1-index混ぜてた 読み込み時に変えておくべきという話はありそう 最初全頂点から全頂…

ABC070 C: Multiple Clocks

C - Multiple Clocks 解き方 最小公倍数を求めるだけ。場合によってはオーバーフローに気をつけないといけないのかな。 github.com

ABC070 B: Two Switches

B - Two Switches 解き方 区間[A:B]と[C:D]の重複区間を求める。[max(A, C):min(B, D)]。 github.com

ABC070 A: Palindromic Number

A - Palindromic Number 解き方 先頭から確認するだけ github.com

活動記録(2017/8/7-8/13)

競技プログラミング ARC 80 結果 204th, レート変更なし 順当に全完できた。 Dでなんか複雑に考えすぎて時間かけてしまった。あと、AtCoderのサイトが変わったことによるテストケース手動取得は時間削減の意味では対処しないといけない。 マイクロマウス PiC…

ARC080 E: Young Maids

arc080.contest.atcoder.jp 解き方 辞書順なので、先頭から埋める 最初の数列で、奇数番目が解答の先頭に、偶数番目が解答の2番目にくる 奇数番目の最小の数字が先頭に、それより後ろで最小の偶数番目が2番目にくる 3つの領域に分割されるので、それらについ…

ARC080 D: Grid Coloring

arc080.contest.atcoder.jp 解き方 左端あたりからジグザグに指定個数ずつ埋めていく ハマったところ WをNと書き間違えた github.com

ARC080 C: 4-adjacent

arc080.contest.atcoder.jp 解き方 すべての数字を4で割った余りに変えても同じ 2は全部連続させて良い(分けることでうまく行くパターンが増えることはない) 2の連続、1のとなりには0が来ないといけない(2...2, 0, 1, 0, 1, ...., 1, 0, 1など)ので、そ…

活動記録(2017/7/31-2017/8/6)

競技プログラミング ARC80 結果: 613rd, 1480->1449 (Perf:1225) 前回が良すぎたのでレート落ちは想定内。前回と合わせて800点問題に手が出るようになってきたように感じられるのもモチベーション向上にはつながった。 ただ、CとDで4回とか実装ミスWA・REさ…

ARC079 F: Namori Grundy

arc079.contest.atcoder.jp 解き方 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ 閉路とそれ以外にまず分ける 閉路以外の部分は、根を0、その上を…としていくと一意に定まる 閉路については、適当に1頂点にxを割り当てて、うまくいくか計算…

DeepCoder 追実装まとめ

概略 [(Input, Output)] => Map[関数, 出現確率]の関数をディープラーニングで学習し,それを利用してプログラム空間を探索・プログラム合成をする. 詳しくは論文. 実装 レポジトリ chainerに慣れていないため、諸々非効率的と思うが、実装自体はそこまで…

DeepCoder追実装記録 (4)

前回まで mhiroaki.hatenablog.com mhiroaki.hatenablog.com mhiroaki.hatenablog.com 学習 思い立って800万件で学習する。学習の様子は以下のような感じ。 この時、p2.xlargeのCPUメモリが足りなくなって強制終了されていた。 今回はg3.4xlargeを使って対処…

ARC079 E: Decrease (Judge ver.)

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

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万で回してい…

DeepCoder追実装記録 (3)

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

AGC018 B: Sports Festival

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

AGC018 A: Getting Difference

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

活動記録(2017/7/17-7/23)

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

DeepCoder追実装記録 (2)

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

ARC078 D: Fennec VS. Snuke

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

ARC078 C: Splitting Pile

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

活動記録(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…