勉強してもすぐ忘れるのでグラフ系の実装や流れについて未来の自分向けに。 処理の流れ スタート地点を決める。スタート地点までの移動コストを０とする。 現在のノード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を見る感…

読み終わったらメモとか書く

自分で書いたときは、与えられたhをリストに格納し、左から０でない部分を探し設問のlに、次いでlから右に向かって一番初めに見つかった0の手前を設問のrとして、[l:r+1]の範囲で最小の値を見つけ、h[l:r+1]からその値を減算すると同時にansに最小値を加算す…

自力では解けなかったのでカンニングした。 考えたこと 375とか537とかの753数の頭に3,7,5のどれかを付け足すと簡単にできそう。 いや、3557も753数。ベースとなる数字が753数とは限らない。 とりあえず3,5,7を適当に並べた数字を作るか。でもその方法が分か…

解けた。 考えたこと 都市番号と誕生年をリストに順番にいれる 同時に辞書に都市番号をキーとして誕生年をリストで入れる 辞書の中の各都市番号の誕生年リストをソートする 全部おわったら、都市番号と誕生年のリストを頭から見ていき、都市番号については辞…

完敗。 C問題 連立方程式を解く感じかと思い込んだため、解けなかった。中心座標がそれぞれ１以上１００以下なので、全組み合わせについて試せるのは盲点だった。 D問題 探索範囲がM**0.5までで問題ないのを思いつかなかったため、TLEを抜け出せなかった。 …

考えたこと 偶数部分と奇数部分に分けて最頻値を取り出すとこまではすぐに思いついた。書き換えた後に両方とも同じ値になる場合をおもいつかず少し手間取った。 そのあと、同じ値になってしまった場合に偶数部分と奇数部分のどちらの書き換え先を変えるべき…

組み合わせの公式は覚えていたが、重複組み合わせの公式は完全に忘れてた。解き方はすぐに思いついたが重複組み合わせのせいでもたついた。 組み合わせ nCk = n!/((n-k)! k!) 重複組み合わせ 今回の問題の文脈でいうと、x個の数字oをn個のリストのマス目の中…

二時間近くかかった。 考えたことと試みたこと ある文字からある文字への変換表を辞書形式で保持しておいて一対一の対応になるか調べたらいけるやんと思う。 はじめは文字列Sのi番目とTのi番目が一致しないときだけ辞書に入れて、文字列S全体について変換表…