現代の量子力学

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

2020/01/07

寒すぎて外に出られません。

Solved By kkktym
Topcoder: 0
Codeforces: 231->233
AtCoder: 1479
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1782->1784
コロナ(東京): 1591->2447

Codeforces Round #556 (Div. 1) (virtual)

12分 1完 div.1 で勝てる気が全くしないぜ!

A. Prefix Sum Primes

全ての要素が1なら、prefix sumは1刻みで増えていくので素数を漏れなくカバーできるのは明らか。2が入ると数字が1つ飛ばされてしまうが、偶数はどうせ素数では無いので偶数を飛ばすようにすれば大丈夫。2が素数であることだけに注意すれば、212...21...1みたいな並べ方が最適だとわかる。全て1だったり、全て2だったりする場合は場合分けする。

B. Three Religions

O(N3) のDPしか見えずに終了。解説ACした。良問だった。

C. Tree Generator™

しばらく考えてわからなかったので解説ACをしようとしている。

修論

1つのファイルに全文章を書いていたらごっちゃごちゃで見にくくなったのでセクションごとにファイルを分けた。ついでにハイパーリンクもつけた。こういうことは書き始める前にやろうね。

タイピング

内定先からe-typingでタイピングの練習をして、1/29までで一番良かった結果をスクショして送れ、と言われているのでやってる。分割キーボードにも慣れてきてようやくSランクが出たよ。Twitter見てると強い人しかいないので焦るね。

まとめ

寒すぎる。大学までの精神的距離が遠すぎる。分割キーボードにしてから肩が凝りにくくなったかも。

2020/01/06

今日は2020/01/07では?

Solved By kkktym
Topcoder: 0
Codeforces: 231
AtCoder: 1478->1479
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1781->1782

ARC088E - Papple Sort

両端から順番に、一番移動距離が短くなるペアを見つけて移動させていく。移動させたあとは位置関係が変わるけど連続的な変化なので遅延セグ木でえいやってやるとできる。解説の方針でもやってみたけどWAがとれません、どうして?

修論

現在56ページ、もういいのでは。

まとめ

みんなバチャやってて楽しそうだった。やりたい。

2020/01/05

年が明けて初めて大学に行きました。

Solved By kkktym
Topcoder: 0
Codeforces: 225->231
AtCoder: 1477->1478
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1774->1781

ABC033D - 三角形の分類

実は昨日から実装していて今日ようやく通った。雑に二分探索二回してO(N2 (logN)2 ) で 3009 ms だった。TL 7000 ms なのでゆるして。

Educational Codeforces Round 79 (virtual)

0:44 ABCD4完 なかなかEの壁を越えられないね

A. New Year Garland

r <= g <= b のとき r + g + 1 < b か否かを判定。

B. Verse For Santa

でかいやつをスキップするのがいいので、最大値を保持しながら前からチェック。一個も取り除かなくていい場合は別でチェック。

C. Stack of Presents

これすき。すでに掘られた部分にそのプレゼントが含まれているなら時間1で取り出せる。

D. Santa's Bot

寄与ゲー。2761 ms かかっておどろいた。TL 5000 ms だった。

Codeforces Round #694 (Div. 1)

久しぶりに出た。1:21 AB2完 でちょい冷え 遅すぎ?

A. Strange Birthday Party

後ろから順に前に詰めていけばいい。なんか実装で迷走して結局dequeを使ってみたりした。

B. Strange Definition

各要素を平方数で割れるだけ割ったものの出現数を管理。wは0か1かだけ見ればいい。平方数で割るパートで何も考えなかったらTLE、それはそう。平方数を103以下の素数の二乗のみに絞ったらいける。

修論

かっこいいイントロを考えていた。もう提出まで3週間しかなくて焦るね。

my new gear...

年末に買った分割キーボードを初めて使った。思ったよりすぐ慣れていい感じ。

まとめ

修論、佳境

2020/01/04

かなりサボった。

Solved By kkktym
Topcoder: 0
Codeforces: 221->225
AtCoder: 1477
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1770->1774

Educational Codeforces Round 99 (virtual)

42分 4完

B. Jumps

k(k+1)/2 がx 以上である必要があり、これでほぼ十分である。x+1 == k(k+1)/2 の場合だけ気をつける。

C. Ping-pong

ギャグ。こんなピンポンはいやだ。

D. Sequence and Swaps

制約が三乗のDPをしろと言っているのでする。

修論

クリスマスに投げた第0稿のお直しが返ってきた。提出まであと3週間なのやばいな。

2020/01/03

わりかしサボった。

Solved By kkktym
Topcoder: 0
Codeforces: 217->221
AtCoder: 1476->1477
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1765->1770

ABC027D - ロボット

DPを高速化する方針で考察し続けて何もわからなかったので解説を見ちゃった。かしこかった。良問。ある程度進んだ方針を途中で変えることができない。

Educational Codeforces Round 101 (Rated for Div. 2) (virtual)

1:56 4完 3ペナ 全然だめ

C. Building a Fence

最大と最小を保持して前から見ていく ( two pointers っていうのか?)

D. Ceil Divisions

しばらく不可能では?ってなってたけどいける。フィボナッチ。

感想

自力ACにこだわりすぎるのはよくない。半年前の自分に言ってあげたいね。

2020/01/02

ABC埋めをしたり、ABCに出たりしました。

Solved By kkktym
Topcoder: 0
Codeforces: 217
AtCoder: 1459->1476
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1748->1765
ACRate: 1807->1846

ABC003D - AtCoder社の冬

包除。

ABC005C - おいしいたこ焼きの売り方

貪欲にマッチングさせる。

ABC008D - 金塊ゲーム

区間DP, 2次元なので領域DPかな。大昔にWA出したときに考察は済んでいたので実装するだけだった。

ABC009D - 漸化式

行列累乗, 初めて行列累乗をちゃんと解いたので嬉しい。

ABC024D - 動的計画法

三つの条件から二つの未知数を決めるので、できる。modintを信じる。

ABC187

リアルタイムで参加。64:07 全完 ノーペナ (えらい)

D - Choose Me

2*A+B でソートして貪欲。これがすぐ解けたのが一番えらかった。

E - Through Path

クエリの頂点対に特に条件がないと思ってしまった。オイラーツアーでいけるかな〜?って考察してたら頂点対は辺で直接つながっていることに気づいて、そのままオイラーツアー+遅延セグ木でいった。オイラーツアーを初めてちゃんと使った。

F - Close Group

O(3N)の bitDP。間に合うか〜?間に合った。一応テストケースで 18 0 を確認してから投げた。

試験管だけど黄 diff を 4 問も埋めてえらいし, 黄パフォでレートを上げたのでえらい.

2021/01/01

あけましておめでとうございます。

今年は解いた問題を毎日メモしていこうかな。

Solved By kkktym
Topcoder: 0
Codeforces: 212->217
AtCoder: 1454->1459
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1738->1748

JOI2021二次予選 (virtual)

173 分 ACDE 400点

A - 往復すごろく (Round Sugoroku)

B - パンケーキ (Pancake)

解けなかったので解説AC。むずかった。

C - イベント巡り (Event Hopping)

DP[i][j] := 参加数i, 町j という状態になるまでにかかる時間の最小値, でDP。

D - 安全点検 (Safety Inspection)

X分で点検できるか?の判定問題を奥から貪欲で埋めていけばO(N)で解けるので二分探索。

E - スパイ 2 (Spy 2)

A, B がスパイだと C はスパイ確定。まず A,B がスパイの発言を処理, 次に C がスパイ確定したことによってA, B がスパイになるような発言を処理。全て処理したらまだ決まってない人を議員にして終わり.