ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces

Codeforces Global Round 5 E. Balanced Binary Search Trees

Problem - E - Codeforces 問題概要 以下の条件を満たす根付き木を二分探索木と呼ぶ。 任意の頂点 について以下が成り立つ。 「左側の子」と「右側の子」がそれぞれ高々1個存在する。 左側の子孫が存在する場合、それら全ての頂点番号は より小さい。 右側の…

Codeforces Round #590 (Div. 3) E. Special Permutations

お題箱より。 Problem - E - Codeforces Editorialのソースコードがよく分からないというリクエストだったんですが、見たところ確かによく分からなかったので、私の解法を書きます。 問題概要 長さ の順列 を と定義する。 長さ の整数列 ()が与えられる。…

Educational Codeforces Round 74 E. Keyboard Purchase

お題箱より。ただ、この問題は元々書こうと思っていました。 Problem - E - Codeforces 問題概要 文字のアルファベットからなる長さ の文字列 が与えられる。アルファベット 個を並べる順列 を1つ決めた時、「 の隣り合う2文字のペアそれぞれについて、その…

Codeforces Round #587 (Div. 3) F. Wi-Fi

お題箱より。 Problem - F - Codeforces セグメント木を使わない解法を…とのリクエストだったので、何通りか解法を紹介します。 問題概要 個の部屋が並んでいて、順に番号 が付けられている。これらの部屋全てにインターネット回線を提供したい。 回線提供に…

Codeforces Round #587 (Div. 3) E2. Numerical Sequence (hard version)

Problem - E2 - Codeforces 問題概要 正整数 に対して、 を十進表記で書いたものをこの順に連結した文字列を とする。例えば "1234567891011" である。 そして、 をこの順に連結した無限の長さの文字列を考える。与えられる 個の整数 に対して、この文字列の…

Codeforces Round #577 (Div. 2) B. Zero Array

お題箱より。 Problem - 1201B - Codeforces 問題概要 個の正整数 が与えられる。これに 異なる2つの要素を選び、それぞれの要素を1減らす。 という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。 制約 解法 この判定は競技プログラミングで…

Codeforces Round #573 (Div. 1) C. Tokitsukaze and Duel

Problem - C - Codeforces 問題概要 0または1からなる 文字の文字列 と整数 が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する 文字を選び、それらを全て0または全て1にする」という操作を行う。…

Codeforces Round #570 (Div. 3) F. Topforces Strikes Back

ちょっと変わった解き方をしたので記録。 Problem - F - Codeforces (追記)公式Editorial もこの解き方でした。 問題概要 以下の問題を ケース解け。 個の正整数 が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件…

Codeforces Round #564 C. Nauuo and Pictures

Problem - C1 - Codeforces Problem - C2 - Codeforces 問題概要 枚の画像がランダムに表示されるWebサイトがある。各画像には重み が設定されていて、画像 の表示確率は である。 画像を 回表示させる。このとき画像が1回表示されるごとにその画像の重みが…

Codeforces Round #556 B. Three Religions

お題箱より。 Problem - B - Codeforces 問題概要 英小文字からなる長さ の文字列 が与えられる。また文字列 があり、これらは最初は空である。 以下のクエリが合計で 個与えられる。 1 i c 文字列 の末尾に文字 を足す。 2 i 文字列 の末尾の文字を取り去る…

Codeforces Round #561 F. Vicky's Delivery Service

お題箱より。 Problem - F - Codeforces 問題概要 頂点 辺の無向グラフがあり、各辺は 色のうちどれかの色で塗られている。 以下のクエリを 個処理せよ。 + x y z 頂点 間に色 の辺を追加する。 ? x y 頂点 から頂点 までの、以下の条件を満たすパスが存在す…

Codeforces Round #561 D. Cute Sequences

Problem - D - Codeforces 問題概要 以下の問題を 個解け。 正整数 が与えられる。以下の条件を満たす整数列 を1つ構成するか、そのような数列が存在しないことを判定せよ。 初項が で末項が である。 項数を として、全ての について とすると が成立する。…

Educational Codeforces Round 65 E. Range Deleting

Problem - E - Codeforces 問題概要 長さ の数列 と整数 が与えられ、 である。 以下の条件を満たす整数の組 の個数を求めよ。 である。 数列 から を満たす要素をすべて取り除くと、残った数列は広義単調増加になる。(空数列でも可) 制約 解説 削除する値…

Codeforces Round #560 F2. Microtransactions (hard version)

Problem - F2 - Codeforces 問題概要 ※microtransactionは、オンラインゲームなどでのアイテム課金を指す言葉だそうです。文中では「アイテム」と訳します。 イヴァンはゲームのアイテムを買おうとしている。アイテムは 種類あり、種類 のアイテムは 個必要…

Codeforces Round #554 F. Neko Rules the Catniverse

Problem - F1 - Codeforces Problem - F2 - Codeforces 問題概要 整数 が与えられる。以下の条件を満たす要素数 の数列 は何通りあるか、 で求めよ。 は相異なる 制約 F1とF2で の範囲が異なる。 F1: F2: 解法 何となく数列の頭から順に決めていくDPを考えた…

Codeforces Round #551 E. Serval and Snake

Problem - E - Codeforces これ結構好き。 問題概要 インタラクティブ問題である。 のグリッドがあり、グリッド内に蛇がいる。蛇の両端は異なるマスにあり、胴体は隣り合うマスを渡って両端を繋ぐパスとして表現される。 以下のクエリを2019回投げることが出…

Educational Codeforces Round 61 D. Stressful Training

Problem - D - Codeforces 問題概要 コンテスト参加者が使う 台のPCがある。 番目のPCの初期電池残量は で、消費速度は毎ステップ である。 初めに充電器の充電速度として非負整数 を決め、以下の処理を ステップ行う。 各ステップごとに、どのPCを充電する…

Codeforces Round #540 F2. Tree Cutting (Hard Version)

Problem - F2 - Codeforces コンテスト単位の記事がなかなか書けずにこどふぉの記事をサボってしまっているので、比較的楽に書ける1問単位の記事も書いていこうと思います。ちょっと方向性模索中。 解法 同じ色の頂点を繋ぐ もし直接辺で繋がっていない頂点…

Educational Codeforces Round 59 参加記録&解説(A~D)

しばらくこどふぉの記事をサポってますね… A. Digits Sequence Dividing Problem - A - Codeforces 問題概要 以下の問題 個に答えよ。 からなる 文字の文字列が与えられる。この文字列を2つ以上の連続部分文字列に分解し、「それぞれの文字列を10進数の数値…

Hello 2019 (Codeforces) 参加記録&解説(A~D, F)

Codeforces 2019年最初のコンテストはABCDFの5完で111位!幸先いいですね。 A. Gennady and a Card Game Codeforces 問題概要 2文字の文字列でトランプのカードを表す。1文字目がランク、2文字目がスートに対応する。 場にあるカードが与えられ、さらに5枚の…

Educational Codeforces Round 57 参加記録&解説(A~F)

猛プッシュ回。その真意はG問題にありましたが、私は解けませんでした… ※2019/01/16 E問題を追記。 A. Find Divisible Problem - A - Codeforces 問題概要 以下の問題 個に答えよ。 整数 が与えられる。 かつ かつ が の約数であるような整数 を1組求めよ。 …

Codeforces Round #529 参加記録&解説

Dashboard - Codeforces Round #529 (Div. 3) - Codeforces だいたい1時間で全完。平和なDiv3でした。 A. Repeating Cipher Problem - A - Codeforces 問題概要 ある文字列 に対して、各文字を「1文字目を1個、2文字目を2個…」と並べた文字列 が与えられる。…

Codeforces Round #528 参加記録&解説(A~D)

Dashboard - Codeforces Round #528 (Div. 1, based on Technocup 2019 Elimination Round 4) - Codeforces 配点の高いDを通し、なんとDiv1で81位!これはそうそう出るものじゃないですね。レートも爆上げ。 A~Dを振り返ります。Div2ではC~Fに対応します。…

Codeforces Avito Cool Challenge 2018 参加記録&解説(A~E)

プレテスト5完だったのですが、Dがしょうもない実装ミスで落ちました… A~Eまで5問振り返ります。 A. Definite Game Problem - A - Codeforces 問題概要 正整数 の初期値 が与えられる。これに以下の操作を0回以上繰り返して、 をできるだけ小さな数にしたい…

Codeforces Round #525 参加記録&解説(A~E)

Dashboard - Codeforces Round #525 (Div. 2) - Codeforces 今回は3完…うーん。Div2でこれは良くないですね。 本番後にEまで通したので5問書いていきます。 A. Ehab and another construction problem Problem - A - Codeforces 問題概要 正整数 が与えられ…

Codeforces Round #522 C. Vasya and Maximum Matching

Problem - C - Codeforces 考察が重かったけど、面白い問題。 問題概要 頂点の木が与えられる。この木の辺それぞれについて辺を取り除くかどうかを考えると、その場合の数は全部で 通りある。そのうち「辺を取り除いた後のグラフにおいて、最大マッチングが…

Educational Codeforces Round 54 参加記録&解説(A~F)

Dashboard - Educational Codeforces Round 54 (Rated for Div. 2) - Codeforces 今回はなんと17位!…なんですが、本番中のD問題のジャッジに致命的なミスがあって正常なコンテストではなかったため、素直に喜べない感じです… 6問振り返ります。 A. Minimizi…

Educational Codeforces Round 53 参加記録&解説(A~D)

Dashboard - Educational Codeforces Round 53 (Rated for Div. 2) - Codeforces 4完で256位。キリ番です(?) Div2オンリーならもっと上を目指したいところ… A. Diverse Substring Problem - A - Codeforces 問題概要 長さ の英小文字列 が与えられる。 の…

Educational Codeforces Round 52 G. Fibonacci Suffix

Problem - G - Codeforces 面白い問題を自力で通せたので記録。 問題概要 文字列の列 を、漸化式 "0" "1" で定義する。この は文字列の結合を示す。 整数 が与えられる。 の接尾辞を辞書順に並べた時、 番目に該当する文字列の先頭 文字を求めよ。(ただし、…

Codeforces Round #516 参加記録&解説(A~C)

Dashboard - Codeforces Round #516 (Div. 1, by Moscow Team Olympiad) - Codeforces 結果は3完!とはいえ、3完速解き勢が多くてレート上昇はそこそこ。Div1は修羅の世界。 A~Cを振り返ります。Div2だとC~Eに相当します。 A. Oh Those Palindromes Proble…