競プロ参戦記

2018年9月30日 01:30

競プロ参戦記第16回「偶奇と多節腕」 ARC 103 [CD]

恒例のARCに参加して、今回もC完でした。

前回も「恒例の」と書いていたので1週間練習してなかったことになります。なるほど……

AtCoder Regular Contest 103 問題リスト：

C - /\/\/\/問題概要：数列 A が与えられる。K 個の要素を変更した。このとき偶数番目の要素 A[2n] はすべて等しい。奇数番目の要素 A[2n + 1] もすべて等しい。しかし A

もっとみる

令掛ベイン

2018年9月24日 17:33

競プロ参戦記第15回「交換と組合せ」 ABC 110

競技プログラミングの大会が毎週開催されるより幸福なことがあるだろうか？ 2日連続で開催されることだ！

昨日の CODE FESTIVAL 予選に続き、日曜日は通常の ABC-only 回です。結果は惨敗 (Bのみ正答) でしたが、まるで完全に理解したかのように解説を書いていきます。

AtCoder Beginner Contest 110問題リスト：

A - Maximize the For

もっとみる

令掛ベイン

2018年9月22日 23:57

競プロ参戦記第14回「上限」 "CODE FESTIVAL 2018 qual A" [ABC]

毎年恒例、競技プログラミングの祭典 CODE FESTIVAL の予選に参加しました。

CODE FESTIVAL は今年で5年目となるリクルート主催のコンテスト。成績優秀な若者は希望すれば「本戦」に出場できて、みんなで大会の会場に集まって競プロができる、らしいです。

とはいえ私は出場資格がないので、いつもの AtCoder Beginner Contest と同じ気持ちでやっていきます。

もっとみる

令掛ベイン

2018年9月15日 23:59

競プロ参戦記第12回「地道な考察」 AGC 27 [AB]

競技プログラミングの大会 AtCoder Grand Contest に参加しました。ABC/ARC より難しい、世界レベルの大会らしいです。

私はA完でした。Bの部分点にかじりついていたんですが分からぬ……

AtCoder Grand Contest 027問題リスト：

A - Candy Distribution Again問題概要：人 i はちょうど a(i) 個のお菓子をもらうと喜ぶ

もっとみる

令掛ベイン

2018年9月13日 01:43

競プロ参戦記第11回「全列挙」エデュフォ50 [ABCD]

エデュフォに参戦(？)しました。C問題にひたすら時間を費やして一つも提出できず、結果的にはゼロ完です。

そういうわけで参戦記というより練習記です。Dまで解説を書いていきます。問題概要は翻訳ではなく、私が簡潔に再構成したものです。

Educational Codeforces Round #50問題リスト：

A. Function Height問題概要：(なんかめちゃくちゃ長い)

簡単に説明

もっとみる

令掛ベイン

2018年9月10日 00:31

競プロ参戦記第10回「転倒数」 Chokudai Speed Run 001 [J]

典型問題を解きました。自作ライブラリの検証もかねて。

Chokudai Speed Run 001J - 転倒数問題概要：バブルソートの交換回数を求めよ

考察バブルソートは有名なソートアルゴリズムです。Rust で書くとこう：

fn bubble_sort(xs: &mut [i64]) -> i64 { let n = xs.len(); let mut k = 0; f

もっとみる

令掛ベイン

2018年9月8日 22:55

競プロ参戦記第9回「コイン大移動」 ABC 109

毎週恒例 AtCoder の競技プログラミング大会に参加したので解説を書きます。今週は ABC-only 回です。

AtCoder Beginner Contest #109問題：

A - ABC333問題概要：正の整数 A, B が与えられる。A * B * C が奇数になるような正の整数 C はあるか？

A * B が偶数なら A * B * C は必ず偶数になるので答えはNo。逆に A

もっとみる

令掛ベイン

2018年9月6日 00:17

競プロ参戦記第8回「方眼紙」 Codeforces Round #506 F

過去問を解いたので解説します。

F. Multicolored Markers問題概要：整数 a, b (≤10^14) が与えられる。無限大の方眼紙の a マスを赤く、b マスを青く塗った。塗られた領域 R は長方形である。赤い領域か青い領域の少なくとも一方は長方形になっている。長方形 R の周長 (4辺の長さの和) の最小値を求めよ。

不要な対称性をなくすため、必ず赤い領域が長方形になるこ

もっとみる

令掛ベイン

2018年9月4日 22:25

競プロ参戦記第7回「近道」 Codeforces #506 E

過去問を解いたので解説します。

E. Tree with Small Distances問題概要：頂点数 N の無向グラフが与えられる。これはツリーである (連結、閉路なし)。いくつかの辺を追加して、点1から他の点への距離をすべて2以下にした。追加した辺の個数の最小値を求めよ。

(ループや多重辺について条件が設定されていますが、無視していいです。)

簡単に分かることを確認すると、追加する辺

もっとみる

令掛ベイン

2018年9月2日 00:34

競プロ参戦記第6回「ループ不変条件」 ARC 102 [CD]

AtCoderの競技プログラミングの大会に参加したので、C/D 問題のみ思考過程込みで解説をしていきます。

AtCoder Regular Contest #102問題一覧：

C - Triangular Relationship問題概要：整数 N, K が与えられる。a, b, c を N 以下の正の整数とする。 a + b, b + c, c + a がすべて K の倍数であるような (a

もっとみる

2018年9月の記事一覧