かっつのメモ帳

主に競プロ　時々日記

2020年12月第2週目

日記

2020/12/07

upsolveなど

てんぷらさんの証明が綺麗だった

二部グラフ&負閉路のないグラフであることが必要

a_i が 0 となる頂点を決め打って、その頂点を起点とした最短経路問題を解く　ワーシャルフロイド法で解いたけど、ベルマンフォード法適用した方が良かったかもしれない(負閉路の扱いで1ペナした)

組み合わせ的解釈は経験量が足りなかったので反省　次から落とさないように…

f:id:KKT89:20201207142159p:plain

それはそうなんだけど、毎回逆元計算してると重いので分母の値を別に計算しておいて最後の一回逆元を取るべき。

Problems見て思い出したように解いた。S_3 の始点と長さを決め打つと簡単な尺取りできる形になる。

大体やりたいことの見当はついてたんだけど重複なく数え上げるの難しいなぁとか思っていた。円環を切り開いて考える必要はなくて、円環のまま区間の切れ目となる頂点を考えるとスッキリと二項係数の簡単な式で表せる。

ド典型なんだけど、a<=bが満たされるようにswapして、aの昇順ソートまで覚えていて、aが等しい値についてはbの降順ソートをするとただの1次元LISになるっていうの毎回頭良いな〜って言ってる気がする。最後の1ステップがよく頭から抜ける。

後回しにし続けていた最小費用流を書いてそれで通した。

考察ステップ一個一個はかなり軽い。のに本番解けなかったのは、全部一まとめにして考えようとし過ぎたからな気がする。包除を適用して1次元の話に落としてから包除が見えていなかった。

寝落ちしたら一日が終了してた、どうして

2020/12/08

取り敢えず起きてyukicoderのアドカレを消化した。12/08 出題

終了後の解説を見たり、WUPCのtesterで似た話題を見たりしたので、操作への寄与回数が二項係数になることは覚えていた。ただまず偶奇に注目して二項係数の偶奇を調べれば1が確定出来る、ってことに気付くのにかなり時間がかかったし、操作列に13両方存在すれば答えは2と思い込んでハマってしまった(反例…313など)

そこから2で割ると元の話題に帰着出来る、確かにそうで一度認識するとそれはそうなんだけど難しかったなぁ。

本番で見た時muriyankonannとなっていたが、今見たら座圧やるだけだったので成長を実感　バグらせまくったけど

最小費用流で解ける。


昼の12時になったので流石に競プロ中断して3限の準備に入る。

とか言ってたんだけど急にアトランチスの謎のプレイ動画が見たくなって(？)、これ見てたら昼休み終わってた(草)

nico.ms

多分ほぼ最短ルートしか見た事がなくて、初見のコースが何個も見れて楽しかった。ゲームセンターCXを見て育ってきた世代です。

3限…普通に出席。2回後の授業からグループワーク開始らしい。

ねっとりとしたbitDP。上の桁から決めていって、適当にAとの絶対値が小さい方にdpを更新…とやっていたが、これでは先にdp[i][j]=100と更新した後にdp[i][j]=-100という更新が無視されるような事があって良く無さそう(実際落ちた)。なので

if(abs(dp[i-1][j])>abs(cost)){
  dp[i-1][j]=cost;
}

if(abs(dp[i-1][j])>=abs(cost)){
  dp[i-1][j]=cost;
}

上の2つの遷移を並べて値が良かった方を採用！としたら無事ACすることができた。正直まだ落とせそうな気がするけど、見なかったことに。


散髪に行った、特に用も無かったので真っ直ぐ帰宅した。

機械製図法の明日締切の課題があるので該当する講義動画を消化していくことに。寸法記入の課題かなりしんどかった記憶があるが、実際出来が悪かったらしくレポートに関する追加の補足説明+再レポートという形が取られていた。

多分採点の収集が付かなかったからだろうけど、割と時間かけたレポートが無かったことになるのは、辛い！でも何がOKで何がダメかを割と明確化されていたのは良かったな、感覚が身についてない状態で課題をやるのはしんどい。

夕食前に機械製図の課題少し手をつけて、その後は寝落ちを繰り返していたら翌日の朝7時になっていた。生活習慣の問題か体力の問題か分からないけど、こうやって日記にやったことをまとめると一日にやったことの薄さが明らかになる…

2020/12/09

起きてまず再レポートを終わらせた。

何かしらの比較関数で貪欲に取っていくのが正解だったとしても全然見当付かないな…と思って放置してたんだけどよくよく制約見るとNが小さかった。計算量の把握出来てないけどメモ化再帰書くと通る。

部屋1の扱いが面倒なので最後に見学出来ないことにして、そのままの数列と部屋1を末尾に持ってきた数列の2通りで解くと楽。いやそんなに変わらないかも。

もうこれはパターンマッチングで、前からの貪欲は難しい→二分探索で区間幅決め打って後ろから貪欲、で解いたけど別解で賢い貪欲法も紹介されていて面白かった。

問題自体は去年から把握してて、しんどいというイメージしか無かったんだけど今見たら全然そんなことなかった。(成長)感じるんでしたよね？

朝からチラチラ見ていた幾何交差に関するレポート(白紙)、内容がいまいち理解できないな〜と放置していて気が付いたら提出1時間前になってて流石に焦った。が、よく見たら数分で終わる内容だった。自信がない箇所があったものの、関連する教科書のページを一通り見ても解釈が変わらなかったのでこれで間違ってたら仕方ない、と思い提出した。

これは典型。一年前のコドフォで出題されて解けなかったのを思い出した。

日記をつけることの利点として、Twitterへの依存が減らせるという点がある気がしてきた(普段からTwitterに依存してなければそれに越したことはない)　タイムラインを見ることが癖になっていてこれはどうしようもないんだけど、ツイートに関しては後から自分の行動や言動を振り返りたいという側面があって、これは日記にすることで解決している。

実際ツイート感覚で少しずつこの記事を更新しています。TLが見るに耐えない時はこのようにして精神的安定を保っていきたい。

心を無にして微分方程式を解く課題をこなしていた。何も誇るべきことではないが、時間をあまり気にせず2時間ぐらい前から始めたら丁度締切5分前に提出が完了した。こういう時自分の時間感覚が正しかった！とちょっと嬉しくなるが、ギリギリに始めることに関しては何もメリットが無いので本当は辞めるべき。何よりギリギリ間に合わなかった時、努力量に対して負の感情が大きすぎる。そもそもギリギリの提出は印象が良くない。

こういう期待値の線形性を上手く用いる問題かなり苦手意識あるので、経験を多く積んでいきたい…

上手い貪欲で行けそうな気もするんだけど、制約的に想定されていそうな O(N^{3}) で部分集合を列挙するDPを書いた。

setで区間を管理しましょう。

二項係数を解説みたいにバラす方法覚えておきたい。実装サボってmodpowを多用したらTLEしまくって真顔になった。

完全に遅延セグ木ブラックボックス状態なんだけど、ACLの使い方調べて通した。流石に自前でも書けるようになるべきなんだけどまずACする手段を1つ覚えたということで…　手元環境でACL使えるようにしたパソコン力のあった過去の僕もありがとう…

f:id:KKT89:20201210011831p:plain

青dif終わり　遅延セグ木さんとお友達になるが今後の目標です。

2020/12/10

寝ながらACLのセグ木のことについて考えていて、あれだけでReplace Digitsが記述できるのかなり便利だな…という考えに至った。

前見た時？だったんだけど、今見たらギャグであることに気がついたので解いた。

起きたら5時間コンテストのお誘いが来ていたので早朝11時からチーム練が行われた。

チームとしての結果はイマイチ、そして何より個人としてのパフォーマンスが最悪で情けなくて結構真面目に落ち込んでしまった。問題について振り返るのは後日にする。

競プロ以外をやろうと思い立つ。放置してたHugo blogのデザインを弄りたいな〜と思い色々調べていた、HTML も CSS に関する知識は皆無なので取り敢えず他人のコードを手当たり次第眺めていた。よく分からないな〜と唸ってたらPCが固まって全てが嫌になって布団に突き刺さって、そのまま寝落ちした。

2020/12/11

9時頃起床。途中起きて消灯したとはいえ、寝落ちは電気代も無駄になるし睡眠の質が落ちるしで反省すべき。

悩んでいたアドカレのネタを思いつき、何も投稿出来ない状況は回避出来そうで一安心。

CBD…そうだね。取り敢えずまだヘラヘラしてても大丈夫なので放置です

2020年12月第1週目 - かっつのメモ帳

放置してたCBD今日なんか dictation test あるらしいよ？と連絡が朝から来ていて壊れる。現実逃避、開始。

午後、本当に任意のやる気が無くなっていて困ってしまった。動画を見ることぐらいはできるだろうと、丁度ツイートで回ってきた動画を視聴することにした。

youtu.be

CBD…油断してたらいきなり教員が現れてdictation test始まって困ってしまった。人生で英語を一度を真面目にやった事がないツケが常に回ってきています。

CF #682(Div2) に出た。ねっとりセットは、最高やな…！

なんかしんどい気持ちになってたけど、CFに出て一日を振り返ったら普通かな〜っていう気持ちになった。

2020/12/12

起きたら HTTF2021決勝オープンが始まってたのでOUPCまでの時間少し手をつけてみようかなと思い挑む。最小全域木に思いを馳せてコードを書いていたが、そこから手を動かせず14時前になってしまった。マラソンコンテスト対策興味かなりあるんだけど、まずアルゴ力がそもそもスタートラインに立てていない気もしてまずそっちの勉強を…という気持ちにもなる。

f:id:KKT89:20201213132302j:plain

jupiroさんと組んで6完20位。かなりチームとしてハマった感があって楽しかった。

  • B Guriko on Line

いきなり難しくて焦ってしまった。落ち着くとグーで勝った回数の偶奇が大事でそこを決め打てば、後は累積和を前計算しておく事により計算量が落ちて解ける。

  • D Intimate Slimes

前回までのスライムの最適なサイズを覚えておけば、その左右どちらにスライムが追加されたかで軸が動く方向が分かり、これは二分探索で求める事ができる。が、その後コストを求める部分の理解が出来ていない…

自分が今から理解するより実装交代して貰う方が速いと無理な頼み込みをする(あのソースコード渡されて続き書くの相当しんどかったと思う…)　僕のBITが 1-indexed で明らかにこれを触ったらヤバイと、2本BITライブラリが貼られる異常継ぎ接ぎ実装になったが無事通す事ができた。

  • E Xor Mart

2進のTrie木上で頑張れば行けそーと言葉で言うのは簡単。実装を一方的に押し付ける最悪ムーブ。通してくれて、ありがとう…

  • G Construction Set

残り30分で出来るか怪しかったが、マッチングパート以外は考察に抜けが無いことをEの実装待つ間に確かめていた。肝心のマッチングパート、どう考えても一般グラフの最大マッチングが求められてないか？となり唸っていた。冷静に考えるとこれは二部グラフなのでフローで解ける。が、冷静では無かったので検索で見つけたyosupoさんの一般グラフの最大マッチングを貼って提出したら通った(草)

早稲田勢の2人チームに勝てて、嬉しい！

CF#689(Div. 2)-F のupsolveを嫌な気持ちになりながらした。嫌な気持ちになったのは自分の実装が汚すぎて触りたくね〜と言いながらデバックをしていた為。

TLで見かけた COCI 2020/2021 CONTEST #3 にSRMまでの時間で出てみる事に。

  • Knijge

O(N^{2}) 回かけて良い制約なので愚直な方法で実装を頑張る。

  • Vlak

Trie木上でDFSをして勝利判定をする。

等で既出なのでコピペACは可能…　自力でも解法理解していきたい。

2020/12/13

SRM795が深夜2時からあった。EM2完で45位

Medのソートして -iしてソートして中央値求めるやつ、絶対典型なんだけど身につかないなぁ。三分探索で通してしまった。ちなみに引き算後ソートし忘れで大量のchal が発生していてレート的にはおいしい。

Easy はもっと速く出来るんだろうけど、まあ仕方ないかなぁ…って気持ち。

Hard がかなりTLで好評だったが、まだ問題に目を通せていない。

お昼過ぎに起床。今日締め切りのレポートを進めつつ競プロの問題をダラダラ考察するなどしていた。

木曜のチーム練で扱ったセットを2題復習した。

英語読解ゲーで、ここで私は苦しみました(本番Hyadoに投げた)

問題自体は簡単な全探索。

JOIの散歩という問題とほぼ一緒。毎回DP用のvector宣言するとTLEするのでグローバル変数を使い回すようにすると通った。

ABC185に出てアホみたいに冷えた　1889 → 1857(-32)

こういうセットで冷えると、情けなくて仕方ない。ABCの速解き対決みたいなの最近上手く行った試しがないな、毎回どっかで頭がバグる瞬間があってそこで順位表見て焦ってお終いになってる気がする。

早々にABC終わらせてレポートやる予定がほぼ90分丸々使ってしまった為、急いで書き上げる羽目になった。TOKIまでに無事提出完了。

TOKI Regular Open Contest #17　2160 → 2154(−6)

中盤のセグ木力が足りず…でもこれで出るの4回目だけどTOKI問題セット毎回面白い気がするな、制約の位置が見にくいこと以外はかなり好きなコンテストサイトだと思う。

航空材料学のレポートを布団に突き刺さりながら書いて寝た。