最短経路問題において、最短経路を通る時、その道を必ず通るか、通らないならば、コストをどのくらい下げれば通るようになるかを出力する問題。すごいバグバグしくて時間かかったけどなんとか通せた…。まずダイクストラ法をして、最短経路のコストを求める。…

M,+,-の3文字の列が与えられて、Mごとに数直線上のどちらかに移動し、+,-で点数を+,-していく。最後に原点に戻ってくる条件の元、最大の点数を考える問題。dpは一瞬で思いついたけど、それじゃあ絶対len(S) == 1e5という制約は満たせないのは明らかだった。…

この前TopCoderやってみたらDiv1に上がったのでとりあえずDiv1.Easy解いてみてなるほど、ってなったのだけ書いていきます。A,Bという数字が与えられて、A 試行回数がK=2000000000なので計算時間を短縮しなければいけない。 最初、何の根拠も無しにA,Bのpair…

一次元のbattleshipをやって、Bobがショットを撃っていった結果、Aliceが言ってることが矛盾する場所を探す問題。最近2分探索のイメージを常に頭の中に入れていたおかげですんなり解法が浮かんだ。 何番目までBobがショットを撃ってもAliceの言ってることが…

数列が与えられて、その中にある公比の3項の等比数列が何通り存在するか、という問題。 まぁmapかなんかで適当に管理して、数列の1項目,2項目,3項目が何通り存在するかを順に更新していけば一瞬で解ける。本番pretest7が全く通らなかった…オーバーフローだっ…

存在する六角形の辺の長さがcm単位で与えられて、その中に1cm辺の三角形をいくつ作れるか、という問題。 よーく考えたら、六角形の辺を伸ばしてあげれば、六角形は三角形-3つの小さな三角形という形になる。 はい終わり。これ思いつくの少し時間かかった…幾…

天下一プログラマーコンテスト予選A、難しすぎて意味がわからなかった。 ただ、この問題は気づけば一瞬で解けるので、発想が出なかったのが悔しい。高さH, 横Wの白と黒で表された絵、A,Bがあり、Aの一個の白or黒を反転させる、または隣り合った白と黒を交換…

AVRのデータシートとか読んでても基本が全然わからないのでようわからん。 ということでまた忘れないうちに用語をまとめてみる。EEPROM Electrically Erasable Programmable Read-Only Memory の略。不揮発性メモリであり、機器の設定情報などの管理に使われ…