幾何系の問題。線分がいっぱいあってそれを原点から半直線で全て貫くときの最小の貫く回数を求める。 端点だけ考えればいいというのはこういう問題の常套手段。 角度でソートしてあげてあとはなるべくたくさん貫くように貪欲に。 ただ、貫きをはじめる場所に…

天下一プログラマーコンテスト2015の予選がもうすぐだったので練習がてらやってみました。 C問題以降はどれも難しかったし、解説なかったから辛かったですね…。文字列に'*'が入った集合がわたされて、それらを全て満たす最小の集合の大きさを求める問題です…

なんか知らないけど、この前のupgradeしたらaptが死んで更新ができなくなりました。 ということで今日絶対直すぞ！という意気込みのもと頑張ったんですが、最終的に昔先取りしてインストールしたlibstdc++-arm-none-eabi-newlibが悪さしていたようです。remo…

これはできなかったのが悔やまれる…。 N人(身長がバラバラ)が並んでいて、i人目に関して、その人が前を見た時に見える人の数を出力する問題。問題を簡単化する。 普通に考えるとi人目に関して、それより前のj人目を見て、そのiとjの間に二人より大きな人が存…

ある文字列を作るために回文を組み合わせるのだが、その回文の長さに応じてコストがあり、そのうちで最小コストの組み合わせをもとめる問題。普通にやるとdpでO(N^3)。 その文字列が回文であるかどうかを判定するテーブルを、文字列のcenterから広げていくや…

多分自分初めてリアクティブ形式の問題やりました。すごいデバッグしづらい…。問題は、50個以内の頂点がある木(辺はわからない)を与えられるので、100回以内の質問(こことここの長さは？)で木の直径を出力せよ、という問題。いや木の直径の求め方なんて知ら…

1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数を求める問題。 これって冷静に考えれば重複組み合わせだからcombination(n+k-1, k-1)じゃん… なんかちょっとむずかしいことしてみたけど結局求めているものは一緒です…はぁ… const ll mod = (ll)1e…

最短経路の組み合わせの数を求める問題。 完全に発想が凝り固まっててすごい時間がかかった…。頭の中で考えてるうちは、普通に始点からつながっているところの組み合わせを更新していくだけじゃ無駄に数えてしまいそうだなぁとか考えていたけど、手を動かし…

dpなんだけど、かなり上手くやらないとTLEする難しい問題。dpは現在の状態を上手く簡単に表すことでいろんな場合を統合して扱うものなので、今回も現在の状態をより簡単に表す方法を探さないといけない。'0'を-1, '1'を+1としてグラフにして見ると、これって…

モーターの種類が個人的にゴチャゴチャしてきたので一回まとめます。直流と交流 直流(DC) 電圧に対しての回転特性が安定していて制御しやすく、一般的には安価。 ブラシや整流子が入っているのでノイズや機械的な劣化が問題になりやすい。 また特徴として、…

回路について知らなさすぎるので、忘れないように用語をまとめてみる(STM32の話多め)。CAN Controll Area Networkの略。相互接続された機器間のデータ転送に使われる規格。ロボット分野に置いても使われる。二本のデータ線からなり、電圧の差動によってデー…

初期点群が与えられ、平行移動、回転、拡大をしたあとの最終点群が与えられたときの拡大率を求める問題。最近、こういう問題にはこれを考える。こういう問題にはこういうアプローチが多い。みたいに頭の中でカテゴリ化していた自分としてはイレギュラーで、…

風船が上がっていくのを撃ち落としてなるべく撃ち落す風船の最大の高さが最小になるようにする問題最近こういう問題多く見る気がする。 最大、最小を求める系の問題である程度値が大きくて時間足りないよぉ> ある高さ以内で撃ち落とせるかを判定して、それを…

盤面のある行とある列を足してKとなる組み合わせの数を出力する問題。 すごい簡単そうなんだけど、普通にやろうとするとO(R*C)でR,Cが10^5なのでTLE どう考えるかというと、盤面ではなくて、飴のあるマスに関してだけ注意を配る。 単純に足し合わせがKになる…

頂点1からその頂点にもどるとき、同じ道を使わない最短経路の最小コストを出力する問題。ダイクストラとかを変形して使えないかなぁと考えたけど無理。 なんとかして最短経路問題に落ち着かせられないか。頂点0に直接つながっている頂点を2つ選んで、その2つ…

もはや蟻本ではないけど、アルゴリズム関係は全部蟻本カテゴリーに入れてしまおう。ゲーム木探索をするときの基本的な方法についてまとめてみる。 minimax法 自分は評価関数が最大になる手を打ち、相手はこちらの評価関数が最小になるように手を打つ。negama…

ゲーム木の問題。 この前も同じのやったんだけどやっぱり考え方がいまいち上手く行かない… こういうので大事なのは、最初からやっても大変だから、一番最後から考えよう、という発想。 つまり再帰的に計算する。あとでゲーム木探索について軽くまとめようか…

辺eにはコストd(e)と容量c(e)が定まっていて、sからtへ流量Fのフローを流したときの全ての辺の流量×コストの和が最小になる時の費用を求める問題。これは単純で、最大流のときとほぼ同じです。残余グラフを考えて、そこでコストを考慮して最短路に沿って流せ…

考察系の問題。 辺を順番に塗っていき、折り返してもう一度塗り直すことができる。こういうときの常套手段として、過去から遡れば、辺の彩色は一度でいいという、つまり塗り直す必要は無いという性質がある。また、これより、分岐の時も何も考えなくていいこ…

試験が残り一つなので適当に蟻本を読んでみることにした。 最大流 …グラフにおいてs(source)からt(sink)に水を流したときに最大どのくらい流せるか？蟻本にのっていたように、最初にdfsでsからtまで限界まで水を流す。 その後、水を押し戻したりして最大にな…

簡単なのにかなり時間がかかった。 なぜかWAが少し生えるのが不思議だったが、最初はlen()がintになっていてオーバーフローしているだけだった。long longに直したのでもう大丈夫… #include<bits/stdc++.h> using namespace std; #define len(v) static_cast<long long>(v.size()) #def</long></bits/stdc++.h>…