現代の量子力学

主に精進の様子を記録する日記帳です

2020/01/14

ゴールが見えると手を抜いてしまう、人間だもの

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1498
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1809

ARC080E - Young Maids

辞書順最小なので先頭から貪欲に小さい要素をとっていけば良い。末尾から足すことになるのでとることができる要素と取り出し方には制限がつく。先頭に持ってこれるのは偶数 index (0-index) のものだけで、2番目は奇数 index のもの、かつ先頭のものより後ろにあるものだけである。これは偶奇 index それぞれの要素についての区間最小セグ木を持っておけばいける。これらの要素を取り除いたら取り除いた部分を境に区間が分断されることになり、区間ごとに同じような操作をすれば良い。この際、先頭に持ってこれる要素の index の偶奇は区間の下端の偶奇に依存するので注意する。あとは区間DPのノリで、更新順をダイクストラのノリで処理すればいける。優先度付きキューちゃんに、std::pair<std::pair<int,int>, std::vector<std::pair<int,int>>> なんていう重たいものを持たせちゃった...ごめんね...

ARC076E - Connected?

サンプル3 を紙に描いてYESであることを確認するのに時間がかかった。曲線の可能性は無限大!って感じ。結局長方形の周上を時計回りに見ていって2回登場する要素の区間が前後しなければおっけー。実装に手間取った。解説では括弧列とみなして stack で判定、をしていて賢かった。fox のやつと一緒だね。

ARC067E - Grouping

要素をいくつかの集合に分ける通り数を、重複なく数え上げるには mex を次の集合に必ず入れることにすればいい! (ABC180F-Unbranched) だ!と思ったけどうまくいかず。要素数の大きい集合っていくつも作れなくない?√Nで抑えるやつか?と考え、素直なDPを考えてみると、√Nのやつでは無かったけど調和級数のやつであることに気づく。あとは素直にDPをするのみ。なんか考察の手札が増えてきてめっちゃ楽しい。

修論

やばい計算ミスに気づく。やばいと思ったけどストーリーをちょっと変えるだけでセーフだったのでそんなにやばくは無かった。

VSCode

めっちゃいい。補完が素晴らしい。Emacs くんは見たことある文字を候補に出してくれるだけだったのに、VSCode くんは先回りして候補を出してくれる。でも、「僕こんな単語知ってるよ!」って見せてくれる Emacs くんが可愛くみえてきた...

まとめ

最近問題解くのが楽しすぎる。コンテストが楽しみ。修論はゴールがみえてからサボり気味...

2020/01/13

ずっと真夜中でいいのに。いいですね。今更ですか。

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1495
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1806

ARC090E - Avoiding Collision

最短距離の数はわりかし簡単に求められるんだぜ。やることが多い感じだけど、各ステップは難しくないので丁寧丁寧丁寧に実装していくと解ける。サンプルが劇的にしょぼいので震えながら提出したけど、一発で通って良かった。

ARC083E - Bichrome Tree

まず、部分木の根ごとに、部分木の要素のそれぞれの色の総和を持ったDPが思いつく。部分木の根を i として片方の色の総和は必ず X[i] なのに気づく。状態数がかなり減る。もう片方の色の総和はできるだけ小さい方がいいことに気づく。めっちゃ状態数が減る。あとは子のマージパートを畳み込めばいける!NTTで間に合うか?となったが、畳み込む片側は常に 0 でない要素が高々 2 つであることに気づく。愚直に畳み込めばいける。あとは丁寧に実装してAC。

修論

今日はやる気がでない日だった。とりあえず一通り書き終えてみた。あとちょっと欲しい画をゲットしてまた数回担当教官とキャッチボールしたら終わりかな?

じゅじゅさんぽ

集中が切れるとおさんぽにいくよ。ついでに呪術廻戦の新刊を買ってきた。またエグい引きだった...芥見ェ...

まとめ

なんか精進関係なく普通の日記になってきた。バチャがしたいです... でも、黄色上位 diff. を 2 つも自力ACしたので今日はヨシ!!!!!!!

2020/01/12

雪にならないくらいの雨が一番しんどい

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1492
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1803

ARC095 E - Symmetric Grid

きれいにフローに帰着したぜ〜と実装していたら嘘に気づく。1時間考察してもわからなかったので解説を見た。N個の要素をN/2個のペアに分けるパターンを全探索するときはペアを選ぶ際に片方の要素はmex にすることにすれば重複なく列挙することができて、パターンの総数は(N-1)!! である。これは Heights and Pairs と Unbranched でやった!になった。最近シナプス繋がりまくっていい感じ。実装は非常にめんどかったしバグった。

修論

言われた部分を直しつつ、物理的背景パートをちゃんと書いた。このへんは書くのが楽しいね。物理学専攻なので。

弘法筆を選ばず

男は黙ってターミナルとEmacs!!! これまでは、黙ってターミナルとEmacs を使っていたけど、会社入ったらVSCode らしいしそろそろ練習しておくことにした。横に分割してターミナルとソースコードって感じでやることにすれば今までとほとんど変わらないので良き。

まとめ

京大生としての良識と自覚

2020/01/11

1/11 なのでポッキーが 111 円で売られていました。11/11 には 1111 円で売られているのでしょうか。

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1491
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1802

ABC147 F - Sum Difference

ず〜〜〜〜っと考察してた問題がようやく解けた。区間をマージしていく処理が必要で、むげんさんの記事を参考にした。ありがとうございます。

おみくじ

下鴨神社で引いた。吉で、願いごと なにごともかなう、らしい。わーい。なんとこれが初詣だった。

おかいもの

カバンのチャックが壊れてたので買った。ユニクロのカバンはいいぞ。

まとめ

11 時に起きるなど、のんびりとしたいい一日でした。明日からは早起きします。

2020/01/10

ABCしか勝たん

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1485
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1796
ACRate: 1835->1888
Rating History、yukicoder だけうまく反映されません...

ABC188

66:36 (1 ペナ) 全完!うれし〜

C - ABC Tournament

シミュレーションしたい気持ちをグッッッッと堪えて前半分と後ろ半分に分けて決勝進出者を調べる。

D - Snuke Prime

はいはい遅延セグ木で殴りましょか〜と思ったら制約が許してくれなかった。イベントソートいもす (動的ないもす?) で対処。なんか時間かかっちゃった、いもすの書き方が自分の中で決まってないのが明らかにだめ、反省ポイント1

E - Peddler

これまでの最小値を持つDPをする。DAGなのにBFSしちゃった、実装に時間かけちゃったし雑にやったら一回TLEした。反省ポイント2

F - +1-1x2

かなり既視感があったね。見た瞬間DPだね、と思う。YからXで見た方が2倍を処理しやすいのでそうする。Yが 2 で割りきれるなら 2 で割る。割り切れないなら 1 足して 2 で割るか 1 引いて 2 で割るかする。遷移先は高々 2 つで、2 つだとしても連続した整数になる。この 2 つからの遷移先も実は 2 つの連続した整数に纏まってくれる。この辺は、 Valid payments を思い出した (どうだっけ?) 。遷移先の 2 整数は遷移元より明らかに小さいので BFS 的な遷移でおっけー。2 で割り切った後は ±1 で X に近づくことにして良いのでよしなにやる。

まとめ

暖まって嬉しいです。実は最高パフォ (2277) でした。嬉しい。コンテスト後に体温を測ったら 37.7 ℃ありました。まじ?身体も暖まってしまうとは…しばらくしたら 36.6 ℃まで下がりました。一安心です。

2020/01/09

最近は青 diff. もほとんど落としてないし、水 diff. 以下は落とすわけないんだよな

Solved By kkktym
Topcoder: 0
Codeforces: 233
AtCoder: 1479->1482
AOJ: 62
yukicoder: 30
library-checker: 0
Sum: 1786->1789

ARC111

97:27 BC2完!?

A - Simple Math 2

開幕40分以上考えて解けず、BC解いた後の時間も考えたけど解けず...本当に300 点か???(10N - 10N%M)/M % M みたいな式変形+行列累乗でずっと考えてて深みに嵌ってしまった...解説を見てACした...くやし〜

B - Reversible Cards

Nosubの色が濃い中、とりあえず問題を開いてみると、とりあえずグラフにしたい気持ちになる。そのまま、するすると考察・実装が進み、サンプルも合ってしまった。開始から1時間、少し提出を躊躇ったがジャッジされたい欲求に負けて(?) 提出しちゃったよ...

C - Too Heavy

人 i, j を swap すると、 a[i] <= a[j] のとき、人 j は必ず疲れないことがわかる。と、いうわけで a[i] の小さい方から決めていけばいい。サイクル分解してサイクルごとに a[i] でソートして貪欲に操作を決めていったが、サイクル分解はいらなかったね。いらないミスを誘発するのでこういうのはやめよう。

D

BCを解き終えて残り20分、一瞬問題を見てAを解き直しに戻った。またちゃんと考えて解いておこう。

まとめ

緑 diff. が解けませんでした!悔しい。解けなかったのもだけど、立ち回りが酷すぎて笑う。Nosubが頭をチラついてAを諦めるのが遅すぎた。それにしてはパフォは耐えた感じなのでえらい。明日のABCは頑張ります。

2020/01/08

Q.心を持ったパンってな〜んだ?

Solved By kkktym
Topcoder: 0
Codeforces: 233
AtCoder: 1479
AOJ: 62
yukicoder: 28->30
library-checker: 0
Sum: 1784->1786

yukicoder contest 277

ゆるっと参加した。AB 2完。Cわからず。

A. No.1329 Square Sqsq

(桁数+1)/2

B. No.1330 Multiply or Divide

これすき。xを頂点とするダイクストラっぽい感じでやった。Pで割り切れる回数が同じならデカい方がつよいのでそれ以外は無視!ができる。

C. No.1331 Moving Penguin

わからなかったので解説を見た。すげ〜、√Nで分割する系の問題、もっと経験を積みたいね。

修論

進捗ミーティングをした。ミーティングするとそれだけでその日は仕事した感が出るのでいいね。

e-typing

Sの上はGood!か〜い。日に日に上達してていいね。

まとめ

A.チョココロネ