・N<=１５なので全探索可能 ・与えられる証言について、不親切な人の証言は参考にならない ・グラフっぽい構造ができそうだからといって、なんでもグラフにするのはよくない まず問題の考察をするときに、 ・全探索は間に合わないかどうか を考えて、間に合…

最近キョウプロを初めて一か月ぐらいで購入してすぐに投げた蟻本をやり直していて、２部グラフをやったので問題を探して挑戦した。 問題読んだけれども２部グラフどこで使うんだろうってなった。 解説読むとすごい分かりやすかったが、偶数個離れたところに…

チャンネルごとの状態が録画中or録画していないなので、各時刻ごとに全チャンネルの録画or未録画を求めて、最後に各時刻を見ていって一番録画しているチャンネルが多いタイミングの録画チャンネル数が答え。 チャンネル数が30と少ないので10^6オーダーでpyth…

Dまでの4完だったが、Dを解くのに時間をかけすぎた。 反省するべき点はあるけれど、実装力と論理的思考力はそこそこの水準になってきていると思っているので、うっかりミスとかを減らしていくことでどこかで飛躍的にパフォをあげられる気もする。また、Dは時…

gRPCとは そもそもRPCとは Remote Procedure Callの略。ここでいうProcedure＝手続きは関数ぐらいの意味合い。 雑にいうと、ローカル環境で実行を命令した関数が、実際は別の環境で行われて処理の結果だけ享受できる感じ。 ローカルで関数を動かしてDB側でク…

以前解いたときは、i番目までのカードの中からｊ枚カードを選択するとして、i番目をj枚目として選ぶときに合計がj*AになるものをDPで数え上げた。が、このやり方だと３次元配列になってややこしいので２次元で何とかしたかった。 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が０になるなら、均等にお菓子を分けられるのは気が付いたので愚直に2重forループでやってTLE。データ数的にTLEになるのは分かっていたけど atcoder.jp で、そこからうまいこと計算…

in ~~ でやると100msだけ早くなったがまだ遅い。collectionsとか使う方がいいのだろうか atcoder.jp

受講目的 業務では携わることのできない部分も自分で触ってみたかったから。業務ではGoでバッチ書いたりGoogleAppsScriptで社内向けWebアプリを作ったりしていて、Webアプリケーション作成に携わっても断片的にしかかかわれないため。 何を学べるのか anond.…

本番では解けなかったので解説見て解いた。優先度付きキューはほとんど触ったことないので発想になかった。別解の方はなるほどわからんなのでそのうち理解したい。 覚えて置きたい所 ・制限の厳しいものから選んでいくと見通しが立ちやすい（今回は残り支払…

明日は今日よりいい日にしたい。 明日は今日よりよりよい技術者になりたい。 最近はなんとなくそんなことを考えている。

def sieve_eratosthenes(n): nums = [True] * (n+1) nums[0] = False nums[1] = False for i in range(2, math.ceil(math.sqrt(n))+1): if not nums[i]: #iが素数ではない continue else: for j in range(i*2, n+1, i): nums[j] = False # iが素数ならiの整…

・円順列みたいな先頭と末尾がつながるものは、配列の後ろに先頭をappendしてあげるとやりやすい ・ごり押しより一般化したほうがデバッグが楽 ・最初に配列を確保しないで後から継ぎ足していくほうが楽な場合もあるが、計算量と相談 ・仮定を置いた部分が齟…

タイトルの通り。 例えばNodeという構造体にさらにNodeを持たせて木構造を作るとか考えるときに、ポインタでないNodeを持たせると、初期化時にゼロ値になるので、Nodeの中のNodeが無限に初期化され続けてエラーがでる。 時々やらかすのでメモ

考えたこととりあえず貪欲法的にポイントの高い寿司からK個選ぶ。選んだ中で小さいものを残りの選んでないネタの寿司のなかでもっとも大きいものといれかえる、を繰り返せばいいはずとは思ったものの、・残ったものの中で選んでないネタの得点の一番大きい寿…

Cまでの3完。Cは最初深さ優先で解いてTLEでたのでDPに変えた。ただ、N＝１，２のを考慮に入れておらず、それに気づかなかったため、何度もREを出した。 発想力と実装力は以前よりよくなってきたと思うが、細部に気を払えるように頑張りたい。特に今回は１，…

勉強してもすぐ忘れるのでグラフ系の実装や流れについて未来の自分向けに。 処理の流れ スタート地点を決める。スタート地点までの移動コストを０とする。 現在のノードi（スタート直後はスタート地点＝ i ）につながっているノードのうち、未探索かつ、最も…

現状の理解というか自分向けメモ いつ/何に使えるのか 物事のつながりを表す/複数のつながりをたどって大きな関係やつながりを表現するのに利用。 都市AからBまでXキロとか、AさんとBさんは知り合いみたいな。 考え方（どこを中心にとらえるか） ノードとエ…

業務でも使いそうなのでGo言語を学習し始めた。 とりあえずA Tour of GOをさらっとやったので、適当にCLIコマンドでも作ってみるか。 そのうちGo関連のメモも書こう。

問題的には→と↓の並べ方をnCrで求める問題なのだが、制限的にオーバーフローを起こすので回避する方法を調べた。 こちらのページのJavaのコードをpython化して回答した。 手法としては、分子と分母の積算の数値をリストの中に入れておいて、割れる部分を先に…

今日はあまり問題解けてないけど眠いから感想書いて寝る 考えたこと N=５０だから組み合わせは2^50なので全探索は絶対終わらない。部分点もらえるので深さ優先でとりあえずやってみる。 部分点はもらえた。一方で全探索しない方法を全く思いつかない。合計が…

ここ一か月でABC35~120のC問題に挑戦して４５からは自力で解けたか解説を見たかが残してあるので自力で解けてないものについて再挑戦する。 考えたこと 文字列は長さが１０までなので、数字の間に＋を入れるか入れないかで2^9通りなので、全パターン試して十…

再帰的な処理は多少かけるが、深さ優先探索を実装することがうまくできないことが多いので、すこしまとめてみた。 どんな時に使えるのか 「ある物/配列要素に対し操作1,2,3...のいずれかを行う（選ぶ/選ばないなど）」のパターン全列挙 いくつかの文字の中か…

1:AtCoderを始めた 就職して一年たったが、現状に危機感を覚え始めたため、外部実績として示せるものを作りたい＆情報科学専攻ではないため、アルゴリズムや計算量などの考え方に疎いので勉強したいということで、AtCoderをはじめた。qiitaやtwitterを見る感…