マガジンのカバー画像

競プロ参戦記

32
競技プログラミングの問題を解いて考察を書いていく日記
運営しているクリエイター

2018年10月の記事一覧

競プロ参戦記 第20回 「差と交差」 天下一2018 [CD]

競プロ参戦記 第20回 「差と交差」 天下一2018 [CD]

久しぶりですが、プログラミングコンテストに参加しました。解けた問題だけ考察を書いていきます。

天下一プログラマーコンテスト 2018概要
「天下一プログラマーコンテスト」はガチンコの競技プログラミングコンテストです。今年もジャッジシステムや問題の作成・監修にAtCoder社が全面協力。
最強最速アルゴリズマーは誰だ!?

私はD完でした。

C - Align問題概要:数列を適当に並べ替えて、隣

もっとみる
競プロ参戦記 第19回「ピラミッドと公約数」 ABC 112

競プロ参戦記 第19回「ピラミッドと公約数」 ABC 112

土曜21時は AtCoder! ABC-only 回に参加したので解説を書いていきます。私はC完でした。

AtCoder Beginner Contest 112問題リスト:

A - Programming Education問題概要:N=1 なら Hello World を出力せよ。N=2 なら A+B を出力せよ。

解説:最初に1行目を読み込んでから条件分岐し、N=2 のときだけ2~3行

もっとみる
競プロ参戦記 第18回「出目の和」 ARC 102 [E]

競プロ参戦記 第18回「出目の和」 ARC 102 [E]

練習記です。解説AC上等で700点問題をやっていく週間。

E - Stop. Otherwise...問題概要:互いに区別されないK面サイコロをN個振ったとき、「どの2つのサイコロの出目の和も t でない」場合の数を 2≤t≤2K の範囲ですべて求めよ。(素数 998244353 で割った余りで答える。)

解説:t は全列挙すればいいので、定数として扱います。

基本事項ですが「互いに区別され

もっとみる
競プロ参戦記 第17回「Tr/ee」 ARC 103 [E]

競プロ参戦記 第17回「Tr/ee」 ARC 103 [E]

練習で700点問題を解きました。

構成問題によくある「図を見ればすぐわかる」タイプなので、解説より考察がメインです。

E - Tr/ee問題概要:長さ N のビット列 S が与えられる。次の条件を満たすN頂点のツリーが存在するか判定し、存在するなら一例を示せ。

S[k] = 1 ⇔ ツリーの辺を1つ削除して頂点数 k の連結成分を得られる

*---*-/-*---* | *

もっとみる