はじめに ちょうどいいタイミングなので振り返りの記事を書きます。過去の同じような記事は以下 レーティング 半年前とのhighest比較がこちら AtCoder: 1919 -> 2177 Codeforces: 1952 -> 2064 Topcoder: 1428 -> 1549 AtCoderは8月あたり、Topcoderはつい先…

問題概要 整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。 0 <= n < 250 k <= 50 解法 1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、…

問題概要 N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる…

https://yukicoder.me/problems/no/109 問題概要 T個の数の組(N, M)が与えられるので、それぞれでN! mod Mを求めよ 1 <= T <= 100 1 <= M <= 109 max(0,M−105) <= N <= 109 解法 まず自明なケースとして、NがM以上の場合答えは0である(N!で掛ける数の中に必…

https://yukicoder.me/problems/no/387 問題概要 Nマスが横に連なったハンコがあり、マスiには色Aiのインクがついている。(2N-1)マスの紙に対し、はじめこのハンコを左端が合うように置き、「ハンコを押すor押さない」→「ハンコを右に1マスずらす」という操…

問題概要 Titanic: Machine Learning from Disaster Kaggleの入門用として位置づけられているコンテスト？で、タイタニック号に乗っていた客のデータ（名前、年齢、客室の等級etc）が与えられるのでその生死を予測してくださいねというもの。実際の正解まで…

https://yukicoder.me/problems/no/511 問題概要 無限行W列のグリッドで、2人ゲームが行われる。このゲームでは2人交互に長方形のブロックを上から落とし、ブロックの各列は一番下か他のブロックにつくまで落下を続ける。ブロックを落とすことである列の高さ…

http://agc002.contest.atcoder.jp/tasks/agc002_d 問題概要 N頂点M辺の無向グラフがあり、頂点には1～N, 辺には1～Mの番号がついている。またQ個のクエリがあり、ひとつのクエリでは2つの頂点番号x, yと整数zが与えられる。各クエリごとに、x, yの2つを出発…

http://tdpc.contest.atcoder.jp/tasks/tdpc_house 問題概要 H階建ての家があり、各階には部屋が1番～R番までのR個存在する。部屋間を以下のルールに従って移動するとき、H階の部屋1から1階の部屋1に移動する経路は何通りあるか。ルール1. h階の部屋rから(h-…

http://arc084.contest.atcoder.jp/tasks/arc084_b 問題概要 正整数Kのある正の倍数を10進法で表したときの各桁の和の最小値を求めよ。 2 <= K <= 105 解法 以下のようなグラフを考え、最短経路問題を解く。 頂点は0～(K-1)のK個 頂点x → 頂点(x+1)%K にコス…

11/3に行われた「DISCO presents ディスカバリーチャンネル コードコンテスト2017」(DDCC2017)の本戦に参加しました。新卒枠100人＋それ以外100人という非常に大規模なオンサイトコンテストで、枠の大きさに助けられて本戦に行くことができました。社会人に…

問題概要 開き括弧と閉じ括弧のみからなる文字列Sが与えられる。初めSの括弧は正しく対応している。Sの一番前にある開き括弧と任意の閉じ括弧のペアを括弧の対応が不正にならないよう取り除く、という操作をSが空になるまで繰り返すとき、括弧の選び方の順番…

問題概要 初期値0の変数Xがある。+1と-1が並んだ命令列が与えられ、前から順番にその命令をXに適用するか無視するかを自由に選択できる。この過程において作れるXの最大値と最小値の差の最大値を求めよ。 解法 +と-の数を数えて大きい方を取る 感想 問題概要…

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_c 問題概要 英小文字のみからなる2つの文字列のペア(Ai, Bi)がN個与えられる。ここで26個のアルファベットの順番を並べ替え、AiがBiより辞書順で小さくなるようにしたい。そのような並…

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_d 問題概要 H行W列のグリッドを4色で塗り分ける。このときマンハッタン距離がちょうどdのグリッド同士は別の色で塗らなければならない。条件を満たす塗り方をひとつ示せ…

http://agc014.contest.atcoder.jp/tasks/agc014_d 問題概要 N頂点の木に対し以下のような2人ゲームを行う。各手番において未着色の頂点を必ずひとつ選び、先手ならば白、後手ならば黒で塗る。すべての頂点が塗られたあと、黒の頂点に隣接している白の頂点を…

http://agc011.contest.atcoder.jp/tasks/agc011_d 問題概要 左右からボールを入れられるN個の装置が横一直線に並んでいる。装置は状態Aか状態Bのどちらかである。状態Aの装置にボールが入ってくると、入ってきた方向にボールを跳ね返し状態Bに変化する。状…

問題概要 あるシステムにおいて、電話番号の桁数はNである。またこのシステムでは特定の接頭辞がついた電話番号はすべて「特別な番号」として予約されている。Nと接頭辞の集合Sが与えられるので、特別でない番号が何通り存在するか求めよ。 1 <= N <= 17, 0 …

http://arc083.contest.atcoder.jp/tasks/arc083_c 問題概要 N頂点の根付き木とN要素の数列Xが与えられる。木の各頂点に白or黒の色と非負整数を割り当てるとき、頂点nを根とする部分木に含まれる頂点のうちnと同じ色のものに割り当てられた数の合計がX_nとな…

http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d 問題概要 英小文字のみからなる文字列Sをいくつかの箇所で区切り、空でない部分文字列に分割することを考える。このとき必ずすべての部分文字列が「並べ替えれば回文…

http://agc011.contest.atcoder.jp/tasks/agc011_c 問題概要 N頂点M辺の単純無向グラフGが与えられる。Gの各頂点は1～Nまでの番号が付いている。Gを元にして以下のようなグラフG'を作ったとき、G'の連結成分の数を求めよ。 頂点数はN2 各頂点は1以上N以下の2…

http://arc078.contest.atcoder.jp/tasks/arc078_c 問題概要 ある正整数Nが設定されている。64回以内の質問クエリでNを特定せよ。質問クエリで正整数nを投げると、「n <= N かつ str(n) <= str(N)」または「n > N かつ str(n) > str(N)」 のときYESが、そう…

問題概要 N行無限列の2次元グリッドがある。各行にはコストが設定されており、その行のマスに1回乗るたびに毎回そのコストがかかる。移動の開始点と終了点が与えられるので最小のコストを求めよ。 N <= 50 解法 開始行→経由行→終了列→終了行という感じで移動…

問題概要 与えられる整数n, kに対して、各行・各列をみたとき異なる数がちょうどk個存在するようなn * nのグリッドを構成せよ。解が複数ある場合は使われる数の種類が最大になるものを答えること。 3 <= n <= 50 1 <= k <= n/2 解法 1 2 3 0 0 0 0 4 5 6 0 0…

問題概要 0～9の各数字について、それぞれを何回まで使ってよいかを示した配列amountが与えられる。amountの制限を守って桁数がblank1の非負整数A, blank2の非負整数Bをつくるとき、ありえるA, Bのすべての組合せにおけるA*Bの総和を求めよ。 max(amount) <=…

問題概要 整数d, kが与えられる。最短距離がdであるような頂点のペアがちょうどk個あるような無向グラフを構成せよ。ただしすべての辺の距離は1とし、辺・頂点とも最大で1000個までとする。 2 <= d <= 50 1 <= k <= 50000 解法 (D-1)個の頂点を一直線につな…

問題概要 ある連続した期間の前半d1日で合計w1個の単語を覚え、後半d2日で合計w2個の単語を覚えたい。任意の連続する2日間において覚える単語の数が高々1しか変わらないように単語を覚えるという制約のもとで、このような単語の覚え方が可能か判定せよ。 d1,…

http://tdpc.contest.atcoder.jp/tasks/tdpc_cat 問題概要 1～Nまでの番号がついたN匹の猫がいる。任意の猫2匹の組合せには親密度が設定されており、各猫の幸福度は自分との距離が1以内のところにいるすべての猫との親密度の和で定義される。1次元の数直線上…

http://tdpc.contest.atcoder.jp/tasks/tdpc_target 問題 半径ri, 中心(xi, 0)のN個の円が与えられる。この中からどの2円をとっても片方がもう片方の内部に厳密に含まれるようにいくつかの円を選ぶとき、選べる円の最大数を求めよ。 解法 円cとx軸上の2交点…

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi 問題概要 iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。 |S…