agc019.contest.atcoder.jp 解き方 A[i] == A[j]を満たすA[i..j]を反転させる時、A[i+1..j-1]を反転させた時と同じになるので、それを引く ハマったところ 最初回文を除かないといけないと考え、実装はしたもののO(N^2)から落ちなかった 回文を除く方針は、…

agc019.contest.atcoder.jp 解き方 ただの貪欲 ハマったところ なんか貪欲法の実装に手間取ってしまった記憶がある https://github.com/HiroakiMikami/procon-workspace/blob/master/src/atcoder/agc019/a.ccgithub.com

競技プログラミング AGC019 結果: 735th, 1470->1475 (Perf: 1523) AとBを見間違えたり、Bを回文を数え上げる問題と思って苦しんだりしつつ、どうにか2完。自分の実力的にはこの辺が妥当そう。 その他 ハンダ付けのために必要と思しき道具を追加購入 BitCoin…

E - Don't Be a Subsequence 解き方 部分列でない最小の文字列の、先頭の文字を決める→2文字目以降の文字列について考える、を繰り返すDP DPする時には、後ろから決めていかないといけない どの文字を先頭にするか決めるために、どの文字がどこに現れるかに…

D - Coloring Dominoes 解き方 左から順々に見ていく。直前のタイルの貼り方と、次のタイルの貼り方は2*2の4パターンなので、それぞれ場合分けしながら計算する ハマったところ 上下に見ようとしたり、DFSしようとしたり、迷走していた 高さ2と小さいのだか…

C - Make a Rectangle 解き方 2個以上存在する数字を大きい方から2つ選んで長方形を作る ハマったところ 正方形のケース（同じ数字が2回登場する）を忘れていた github.com

競技プログラミング ARC081 結果: 446th, 1449 -> 1470 (perf 1614) Cの凡ミスと、Dで無意味に時間を書けたのはもったいなかったなぁ。E、Fは手が出る感じなかったし、今の自分の実力はこんなものなのだろう。 AOJ0121, AOJ0525 蟻本の練習問題 paiza 暇だっ…

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

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

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

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

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

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

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

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

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

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

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

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

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

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