新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:ソフトウェア開発、参加記録:天下一プログラマーコンテスト

[学習記録] ソフトウェア開発

参考書籍

ピープルウエア 第3版

ピープルウエア 第3版

内容

第I部 人材を活用する・ 第II部 オフィス環境と生産性
  • ソフトウェア開発上の問題
    • 多くは技術的ではなく社会学的な問題である
    • 技術面より人に気を配っているマネージャーはほとんどいない(自分はそうしていると思い込んでいる者は多い)
    • 「ハイテクの幻想」
  • 「いつも手を動かしていないと仕事をした気にならない」という企業人
    • 頭を使う仕事の重要性、仕事以外の余裕の時間が大事
    • 新技術の調査、こまごまとした仕事の改良、専門書を読む、スケジュール作成…
  • 品質と時間はトレードオフではない
    • 品質を上げることが、生産性を上げることに繋がる
    • 不合理かつ非現実的なスケジュール(○日で仕上げろ)は生産性を下げるだけ
  • ソフトウェア開発のマネジメントにおける錯覚
    • 生産性を飛躍的に向上させる方法があるはず
    • 他のマネージャーは何倍も成果を上げている
    • 技術は日進月歩で、油断するとすぐ置いていかれる
    • プログラミング言語を変えれば、生産性は大幅にあがる
    • 何もかも自動化できる
    • 部下はプレッシャーをかけるほどもっと働く
  • オフィス環境と生産性は密接な関係がある
    • 一人当たりのスペース・騒音・電話・無意味な中断・プライバシー…
    • 条件の良いオフィスでは生産性が上がる(もしくは生産性が高い人が働いている)
    • 「仕事に集中するためにオフィス外に出る」という無駄
  • フロー状態
    • プログラマの理想的な作業状態=作業に没頭し、ほとんど瞑想状態になること
    • 通常、15分以上の精神集中過程が必要
    • 仕事時間ではなく、中断なく仕事をしていた時間が大事

[参加記録] 天下一プログラマーコンテスト2014予選B

結果

  • A問題、B問題完答とC問題部分点(25点)の計105点
  • A問題:文字列の置換
    • StringのfirstReplace()メソッドを使用(置換する文字列は1回しか登場しないので)
  • B問題:N個の文字列を繋げてある定められた文字列にするパターン数を求める
    • 解答の文字列をans、N個の文字列をstr[N]とする
      • str[i]についてansの接頭辞と等しいか調べる(String.startWithメソッド
      • 等しければansからstr[i]を取り除いたnewAnsを作り(replaseFirst)、再帰呼び出し
      • 呼び出し先では、str[i]についてnewAnsの接頭辞と等しいか調べる
      • 最終的にansが空文字になったらパターン数に1を足す
    • 上記ではTLEになったので、さっそく動的計画法(メモ化再帰)を使用
    • 例えばansが"aaaaaa"で、strが"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa"の場合
      • メモ化再帰を使わないと、newAnsが"a"になったとき、毎回"a","aa","aaa"...について調べ、結局パターン数に1を足すだけ
      • 同様に、newAnsが"aa"になったときは、"a"+"a"と"aa"の2通りだが、これも毎回"a", "aa", "aaa"...と調べてしまう
      • そこで、ある再帰が終了した時点で、MapにそのときのnewAnsとパターン数を格納
      • 例えば("aa", 2)のような数が格納される
      • パターン数を数えるため、再帰メソッドにはパターン数を格納する引数を追加
    • 何故かWAになったが、パターン数が余りに大きくなったときに数がオーバーフローした模様
      • 問題はパターン数を1000000007で割った余りを求めろ、というもの
      • もともとは最後の出力時にのみパターン数を1000000007で割っていた
      • 再帰内の計算でも1000000007で割るようにしたところ、AC
  • C問題:ある条件に従って変化する盤面について、与えられた盤面になるような変化前の盤面を求める
    • マスは黒か白のどちらかをとり、周囲の黒マスの数が奇数か偶数かによって次の状態が決まる
    • 最初は与えられた盤面から逆算しようとしたがどうにもプログラムが書けず
      • 左上のマスが黒=その右かその下は黒マスだった、左真ん中上のマスが白=周囲のマスは全て白だったか、一つだけ黒…
      • ↑こんな感じの情報の溜め方と最後のまとめ方がわからず断念
    • 結局全探索
      • 再帰であらゆるパターン(2^マス数)の盤面を生成
      • 全てのパターンについて条件に従い盤面を変化させ、与えられた盤面と等しいかチェック
      • 等しければその盤面を出力
      • 3x3のパターンまではACだったが、あとは当然TLE

感想

  • 98位と100位以内に入れたので嬉しい
    • 早速メモ化再帰を使って解けたのはとても嬉しい
    • とはいえC問題以降のようにちょっと複雑になると歯が立たない(話が2次元になると辛い…)
    • 少しずつ数学・アルゴリズムなど学習していこう