class ListNode(object): def __init__(self, key, val): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.head = ListNode(-1, -1) # 新しいほう self.tail = ListNode(-2,-2) …
作ったアプリが動かず、Twitter API から 406 が返ってきていたので、リクエスト不正なのでパラメータ作成周りのコードをずっと調べてたのだけど、問題はDBの方だった。 MongoDBに作ったテーブル名が、pollsのつもりだったのだけど、polssになっていて、レコ…
目的 Go書きたい&ソケット通信でなんか作ってみたかった(現職では他社システムから叩かれるAPIをつくっていて、ソケット通信に関する知識がないため)。 Goでサーバ立ててチャットアプリ作って、Googleとかを利用した認証機能を作って、アイコン画像アップ…
2章 宣言的コード:SQLクエリのような、「結果をこのような形でください」というような依頼。裏側で処理をどのように行っているかは気にしなくてよく、CPU利用などのその時に適した最適化なども期待できる。一方で、既存の命令セット(という表現はよいのか…
はい
唐突にやったこと記録を付け始める 今週やったこと ・カジュアル面談を受けた ・「応用技術者合格教本2020」を7割ぐらいまで読んだ ・「コンピュータシステムの理論と実装(nand2tetris)」をやり始めた ・「達人に学ぶDB設計徹底指南書」を半分ぐらい読ん…
問題ページ atcoder.jp 愚直解L以下の全a,bに対して、a + b <= La xor b = a + bになるか見ていって、条件にあうものを数え上げる。計算量は O(N^2) で、最大でa,bそれぞれ 10^5 通りぐらいあるので、間に合わない 愚直解の良くない点として、例えばL = 1111…
問題ページ atcoder.jp 愚直に考えると、0~N-1の範囲で、部分文字列の左端と右端を選んで、その部分文字列が P で割り切れるか、全ての(左端、右端)の組で判定する。計算量はO(N^2)で、N <= 2*10^5 より間に合わない。 計算量をO(N)程度に落としたい。S=1234…
コンテスト中のミスが目立つので、解くときの手順書を用意した。 個人的に、以下のミスが目立つ 問題を読み違える 制限を見忘れて、方針を間違える typoや使う変数を間違える ミス→焦る→ミス の無限ループ 実装に入る前 手はキーボードかメモ以外に置かない…
今日も灰灰茶緑水水。 問題ページ https://kenkoooo.com/atcoder/#/contest/show/32e8a4f0-132c-4d2d-84d6-d3b9daaf124a 緑までの4完。Static Sushiが難しかった。6問目も後で解いておく。 3問目 atcoder.jp 解けたけど時間がかかってしまった。RLの部分に…
今日も灰灰茶緑水水。 https://kenkoooo.com/atcoder/#/contest/show/6c335dc6-7c7e-446c-90fc-92680f984c65 誤って茶の問題を飛ばしてしまった。 問題を見るに二つの紙幣の数を全探索(残りの紙幣はNから引くとわかる)で間に合うはず。 集中力切れで水の二…
競プロの練習に、できるだけ毎日バチャコンをやることにした。いつまで続くかな? 難易度は、灰灰茶緑水水で、緑までは早解き&水もなるべく解く感じの練習 問題 https://kenkoooo.com/atcoder/#/contest/show/2bc092d1-573f-40db-a225-e9fad66e6d91 問題1 …
コンテスト中に考えたこと A_i <= A_i+1 N,M <= 10 なので、雑に全通り考えると1010 <- 間違い 得点の高いものから貪欲でいけるかも?試してみるか <- まずは証明しましょう どうすれば解けたか A_i <= A_i+1があるので、単調非減少だから、 1010 ではない …
難しかった。 [ポイント] ・123456789みたいな数字について、12345 = (123456789 - 6789) / 10**4 の発想 - これめっちゃ頭いいと思った - 累積和ではないけど累積和風味の発想がおもしろい ・余りの問題は、計算過程から余りをとっておくと高速化できてよい…
転職するぞ!
「失敗」に関して、最近なんとなく思っていることについてメモ。 失敗は不可避不可欠 失敗は避けられない(永遠に成功し続けることは不可能) 失敗しない = 過去の成功パターンの繰り返し -> 改善や進歩がない 変化しない = 停滞 = 相対的に後退している 失…
・N<=15なので全探索可能 ・与えられる証言について、不親切な人の証言は参考にならない ・グラフっぽい構造ができそうだからといって、なんでもグラフにするのはよくない まず問題の考察をするときに、 ・全探索は間に合わないかどうか を考えて、間に合…
最近キョウプロを初めて一か月ぐらいで購入してすぐに投げた蟻本をやり直していて、2部グラフをやったので問題を探して挑戦した。 問題読んだけれども2部グラフどこで使うんだろうってなった。 解説読むとすごい分かりやすかったが、偶数個離れたところに…
チャンネルごとの状態が録画中or録画していないなので、各時刻ごとに全チャンネルの録画or未録画を求めて、最後に各時刻を見ていって一番録画しているチャンネルが多いタイミングの録画チャンネル数が答え。 チャンネル数が30と少ないので10^6オーダーでpyth…
Dまでの4完だったが、Dを解くのに時間をかけすぎた。 反省するべき点はあるけれど、実装力と論理的思考力はそこそこの水準になってきていると思っているので、うっかりミスとかを減らしていくことでどこかで飛躍的にパフォをあげられる気もする。また、Dは時…
gRPCとは そもそもRPCとは Remote Procedure Callの略。ここでいうProcedure=手続きは関数ぐらいの意味合い。 雑にいうと、ローカル環境で実行を命令した関数が、実際は別の環境で行われて処理の結果だけ享受できる感じ。 ローカルで関数を動かしてDB側でク…
以前解いたときは、i番目までのカードの中からj枚カードを選択するとして、i番目をj枚目として選ぶときに合計がj*AになるものをDPで数え上げた。が、このやり方だと3次元配列になってややこしいので2次元で何とかしたかった。 prd_xxxさんの解答が行数少…
・相手の取得するマス目を減らすように行動する→相手よりそのマス目に近ければ取得できる ・DFSするときは再帰の回数を増やしておく(いつも上限に達してRE出てから気が付くので気を付ける) atcoder.jp
問題は人のグラフを言語のグラフ(辺?)を使って全員をつなげるか、みたいな感じでUnionFindですべて同じUnionにできるかどうかなどで判断できると考えた。 今回は愚直に人を言語の辺でつないでいった。最初はdequeを使っていたが、dequeを使っても何度も何…
・後ろからDP ・部分文字列がかぶってはいけないのでmax(dp[i][j], j - i)でうまいことかぶらないようにする ・pythonで二次元DPはデータ数によるが遅くて間に合わない ・重要な部分だけ取り出せば、DPをやめて配列操作を削除できるかも 難しいけど学びは多…
その時最大の値を //2 すればいいよね→とすると計算量がO(NM)で解けなくね? っとなって死んだ。 毎回最大や最小の値が必要な場合、優先度付きキュー(pythonだとheapq)があるのでこれを使えばいいことが分かっていれば瞬殺できる問題だった。 heapqは子が…
editorialを読んでなるほどわからんとなって解説放送をみてどういうことだってばよ、となったので人の解答みたり手元で適当な数字をいじってなんとなく理解できた。 5678で考えると、先頭から見ていくときに 5 mod 13 : 5 56 mod 13 : (5*10 + 6) mod 13 ~~~…
最近300~500点問題でDificultyが1000~ぐらいの問題を一日2問解くみたいなチャレンジをやっていて、毎日学びがある。python高速化周りの記事を書こうかなとも思ったのだけど、タイトルの問題で結構感動したのでこの問題について記録しておく。 最初の提出はこ…
お菓子の個数の累積和をとっておいて、lとrを動かして、累積和の差分のmod Mが0になるなら、均等にお菓子を分けられるのは気が付いたので愚直に2重forループでやってTLE。データ数的にTLEになるのは分かっていたけど atcoder.jp で、そこからうまいこと計算…
in ~~ でやると100msだけ早くなったがまだ遅い。collectionsとか使う方がいいのだろうか atcoder.jp