強くなりたい

毎日無意識に生きてて良くない

頭痛

昨日は頭が痛くて21時頃からずっと寝てた、おかげで今朝には治っていたがそのせいでタスクを消化できなかった、、

昨日の頭痛は特に酷かった、吐き気がするほどの頭痛は久しぶりだった。

今日はDijkstra法を実装した。1発でACしたので嬉しい。しばらくは最短経路問題とグラフの問題を練習していこうと思う。(あと余力があればDPも)

星4以下埋めが終わった

典型90問の星4以下の問題を全て解いた。いやー星4以下だけでもかなりボリュームあったなーって思う。特に043と079は難しかった(どっちも解説AC)

ただ全部写経はせずにACとれたからきっと成長してるはず、夏までに入水したい。

明日からは星5以上の問題を解いていく、おやすみー

典型90問 061~070

061 - Deck(★2)

dequeを使うのかと思ったけど中央部分へのアクセスが重かったことを思い出したのでappendをうまく使う方法で実装した。

たしかinsertは遅いんだよなっておもったから上側と下側の配列を別々につくってappendで挿入の操作を書いた。 AC

063 - Monochromatic Subgrid(★4)

Hの制約が小さいことに着目してbit全探索。 途中で配列のコピーをとるときに参照渡しをしていたせいで何回かバグらせた。

deepcopyを使うことで解消した。

AC

064 - Uplift(★3)

階差の数列を作ることで土地が隆起(沈降)した場合にそこでの高さをすべて変更する必要がなくなる。アイデア自体は簡単だが添え字がちょっとややこしい。

AC

Submission #31942523 - 競プロ典型 90 問

10進法からn進法に変換する関数をネットから取ってきたらWAになってしまった。

また気を取り直して正しそうな関数をもう一度とってきたら次はコーナーケースのN=0の場合に引っかかってしまった。

このあたりは自分でライブラリを作っておいた方がいいかもしれない。

AC

典型90問 051~060

052 - Dice Product(★3)

分配法則の式変形を考えるともとめるのは

 \displaystyle
\prod_{i=1}^N \left( \sum_{j=1}^{6} A_{ij}\right)

AC

055 - Select 5(★2)

愚直に実装しても間に合う。

AC

058 - Original Calculator(★4)

 10^5 で割ったあまりを考えることと、Kの制約がかなり大きいことを加味すると周期性を考えればよいことがわかる。

AC

ふがいない

今日の講究の発表はふがいない結果に終わってしまった。

命題を示している途中に先生に「それ標数pの場合はどうなりますか?」って言われて何も答えられなかった。本当に情けない。

あと最初に勢いよく飛ばしすぎて途中からバテてたし、次はもっとうまく発表できるように準備しよう。。。。

講究の準備

講究の準備がやばい!!いやちゃんとやってはいるんだけど2時間で発表しきれなさそうでやばい。

拡大体の定義から入ってガロア対応まで示すとか、これ下手したら一学期分の連続講義でやる内容じゃん……。明日が不安だ。

演習問題でもアイゼンシュタインの既約判定法使う問題出てきたし、さすがにこれは事実として認めていいか……?これを証明してたら絶対間に合わん。俺の後に発表する人に迷惑かけてしまう。

とりあえず発表する内容は頭に入れたけどどうなることやら。明日は起きたらまた発表準備する。おやすみ。

典型90問 041~050

042 - Multiple of 9(★4)

Kが9の倍数であることとKの各桁の和が9の倍数であることは同値。

さらにDPテーブルを次のように定め、遷移は各桁の最高位の数に着目して考える。


dp[k] = (各桁の数字の和がkであるような自然数がいくつあるか)

AC

043 - Maze Challenge with Lack of Sleep(★4)

01BFSというやつらしい。かなり苦戦した。 下の記事がめちゃめちゃわかりやすかった。

01-BFSのちょっと丁寧な解説 - ARMERIA

またそのまま書いてもギリギリTLEするので入力の受け取りを工夫する必要があった。 AC

well-defined.hatenadiary.com

044 - Shift and Swapping(★3)

右方向へ配列をシフトする操作を愚直に書くと計算量が膨大になるので、それをメモするところがポイント。

AC

046 - I Love 46(★3)

46で割ったあまりでそれぞれの数字が何回登場したかを記録しておけば全探索できる。

AC

048 - I will not drop out(★3)

問題文を言い換えると1分でA_i-B_i,B_i点の問題が解けるということなのでこれらをまとめた配列を降順にソートして上からK個分の合計得点を出力すればよい。

AC

050 - Stair Jump(★3)

見るからにDP

AC