Educational DP Contest / DP まとめコンテストの「B - Frog 2」をPythonで

概要

  • 久しぶりに、プロコンをやろうと思って、https://atcoder.jp/contests/dpPythonでやってみた。
  • 二問目に挑戦してみたが、TLEで全然通らない。
  • 謎のnumpyを使わない縛りで挑戦していたが、これ以上は無理だと判断したので、供養目的で、ここに載せておく。

コード

def test3():
    import sys
    N, K = list(map(int, sys.stdin.readline().split()))
    h = list(map(int, sys.stdin.readline().split()))
    from itertools import tee
    its = list(tee(range(1, K+1), N))
    INF = 10**9
    dp = [INF] * N
    dp[0] = 0
    myabs = abs
    for i, hi in enumerate(h[1:], 1):
        value = INF
        for k in its[i]:
            key = i - k
            dpval = dp[key]
            if dpval >= INF:
                break
            tmpv = myabs(hi - h[key]) + dpval
            if tmpv < value:
                value = tmpv
        if value != INF:
            dp[i] = value
    print(dp[N-1])

test3()
  • 頑張ったポイントは以下
    • teeで予めループ用のiteratorを作っておく
    • sys.stdin.readline()の方が、input()より速いらしい
    • INFはギリギリの値(10**8だと通らない)
    • 関数はローカル変数に紐付けしておく(myabs)
    • minとか使わないで、if文
    • Nでループしないで、h配列でループ
    • 可能な限り、同じ計算を2回以上しないようにした
    • 配列へんアクセスを最低限にした(set/getともに)
  • ちなみにこれだけ頑張ると、1_03は何回かに1回は通る様になった。1_11はムリぽ。

感想

  • 此のコードの改変に1日費やしたから、他の問題が結局やれなかった…
  • pythonで挑戦する場合は、numpy使わないとどうにもならないみたい。
  • 正直な所、1問目からわからず、地力の低さを改めて感じた。
  • 次問からは、諦めてnumpyを使うことにします。

stoiが使えない

概要

 C++のstringモジュールに、stringからintへの変換関数(stoi())があるのだが、なんでかわからんが使えないので調べた。

前提

 DxLibをLinuxでビルドするとか言う、若干特殊な環境である。

調査

  • std::stoi()は、C++11以降で利用可能との事なので、g++とgccを4.8以降にしてみた。
    • とりあえず、普通にビルドする場合には大丈夫だったが、DxLib用のビルドをするとダメだった。
    • (2018-11-09追記) よく考えたら、MinGWを使ってたからg++更新しても意味なかったのでは?
# 使ってた奴↓
$ i686-w64-mingw32-g++
  • ここを見ると、「特定の条件下でガードされる場合があるので、以下のdefineを切ってみて」とか言っているのでやってみたがダメだった。
#define _GLIBCXX_USE_C99 1
  • 上記リンクのもうちょっと下に、ビルド時のオプションを調整してみては?的な事が書かれていたので、やってみたらOKだった。
-std=c++11 

まとめ

 とりあえず、ビルド時にc++11であることをオプションを使って分からせるといいらしい。
 他にもc++11で大丈夫なはずのvector<vector<string>>とかでエラーが出てたから、c++11以前の状態でビルドしてたっぽい。

gnumericでCSV保存

概要

 Excelの簡易版でLinuxで使えるgnumericというアプリケーションがあるのだが、CSVの作成方法がそんなに簡単じゃなかったので、やり方を残しておく

やり方

  1. 上のバーから「データ」を選択
  2. 「Export Data」で子メニューの表示
  3. 「Export as CVS File...」を選択

参考

openssh-serverが入っているのにsshでログインできない

概要

 新しくBasix4.0(OS)をインストールしたので、sshログイン関連を設定して遠隔ログインしようとしたができなかったので、原因を調査した。

現象

 sshコマンドでログインしようとすると、以下のメッセージが出て終了してしまう。

Connection closed by 192.168.11.10 port 22

調査1

 とりあえず、以下の点を調査した。

  1. サーバ(Basix4.0のPC)にopenssh-serverが入っているか?
  2. /etc/ssh/sshd_configの設定は?
  3. Firewallでport 22が拒否されてないか?

 結果は以下の通り

  1. 入ってる
  2. とりあえず、以下の様に設定して、サービスを再起動してみたがダメ

    Port 22
    PermitRootLogin no
    PasswordAuthentication yes

  3. そもそもFirewallがOffだった

調査2

 ということで、原因がわからなかったので、sudo service ssh statusでsshのサービスの状態を見てみると、以下のファイルの読み込みに失敗していた。

 上記ファイルは、/etc/sshにあるらしいのだが、何故か無かった。次のリンク先のアドバイスで、一回消して作りなおせとあったので、以下のコマンドで作り直しだけやってみると、無事sshができるようになった。

sudo dpkg-reconfigure openssh-server

 

結論

 公開鍵情報が無かったのが問題だったらしい。
 普通はopenssh-serverのインストール時に作られるはずだが、作られていなかった。何故かは不明。

guakeの起動時にコマンドを実行するオプションが効かない件

概要

  • guakeの起動時にbyobu-screenを実行させたい。
  • 以下のコマンドを叩くと、VTEの引数がおかしい的なエラーが出る
guake -e byobu-screen

調査

 本家のissueに当該内容の記述があったので、以下のファイルの外部コマンドを渡す箇所を修正してみた。

  • ファイル : /usr/lib/python3.6/site-packages/guake/guake_app.py
#terminal.feed_child(command, len(command))
terminal.feed_child(command)

 修正して実行してみると、「0番目のアイテムは文字列ではなく、数字を渡してください」とか言ってきた。しょうがないのでVTEのAPIを見に行ったが、何も解決しなかったので諦めろん

どうしようか?

 コマンドの実行は無理っぽいので、別アプローチを模索していたところ、guakeの設定をよく見てみると、Shellなる項目があった。中を見るとDefault Interpreterという項目があり、ここに設定したコマンドが、起動時に実行されるらしい。なので、ここにbyobu-screenを設定できればよいはず。
 項目の増やし方がわからなかったが、この質問の回答よると/etc/shellsの記述を表示しているだけらしい。追記して再度Default Interpreterのリストを見てみると、追加されていた。

結論

  • /etc/shells に /usr/bin/byobu-screen を追加する
  • guakeの設定のShellで、Default Interpreterにbyobu-screenを設定する

byobuのエスケープキーの設定

概要

  • basix4.0に変更したので、byobuをインストールし直した。
  • エスケープキーがデフォルトで"A"になっているので、"]"に変更したい
  • 何度やっても反映されない!

解決

 よくわからんが、"]"はF1のconfig画面からだと設定できないようである。
 以下のファイルを直に変更することにより、直接エスケープキーを変更する。

  • ファイル
    • $HOME/.config/byobu/keybindings
bindkey "^A"
escape ^]]

Hylangで蟻本

Hylangで蟻本をやる

蟻本って何?

 プロコンの勉強本としてお馴染みのプログラミングコンテストチャレンジブック(通称:蟻本)

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

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

概要

 蟻本自体はC++で書いてあるので、C++のソースをHylangに移植する。

進捗&作業期間

 完了
 本を買ってから5〜6年ぐらい、Hylangで実装を初めてから足掛け3年ぐらい

Github

ここ : GitHub - dis-kaichi/programming-contest-challengebook

感想

 クッソ疲れた(訴訟)。以下は愚痴
 この本についてだが、基本的にソースが載っているのでソレを打ち込めば動くのだが、入力を一部変換して実装してあったりするところが有り、単純に打ち込めば終わりというわけでも無かった。グラフとか最後の方とかで、前の方のページで実装済みを前提でコードが書いてあったり、本に載っていない短縮記法(for文とか)がいきなり出てきたりしたことがあったので、そこら辺はちゃんとリンクとか注意書きとか書いて欲しかった。
 物量がかなりあるので、頭から全部実装するとかは余りオススメしない。(時間のかかりぐあいが半端ない)何が書いてあるのか抑えておいて、後から必要に応じて実装してみるのがいいと思う。勉強にはなるので、時間があるときにちょこちょこやる感じがいいかな?

 今回、C++からHylangの移植を行ったが、言語間の仕様の差を埋めるのが結構大変だった。
 特にHylangの仕様が固まっていないので、2〜3年の間に書き方がガラリと変わった事が大きかった気がする。昔は引数の展開(*list, **dict)みたいなやつが書けなかったので、applyを使って無理やり書いてたし、letが途中削除になったので、修正したり(今は復活)、defが削除になったので、setvに書きなおしたり、強制敵にreturnができなかったり(今はできる)などなど。

 この本に手を出した経緯については、プロコンに興味があったので、本を買ってC++で勉強したのが、5〜6年前。それで途中で飽きて放置、完全に積読本となっていたのを掘り出したのが3年ぐらい前、その時ちょうどPython上で動くLispの方言(Hylang)を見つけたばっかりだったので、勉強がてら実装してみようと始めたのが苦行の始まり。完了するのに3年も掛かった上、今年のGWはコレで潰れた(憤怒)。当時はLispの書き方もよくわからんかったのが、今ではかなり書けるように…(Hylang限定)。大分成長したなぁ。
 取り敢えず、githubのアドレスは晒しておくので、Hylangを勉強していて、蟻本にも興味がある人の一助になればいいなぁと思う。(そんな奴いるのか?)

 以上、終わり