金魚亭日常

読書,ガジェット,競技プログラミング

AtCoder ABC #077

1185 -> 1172 C 二分探索するところまでは思いついたが,その後難しく考えすぎて解けなかった. B より大きいCの個数は毎回求めてたらTLEしたので,前計算する. AtCoder ABC #077

AtCoder ABC #076 D - AtCoder Express

AtCoder ABC #076 D - AtCoder Express

2017年10月に読んだ本

今月は Wシリーズ新刊, 数学ガール 積分 食戟のソーマ を読んだ. 食戟のソーマ読むと,焼きたてジャぱん を読みたくなる. ◇ what_alnkのバインダー期間 : 2017年10月読了数 : 22 冊ペガサスの解は虚栄か? Did Pegasus Answer the Vanity? (講談社タイガ…

RubyInstaller2 をビルドする

環境 OS: Windows 10 Pro Version 1709 Build 16299.19 MSYS2 Ruby2.4(RubyInstaller2, ruby 2.4.2p198 (2017-09-14 revision 59899) [x64-mingw32]) 普通にビルドする Ruby Installer 2 bundler 使うので入れる gem install bundler README にある通りに…

AtCoder ABC #076

Rating は変動なしで 1185 A 式変形して を出力 B 両方の操作の結果を毎回比べて小さい方を取る. C 左から順番に文字列 を走査していって, と一致させることができる部分が見つかったら,その部分を で置換したものを配列に入れる. 終わったらソートして…

Code Festival 2017 予選 C

CODE FESTIVAL 2017 qual C - CODE FESTIVAL 2017 qual C | AtCoder A 文字列を2個ずつ処理. 今回は Array にして each_cons() を使った. B 差が1以下なので,とれる範囲は元の数字とその前後の3通り. 一つでも偶数のものがあればいいので,全通りの から…

AtCoder ARC #049 B - 高橋ノルム君

B: 高橋ノルム君 - AtCoder Regular Contest 049 | AtCoder コストを固定して,二分探索. 何回するかがパッと思いつかないが, ぐらいなら 回ぐらいで十分らしい. AtCoder ARC #049 B - 高橋ノルム君

AtCoder ARC #047 B - 同一円周上

B: 同一円周上 - AtCoder Regular Contest 047 | AtCoder マンハッタン距離 => 45度回す AtCoder ARC #047 B - 同一円周上

AtCoder ARC 046 B - 石取り大作戦

B: 石取り大作戦 - AtCoder Regular Contest 046 | AtCoder AtCoder ARC 046 B - 石取り大作戦

AtCoder ARC #043 B - 最短路問題

B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder 距離が同じもの同士は,ペアの選び方が なので, 通り 距離 から は ,距離 のそれぞれから 距離 のそれぞれについてつなぐ・つながない 二通りあって,全部つながないというのを除くので, 距離 が …

AtCoder ARC #043 B - 難易度

累積和 1回 にしたつもりが になっていて,TLEになった. AtCoder ARC #043 B - 難易度

AtCoder ARC #042 B - アリの高橋くん

頂点の座標が の三角形の面積 は (サラスの公式) なので,点を原点まで平行移動した後,面積を求めて, を底辺の長さで割ると辺までの距離が出る. AtCoder ARC #042 B - アリの高橋くん

AtCoder ARC #041 B - アメーバ

端の列を除いて,4近傍の最小値を取っていく. 値が決まったら,元の4近傍から値を引いておく. 解説は,上から順番に決めていく方式だった. AtCoder ARC #041 B - アメーバ

AtCoder ABC #075 D - Axis-Parallel Rectangle

最初,ユークリッド距離で近い順にK点選んで長方形を作る,ってやっていたけど,だめだった. x座標とy座標それぞれソートしてから長方形を全部作り,K点以上含まれるかどうか判定する. で,Ruby で書くとTLEだったので Rust. AtCoder ABC #075 D - Axis-P…

AtCoder ARC #040 B - 直線塗り

B: 直線塗り - AtCoder Regular Contest 040 | AtCoder 再帰でやると思ったが違っていた. AtCoder ARC #040 B - 直線塗り

AtCoder ABC #075

Rating 変動なし A 場合分け B 爆弾の8近傍をプラス1していく C 取り除く辺を決めて,Union Findして連結判定する AtCoder ABC #075

AtCoder ARC #039 B - 高橋幼稚園

出来るだけ個数が均等に配る方が良い. アメの個数が足りているときは,x を 余り x = K % N として 足りてないときは, (重複組み合わせ) を出力. AtCoder ARC #039 B - 高橋幼稚園

AtCoder ARC #038 B - マス目と駒

B: マス目と駒 - AtCoder Regular Contest 038 | AtCoder メモ化全探索 こういうのは 最後の盤面の状態から決めて行くのがいいらしい. AtCoder ARC #038 B - マス目と駒

AtCoder ARC #037 B - バウムテスト

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder Union Find でそれぞれの木を求め,深さ優先探索で閉路を検出し,閉路のないものの個数を出力. AtCoder ARC #037 B - バウムテスト

AtCoder ARC #036 B - 山のデータ

B: 山のデータ - AtCoder Regular Contest 036 | AtCoder ピーク位置を求めて,左斜面と右斜面の和 + 1 をそれぞれのピークについて計算し,その最大値を出力. AtCoder ARC #036 B - 山のデータ

AtCoder ARC #035 B - アットコーダー王国のコンテスト事情

B: アットコーダー王国のコンテスト事情 - AtCoder Regular Contest 035 | AtCoder 解くのにかかる時間が小さい方から解いた方がペナルティは少ない. 何通りあるかは,それぞれの問題数の階乗の積. AtCoder ARC #035 B - アットコーダー王国のコンテスト事…

AtCoder ARC #032 B - 道路工事

B: 道路工事 - AtCoder Regular Contest 032 | AtCoder Union Find でグルーピングして グループの数を数えて グループ数 - 1 が答え AtCoder ARC #032 B - 道路工事

AtCoder ARC #031 B - 埋め立て

B: 埋め立て - AtCoder Regular Contest 031 | AtCoder 埋め立てる場所を全て試して,島の面積が総面積に等しくなったら YES 最後まで試して等しくなるところがなかったらNO AtCoder ARC #031 B - 埋め立て

AtCoder ARC #033 B - メタ構文変数

二つの文章中に出てくる文字の頻度についての Jaccard 係数 を求める. set を使う. AtCoder ARC #033 B - メタ構文変数

AtCoder ARC #030 B - ツリーグラフ

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder 再帰がうまく書けない 参考: http://arc030.contest.atcoder.jp/submissions/287007 AtCoder ARC #030 B - ツリーグラフ

Code Festival 2017 予選B C - 3 steps

C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder 二部グラフかどうかで答えが変わる(あまり理解できていない). 二部グラフの判定は,蟻本より. 普通にやると再帰が深すぎてREになるので, RUBY_THREAD_VM_STACK_SIZE をいじる. Code Festival 2017 …

Code Festival 2017 予選 B

B - Problem Set T,D 両方ソートして,T と等しい D を小さい方から順に選んで行く. 配列から順番に値を取り出していって,空になったら終了. 一度選ばれなかったD は二度と選ばれることがない. Code Festival 2017 予選 B

DDCC 2017 予選 D - 石

解説を見て実装 bit を使って数え上げていてなるほどと思った. DDCC 2017 予選 D - 石

AtCoder ARC #028 B - 特別賞

優先度付きキューを使う Python の heapq は 最小値を取り出す AtCoder ARC #028 B - 特別賞

DDCC 2017 予選

DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder C 2本しか入らないので,小さいものと大きいものをペアにすることを考える DDCC 2017 予選