torus711 のアレ

主に競技プログラミングの問題について書きます

競技プログラミングを始めて人生が変わった話

はじめに

 (少なくともブログ上では)お久しぶりです.この記事は,Competitive Programming (その2) Advent Calendar 2016 - Adventar の 14 日目の記事です.
 いわゆる思い出ポエムが流行って(?)いて,わたしも楽しく読ませてもらっています.人々の昔話を読みながら昔のことを思い返してみたところ,競技プログラミングにハマる以前からは想像できないような未来に生きていることに気付いた(というか再認した)ので,わたしもちょっくら書き残してみようかな,と思いました.丁度枠が残り一つだったのと,「何か」を飲んでいたので,


といった具合で登録しました.
 話としては,「色々あったけど,わたしは現状に割と満足しているので,紆余曲折あったけどこのルートに来れてよかったなァ」という感じです.

 全編に渡って自分語りをするわけですが,冷静に考えてしまうと小恥ずかしいので,今も「何か」を飲みながら書いています.「何か」の効力が切れる前に書き上げて投稿ボタンを押さねばなりません*1

*1:この部分を書いてから本文を書き始めたけど,全然間に合わなかったので結局 3 杯飲んだ

続きを読む

TopCoder SRM 684, Division 1, Level 1 : CliqueParty

問題概要

 正整数の集合が次の条件を満たすとき,k-smooth であるとする.

  • 任意の 2 要素 $A, B$ ($A \neq B$) について $A \leq kB$

 正整数の集合を表す配列 $a$ と正整数 $k$ が与えられる.条件

  • 部分集合の全ての 2 要素 $A, B$ ($A \neq B$) について,|A - B| からなる集合が k-smooth である

を満たす部分集合の内,最も要素数が多いものの要素数を求めよ.

  • $2 \leq |a| \leq 50$
  • $1 \leq a_i \leq 10^9$
  • $a_i \neq a_j$ ($i \neq j$)
  • $1 \leq k \leq 10^9$
続きを読む

GCDLCM2

問題概要

 正整数の配列が与えられる.この配列に対し,以下の操作を任意回行う.

  1. 2 つの要素 $x, y$ を選ぶ
  2. $x, y$ を削除する
  3. $\mathit{ GCD }( x, y ), \mathit{ LCM }( x, y )$ (それぞれ最大公約数と最小公倍数)を追加する

 配列の要素の和として達成できるものの最大数を $S$ として,$S \bmod{ 10^9+7 }$ を求めよ.

 入力となる配列は,生成のためのアルゴリズムとそれに与えるパラメータとして与えられる.完成した配列の要素数は $10^5$ 以下,各要素は $10^7$ 以下となる.

続きを読む

TopCoder SRM 681, Division 2, Level 2 : ExplodingRobots

問題概要

 平面上に二つのロボットを置く.一つは座標 $( x_1, y_1 )$ に,他方は $( x_1, y_1 )$ に置く.
 各ロボットは,$U, D, L, R$ からなる命令列 $\mathit{ instructions }$ を処理する.各命令は,いずれかの座標軸lに垂直な四方向へ距離 $1$ 移動することを表す(正確には問題文参照のこと).しかし,ロボットのプログラムにはバグがあり,命令列の任意の部分列を無視してしまう.これはそれぞれのロボットで独立に発生するので,二つのロボットの動きは異なりえる.
 二つのロボットが同じ座標に存在しようとすると,ロボットは爆発してしまう.
 命令列がどのように無視されても爆発しないならば "Safe" を,そうでないならば "Explosion" を返せ.

  • $-25 \leq x_1, y_1, x_2, y_2 \leq 25$
  • $( x_1, y_1 ) \neq ( x_2, y_2 )$
  • $| \mathit{ instructions } | \leq 50$
続きを読む

TopCoder SRM 681, Division 2, Level 1 : CoinFlipsDiv2

問題概要

 表裏を区別できる $N$ 枚のコインが一直線上に並んでいる.コインは左から右に $0$ から $N - 1$ で番号付けられている.コインの状態は長さ $N$ の配列 $\mathit{ state }$ で与えられる.$\mathit{ state }_i = H$ のとき,$i$ 番のコインが表を上にして置かれていて,$\mathit{ state }_i = T$ のとき,裏を上にして置かれている.
 各コインについて,異なる面を上にして置かれているコインと隣接しているとき,そのコインを interesting であるという.
 interesting なコインの枚数を求めよ.

  • $1 \leq N \leq 50$
続きを読む