記事一覧
yukicoder No.11 カードマッチ
問題解説H×Wのマス目を考えればよい。 #input5621 32 5 W = 5, H = 6, N = 2で,手持ちのカードが(1,3), (2,5)だとする。(1,3)とマッチするカードを図示すると以下の図…
ABC120-D Decayed Bridges(Union-Find)
ABC120-D Decayed Bridgesに挑戦した。 正直,なんかグラフだな,木を使いそうだなくらいで全然できなかったので公式editorialを読みました。 https://img.atcoder.jp/ab…
yukicoder No.11 カードマッチ
問題解説H×Wのマス目を考えればよい。
#input5621 32 5
W = 5, H = 6, N = 2で,手持ちのカードが(1,3), (2,5)だとする。(1,3)とマッチするカードを図示すると以下の図の灰色の部分。(赤マスは(1,3) )
次に,(2,5)とマッチする部分を追記すると
求めるるのは,この図の灰色のマスの個数である。そのために,灰色の部分を端に寄せると以下のように
yukicode No.8 N言っちゃだめゲーム
問題昔,古畑任三郎というドラマの中で古畑さんが犯人とやっていたのを見たのが,私のこのゲームとの初めての出会いであった。詳細は以下。
考察1(後ろから考える)n=30,k=5だとしよう。
1からはじめていって,5以下の数字を交互に宣言し,30を宣言した方が負けである。相手に30を宣言させれば勝ちともいえる。ということは29を自分が宣言すれば勝ちである。29を自分が宣言するためには,24~28のい
AGC034 A-Kenken Race
1.概要今日トライした問題は以下。
岩が2つ続いていたらダメ,というのが基本的な考えかた。問題文の制約からA<B<Dは確定するので,CがA,B,Dの間のどこに来るかで3パターンに分かれる。
1. A < C < B < D2. A < B < C < D3. A < B < D < D
2. パターン1 ( A < C < B < D )AはCに向かい,BはDに向かうので,A-C間とB-D間
Pythonのheapqとdeque
AtCoder ABC088 D Grid Repainting台風で外出できない連休だったので,家でAtCoderをやっていた。今回はこれ。
問題文を読んだ瞬間に,「あ,BFSだな」というのはわかりました。蟻本を読んでいましたからね!で,見様見真似で実装したコードがこちら
import sysimport osimport heapqINF = 10**5H, W = map(int,inp
Pythonの切り上げと天井関数
こつこつAtCoderで精進しています。今日はARC062のAtCoDeerくんと選挙速報をやっていました。
とりあえず解けたつもりで提出したら数ケースWAになったので解説を読みましたが,私の解釈では,解説と同じことをコードに落としているつもりでした。
そこで悪いとは思いつつも,テストケースをのぞかせてもらいました。
するとWAになっているケースの想定解と私の解はそれぞれ以下の通りでした。
ABC119-C Synthetic Kadomatsu
ABCの問題名って読み飛ばしちゃったりすることが多いですが,合成門松!ときました。うん,できない。C問題だから簡単かなと思ったけどよくわからない。こないだ蟻本でやったことを思い出したけどよくわからず。
で,解説を読みました。やはりdfsを使うようでした。でも解説読んでソースを読みますがしばらく意味が分かりませんでした。
ret0 = dfs(cur+1, a, b, c) ret1
ABC120-D Decayed Bridges(Union-Find)
ABC120-D Decayed Bridgesに挑戦した。
正直,なんかグラフだな,木を使いそうだなくらいで全然できなかったので公式editorialを読みました。
https://img.atcoder.jp/abc120/editorial.pdf
すると,一行目に衝撃の事実が書かれていました。
「島を頂点、橋を辺としたグラフを考えます。グラフから辺を削除していくのは難しいことが多い
蟻本をPythonで(FenceRepair)
今日は蟻本のCh.2 貪欲法のあたりから。ここまではまぁそれなりに読み進めましたけど,はじめて詰まった感じになったのが,このFenceRepair(POJ 3253)の問題でした。
まず,問題文から直接読み取れるコストは以下である。
1. 15の板を7と8に切断・・・コスト152-1. 7の板を3と4に切断・・・コスト72-2. 8の板を5と3に切断・・・コスト83-1. 3の板を2と1に切
ABC141-D問題のTLE
AtCoderのABCに定期的に(と言ってもまだ5,6回)参加している。
リアルタイムの参加はできなかったが,ABC141のD問題に挑戦したので記事にしようと思う。
問題は公式サイトを参考にしてください。
一番値段の高いものにディスカウントチケットを使っていけばいいなというのは(直感で)わかる。また,一枚ずつ何回も使うのと,複数枚を同時に使うことの差もないことも少し実験すれば確認できる(本当
蟻本をPythonで(LakeCounting)
AtCoderのコンテストに参加したり,蟻本を読んだりし始めました。
使用言語はPythonの予定。そこで,コンテストの参加記録や蟻本で勉強したことを書いていければいいなと思っています。
今回は第二章の全探索(深さ優先探索)。POJ2386のLakeCountingです。
C++とPythonで違うところはほとんどないので,そのまま真似して書けばOK.
N,M = map(int,inpu