kNakajima's Blog

技術系のアウトプットブログです。

AGC037 A - Dividing a String

競技プログラミング

AGC037 A問題の解説と解答例です。問題文

問題の概要

  • "aabbaa" といった文字列をN個に分割する。
  • ただし、分割の仕方には条件があり、S = ["a", "a" "bb", "aa"]のように分割したとすると、S[i] == S[i+1]となる部分を作ってはいけない。(この場合、S[0] == S[1] となってるため条件を満たしていない。)
  • このルールで分割するとき、最大のNを求める。

解き方

解答例に載っているように、Nが最大になるような分割では、分割した文字列の長さはそれぞれ1か2のどちらかになる。

  • "aabbaa" → ["a", "ab", "b", "aa"] (N = 4)
  • "aaaccacabaababc" → ["a", "aa", "c", "ca", "c", "a", "b", "a", "ab", "a", "b", "c"] (N = 12)

どの連続する2文字を連結して、分割するかをO(N)で求める必要があるため、動的計画法を用いて解く。
入力された文字列Sのi文字目までの最大分割数を記録していく。分割された文字列は1文字か2文字であるため、想定されるパターンは次の4通り。

  • 直前の分割された文字列が1文字で、文字列Sのi文字目を1文字で分割する
  • 直前の分割された文字列が1文字で、文字列Sのi文字目とi+1文字目の2文字で分割する
  • 直前の分割された文字列が2文字で、文字列Sのi文字目を1文字で分割する
  • 直前の分割された文字列が2文字で、文字列Sのi文字目とi+1文字目の2文字で分割する

よってi文字目における最大分割数を上記の4パターンで記録しておく必要があるため、下記のようなリストを用意しておく。

dp = [[0 for _ in range(4)] for _ in range(len(S))]

このリストと上記の4パターンを対応させると次のようになる。

  • dp[i][0] : 直前の分割された文字列が1文字で、文字列Sのi文字目を1文字で分割する
  • dp[i][1] :直前の分割された文字列が1文字で、文字列Sのi文字目とi+1文字目の2文字で分割する
  • dp[i+1][2] : 直前の分割された文字列が2文字で、文字列Sのi文字目を1文字で分割する
  • dp[i+1][3] :直前の分割された文字列が2文字で、文字列Sのi文字目とi+1文字目の2文字で分割する

ここで、文字列Sの1文字目を1文字で分割する場合、文字列Sの1文字目と2文字目で2文字に分割する場合はそれぞれi文字目までの分割数が1なので、次のように初期化する。 (1文字目に対応するリストのインデックスは0)

dp[0][0] = 1
dp[1][1] = 1

最後にfor文で1文字目から文字列Sの最後の文字まで、上記の4パターンをリストに記録していく。

for i in range(1, len(S)):

  # 直前は1文字で分割 次は1文字で分割
  if S[i-1] != S[i]:
    dp[i][0] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は1文字で分割 次は2文字で分割
  if i < len(S) - 1:
    dp[i+1][1] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は2文字で分割 次は1文字で分割
  dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + 1

  # 直前は2文字で分割 次は2文字で分割
  if  2 <= i < len(S)-1 and (S[i-2] != S[i] or S[i-1] != S[i+1]):
    dp[i+1][3] =  max(dp[i-1][1], dp[i-1][3]) + 1

解答コード全文

S = input()

dp = [[0 for _ in range(4)] for _ in range(len(S))]

dp[0][0] = 1
dp[1][1] = 1
for i in range(1, len(S)):

  # 直前は1文字で分割 次は1文字で分割
  if S[i-1] != S[i]:
    dp[i][0] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は1文字で分割 次は2文字で分割
  if i < len(S) - 1:
    dp[i+1][1] = max(dp[i-1][0], dp[i-1][2]) + 1

  # 直前は2文字で分割 次は1文字で分割
  dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + 1

  # 直前は2文字で分割 次は2文字で分割
  if  2 <= i < len(S)-1 and (S[i-2] != S[i] or S[i-1] != S[i+1]):
    dp[i+1][3] =  max(dp[i-1][1], dp[i-1][3]) + 1


print(max(dp[-1]))

Binaly Search (二分探索)の理論と実装

コーディング面接対策

コーディング面接の対策の第2回目は、Binaly Search (二分探索)です。

Binaly Search (二分探索)について

Binaly Search (二分探索)とは、ソート済みの配列に対して、任意の値のデータを探索するアルゴリズムです。
1回の処理ごとに配列内の探索する範囲を半分にしていくため、計算量はO(log n)となります。(logの底は2)

Pythonでの実装例

def binary_search(array, query):
    
    def search_query(left, right):
        if right >= left:
            mid = (left + right) // 2
            
            if array[mid] == query:
                return mid

            elif array[mid] > query:
                right = mid - 1
                return search_query(left, right)

            elif array[mid] < query:
                left = mid + 1
                return search_query(left, right)
            
        return "存在しない値です"
    
    return search_query(0, len(array)-1)

良い読書をするために

無駄な読書をしないために個人的に大切だと思うことのメモ。

1. 読みたい本だけを読む

「読みたい本・読む必要がある本だけを読む」

個人的によくあるのは、現時点で興味もないし読む必要もないが、「将来のために読んでおいたほうが良さそう」というモチベーションで本を購入するパターン。このパターンで買った本を読みきれたことがほとんどなく、読んだとしても内容が定着しない。

 

2. 積読をしない

「今読んでいる本の次に読む本を決めない・考えない」

読書をする目的は、本の内容を理解して頭に残すこと。積読を作ると次に読む本のことが気になり、下手に焦ってしまい、今読んでいる本の内容が頭に残らなことがある。とにかく本を読んでいるときは、他の本のことは考えない。

健康を支える食事

健康

日常的に摂取していて、これからも習慣として摂取し続けようと思っている食べ物・サプリをまとめた記事です。今後も順次追加予定。

健康を支える食品たち

My Protein (プロテイン)

毎日飲んでいるプロテイン。朝と寝る前の2回飲んでいます。国産のプロテインと比べて値段に対してタンパク質の量が多かったり、セールだとかなり安く購入出来たりと良いことしかないです。味はナチュラルチョコレートとナチュラルストロベリーがオススメです。

 

My Protein (サプリ)

My Proteinではサプリも購入できます。プロテインを買うついでにいつも買っています。現在飲んでいるサプリはOMEGA369, マルチビタミン, 亜鉛です。不足しがちな栄養素を一瞬で補えるのは素晴らしいですね。

 

Base Food

美味しくて手軽な完全栄養食です。まだ始めたばかりではありますが、味もよく栄養価も豊富で満足度が高いです。ただ、学生の自分にはやや値段が高めなので、社会人になったら再開しようと思っています。

 

毎日1杯の青汁

 作業中の飲み物として水では物足りない時に飲みます。抹茶風味で美味しい。カフェインも糖類も入っていないので、健康にも良い。

伊藤園 毎日1杯の青汁 粉末タイプ (糖類不使用) 5.6g×20包

伊藤園 毎日1杯の青汁 粉末タイプ (糖類不使用) 5.6g×20包

  • 発売日: 2016/03/21
  • メディア: 食品&飲料
 

 

野菜ジュース

 カゴメの野菜ジュース。毎朝プロテインと一緒に飲んでいます。amazonで1ヶ月ごとに定期購入しています。普通に生活しているとつい野菜不足になってしまいますが、これ一本で最低限の野菜を補えそうです。

カゴメ 野菜一日これ一本超濃縮 高リコピン 125ml×24本

カゴメ 野菜一日これ一本超濃縮 高リコピン 125ml×24本

  • 発売日: 2014/03/04
  • メディア: 食品&飲料
 

2019年振り返り

その他

2019年も残すところあと1週間ということで、今年一年行ったことをザックリと振り返ってみます。

2019年に行ったこと

学会発表 (1月 - 2月)

1月と2月に学会発表を行いました。1月はポスター発表で初めての学会参加&初めてのポスター発表で、2月は口頭発表でした。2回の発表それぞれで同じテーマに対して異なる手法を提案しました。内容はさておき、初めて学会発表で2回ともかなり緊張したのを覚えています。しかし、これを機に人前で話すことへの抵抗が減ったり、スライド作成技術を磨けたりと自分の成長を実感できました。

大学卒業 (3月)

学会発表に向けて研究を進めていたため、卒論発表のポスターは学会のものを使い回しました。進学ということで周りの人間関係や環境もほとんど変わらないため、イマイチ「卒業」という実感は湧きませんでしたが、無事に学位を取得できました。

論文投稿 (5月 - 8月, 11 - 12月)

2月の学会で発表した内容を論文にして投稿しました。初めての論文執筆であり、大学院の授業期間に論文を執筆していたため、かなり苦労しました。締め切りの1週間ほど前に担当の先生からOKをもらいなんとか投稿。11月頃に査読結果が返ってきて、一部修正などの対応を行い、無事に受理されました。

インターンシップ参加 (8月 - 9月)

結構たくさんの会社さんにエントリーして、結構落ちました。最終的にインターンシップに参加させていただいた会社さんは、いい生活, サイバーエージェント, MTIの3社です。

就職活動 (10月 - 11月)

10月から本格的に活動を開始。10月は週2〜4日くらい面接で予定が埋まっていました。最終的に第一志望群であったWeb系企業から11月に内定を頂き、そちらに入社する予定です。

 

その他アウトプット

Qiitaへの投稿

今年は2本の記事を投稿しました。総いいね数は163(2019年12月25日時点)でした。年末のFlaskアドベントカレンダーに投稿しようかと考えたのですが、ネタが思い浮かばずに結局投稿しませんでした。来年は挑戦したいことの一つです。

AtCoder

3月に大量に問題を解いてレートも1100まで上がったが、その後は下落する一方でした。さらに4月からはコンテストに参加する頻度もやや少なくなり、熱が冷めてきた感じになりました。解いた問題数は623問(2019年12月25日時点)でした。

 

まとめ・来年

まとめ

大学生活の中では、最も頑張った一年だったと思います。学会発表やインターンシップは、参加前は不安が大きかったのですが、終わってみれば参加してよかったという気持ちが大きいです。来年もいろいろなことに挑戦していきたいです。