2020-12-14

AtCoder Beginner Contest 185 E - Sequence Matching 解説

やらかし反省録が増えました！！！！！！！！！！！！！！！！！！！

問題リンク

https://atcoder.jp/contests/abc185/tasks/abc185_e

問題概要

$N,\ M$ 要素からなる整数列 $A,\ B$ があります。 $A,\ B$ からいくつかの要素をコスト $1$ で取り除くことができます。取り除いたあと、 $A,\ B$ の要素数が同じでなくてはなりません。
取り除いたあとの $A,\ B$ について $A_i\neq B_i$ である要素があれば、その個数だけコストが $1$ ずつ上乗せされます。
コストの最小値を求めてください。

制約

$1\le N,\ M\le 1000$
$1\le A_i,\ B_i\le 10^{9}$

2020-12-11

yukicoder No. 1314 - N言っちゃダメゲーム (5)

競プロ解説 yukicoder

ネタ被りが前日に発覚して (4) が (5) になるってどんな偶然なんですか？？

問題リンク

https://yukicoder.me/problems/no/1314#

問題概要

N言っちゃダメゲームをします。つまり、先手であるあなたは $0$ から始め、お互いに $[1,\ K]$ の整数を加算したものを言っていき、 $N$ 以上の整数を言った人の負けです。
$N$ は今回 $2$ 以上 $M$ の各整数を用います。先手の人は残っているものの中から好きなものを選び、その回の $N$ とします。一度使った数は以降使えなくなります。 $2$ 回目以降のゲームは前回負けたプレイヤーが先手をします。

お互いに各ゲームではわざと負けたりしない条件のもと勝つ回数を最大化します。あなたが勝つか負けるか、引き分けになるかを求めてください。

制約

$2\le M,\ K\le 10^{9}$

2020-12-10

yukicoder No. 1313 - N言っちゃダメゲーム (4)

競プロ解説 yukicoder

問題リンク

https://yukicoder.me/problems/no/1313

問題概要

先攻のプレイヤーであるあなたは $0$ から始めます。交互に $[1,\ K]$ のうちのどれかの整数を加算していきます。 $N$ 以上の数字、または予め指定された危険な数字を言ってしまうと負けです。

あなたが勝つ場合は最初に宣言して勝てる数字を全て出力してください。あなたが負ける場合は $0$ を出力してください。

制約

$N,\ K$ は整数
$1\le K\lt N\le 2\times 10^{5}$
$|S|=N-1$
$S_{i}$ が x のときは $i$ は「危険な数字」で、o のときはそうではない

2020-12-09

yukicoder No. 1312 - Snake Eyes (Advent Calendar Contest 2020 - I) 講評

Writer記録 yukicoder

これから私が yukicoder において Writer/Tester をした問題やコンテストの講評は開催されるたびに上げようと思います。当然ですが、問題のネタバレを含みます。

私の Writer をした問題では初出題です。yukicoder 毎年恒例のアドカレコンのうち 1 問を担当させて頂きました。色々不慣れな点もありましたが無事出題でき、良かったです。Tester のりあんさんには感謝です！

yukicoder No.1312 Snake Eyes

yukicoder Advent Calendar Contest 2020 の 12 月 9 日公開問題です。

問題ページ
https://yukicoder.me/problems/no/1312

2020-12-09

AtCoder 青 / Codeforces 紫 / Topcoder 黄になりました

色変記事 AtCoder Codeforces Topcoder

この記事は、色変記事 Advent Calendar 2020 の12月9日公開の記事です。

色変記事アドベントカレンダー、なるものの募集を見ました。

色変記事AdventCalendarを作成しました。
みなさまの勇気ある宣言をお待ちしております！https://t.co/1NqMxq7Wu3
— 蟹道きりみ@競プロvtuber (@ayoiyouyoeyo) 2020年11月4日

この恐ろしいアドベントカレンダーを見てしまった私。そういえば、AtCoder 青も Codeforces 紫も、近かったような……あれ、Topcoder も黄になれるんじゃ？

f:id:fairy_lettuce:20201105125829p:plain:w320

ということで、参加してみました。完全にノリですが、Topcoder はともかく AtCoder と Codeforces はずっと色変しないまま膠着していたので、これを期に色変してやろうと考えました。

(達成できたら)恐らく前代未聞の、3 コンテストサイト同時の色変記事になります。

前回 (AtCoder 水色) の色変記事
色変報告
- AtCoder 青に……
- Codeforces 紫に……
- Topcoder 黄に……
AtCoder 青になるまでにやったこと
- 精進記録
  - AtCoder
  - Codeforces
  - Topcoder
  - yukicoder
  - その他
  - おまけ (Online Math Contest)
- 身につけたアルゴリズム・データ構造
  - 何の迷いもなく書ける・使えるようになった
  - 調べたら使える・ちょっと苦労するけど書ける程度
  - あまり理解していない
- その他にやったこと
  - バチャ
  - Upsolve をするようにした
  - 解説記事執筆
  - 本を買った
その他競プロをする上で意識したこと
- 競プロの戦い方
- メンタルの持ち方
アドベントカレンダーに参加しての感想
おわりに

2020-12-08

yukicoder No.1311 - Reverse Permutation Index 解説

競プロ解説 yukicoder

yukicoder Advent Calendar Contest 2020 の 12/08 出題問題です。

一見すると $N,\ S$ の間に簡単な法則が成り立ちそうですが、どうなんでしょう。面白いですね。

問題リンク

https://yukicoder.me/problems/no/1311

問題概要

ある順列が辞書順で出てくる順番をインデックスと呼びます。また、 $S$ 要素で $1$ -indexed な順列 $a$ に対して $b$ が $a_{b_{i}}=i (i=1,\ 2,\ \dots,\ s)$ を満たすとき、 $b$ を $a$ の逆置換と呼びます。
$S$ 要素の順列の中で、 $N$ 番目の順列の逆置換のインデックスを求めてください。