2019-03-24

AtCoder ABC122 3完うーむ。

AtCoder

ABC122 序
- A
- B
- C
- D
  - 2019/03/30 やった
ABCはかったるい

ABC122 序

　どうせレートじわじわ落ちるんだろ？とおもいながら参加したら簡単でびびった。といいつつDはできず。(あとでさらえた)

A

　辞書。2分。

B

　ACGTが続く間旗立てたりおろしたりして長さを数えた。ここまで11分。ちなみに旗を上げ下げしなくてもできる。

C

　最初に'AC'のCの出て来る場所を例によって例のごとく旗を立てたりおろしたりして数え、あとは二分探索でいちいち区間がどこかみつけた。旗の上げ下げに失敗して1waのあと15分ほど無駄に消費した。

　二分探索するよりは最初から数えていって累積和的な長い配列をつくった方が速かったな。辞書への愛が足りない。

D

　AGC/ACG/GAC と ATGC / AGTC まではわかったがそこから先重複をどうやって省くのかについて横になって考えてたらいつのまにか終わっていた。こういうときDPをつかうと簡単にとけるらしい。なるほど。

2019/03/30 やった

　適当にやりだしたら微妙に答えがあわない。みなおしたがどこの考え方が間違っているのかよくわからず、結局他の人のコードをみたら、yydoco氏のものの核心が似てたので参考にしたら通ったのでなぜそこで通ったのか考えて説明を書いた↓。最初 GA[i] = G[i-1] - AG[i-1] としてたせいで微妙に合わなかった。何を消すべきかわかってないあたり、根本的によくわかっておらず辻褄合わせでなんとかしようとしていたことがわかる。考え方が正しくないのでいつまでやっても合わない。ひょっとして頭の中の基本ロジックが絵合わせなのかもしれんな。

def 解():
    N = int(input())
    iD = 10**9+7

    #3210
    #***A
    #***G
    #***C
    #***T
    #*ACG
    #*GAC
    #*AGC
    #AGGC #A*GC AG*C から重複を消したもの
    #AGTC
    #ATGC

    A = [0]*(N+1)
    G = [0]*(N+1)
    C = [0]*(N+1)
    T = [0]*(N+1)
    AC = [0]*(N+1)
    GA = [0]*(N+1)
    AG = [0]*(N+1)
    AGG = [0]*(N+1)
    AGT = [0]*(N+1)
    ATG = [0]*(N+1)

    A[1]=G[1]=C[1]=T[1]=1 #種
    for i in range(2,N+1):
        #前の桁の末尾に一文字足したものから条件を満たすものを消す
        A[i] = A[i-1] + G[i-1] + C[i-1] +T[i-1]
        A[i] %= iD
        G[i] = A[i] - AC[i-1]
        C[i] = A[i] - GA[i-1] - AG[i-1] - AGG[i-1] - AGT[i-1] - ATG[i-1]
        T[i] = A[i]

        #この桁の末尾の場合の数を計算
        AC[i] = A[i-1] - GA[i-1]  # **AC を計算するために**A*を使うが*GAC の分(*GA*)はこの桁で消えるので消す
        AG[i] = A[i-1]
        GA[i] = G[i-1]

        AGG[i]= AG[i-1]
        AGT[i]= AG[i-1]
        ATG[i]= A[i-2]

        G[i] %= iD
        C[i] %= iD
        AC[i] %= iD

    print((A[N]+G[N]+C[N]+T[N])%iD)
解()

　DPって毎度ながら感心するテクだなぁ

ABCはかったるい

f:id:inudaisho:20190324234940p:plain — レート変化

　レートは微増。茶色に落ちたらスパっとやめれるのに。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆
出版社/メーカー: マイナビ出版
発売日: 2015/01/30
メディア: Kindle版
この商品を含むブログを見る

2019-03-24

AtCoder AGC032 B1完

経緯
- A
- B
- C
うーむ。レートが上がってしまった。

　んー。今回で茶色に叩き落とされるとおもっててそれでもう終わりだなとおもってたら普通にレート上がってしまった。撤退しづらいな。

経緯

A

　しばらく考えてなんか面倒くさそうだったのでBを見た。

(あとからtwitterで見てるとなるほどそんな簡単なことか、という印象)

B

　グラフの問題。「単純グラフ」の意味はググってなんとかした。ここのお絵描きで時間を潰してしまう。頂点が7くらいのところまで場合を出してだいたい感触つかんだので、それで行けるかどうか頂点10の場合を考えたが厳しい。辺を減らす方法を一般化しようとしたがうまくいかなかったのでそれはやめて、とりあえず安直な方法でなんとかした。

　安直な方法とは、要するに2つづつの組をつくって(Nが奇数の場合ひとつだけの組がひとつできる)、頂点からその組以外の頂点に全部辺を引いてしまう。終わり。

C

　さて、Bのお絵描きに興じている間に時間がなくなったのだが、のこりの時間でCをみてみると、これも DFS で印つけていって戻る回数を数えていって三回目で余ってるか調べたら終わりそうだなと思った。が、どうもコーナーケースが厳しくてそこで詰るらしく、そうそう簡単でもないらしい。

うーむ。レートが上がってしまった。

f:id:inudaisho:20190324001503p:plain — レート上がってしまった

　今回はもう茶色に落ちるだろうということで精進もせず、しかも大阪の日本橋へいってジャンク漁りなどして頭を空っぽにして AGC に臨んだのだが、それがかえってよかったのか、むしろやめる気満々でやったのがよかったのか、とりあえずレートが上がってしまった。どうしようかな。茶色に落ちた記念で撤退エントリでも書こうとおもってたのに。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

最強最速アルゴリズマー養成講座プログラミングコンテストTopCoder攻略ガイド

作者: 高橋直大
出版社/メーカー: SBクリエイティブ
発売日: 2012/09/27
メディア: 単行本
購入: 9人クリック: 319回
この商品を含むブログ (8件) を見る

2019-03-19

井上章一『京都ぎらい』の花園・嵯峨の田舎具合と20世紀の都市の拡大

京都井上章一都市

京都ぎらい (朝日新書)

作者:井上章一
発売日: 2015/09/11
メディア: 新書

　こないだブックオフに行ったとき、井上章一『京都ぎらい』朝日新書 2015 のクタクタになった本が108円で売ってたので買ってきた。うーむ。なんというか屈折した感情で京都をあれこれ書いてて正直微妙な本だが、さてここで井上章一の言う花園・嵯峨がどれくらい田舎かみてみよう。今昔マップの明治末の京都の地図。

f:id:inudaisho:20190319183302p:plain — 明治42年(1909)測図今昔マップより

(地図内の色付記入は筆者による。以下同様)

　これでわかるように嵯峨はおろか花園でさえも京都の市街地から離れている。花園も嵯峨も京都市に入ったのは昭和6年で、それまではそれぞれ花園村・嵯峨町(大正12年(1923)から町制)だった。花園は京都の市街地から妙心寺の南門へ行く街道筋の町でいうなら門前町に近いがその南側はまだ空き地だった。この明治末の状態から大正の15年間で京都市の市街地は天神川と山陰線の東側まで拡大する。このころでも北野天満宮のあたりが京都市街地の北西端にのみこまれつつあったわけだ。

f:id:inudaisho:20190319190309p:plain — 大正11年(1922)測図今昔マップより

　そこから関東大震災による関西方面への人口移動にくわえ、関西経済の成長もあり京都の市街地も急速に拡大する。

f:id:inudaisho:20190319190942p:plain — 昭和6年(1931)測図今昔マップより

　山陰線の花園駅と妙心寺を結ぶ道のあたりに町が展開しているのがわかるだろうか。つまりこのあたり昭和になってから急速に市街地が拡大した場所だったわけだ。井上章一はこの花園で戦後の1955年(昭和30年)生まれということなので、新興住宅地か在来の花園村の方だったのかはわからないが大正末までの状態を知っている人からすれば京都ではないに違いない。嵯峨はさらにその先なので言うまでもない。井上章一が嵯峨が京都か京都でないかのような話をグチグチ書いているが京都でないと思う人がいる方が普通だろう。井上章一が20代の若者だったのは昭和50年代ということになるが、市街地が天神川の西側に伸び出してからまだ50年くらいしかたっていない。

　明治末までの都市の規模というのはそれほど大きいものではないのは当然の話で、たいていの日本の都市が現代の市域になったのは世界的にも人口が爆発した20世紀の中頃である。井上章一のように都市の近郊に住居があり、その後市街地に飲まれた人というのは別に京都にかぎらず日本中世界中にあるだろう。たとえばこれは明治末の大阪の地図だが、

f:id:inudaisho:20190319193108p:plain — 明治41年(1908)測図今昔マップより

(黄色が鉄道)

　今の大阪の環状線は当時の市街地の外側を巡るように走っていた鉄道が元だということがわかる。また、今の阿倍野のあたりは「野」らしく本当に何もなく、「新世界」とかあるあたりはこの後開発されたところで本当の意味で「新世界」だったこともわかる。まぁ大阪は今でもこの上町台地の上だけに繁栄が集中している感じはあるが、人間の行動範囲が徒歩で制限されていた時代の都市は市街地と市街地外がこのように明瞭に分かれていた。都市はその後急速に拡大し、周辺地域は市域に次々と飲まれていったわけだが、その元周辺地域の市域の人と旧市街地の人たちの間で帰属感に微妙な差が生じたことは日本中の都市でもあったことだろう。京都は都市としての歴史が日本の中では長かっただけだが、それも実のところ秀吉くらいのころに大改造されたのが今の京都のもとだということは当の『京都ぎらい』の中でも家康の開発した京都という形で指摘してある。日本の今の県庁所在地の都市は織豊期から江戸初期に城下町として始まったところが結構多く、町の歴史として見ると京都も案外変わらなかったりするので、古い歴史を誇る人達と周辺地域の人たちの都市への帰属感の差はそこでも見られたことだろう。要は『京都ぎらい』の中で冒頭指摘してるような事は規模こそ違え、全国的にあったことである。京都は幕末の地震以後空襲も受けずにいたので強く残った面はあるだろうが。

　井上章一はその都市近郊民の微妙な帰属感を京都の歴史とからめていやらしく書いてるだけなので、この本からただよう京都の「いけず」さというのはむしろ井上章一本人の「いけず」さだ。若いころに受けた田舎者扱いという貴重な体験を20世紀都市論に展開できず、ひたすら京都に因縁をつけていくだけのくだらない本にしてしまったあたりに井上章一の限界がある。どんな本を書こうが勝手だが、この程度の本が2016年の新書大賞とやらを取ったというのだから今の知識人とやらの頭脳の退廃も徹底したものだ。平成の30年間というのは本当に腐敗と堕落の30年だったということだな。

　全然関係ないが井上章一の本で読んだことあるものでは↓がおもしろかった。ヨーロッパでいう「古代」というのは狭い意味ではローマ帝国の領域だったか否かということで、中国周辺の歴史でいうとそれに相当する古代帝国は漢のことになるから漢の領域になかった日本に古代はないというのは、ヨーロッパ的な「古代」の使い方を適用するなら確かにそうなのだ。これはソ連マルクス主義的史観で「古代」を規定してたようなちょっと前の日本史学者からはでてこない視点で、そういった美術史的な「古代」史観をベースにもつ建築史の専門家だった井上だからこそ持てたものなのだが、こういう虚を突くような本ばかり書いてりゃいいのに。『京都ぎらい』を書いたときは60歳ということだが、もう早ボケてきたのかな？これだから戦後生まれは...

日本に古代はあったのか (角川選書)

作者:井上章一
発売日: 2008/07/10
メディア: 単行本

2019-03-17

百均のシリコンゴムベラで抹茶をたてる

抹茶

前回の結果マドラー
シリコンゴムヘラ
- 作業
- 飲んだ後
結果: 緑の粉をキメるならシリコンゴムのヘラがおすすめ

　さて抹茶を百均の小物でたてる外道シリーズである。

前回の結果マドラー

　前回はマドラーを試したが、その結果としてはそれなりの味ではあったものの、ダマがのこり、コクもない微妙な出来上がりだった。しかし、残った抹茶のダマをみるとかなり細かくなっている。ただ、お湯を入れたときの粒度とそれほど変わっているように見えない。実はマドラーや泡立て器のようにある程度の太さのある物質での攪拌ではそこまで細かくならないのではなかろうか。そこで、シリコンゴムのヘラで積極的に潰していくとよさそう、という案をおもいついた。

シリコンゴムヘラ

　ということで、今度はダイソーに行ってシリコンゴムのヘラを買ってきた。ちなみにダイソーに行ったのは安い茶筌/茶筅があるという話だったので見に行ったのだが、なかったので結局ヘラを買ってきたのだ。まぁ、自分のような独身ハゲの下流中年には茶道なんか関わりのないことなので、カフェインたっぷりの「緑の粉」をキメるのにいい道具があれば何でもいい。ちなみにちょっとググったところではヘラで抹茶を潰すという案は誰もネットに出していない。みんなコーヒー・紅茶には凝っても抹茶には凝らないのかな？