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

水面下の夢

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

TTPC2015に参加しました

4問しか解けなかった.120位.
しかも寝坊して2時からの参加,その上筋肉痛と眠気がひどく,途中で栄養ドリンクの購入などもしていたため,実質コンテストには3時間くらいしか参加できていなかった.時間が長くなればもっと解けた可能性… はあまりないと思うが,1問くらいは進められたのかもしれないと思うと,若干悔いが残る.
やっぱり,競技プログラミングで一番重要なのはコンディションってそれ一番言われてるから(反省が生かされない)

f:id:kawasumi_yume:20150921180126p:plain

各問題の感想.
A問題,僕の学生証.非常に簡単でした.ABCのAとかB位だと思う,さくさくっとAC.

s = input()
print({"D":"Doctor", "M":"Master", "B":"Bachelor"}[s[2]], s[0:2])

B問題.ラー油.なんか見た時にとっさにDPだこれ,と思ってC++で書き始めるものの,TLEで通らず,頭を抱えていた.
正しくは貪欲法,自分のDPの処理がおかしいと疑っている前に,自分のアルゴリズムがおかしいことに気付こう! こどふぇすの予選じゃなくてよかった.普通に大きい数字を中心に見て,貪欲にかけばよいだけだった.
これに1時間半くらいかかったのは,流石にダメだったと思う.

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);
 
  int N, B, C;
  cin >> N >> B >> C;
 
  if(B == 0 or C == 0) {
      cout << "0" << endl;
      return 0;
  }
 
  int A[N];
  REP(i, N) cin >> A[i];
 
  int res = 0;
  int idx = N-1;
  while(C >= 0 && idx >= 0) {
      if(C - B < 0) {
          res += C * A[idx];
          break;
      }
      res += B * A[idx];
      C -= B;
      idx--;
  }
 
  cout << res << endl;
  return 0;
}

DPで書いた場合,私のヘボコードでは,60件目あたりでTLEしだした .


C問題.補足性がありそうだなあと思いつつ,文字数の制限を見て問題文通りに普通にシミュレートすればOKか,と解釈.
Oと0(大文字のオーとゼロ)を見間違えていたり,左から処理しなければいけないという条件を見落としており,2WAしたのはもったいなかった.B問題に比べればあっさりだった.

s = input()
o = "oookayama"
while o in s:
    fidx = s.index(o)
    lidx = fidx + len(o)
    while fidx >= 0:
        if s[fidx] != "o":
            break
        else:
            fidx -= 1
    fidx += 1
    t = s[fidx:lidx]
    while "oo" in t:
        if "oo" in t:
            tfidx = t.index("oo")
            t = t[:tfidx] + "O" + t[tfidx+2:]
        if "OO" in t:
            tfidx = t.index("OO")
            t = t[:tfidx] + "o" + t[tfidx+2:]
    s = s[:fidx] + t + s[lidx:]
print(s)

D問題.素数のリストを作るのがうまく出来ないため,これ事前にライブラリを用意しとかないとダメだなあということを再認識した.
Python素数のリストを書こうとするも,どう考えても処理時間がダメそうだったので,元から素数ライブラリが提供されているRubyで書くことに.Rubyなんて普段殆ど書かないので,当然文法とかガンガン調べながらすすめる.プログラム組んでるより,文法とかメソッド仕様とか調べてる時間のほうが長かったかもしれない() あと内部仕様とか.
問題自体は変換を総当りして,それが素数かどうか考えるだけなので,アルゴリズム的には簡単だったが,実装にはかなり苦労した.

require 'prime'
 
s = gets.chomp
 
als = {}
for c in s.split("") do
    if c =~ /[[:alpha:]]/ && !als.has_key?(c)
        als[c] = 1
    end
end
 
lssize = als.size()
if lssize > 5
    p -1
    exit(0)
elsif lssize == 0
    p Prime.prime?(s.to_i) ? s.to_i : -1
    exit(0)
end
 
nums = ["1", "3", "5", "7", "9"]
for arr in nums.permutation(lssize).to_a do
    ts = Marshal.load(Marshal.dump(s))
    idx = 0
    for k in als.each_key do
        ts.gsub!(k, arr[idx])
        idx += 1
    end
    ts = ts.to_i
    if Prime.prime?(ts)
        p ts
        exit(0)
    end
end
 
puts -1

rubyについて参考にしたサイトは以下のとおり.

素数ライブラリ関係
Rubyで素数で遊ぶ(prime モジュール) - Qiita

hash関係のメソッド
each_key (Hash) - Rubyリファレンス

文字の判定(英小文字か,数字か,など)
Doesn't Ruby have isalpha? - Stack Overflow
正規表現で、文字列は全て半角英数字か?のチェック(Ruby編): プログラマーの雑記帳

文字列の置換(gsub)
instance method String#gsub (Ruby 2.0.0)
gsub, gsub! (String) - Rubyリファレンス
http://doruby.kbmj.com/toma_on_rails/20080919/1

配列を利用した組み合わせの総取得(permutation, combination)
permutation (Array) - Rubyリファレンス
combination (Array) - Rubyリファレンス

ディープコピーする方法(Marsal)を使う
Rubyメモ - ディープコピー

これくらいを全力で調べてなんとかしました^^;



残りは通せなかったのだけれども,読んだ問題の感想.
E問題.時間がなかったことに加えて,問題文の読み取りがうまく出来なかった.どこを選ぶんだこれ?? みたいな感じで.アルゴリズム的には思いついていないのだけれども,どういう範囲を中心に調べればいいのかはなんとなーくわかったような気がする.でも実装できないです.解説を引っ張ってこれたらちゃんとときます.
F問題.求め方がよくわからないから断念.桁DPみたいな感じで行けるとのことですが,私は桁DPがわからないので,あ… やっぱり知識が足りないんじゃないか(絶望) これも解けるようになりたい.
G問題.これは一瞬取り組んで,出したけどだめ.原因としては文字列の順番を考慮してないから,ということのようだ.私は単に出現頻度だけを撮ってきて,カウントしていただけだったのだが,それじゃダメってことみたい.順序を考えないと.
あと他の方のソースコードを呼んで,Python使ってるならなんでCounter使ってないんですかね,私は… ってなったので,次回以降,文字列を分割して,出現頻度が必要な問題が出れば活かしたい.

Counterなど,出現頻度を読み込むものの参考サイト
Python Tips:文字列の中の文字をカウントしたい - Life with Python

h問題は幾何で見た瞬間に残り時間じゃ解けねえなと思って投げた.



うーん,結果的に見ればG問題だけしかわからなかったため,G問題に取り組んだのは正解かなと思いました.
せめて100点扱いになっている,I問題くらいまでは解けるようになりたいなあというのが,私のささやかな希望です.



修行が足りない! はい.
最近基礎知識が足りてないことと,どう実装していいのかわからないことが多いので,問題ときつつも,あり本(ほとんど読めていない)を読まなきゃダメですなあって感じです.頑張りましょう.

ただ,3言語でコンテストに挑むのもどーよって感じがしますけど.