かっつのメモ帳

主に競プロ　時々日記

2020年12月第1週目

日記

今年も日記付けます。12月ポエム投稿をしたくなるのは何故？

2020/12/01

日付変わるタイミングでECR99があった。結果は微妙でBで焦って1ペナ出した分Cで慎重になってしまって踏んだり蹴ったりという感じ。E問題で TLE/WA のhackが多発してた、本番中詰めてた方針は3分探索なのでダメみたいですね…

Yukicoderのアドカレも今日から。12月を実感してしまうな。今年は解けそうな奴は積極的にチャレンジして行きたい。

12/01出題 色々ゴタゴタしてたのは置いといて、問題は普通に面白かった。dp\lbrack i \rbrack \lbrack j \rbrack から、dp\lbrack i+2 \rbrack \lbrack j \rbrack への遷移(同じ要素を2連続で使う場合を除く遷移)の係数で少しハマってしまった。

今日は材料力学の演習があって、ただでさえ前期落としてしまったのに今季も講義動画溜めていてかなりマズいので視聴を進めようかなあとか思いつつ書いてます、今。

↑上の文章書いていたのが12/1の朝4時ごろで、今書いてるのが12/2の朝5時。普段やらないことをやっているので溜まるのはそれはそうなんだけど、昨日のことを思い出しながら書くこの時間いる？ってなってしまう。けど日記って夜寝る前その日あったことを振り返りつつ書くイメージがあるから、僕の生活習慣ではこれが在るべき姿なのかもしれない。

昼前に起床。3限の授業に出る。機械学習のkiも分からない人間なのでアレなんだけど、講義資料の実装を追っていってもフワフワした感じでどこか身に入らない。実際に自分で調べながら手を動かしたらまた変わるのかな。とはいえ1週間の中でも楽しみにしてる講義なので、ちょいちょい他の事の手を動かしながらも真面目に出席。

5限が上で言及した材料力学の演習なため4限の時間に少しでも講義動画を進めるべきだったんだよな。結局yukicoderのアドベコンのFastest狙いとc++でゴルフをしていたら4限が終わっていた。c++もまだ縮める余地はありそうだけどこのままだとゴルフは険しそうだなと感じる。

5限の演習。同じサークルで同学科の人々と久々に通話をする。5/6が講義放棄病を拗らせていて、お終い。4限に講義動画を見たというtosuke先生のノートが簡潔にまとまっていて分かりやすかった、僕も何らかの形で手元にまとめておくべきな気がしてきた。

演習は最低限の出来、って感じ。情けないぜ。

何個かレポートが返却されていたので確認する。概ね自分が把握してたミスだったのでOK。一個だけ見るのが不安だったレポート(時間配分ミスって提出1分前に提出することになった)も良好なフィードバックを貰っていたので一安心。

2020/12/02

寝落ちしたり風呂入ったりしていたら日付が変わっていた。Shortestが取られていて、それはC言語による実装だったので僕もC言語でコードゴルフやってみようかなと思う。大学一年生の時の講義以来にCを書いた。軽く調べると色々テクニックが存在していて、かなり面白い。つい夢中になって自分の書いたコードと睨めっこしていたら4時になっていた、お終いです。

少しずつ発見があってコードを縮んでいく過程がかなり楽しかった。初め書いた295Byteのコードから279byteまで縮んだ。これ以上縮まないだろ！w→いやここの変数使い回せるから2Byte縮むわ…みたいなことやってると無限に時間が溶けて危険。あと夢中になると他のことに手が回らなくなるので今課題がピンチ。

結局273Byteまで縮めて課題に手をつけた。

機械製図法…今週の課題はCADを使わずに寸法許容差の表を読み取るだけの課題で軽かった。教科書読み進めるやる気を出すのが大変だったが、始めたら簡単な計算をやるだけだったので難なく終わった。

工数…なんかこっちも軽かった。定数変化法を用いて微分方程式を4問解けば終わり。

提出当日になって課題openして軽さに救われているの良くないけど目先の安堵が先に来てしまう。

リクエスト(？)があり、毎日更新することになった。見られるの恥ずかしいのでTLに流すのは辞めておこうかな。

課題をやっている間に件の問題が大幅に更新されていた。273Byteでひいひい言ってたら240Byteを容易く達成されていて、その後227byteまで縮められていた。

わざわざ反応して頂いて嬉しい(単純)　折角なので印象に残ったテクニックのメモを少々。

入力

N K X Y

A_1 A_2 … A_N

のような入力を受け取りたいとする。

普通の実装　128Byte

int main(){
    int n,k,x,y;
    scanf("%d%d%d%d",&n,&k,&x,&y);
    for(int i=0;i<n;i++){
        int a; scanf("%d",&a);
    }
}

僕の書いたコード(scanfの返り値を有効活用)　75Byte

n,m,x,y;
main(a){
    for(scanf("%d%d%d%d",&n,&m,&x,&y);~scanf("%d",&a);)
}

tailsさんのコード　67Byte

n,m,x,y;
main(a){
    for(;~scanf("%d",&a);)n?:(n=m,m=x,x=y,y=a);
}

感動した。scanfはどうしても嵩張るのでまとめて何とかならないか、と思っていたらこんな解決の仕方があるとは。パズルっぽくて好き。更に三項演算子の中間項に別処理を挿入出来るので無駄がない。

実際最短コードではこう。

n?k-=d[a]?0:++d[a]:(n=m,m=x,x=y,y=a);

有名テク

さっきのscanfの返り値を利用する奴とか、こういうの。

code golf入門/C言語編 - プログラミングスレまとめ in VIP

このサイトで色々勉強になった。

その他

for(;x<N;)r+=(x<=y)*d[i+x++];

こういう事がしたかった。条件式に

x<N&&x<=y

を書くのは筋が悪いと思っていた(冷静になるとこっちのが1Byte短い)が、bit演算として捉えると&が一個で良いですね。これで2Byteの短縮。

for(;x<N&x<=y;)r+=d[i+x++];


不規則な生活リズムで15時ぐらいに寝て夕食のために一回起きてまた21時頃まで寝るみたいな生活をしていた気がする。

12/02 出題　期待値の式知らなくてWolframに投げてしまった、前者の期待値が p に一致するの勉強になりました。

2020/12/03

yukicoderの問題を見る。かなり眠かったけど翌日は違うことやりたいと思っていたので寝る前に片付けたいと考えていた。結局考えていた解法が嘘だったので不貞寝してしまった。

8時起床　生活習慣、手に入れちゃったね。

週末学内の競プロerでLT会をやろうという話になっていて、その発表を担当することになっていたので朝からずっとスライドを作成していた。

熱力学…小テストの中身が基本的にお気持ち表明しんどい。1問目はまだ良いとして、2問目が授業で印象に残ったことを記述せよ、という問題で講義動画を見ていなかった僕にはしんどすぎる(1週間の公開期間みたいな講義動画見れた試しがない)。怪文書を生成して提出した。2問目配点が大きいらしくて驚いた、救済の意味もあるだろうがただ問題解かせるよりそういうのに重きをおく思想らしい。終了後のzoomで公開説教(？)みたいなのあって怖くて泣いてしまった。大人しくスライドを作っていた。

夕食はmugenさんとラーメンを食べに行った。久しぶりに競プロの話をリアルで出来て楽しかった。

今日スライド作成しかしてないな(気付き)

2020/12/04

気が付いたら3時で壊れた　TDPC-Tを解いた。

課題を終わらせてから寝ようと思い立った。

ダイナミクス…ほぼ講義資料の議論の丸コピでなんとかなる、まあ分からないよりはマシなんだけど……

寝ながらyukicoder 12/03の問題を考えていたら解けたので起きてまずこれをやる。

考察微妙に詰まってないところがあったが、O(N^{2})かけても大丈夫なので適当に誤魔化した。結果信じられないほどバグらせて、1時間もかけてしまった…インタラクティブのprintfデバックで毎回応答手打ちしてるの時間かかるので早い段階で切り替えるべきだったのかもしれない。が人間はこのprintfデバックで最後のバグが見つかると思い込んで手打ちで妥協してしまうんだなぁ

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

家族の夕飯の時間帯と僕の眠気のピークが被ってるので食欲があんま無くて険しい。今凄いお腹空いてるのにね

布団に突き刺さりながらきたまさ法を多項式のべき剰余と見なす話について考えていた、なんとなく理解が進んだかもしれない。

22時からの人権コドフォがあった。4完で微増。B/CがDiv2にしては難しくてびっくりした。E後で解き直す

2020/12/05

SRM794が25時からあった。Easy/Med共に考察要素があまりない実装問題だった。こういう実装の問題落とすの良くなかったなあ、Medは最後x座標ごとに見るべきところを、座圧した長方形のまま見てしまっていた

Medのupsolveをしてスライド少し書いて寝た

起きてスライド書いてた　理解の進みが悪くて険しい

ARC110に参加　1874→1889(+15)

ABCそこそこのスピード出せたのにそこからが良くないね。Dは普通に練習不足だった。Fの想定解面白いよね(これ最後の最後に思いついたんだけど実装間に合わなかった)

2020/12/06

起きてスライドを書いてた

BM法について興味を持ったので折角だし勉強してみようって思って発表テーマに選んだんだけど、理解が間に合いませんでした(完)　供養

LT会自体はかなり良かった。ICPCのチームメイトでもあるHyado、hotmanが発表して、そして弊学OBでICPC WF出場経験のあるimulanさんの話も聴けて大満足。

発表中のコメント追うどうしようかな、って思ってたんだけどcomment screenってのを教えて貰って導入したら案外良かった。

結果として11人も参加していた、予想以上の集まりにびっくり。やる気の問題にはなるけど、定期的にこういう活動もやれて行けたら良いね。

寝て起きてレポート消化してたらCGR 12の時間に。

C2の構築面白い(解けなかったけど)

E問題の言及で見かけた牛ゲー(？)履修した方が良いのかな

LT会終わったので競プロの溜まってるupsolveの方を今週は頑張っていきたいところ。