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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

今日の競プロ(2015/05/10)

適当にやって解ける問題がいよいよ少なくなってきました.

京都大学プログラミングコンテスト2012 practice A問題

問題

A: Wikipedia - 京都大学プログラミングコンテスト2012 practice | AtCoder

回答

Submission #402852 - 京都大学プログラミングコンテスト2012 practice | AtCoder

アッカーマン関数の計算.
普通に組むと落ちます.再帰関数なので,再帰数の限界超えるんですよね.
詳しく調べていませんが,python再帰の限界は1000回って聞いたような.

なので,どうすればいいかというと…
ぶっちゃけ答えはWikipediaにのっているも同然…
mが3以下と保証されており,mが3以下の一般式はWikipediaにのっています….
というわけで,mの値で分岐させて計算するだけ.最初からおとなしくWikipedia見ればよかった^^;

def ackerman(m, n):
    if m == 0:
        return n + 1
    elif m == 1:
        return n + 2
    elif m == 2:
        return 2 * (n + 3) - 3
    else:
        return 2 ** (n + 3) - 3
 
m, n = map(int, input().split())
print(ackerman(m, n))

条件をよく見て処理しなければならないなと感じた一問でした.

京都大学プログラミングコンテスト2012 practice B問題

問題

B: String Sorting - 京都大学プログラミングコンテスト2012 practice | AtCoder

回答

Submission #402854 - 京都大学プログラミングコンテスト2012 practice | AtCoder


個人的にはB問題ですが,こちらの問題のほうが簡単でした….
降順ソートして,それをjoinつかってくっつけるだけです.単純.

N, K = map(int, input().split())
ali = input().split()
ali.sort(reverse=True)
print("".join(ali))

ただ,もう少し短く書けないんですかね….中身で何が起こっているのかよく調査しなければいけないものもあるのですが,本当はこんなかんじで書きたいですよね.

print("".join(input().split().sort(reverse=True)))

型の解釈が上手く行ってないんだろうなあという予想.
検証する機会があれば,調べてみようかな.

追記.

@ininsanus さんからツイッターでアドバイスを頂き,簡潔に書くことが出来ました.
sortedを使うことで実現できました.(この辺り,返り値として何が返ってくるのかもう少し調べないとね^^;)

Submission #403599 - 京都大学プログラミングコンテスト2012 practice | AtCoder

N, K = map(int, input().split())
print("".join(sorted(input().split(), reverse=True)))
京都大学プログラミングコンテスト2012 A問題

問題

A: アルデンテ - 京都大学プログラミングコンテスト2012 | AtCoder

回答

Submission #402870 - 京都大学プログラミングコンテスト2012 | AtCoder


単純な問題なのですが,なーぜかうまくいかないので,回答を見て確認.
単純な総当りなのは明らかなんですけどねえ.
なんでうまく行かなかったんですかね….

N, T, E = map(int, input().split())
xli = list(map(int, input().split()))
res = -1
 
for i in range(N):
    for time in range(T - E, T + E + 1):
        if time % xli[i] == 0:
            res = i + 1
            break
    if res != -1:
        break
 
print(res)

追記

こちらも @ininsanus さんからツイッターでアドバイスを頂き,通らなかった方のアルゴリズムを改良して通せました.
模範解答では,T - E ~ T + E の範囲でxの値でMOD取る形で解いていましたが,こちらのアルゴリズムでは,ひたすら T - E より大きくなるようにxの値をひたすら足していき,範囲内であればOKとするようなものになっています.
Tが大きいと多分機能しないと思います… いろいろとダメそうですね^^;
ただ,本問題を通すくらいならなんとかなるんでしょう.はい.

Submission #403605 - 京都大学プログラミングコンテスト2012 | AtCoder

N, T, E = map(int, input().split())
xli = list(map(int, input().split()))
res = -1
 
for x in xli:
    tx = 0
    while tx < (T - E):
        tx += x
 
    if T - E <= tx <= T + E:
        res = xli.index(x) + 1
        break
 
print(res)
天下一プログラマーコンテスト2012 予選B A問題

問題

A: 孫子算経 - 天下一プログラマーコンテスト2012 予選B | AtCoder


回答

Submission #402874 - 天下一プログラマーコンテスト2012 予選B | AtCoder


探索する範囲が狭いので,これも総当りで問題無し.
ただ,以下に短く書くのかをちょっと考えつつ….
for文と内包表記で書きました.
探索範囲が広くなったらセットを利用して計算しようかなあというところも考えましたが,どうなんだろう…
(なるべくループを増やしたくないので,積集合で求めてしまおうというわけです…)

a, b, c = map(int, input().split())
res = [i for i in range(1, 128) if i % 3 == a and i % 5 == b and i % 7 == c]
for r in res:
    print(r)

(3つも条件式andでくっつけるのあまり気持ちよくないっすね)

DigitalArts プログラミングコンテスト2012 B問題

問題

B: Password - DigitalArts プログラミングコンテスト2012 | AtCoder


回答

Submission #402896 - DigitalArts プログラミングコンテスト2012 | AtCoder


以外にうまくかけたんじゃないかなーというコード.
数字の割り当てがアルファベット通りなので,アスキーコードに落としこんで計算.
あとは,場合わけですねえ….
ハッシュ値 > 26 ならば,ハッシュ値が26以下になるまでzで埋めて,最後の文字は適当なアルファベットで.*1 zzzyみたいな文字列が渡されることを想定して,もし入力と同じであれば文字列を反転….
ハッシュ値 <= 26の時のほうがめんどくさかったですよね.一文字なら,一つ前のアルファベット + "a" とかすごく適当な処理でいいんですが….複数文字を想定していなかったので,思ったように行かず.26以下なので,一文字のアルファベットで置き換えれば良さそうだったので,置き換えました.

言葉で説明するとそんな感じですが,何とか解けてよかった.

def clachashnum(s):
    ret = 0
    for c in s:
        ret += ord(c) - ord("a") + 1
    return ret
 
s = input()
hashnum = clachashnum(s)
if not 2 <= hashnum <= 519:
    print("NO")
else:
    res = ""
    if hashnum >= 27:
        while hashnum >= 26:
            res += "z"
            hashnum -= 26
        res += chr(ord("a") + hashnum - 1)
        if s == res:
            res = res[::-1]
    else:
        # 1 alpha
        if len(s) == 1:
            res = chr(ord("a") + hashnum - 2) + "a"
        else:
            res = chr(ord("a") + hashnum - 1)
        
    print(res if clachashnum(s) == clachashnum(res) else "NO")


さて,冒頭にも書きましたが,適当にパパっと解ける問題がなくなってきた気がするので,データ構造とかもっと勉強しないとなあと思います.(少しつづね…)


明日から平日で,どれくらい忙しくなるのかわかりませんが,少しづつ続けて蹴るよう,頑張りたいです.

*1: これもしかしたらテストケースが弱い? zzzのパターン,多分落ちるわ…