【ARC011】A〜Cの解法 in Python

プログラミング熱が再燃

毎日毎日、大学卒業から就職までのありあまる時間の全部をDota2に費やすつもりだったのが、糞ドコモ光のせいで計画が丸つぶれになったので、代償行動にプログラミングを選んだ。

forcestaff.hatenablog.jp

アルゴリズムを体系的に、実感を持って理解したいと思っていたので、AtCoderを練習台に学習することにした。AtCoderは、面白そうな問題を見つけては後で読むアプリPocketにぶち込んで、1ヶ月のヨーロッパ卒業旅行中の暇な時間に虫食い的に解いていたので、ある程度勝手を知っている。今回は久しぶりに同回の問題をまとめて解いたので、思考の流れと解法を合わせて記す。

f:id:airking05:20170321010247p:plain

A 鉛筆リサイクルの新技術

問題文を読み替えることなく素直にコーディングできる

# -*- coding:utf-8 -*-
m,n,sell = map(int,input().split())

z = 0
total = 0
while True:
    total += sell
    if sell+z < m:
        break
    tmpsell = int((sell+z)/m)*n
    z = (sell+z)%m
    sell = tmpsell

print(total)

書いたコードを見返すと、変数名が滅茶苦茶で面白い

B ルイス・キャロルの記憶術

これも素直にコーディング。面倒くさい空白処理を最後にまとめた

# -*- coding:utf-8 -*-
n = int(input())
words = input().split()
output = ""

table = [["z","r"],["b","c"],["d","w"],["t","j"],["f","q"],["l","v"],["s","x"],["p","m"],["h","k"],["n","g"]]
for word in words:
    o = ""
    for s in word:
        for i,t in enumerate(table):
            if s.lower() in t:
                o += str(i)
                break
    if o:
        output += o + " "
output = output.rstrip()
print(output)

C ダブレット

問題文を読むと、経路問題であることが分かる。条件に「ただし、k が最小となる変換過程でならなければならない。」とあるし、幅優先探索か?とあてをつける。実は、全探索アルゴリズムを覚えたのが昨日で記憶が鮮明だったのが助かった。完全自力でBFSを解くのは初めてだが、順序を踏んで組み立てる。探索条件での絞り込みでキューをできるだけ小さくなるように工夫すればOK

# -*- coding:utf-8 -*-
first,last = input().split()
n = int(input())
words = [input() for _ in range(n)]
words.insert(0,first)
words.append(last)

def debug_print(t):
    for i,row in enumerate(t):
        print("%s:%s"%(i,row))

def is_candidate(w1,w2):
    count = 0
    r = False
    for s1,s2 in zip(w1,w2):
        if s1 == s2:
            count += 1
    if len(w1) - count == 1:
        r = True
    return r

class Path:
    def __init__(self,word,prev = None):
        self.prev = prev
        self.word = word
    def print_path(self):
        if self.prev:
            self.prev.print_path()
        print((self.word))
    def count_prev(self,n=0):
        if not self.prev:
            return -1
        return self.prev.count_prev(n+1)+1

def bfs(s,g):
    ans = []
    queue = [Path(s)]
    memo = [0 for _ in range(n+2)]
    if s == g:
        print(0)
        print(s)
        print(g)
        return 0
    while queue:
        cur = queue.pop(0)
        for i,word in enumerate(words):
            if memo[i] == 0 and not word == s:
                if is_candidate(word,cur.word):
                    if word == g:
                        cur = Path(word,cur)
                        print(max(cur.count_prev(),0))
                        cur.print_path()
                        return 0
                    memo[i] += 1
                    queue.append(Path(word,cur))
    print(-1)
bfs(first,last)

自分のキャパシティを少し超えた問題を解いた時の気持ちよさを思い出した。大学受験以来の感覚で、懐かしい。

言語使い分け問題

Cのような一見処理時間を食いそうな問題を解く時には、Pythonのようなスクリプト言語よりもC++のようなコンパイル言語を選択すべきではないかという思いに駆られる。C++は高速である。それは紛れもない事実である。しかし、コンパイル言語に不慣れなnoobが、Pythonのようにnoobにもお手軽に使える高度なモジュールを備えていない言語でプログラムを書くにはどうしても時間がかかる。プログラムの大枠を考えると同時に新しい言語の記法・文法の子細に気を配る余裕はない。しばらくはPython一本になりそう。

競技プログラミングの記事を書こうと思う【AtCoder】

書こうと思う

きっかけ

以前からプログラミングは独学(笑)でいろいろと触っていて、ウェブサービスやトレードシステムをせっせと書いて遊んでいたのだけれど、 自分の発想から出る新しいハードルが期待できずに時間がすぎ、マンネリ化していたので、技術的な向上を求めて競技プログラミングをしてみることにした。

物怖じせず頑張りたい。

言語

PythonC++ Pythonで書いてTLEならC++にする。

問題タイプ分析

どうやら問題には大きな枠組みで数種に分類できそう。ある程度解いたら追記しよう。

ドコモ光がオンラインゲームで全く使えない理由

まとめ

  • ドコモ光はスマホ光回線の二重縛りで害悪
  • 利用者急激増加でping激遅、ひどい時には国内サーバに300msも
  • 昼間は比較的快適にオンラインゲームができる

f:id:airking05:20170321010349p:plain

ドコモ光とは

2013年夏ごろから開始し、スマートフォンをドコモで契約している人を対象に割引価格で光回線を提供するサービスであったが、その実態は情弱を騙して抱き合わせ契約を押し付け、スマホ光回線の相乱れた2年縛りの網に絡めとる代物であった。どの時点で解約しても違約金を請求してくるなんて考えた人はかなり頭がいい。サービス開始当初は、解約なんて頭にないドコモ信者にとっては最高の光回線契約だった。

普及と共に品質がゴミ化

なんだかんだドコモ信者だった自分も無事ドコモ光との契約を済ませ、2016年末ごろまで快適にインターネットライフを送っていた。が、2017年2月頃、京都から大阪へ転居し、同じドコモ光でオンラインゲーム(DotA2)をプレイしていると異常に気がついた。夕方から夜にかけて、ping(サーバとの接続応答時間)が恐ろしく高く跳ね上がっていた。国内のサーバへの接続であれば1〜20ping程度が通常と言えるが、日本サーバでプレイしているにも関わらず300、400と、理解不能な応答速度が画面に表示されていた。ゲーム内は夢の中で自分の体を動かす時の、水の中にいるような感覚で、そのまま自分のキャラクターは相手チームに蹂躙された。大feedである。DotA2日本サーバが韓国に在るという事実を考慮に入れても遅すぎである。俺は思った。ドコモ光は情弱でいっぱいになったのだ。糞が。就職までの1ヶ月ゲームに溺れた生活を送るはずだった俺の計画が全部狂った。ドコモ光死ね。

救いはある

といっても、ping激遅タイムはどうやら「夕方から夜中」の間らしく、自分調べでは4時〜16時は快適にオンラインゲームが出来そうだ。生活リズムが良くなった。また、夜はゲーム以外に、自己研鑽に励む時間を確保することができた。最近は競技プログラミングをしています。

プログラミングとかDota2の記録を書く日記

ブログを始める目的

ただひとつ。

ブログを書くことで、自分の頭が多少なりとも磨かれることを期待している。余暇の大部分を投入して遊んでいるプログラミングやゲームは、アウトプットという過程を踏んで初めて体に馴染む記憶として脳に定着すると考えている。今まで、何の技術交流もアウトプットもしてこなかった自分にとって、得た経験を一歩引いた目線で言語化して理解するというプロセスは、億劫だけどやらなければならない(やらないともったいない)急務だった。

ブログのジャンル

C++Python競技プログラミング、Dota2、シャドウバース