金魚亭日常

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

競技プログラミング

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 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

Codeforces #417 Div2

Newbie まで落ちました. Codeforces #417 Div2

AtCoder AGC #015

A,B は解けた. Aは,コーナーケースに気をつけて書く. Bは,実はすべての移動で1回か2回で移動できる,ということに気づけば解ける. AtCoder AGC #015 Cは解説と他の人のコードを見て書いて見たがTLEだったので,それをさらにC++に. AtCoder AGC #015 C…

AtCoder ABC #062

Bまで解けた. Cは,2つ目と3つ目の分割の仕方が2方向あることを見落としていた. AtCoder ABC #062 (2017-05-21 12:25) D は Priority Queue を使うらしいので,Python で. AtCoder ABC #062 (D, python)

AtCoder ABC #061

Cまで解けた. AtCoder ABC #061

Codeforces Round #414 Div1 and Div2

B問題,相似ということを利用して解くと思うのだけど,時間が足りなかった. Codeforces,最近また出場し始めたけど,出るたびにレイティングが下がって行って厳しい. Codeforces Round #414 Div1 and Div2

Codeforces #412 Div2

Codeforces #412 Div2

AtCoder AGC #014

A問題 最初に奇数が含まれていたら 0 すべて偶数かつ同じ数字なら -1 それ以外は,愚直にシミュレーション とする. が,勘違いしていて,最初に奇数が含まれていたら -1 としていて通らなかったので, 229 < 109 < 230 なので, 30回繰り返して終わらなかっ…

AtCoder ABC #060

B問題,小難しく考えてしまったが,B倍まで試せばよいらしい. AtCoder ABC #060

Codeforces #410 Div2

Bは解けたと思ったら間違っていたのでやり直し. Codeforces #410 Div2

AtCoder ABC #057

Cは難しく考えすぎて失敗 AtCoder ABC #057 Ruby

AtCoder ABC #056

C問題,どの範囲に入るかを出せるはずだけど,うまく書けなかったので,順番に足していっても時間的に間に合うだろうということで愚直な方法にした. D問題は,問題の意味がよくわからなかった. AtCoder ABC #056 Ruby

AtCoder ABC #054

A, B, C は解けた. C,とっさにどう書いていいのかわからなくなってめちゃくちゃ時間がかかってしまった. グラフに対して苦手意識がある. AtCoder ABC #054 Ruby

AtCoder AGC #010 [Ruby]

ABC は結構解けるようになって来たけど,AGCはやはり厳しい. AtCoder AGC #010 Ruby

AtCoder ABC #053 [Ruby]

AtCoder ABC #053 Ruby

AtCoder AGC #009

A問題, Bが1 Aが0 の場合,Aは必ずBの倍数になる. 特に,「0は全ての倍数」 というのに気づかなくて,かなり手間取った. AtCoder AGC #009

AtCoder ABC #052 [Ruby]

C問題,素因数分解しないといけないやつだけど,Ruby なので require 'prime' x = Prime.prime_division(i) とすると,i を素因数分解した結果の が [[n_1, e_1], [n_2, e_2]...] という形で x に入る. AtCoder ABC #052 Ruby

AtCoder ABC #051

AtCoder ABC #051 Ruby

AtCoder ABC #049

なんか投げやりなコードになってしまった. AtCoder ABC #049 Ruby

AtCoder ABC #030 A. 勝率計算 [C++]

AtCoder ABC #030 A. 勝率計算 C++

AtCoder ABC #031 A. ゲーム [C++]

AtCoder ABC #031 A. ゲーム C++

AtCoder ABC #032 A. 高橋君と青木君の好きな数 [C++]

AtCoder ABC #032 A. 高橋君と青木君の好きな数 C++

AtCoder ABC #033 A. 暗証番号 [C++]

AtCoder ABC #033 A. 暗証番号 C++

AtCoder ABC #034 A. テスト [C++]

AtCoder ABC #034 A. テスト C++

AtCoder ABC #035 A. テレビ [C++]

AtCoder ABC #035 A. テレビ C++

AtCoder ABC #036 A. お茶 [C++]

AtCoder ABC #036 A. お茶 C++

AtCoder ABC #037 A. 饅頭 [C++]

AtCoder ABC #037 A. 饅頭

AtCoder ABC #038 A. お茶 [C++]

AtCoder ABC #038 A C++

AtCoder ABC #039 A. 高橋直体

AtCoder ABC #039 A C++

AtCoder ABC #040 A. 赤赤赤赤青 [C++]

AtCoder ABC #040 A C++

AtCoder ABC #041 A. 添字 [C++]

AtCoder ABC #041 A C++

AtCoder ABC #042 A. 和風いろはちゃんイージー / Iroha and Haiku (ABC Edition) [C++]

min, max (algorithm) min({a, b, c}): g++ -std=c++11 AtCoder ABC #042 A C++

AtCoder AGC #007

A はいろいろ複雑に考えてしまっていたけど,解説見ると最短経路かどうかを答えるだけだった. というか, # を数えたら終わり. B はよくわからず. 解説聞くと,なるほどそうやってつくるのか,という感想. レイティングは下がって,1054. A問題,電車に…

AtCoder ABC #043 A. キャンディーとN人の子供イージー / Children and Candies (ABC Edit) [C++]

AtCoder ABC #043 A C++