2021-08-17

#夏休み１２日目

夏休み１２日目

無
進捗
？
yukicoderの作業進んだ

明日

有を目指す
凍結してたunityいじり再開したさがある

2021-08-17

夏休み１１日目

起きた時点で１２時なので半日しか過ごしてない

進捗

雑タスクを終わらせる
- 費用納入とか
成績確認
- お察し　アルゴだけ良かった
学科の実験課題選択希望を出す
- 忘れてた
APのお勉強
- 50ページくらい
- ｺﾝﾋﾟｭﾛｱｰｷﾃｸﾁｬでやった内容がまだ多い
- 半分くらい忘れてそう（え？）
div2バチャ（736）
- こどふぉ半年ぶりくらいにやった
- A : こどふぉにありがちなやつ　気づくのに６分は、まずい
- B : 左から見てって左に行って損はしなさそう　証明 : AC
- C : 自分より大きいのが隣にいたら残れなさそう　証明 : AC
- D : セグ木二分探索だね→TLE 　logは定数ではない...
- E : コンテスト後にヒント見て解いた　dpの定義上手ですね

明日

午前中に起きてくれ
こどふぉしたい　かも？

2021-08-16

夏休み１０日目

日曜日は休日！（デジャヴ）

進捗

勉強
- 2A/3Sの数学の復習をし始める
- 全て忘れてる
AP
- 100ページくらい進んだ
- アルゴとかなのでまあ
競プロ
- yukicoder
  - testerさんが1問以外見つかる
  - いつ出題できるのか...
寝落ち
- 夕飯買おうと思ったあたりで記憶が飛ぶ
- 今起きました（8/16 1:40)
- 腹へった　どうしてくれんの

明日

寝落ちしないで
平日なのでそろそろ進捗を...

2021-08-15

夏休み9日目

夏休み９日目

土曜日は休日！（素振り）土曜日は休日！（素振り）

進捗

競プロ
- RGB Balls(2202)
  - 最小値はなんとなく分かったけどそこからグダる
  - dpでも二項係数でもない数え上げが出来なさすぎる
- ABC214
  - ABCDFの５完
  - F は部分列dpほぼ貼っただけだし実質何もしていない
- yukicoder
  - testerを募集し始めた
  - 最速で出題 9/17 ってまじ？夏休み終わってしまう
その他
- 何もしていません　え？
- 休日は休む日

明日

書くことがあると良いですね

2021-08-14

夏休み８日目

日記が２日続いた快挙　継続の天才

進捗

家の大掃除
- 勉強しようと思ったら机汚すぎてやる気が起きなかったため掃除
- 今？
寝落ち
- 負の進捗
- 掃除終わって布団が気持ちよかったんです（言い訳）
競プロ
- バチャが早速０完になりかけた　やる気ある？
- 暗闇帰り道（1972）
  - にぶたんしろと書いてる
  - MLE&二分探索の端を間違えて3ペナ
- シャッフル席替え（2194）
  - $O(N! N^{2} K)$ のdpを書いて当然のようにTLEする
  - 想定解みたけど知らないと分からん
- I hate Shortest Path Problem (2291)
  - バチャ終わった後に通した
  - 区間で管理するやつ
  - multisetがC# に存在しないのでC++を書いて当然のようにバグる　lower_bound(x)がx以上なのかより大きいなのか以下なのかさえ覚えてない
  - multisetを作れ
寝落ちのせいで進捗が薄い

明日

掃除したんだから勉強してください
yukicoderの作問作業結局今日やらなかったのでやる

2021-08-13

夏休み７日目

７日目だということを知って驚愕する　人生の浪費が上手

進捗

買い物
- 参考書などを買う
- 積読を増やすな
競プロ
- 未AC埋めバチャをし始める
- Tree Burning
  - X が番号順に単調増加（当たり前）なこと忘れてlogをつけそうになる
  - 考察は無　添字で嫌な気持ちになる
- Graph Smoothing
  - 制約が行列累乗ですと言っているのでやると通る
- Three Coins
  - 解けません（え？）
  - 嘘DPを書いて終了

明日

APとか悲惨だった学業の復習とか早く始めてください　はい...
yukicoderの作問作業が終わりそう
https://kenkoooo.com/atcoder/#/contest/show/15c65a5b-c93d-4214-9d82-b598dc8153a1 をやる　何日続くでしょう

2021-06-28

ARC110-E Shorten ABC 解法メモ

公式解説と若干違う解法だったのでメモしておきます

解法

まず公式解説と同様に A,B,C をそれぞれ 1,2,3 に対応させます。このとき、1 xor 2 = 3、1 xor 3 = 2、2 xor 3 = 1 なので、操作は隣接要素をその xor に置き換える操作と言い換えられます。（ここまでは公式解説と同じです）

次に、累積 xor を取ります。 $A_0 = 0,\ A_i = A_{i-1}\oplus S_{i}\ (1\le i\le N)$ とします。こうすると、操作は以下のように言い換えることができます。

$1\le i\le N-1$ かつ $A_{i-1}\neq A_{i+1}$ であるような $i$ を選び、 $A_i$ を列から消去する。

この結果できる列を数え上げれば良いです。これは、消去しない要素を選ぶ、即ち部分列の数え上げと捉えることができるため、部分列 dp の要領で、以下のような動的計画法で数えられます。

$dp[ i] := 0,\cdots ,i$ 番目の要素まで考えて、最後に $A_i$ を消去せずに残すような部分列の取り方の総数。

ただし、部分列dpと同様に、最終的な列を決めたとき、残す文字は可能な限り先頭のものを選ぶことにします。 $dp[ i]$ からの遷移を考えます。次に取る値を $d = 0,1,2,3$ とし、 $i \lt j$ であって $A_j = d$ であるもののうち、最小の値を $next(d)$ とおきます（そのような $j$ がない場合は遷移しません）。

$d = A_i$ のとき : まず、 $S_i\neq 0$ なので、 $A$ の隣接項は互いに異なります。すると、 $next(d) \gt i+1$ が分かります。このとき、どのような消去手順を取っても最終的に $A_i$ と $d$ に挟まれた値を消去できないことは明らかなので、遷移不能です。
$d\neq A_i$ のとき : 必ず遷移できます。これは、 $i\le k\lt j$ を満たす全ての $k$ に対して、 $A_k\neq d$ であるので、必ず $d$ の手前の値を消去できるためです。

以上より、この dp は $O(N)$ で全て計算できます。

最終的な答えを求めます。明らかに、末尾の値は消去不能なので、残る部分列の末尾の値は $A_N$ であることがわかります。先ほどの部分列 dp のルールから、末尾が $A_N$ である部分列の総数とは、 $A_i = A_N$ であるような全ての $1\le i\le N$ に対する $dp[ i]$ の総和として求まります（ $A_N=0$ のとき、 $A_0=0$ が末尾のパターンを数えないように注意）。

というのは半分嘘で、仮に消去不能なために必ず $A_N$ が $K$ 個以上は残る、というような場合には $K$ 番目以降の値しか足しあげてはいけません。しかし、実際にはこの制約が生じるのは $S$ が全て同じ文字からなる場合のみです。これは、

もし $A$ に $A_N$ 以外の値が２種類以上含まれていた場合、全ての文字が消去できる。
$A$ が２種類しか値を含まない場合、隣接項が異なることから、 $A$ は 01010101010...のようになっていて、これは $S$ の文字が全て同じ時に他ならない。

というように示すことができます。よって、予め $S$ が全て同じ文字の場合は 1 を出力し、それ以外は上記の計算によって正しい答えが求められます。

提出（C++）

atcoder.jp

備考

結局最後の答え足しあげパートで公式解説っぽいことをしているので遠回りな気もしてきました（？）

eSeFの日記

タイトルで既にネタ切れ

#夏休み１２日目