金魚亭日常

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

競技プログラミング

天下一プログラマーコンテスト2017

Beginner の方に出て A, B, C 解けて 69位 Rating は 1157 -> 1210 B 順位でソートして,最下位の順位 + 最下位の得点 を出力 C N が偶数の場合は なので,N, N, N/2 を出力 Nが奇数の場合は, だから, が偶数にならないといけなくて,それはn と h のどち…

CSAcademy #050 D. Min Races

増加数列の組に分ける,ってとこまではわかるんだけど,その個数が最長減少数列の長さに等しい,というのがわからない. Segment Tree 使うのはこういうところで使うんだ,と思った. とにかく,解説を写経. CSAcademy #050 D. Min Races

CS Academy Round #50

初出場. レイティングは 1500 スタートらしく, 1500 -> 1457 問題セットは, 100 - 100 - 100 - 400 - 700 で,100 の3つは解けた. 解説がすぐに出るのがよいと思った. CSAcademy Round #50

TopCoder SRM #721 Div2; Small. FlightDataRecorder

普通にシミュレーション そういえばSRM ってPython 2系だったっけ TopCoder SRM #721 Div2; Small. FlightDataRecorder 久々に出場しようとしたが,High Sierra のアップデートに失敗してMacが死んでいたので出られなかった.

AtCoder ABC #024 C. 民族大移動

貪欲法 グラフかと思ったけど,図を書いてみると直線でいけるらしいとわかった. AtCoder ABC #024 C. 民族大移動

AtCoder ABC #025; C. 双子と○×ゲーム

ゲーム木の探索 メモ化しないと TLE になった memo の key を作るのを,join() から pack() に変えて,min() max() を if にしたら 80ms ぐらい速くなった. AtCoder ABC #025; C. 双子と○×ゲーム

Google Code Jam Kickstart 2017 Round F; D. Eat Cake

面積Nをいくつかの正方形で表すとき,必要な最小個数を求める dp する. 最大になるのは,1ばっかりで作るときで,そこから 面積x の正方形を使うか使わないか で決めていく.

Google Code Jam Kickstart 2017 Round F

A の small と large だけ解けた A. Kicksort クイックソートの亜種が与えられて,ピボットの選び方が最悪ケースになるかどうかを判定. 最悪な選び方というのは,最大もしくは最小を選ぶ場合なので,それをシミュレーションする. 制限時間12時間あったので…

AtCoder ABC #027 C 倍々ゲーム

を左, を右としてシミュレートして二分木を作ると,深さの偶奇によって,それぞれのプレーヤーの最適な戦略は常に左もしくは常に右となる AtCoder ABC #027 C 倍々ゲーム

Code Festival 2017 Qual A C: Palindromic Matrix

解説見て解いたら通らなくて,色々見てると,4個の組みは考慮しなくてもいいらしい,となった. 4個の組みは2個の組みに分解できるから,みたいなことだろうか. Code Festival 2017 Qual A C: Palindromic Matrix

Code Festival 2017 Qual A

A, B の2問解いて 1024位でした. Rating: 1161 -> 1157 あんまり下がっていなかったので,難しかったのではないだろうか. 行列ばっかり出てきて辛かった. B 全部試せるなー,と思って考えてたらできた. C,D ぐらいまでは復習しよう. Code Festival 201…

AtCoder ABC #070 D Transit Tree Path

再帰で書くとREになって,stack level too deep (SystemStackError) らしいので,ループで書く. AtCoder ABC #070 D

AtCoder ARC #083 / ABC #074 D Restoring Road Network

AtCoder ABC #074 / ARC #083

AtCoder ARC #083 / ABC #074

A, B, C 1112 -> 1161 C 全探索するのだけど,普通にやると間に合わないので,stepを適切に求めてからする. D Restoring Road Network まず,全点対最短経路であるとしてワーシャルフロイドを試し,最短ではなかったら -1 . そのあと,寄り道した場合と直…

AtCoder ABC #073

A, B, C 1147 -> 1112 D はワーシャルフロイドで全ての町の間の距離を求めて,訪れる町の順列をすべて試す. AtCoder ABC #073

AtCoder ABC #070 C Multiple Clocks

AtCoder ABC #070 C

AtCoder ARC #080 E Young Maids [Rust]

勉強のために Rust にも移植. 150 ms. 慣れていなくて全然コンパイルが通らないんだけど,エラーメッセージに従ってなおして行くと通るようになって楽しい,みたいな感じになってくる. ここは mut でしょ,って書いてたら mut じゃなくてよくね,って言わ…

AtCoder ARC #080 E Young Maids

Python で解いてTLEだったので,Go に移植. 最初,通ったものの1600 ms とぶっちぎりで遅かったので, qiita.com を見てプロファイリングしてみたら,どうやら読むとこと書くとこが遅いっぽかったので, 最後に書き出すところを strings.Join() してから fm…

AtCoder ARC #080 / ABC #069

C問題にはまってしまって,時間がかかりすぎた. Dは簡単だったので,先に解けばよかった. 1201 -> 1183 C 2を0,1,2個含むものに分けて数える. 解説見ると,難しく考えていたみたいだ. D 順番に出力すれば終わり. 端に行ったら折り返す. 「うなぎ」っ…

Rust で競プロ: 標準入力読み込み

まだ何がベストかわからないのだけど,とりあえず現状は, N M みたいに整数のペアが空白区切りで与えられた場合, use std::io; use std::str::FromStr; fn main() { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).ok(…

AtCoder ABC #068 / ARC #079

C問題 1から出てる船 と Nに向かう船 を別々に配列に保存しておいて, Nに向かう船それぞれの始点について,1から出てる船の終点と一致するものがあれば “POSSIBLE",なければ"IMPOSSIBLE” D問題,E問題 DとEはセット. Dは解説放送見てEditorial読んだら解…

AtCoder Chokudai Speed Run #001

AtCoder の新しいウェブサイトのテストとして開催されたコンテスト. 12問 速解き. A 最大値 数列の最大値を出力 max() B 和 数列の和を出力 sum() C カンマ区切り 数列をカンマ区切りで出力 join() D ソート 数列をソートして半角スペース区切りで出力 sor…

AtCoder ABC #067 / ARC #078

AtCoder ABC #067 / ARC #078

AtCoder AGC #017

Aしかとけず. A問題,頑張ってCombinationで解いたんだけど,解説読むとCombination使わないらしくて,失敗. 通ったからいいが,結構時間かかった. AtCoder AGC #017

AtCoder ABC #066

Cまで解けた. D の二項係数の計算の部分は, http://hos.ac/slides/20130319_enumeration.pdf を見た. AtCoder ABC #066

AtCoder ARC #075 / ABC #065

ARC に出て,Cしか解けず. Dは,最小全域木の問題. 最小全域木を実装するには,プリム法とクラスカル法があって,解答を見るとみんなクラスカル法みたいだったのでそちらを使ってみた. クラスカル法は,UnionFind木を使う. 実装は,アリ本より. 次回か…

AtCoder AGC #016

Aしか解けず AtCoder AGC #016

Google Code Jam Kickstart 2017 Practice Round 2

先日は過去問をやったが,ちょうど練習回があったので参加して見た. これは,本番形式で過去問を解く,というものらしい. 出典は, A: APAC Test 2017 Round E Problem A B: APAC Test 2017 Round C Problem B C: APAC Test 2017 Round E Problem B D: APA…

Google Code Jam Kickstart 2017 Round B

Google Code Jam の学生を対象としたやつ? 就職につながる感じなんだろうか. 年中いつでも登録できて,数か月おきにコンテストが開催されるらしい. とりあえず,過去問を解いてみた ちなみに,AtCoder などのようにソースコードを提出するのではなく,解答…

AtCoder ABC #064

A,Bは解けた Cは,なんで通らなかったか解明できていないけど,解説放送見て書いたら通った. 最初は色数の上限が8だと思ってたけど,違うらしい. 質問タブで複数人質問している人がいて,見ればよかった. Dは有名問題らしい. AtCoder ABC #064