2020/01/21-02/03
日記さぼりすぎた...
Solved By kkktym
Topcoder: 0
Codeforces: 267
AtCoder: 1519
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1858
ABC189(1/23)
79:55 5完で、レートは1866 → 1854 (-12)。くう...
D - Logical Expression
dp[i][j] := xi まで決めたときに yi = j となるような組み合わせの数、とするDPでおっけー。Nが異様に小さいのは答えがオーバーフローしないようにかな？
E - Rotate and Flip
操作列だけ保持しておいて、クエリが来たら点に対して操作すればいいやつ。操作1,2 は回転行列でいいね〜となるも、操作3,4で困る。定数項がついてしまう。この定数項についても保持しておいて、点と一緒に操作しちゃえばいいことに気づいて事なきを得た。アフィン変換か、なるほど。かなり実装めんどくさかったけどバグらせなくてよかった。
C - Mandarin Orange
O(N2) しか思いつかなくてとばしたけどしばらく考えてもO(N2)しか思いつかない。3000人以上通してるし、O(N2)が間に合うんだろうなーと思って通した...まあ、O(N2)を落としたかったらN <= 105 とかにしますよね...結局ここで順位が決まってしまった。
F - Sugoroku2
期待値DPしか思いつかない。遷移を考える。振り出しに戻るをどうにかしないといけない。え〜どうすんねんってなってたらおわった、くそう...
コンテスト後に解説AC。わからんものはとりあえず変数におく、なるほど。一次式をもって遷移していく、なるほど。初めて見るタイプの問題で面白い。
ABC190(1/30)
43:40 6完 1ペナで、レートは1854 → 1913 (+59)。やったぜ
D - Staircase Sequences
苦手なタイプだけど式変形の選択肢がほとんどないのですんなり解けた。よかった。初項a、項数mとして2N/m = 2a + m - 1なので、mは2Nの約数しか有り得なくて、両辺の偶奇のつじつまが合えばおっけー。
E - Magical Ornament
はい、ダイクストラしてbitDP。ダイクストラで間に合うか心配でBFSするか迷ったけどスピード重視でライブラリを貼るだけのダイクストラでいった。間に合ってよかった。
F - Shift and Inversions
kが1増えると先頭の要素が末尾につくだけなので、転倒数への寄与が簡単に出せる。あとは初期状態の転倒数をセグ木を使って求めて、おわり！ってやったらWAがでた。Fだし、そんな簡単なわけないか、と思って順位表を(このコンテスト中初めて)見てみると、Fがたくさん通されていて焦る。よくみるとオーバーフローしてたので直してAC。この時点ではpredictorくんはが2400パフォを示してくれていてかなり興奮したが、ペナの5分を待つ間にみるみるとパフォが落ちていき、結局60くらいパフォが落ちてしまった。とてつもなく長い5分間であった。
修論
本文を提出して、発表会も無事終わり、今まさに審査を待っているところ。あんなに修論が終わるのが待ち遠しかったのに、いざ終わってみるとやるべきことがなくなって困る。とりあえず飲酒した。
まとめ
とりあえず修論が終わってかなりハッピー。なんかレートも上がっててハッピー。
2020/01/20
PUI PUI モルカー
Solved By kkktym
Topcoder: 0
Codeforces: 241
AtCoder: 1505
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1818
ARC071F - Infinite Sequence
Twitterで話題になっていたので解いた。適当に実験してみると2以上の要素の後ろに2以上の要素が来たらそれ以降は1通りになってしまうことが判明する。DP[i] := AiとAi+1に好きな数字をいれても良いようなAi-1までの数列の通り数。がわかればいけるので区間加算セグ木とかで殴るといける。気づかないパターンとかもあって時間がかかってしまった。
ARC092E - Both Sides Merger
大昔に嘘を投げてWAを出したきりだった。久しぶりにチャレンジしたらまた嘘を投げてしまった。嘘に気づいてから実装がめんどくさくて1週間くらい放置しちゃった。実装して投げるも、WA。なんかテストケース名がヒントになってしまってデバッグした。くう...
まとめ
今日はちょっと疲れた
2020/01/19
大喜利のコツ、その1 : お題をずらす
Solved By kkktym
Topcoder: 0
Codeforces: 241
AtCoder: 1504
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1817
ABC027C - ABland Yard
AにもBにも向かえる頂点のみで構成された誘導部分グラフが作れれば良い。AもしくはBに向かえない頂点はいらないので消す。消したことによって、新たにいらない頂点が発生することがあるのでそれらも消す。BFS的に見ていけば計算量が爆発しない。残った頂点が存在すればYes。
学会アブスト
なんで3月の学会に出ることにしちゃったんでしょうか。
まとめ
大喜利は瞬発力
2020/01/18
月曜日、一番好きな曜日です
Solved By kkktym
Topcoder: 0
Codeforces: 241
AtCoder: 1503
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1816
ジャンプ
2週間ぶりのジャンプ。実はジャンプが大好きで大学に入学してからの七年間は毎週買って全ての漫画を読んでいる。
呪術廻戦
盛りだくさん。九十九由基！退屈が裏返る予感がしてきたぜ
ロボコ
スラダンが好きすぎる。今のジャンプで一番面白い。
ワンピース
今週めっちゃ面白かった。ローが体内から医術的な死を与えてやるぜ...っていいながら落石で攻撃しててダメだった。
モリキング
おわっちゃった...でも綺麗におわったのでヨシ。ありがとう！またいつか！！
新連載
次号、松井優征新連載じゃん、やったー！篠原健太もおるし、ジャンプはじまったな
修論
え？もう来週提出ですか？
まとめ
久しぶりのジャンプは滲みる。精進？？？
2020/01/16
キーエンス プログラミング コンテスト
Solved By kkktym
Topcoder: 0
Codeforces: 241
AtCoder: 1503
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1816
ACRate: 1888 -> 1866
キーエンス プログラミング コンテスト
ABC 3完 (60:55+2ペナ) 冷えた、あかん
A - Two Sequences 2
Cn を決める際に新たに An と Bn のみチェックすればいいだけということはわかる。Cn = max(Cn-1 , max(Ai)*Bn) (1 <= i <= n) なので、Aの最大値を保持しておけばできる。
B - Mex Boxes
非常にこどふぉっぽさを感じた。まず 0 の数が X 個 (<= K) だった場合 K - X 個の箱については 0 が表示されることが確定する。確定した箱については除いて次に 1 について同じように見る。なんか変な実装をして 1 ペナもらってしまった。本当にダメ。
C - Robot on Grid
マスの位置を状態に持ってそのマスに到達できる経路数を管理するDPで、書いてある文字に応じて遷移が変わるやつ。ここまでが典型で、あとは全ての盤面についての経路数を考えないといけないところがちょっと考えるポイント。遷移する時にうまいこと数えられないかを考える。例えば、あるマスから右に移動した時には移動元のマスより下にある空白マスについては通らないことが確定するので、自由に文字を選べることになる。空白マスの数を X とすると 3X を経路数にかけてあげればよし。前処理として、各マスの右にある空白の数、下にある空白の数を求めておく。サンプル 3 をコードテストにぶち込んで 1681 ms を確認！提出！→ MLE！？初めてMLEになってめっちゃ焦る。でもよく見ると 1024MB 制限のところを 1078MB だったので、ひと工夫でいけそう。DP 配列を使い回すことにして改造。 しかし、めっちゃバグらせて 20 分も使ってしまった...
D - Choosing Up Sides
一回のチーム分けで同じチームになるペアの数は Comb(2N-1, 2)*2 増える。全ペア数は Comb(2N, 2) なので、この最小公倍数をとりたくなる。すると結局、(n, m) = (2N-1-1, 2N-1 ) となることがわかる。これはもらったぜ！と思ったがここからが本番で、うまい構築が全然できずに死。 こんなのは綺麗な簡単な構築法があるはずなんですよね、手でがちゃがちゃやるんじゃなくてそれを考えるべきだった...
ARC108 D - AB
コンテスト前にウォーミングアップを兼ねて通しておいた。場合分けをすればいいことはもう知っていたので、した。A と B の対称性をうまく処理できなくて WA が嵩んでしまった。
おさんぽ
たまたま家の近くに哲学の道があるので散歩した。もう inf 回散歩したけど、来年からできなくなることを考えると既に郷愁の念で胸がいっぱいです。
まとめ
結構気合を入れて参加したコンテストで冷えて悲しい。でも最近明らかに高難度が通せるようになってきてるのは確かなので気にせずがんばる。
