とも

理学（修士）数学専攻 ＳＥ3年（VB.NET，Java）の後，高校教員（数学）へ転職。…

とも

理学（修士）数学専攻 ＳＥ3年（VB.NET，Java）の後，高校教員（数学）へ転職。 趣味でプログラミングをやっています。触ったことがある言語はVB.NET，Java，Python。 勉強したことなどを記事にする予定。専門的なことを書ける自信はない。

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言っちゃだめゲーム

      問題昔，古畑任三郎というドラマの中で古畑さんが犯人とやっていたのを見たのが，私のこのゲームとの初めての出会いであった。詳細は以下。 考察１（後ろから考える）n=30,k=5だとしよう。 1からはじめていって，5以下の数字を交互に宣言し，30を宣言した方が負けである。相手に30を宣言させれば勝ちともいえる。ということは29を自分が宣言すれば勝ちである。29を自分が宣言するためには，24～28のいずれかで自分に回ってくれば，29を宣言できるので勝ちである（k=5なので，24-

      とも

      • AGC034 A-Kenken Race

        １．概要今日トライした問題は以下。 岩が2つ続いていたらダメ，というのが基本的な考えかた。問題文の制約からA<B<Dは確定するので，CがA,B,Dの間のどこに来るかで3パターンに分かれる。 1. A < C < B < D2. A < B < C < D3. A < B < D < D ２． パターン１ （ A < C < B < D ）AはCに向かい，BはDに向かうので，A-C間とB-D間のそれぞれの区間に岩が2つ続けて存在するときは到達不可能。それ以外は到達可能。

        とも

        • Pythonのheapqとdeque

          AtCoder ABC088 D Grid Repainting台風で外出できない連休だったので，家でAtCoderをやっていた。今回はこれ。 問題文を読んだ瞬間に，「あ，BFSだな」というのはわかりました。蟻本を読んでいましたからね！で，見様見真似で実装したコードがこちら import sysimport osimport heapqINF = 10**5H, W = map(int,input().split())S = ["" for _ in range(H)]c

          とも

        yukicoder No.11 カードマッチ

        とも

          Pythonの切り上げと天井関数

          こつこつAtCoderで精進しています。今日はARC062のAtCoDeerくんと選挙速報をやっていました。 とりあえず解けたつもりで提出したら数ケースWAになったので解説を読みましたが，私の解釈では，解説と同じことをコードに落としているつもりでした。 そこで悪いとは思いつつも，テストケースをのぞかせてもらいました。 するとWAになっているケースの想定解と私の解はそれぞれ以下の通りでした。 999455005490758562999455005490758230 こ

          とも

          Pythonの切り上げと天井関数

          とも

          ABC119-C Synthetic Kadomatsu

          ABCの問題名って読み飛ばしちゃったりすることが多いですが，合成門松！ときました。うん，できない。C問題だから簡単かなと思ったけどよくわからない。こないだ蟻本でやったことを思い出したけどよくわからず。 で，解説を読みました。やはりdfsを使うようでした。でも解説読んでソースを読みますがしばらく意味が分かりませんでした。 ret0 = dfs(cur+1, a, b, c) ret1 = dfs(cur+1, a + l[cur], b, c) + 10 re

          とも

          ABC119-C Synthetic Kadomatsu

          とも

          ABC120-D Decayed Bridges(Union-Find)

          ABC120-D Decayed Bridgesに挑戦した。 正直，なんかグラフだな，木を使いそうだなくらいで全然できなかったので公式editorialを読みました。 https://img.atcoder.jp/abc120/editorial.pdf すると，一行目に衝撃の事実が書かれていました。 「島を頂点、橋を辺としたグラフを考えます。グラフから辺を削除していくのは難しいことが多い」 なななんと，そうなのか，という感じです。左様でしたか。なので逆からやると。

          とも

          ABC120-D Decayed Bridges(Union-Find)

          とも

          蟻本をPythonで(FenceRepair)

          今日は蟻本のCh.2 貪欲法のあたりから。ここまではまぁそれなりに読み進めましたけど，はじめて詰まった感じになったのが，このFenceRepair（POJ 3253）の問題でした。 まず，問題文から直接読み取れるコストは以下である。 １．　　１５の板を７と８に切断・・・コスト１５２－１．　７の板を３と４に切断・・・コスト７２－２．　８の板を５と３に切断・・・コスト８３－１．　３の板を２と１に切断・・・コスト３ ただ，冒頭の解説ではこのようなことが書いてあった。 板の切

          とも

          蟻本をPythonで(FenceRepair)

          とも

          ABC141-D問題のTLE

          AtCoderのABCに定期的に（と言ってもまだ５，６回）参加している。 リアルタイムの参加はできなかったが，ABC141のD問題に挑戦したので記事にしようと思う。 問題は公式サイトを参考にしてください。 一番値段の高いものにディスカウントチケットを使っていけばいいなというのは（直感で）わかる。また，一枚ずつ何回も使うのと，複数枚を同時に使うことの差もないことも少し実験すれば確認できる（本当は証明が必要。公式editorialには証明も載っています）。 とりあえず書い

          とも

          ABC141-D問題のTLE

          とも

          蟻本をPythonで（LakeCounting）

          AtCoderのコンテストに参加したり，蟻本を読んだりし始めました。 使用言語はPythonの予定。そこで，コンテストの参加記録や蟻本で勉強したことを書いていければいいなと思っています。 今回は第二章の全探索（深さ優先探索）。POJ2386のLakeCountingです。 C++とPythonで違うところはほとんどないので，そのまま真似して書けばＯＫ． N,M = map(int,input().split())field = [""]*Mfor i in range

          とも

          蟻本をPythonで（LakeCounting）

          とも