Into the Horizon

programming, photography, and daily log

Codeforces #95 Div2 Only (11/25)

A. cAPS lOCK
問題:全ての文字が大文字、もしくは先頭以外の全ての文字が大文字であれば、文字の大小を反転して出力せよ

  • 大文字小文字の判定が即できない残念な感じ。タイムロス

B. Opposites Attract
問題:n個の数t1, t2, ... tnが与えられる。これらの要素のうち、符号が反転している関係の数の組み合わせは何個あるか

  • A=-BであるようなAとBがそれぞれa,b個あれば、そこからできる組み合わせはa*b個。 0だけ例外なので気をつける
  • WA…。あ、long longにしてない。通った
  • SystemTestでWA……。あ、sumの関数わざわざ書いたけどここだけintだorz

C. The World is a Theatre
問題:n人の男とm人の女からt人を選ぶ組み合わせの数は?(ただしn>=4,m>=1)

  • 女性をi人選ぶときの組み合わせの数はnCt-i * mCiである。t-i>=4, n>t-iなどに気をつけて計算
  • 上手くいかない…んー。 
  • 前に書いておいたcombinationの関数が怪しい?使い慣れてるpythonで実装。テストしたら値が違う。なんだと…… 
  • pythonのコードで通った

D. Subway
問題:地下鉄の線路は円形の線路とそれにつながる線路で必ず構成される。円から外れた線路上の駅について、最も近い円上の駅までの距離を求めよ

  • 接続してるのが1駅だけの駅を切っていけば、円が見えてくる。円を構成する駅さえわかれば後は距離を求めるだけ。
    • 前回の靴ひもの問題と同じじゃ…。そしてまだ復習してなかったあの問題。なぜWAだったのかわかってない
    • 配列操作周りにミスがあった気がしてたので、信頼のpythonで書いて通った。

E. Yet Another Task with Queens
問題:NxN上のマスにM個クイーンが置かれている。他のi個(0~8)のクイーンから取られる位置にある(移動線上にある)クイーンの数を求めよ

  • 縦横ナナメについてのリストを持てばよさそう。
    • ってのはすぐわかったけど、ナナメの実装が苦手で時間食う
  • 信頼のpython。実装終わった辺りでコンテストも終わり。上位陣はFまでで一時間切ってるのか…凄いなあ
  • SystemTestでWA………。なんだと…
    • ソートされたリストが前提だったけど、ソートしてなかった orz
    • 後から書き直したけれど、TLE。高速化を色々試みたけれど駄目。C++で書いたらいけた。pythonでもいけるようなスマートなやり方が他にあるのかな?


結果:
oxoox- +0, 2952pt, 357位
レーティング 1583 -> 1580 (-3)

反省タイム:

  • 大文字小文字 isupper()を使うか、普通に'A'<= char, and char<='Z'するかでおk
  • Combinationの中身 long longでもオーバーしてた。桁を全く気にしなかったpythonの癖が直らない…
    • 組み合わせの数について復習。 nCr = n-1Cr-1 + n-1Crなんて式もありましたね
  • 全体的に桁についてもっと気にする必要性


2問もWA。凹む。
来週くらいまで競技プログラミングの勉強に費やす時間ができそうなので、集中して勉強したい